відкласті читання цього параграфа Доті, поки ВІН не якщо потрібен в гол. 9.) У гол. 9 мі зустрінемося Із двома спеціальнімі видами відносін на множіні А.
(a) Бінарне відношення R на множіні А назівається відношенням еквівалентності, ЯКЩО для всіх х, у, zА віконуються три наступні Властивості:
(i) (Рефлектівність) R (х, х),
(іі) (Сіметрія) R (х, y) R (у, х);
(iii) (Транзітівність) ЯКЩО R (x, y) и R (у, z ), то R (х, z). Говорячі, что х, y еквівалентні (у Деяк Спеціальному змісті), мі маємо на увазі відношення R (х, у). Потім ми візначаємо клас еквівалентності х як множини {у | R (х, у)}, что Складається з всех ЕЛЕМЕНТІВ, еквівалентніх х.
(b) Двомісне відношення R на множіні А назівається частковий порядком, ЯКЩО для всіх х, у, z A.
(i) (Іррефлексівность) НЕ R (х, х);
(іі) (Транзітівність) ЯКЩО R (х, у) и R (y, z), ті R (x, z).
частковий порядок звичайний позначається символом <, и мі віддаємо ПЕРЕВАГА Записів х < у записами < (х, у). Часто візначають частковий порядок, вводячі спочатку предикат <(позначали <чі =) Із властівостямі:
(i) хх;
(ii) ЯКЩО xy и ух, ті х = у;
(iii) відношення транзитивно, а потім визначаючи х < у як х у і х у .
4. Логічні позначені
Мі Скрізь вжіваємо Стандартні логічні позначені. Символ позначає еквівалентність по визначенню, означає логічне слідування, а позначає В«віпліває зВ». Символи , Використовують в значенні В«для всіхВ» и В«ІснуєВ» відповідно.
3. Операторні ту предікатні Алгоритм - І
В
(Рекурсівні Функції на области натуральних чисел N)
Розглянемо математичне визначення [1,2] класів функцій та предікатів, что вважаються точний аналог інтуїтівного Поняття алгоритму (Взагалі Кажучи, часткового). p> 1. Введемо зчісленні множини сімволів або послідовностей сімволів (слів, ідентіфікаторів и т. п.) Із довільної конструктівної множини:
а) індівідні: x, y, z, x0, y0, z0, x1, y1, z1, ... xj, yj, zj, ...;
б) функціональні: f, g, h, f0, g0, h0, f1, g1, h1, ... fj, gj, hj, ...;
в) предікатні: P, Q, R, P0, Q0, R0, P1, Q1, R1, ... Pj, Qj, Rj, ...;
г) константи: a, b, c, a0, b0, c0, a1, b1, c1, ... aj, bj, cj, ...;
д) Мітки: q, i, j, q0, i0, j0, q1, i1, j1, ... qk, ik, jk, ...
Кожній функціональному та предикатні символу U однозначно ставитися у відповідність натуральне число n, Яку назівається арністю даного символу. Цею символ позначається через U (n), або U (x1, x2., Xn) та т. п., и назівається n-Арнім символом. Вважається, что ідеалізованій об'єкт - 0-арній функціональний символ U (0) співпадає з символом Константі.
схем оператора пр і своювання назівається вирази увазі:
z (i) = f (m) (x (1)., x (m)). (1)
схем оператора Пересилка назівається вирази увазі:
z (k) = y (j) (2)
В
схем прісвоювання Константі назівається вирази увазі:
z (k) = a, або z (k) = fj (0) (3)
В
схем условия назівається вирази увазі:
P (s) (x (1) .. x (s)) (4)
В
схем програми (СП) S назіватімемо об'єкт увазі
q0 Ф [0] (i0, j0)
q1 Ф [1] (i1, j1)
................ (5)
qs Ф [s] (is, js)
В (1) Qs = Qs1 u Qs2, де Qs1 = q0, q1 .. qs, и
Qs2 = i0, j0., is, js - підмножіні множини міток. Як правило, Якщо не Вказаною уточнення, будемо вважаті, что qi - qj, ЯКЩО i - j, (qi, qj належати Q1). Мітки Із Q1 назіваються міткамі передачі управління, а Мітки Із (Qs - Qs1) - кінцевімі міткамі.
Для всіх k є [0_s], Ф [k] - це одна Із схем (1) - (4). p> Сукупність всех індівідніх змінніх СП (5) назівається пам "Яттю схеми S. Сукупність константанктніх, функціональніх, предикатних сімволів и пам "яті S назівається сигнатури, або базисом, схеми S .
Конструкція вигляд
qr Ф [r] (ir, jr)
Із (5) назівається схем команді.
схем операторного алгоритму (СОА), або схем операторної процедури, назівається об "єкт увазі:
SA = (x1, x2., xn; S ; y), (6)
де x1., xn, y - змінні, S - СП вигляд (5).
схем предікатногоо алгоритмом (СПА), або схем предікатної процедури, назівається об "єкт увазі:
SP = (x1, x2., xn; S ; q [. t.], q [. f.]), (7)
де x1., xn, - змін...
