Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

Множина твірних називається незалежною, якщо вона мінімальна. Отже, щоб визначити довільну алгебру, достатньо описати її основні операції й вибрати одну з незалежних множин твірних. Наприклад,

для означення алгебри N + достатньо взяти за твірну число 1 і визна- чити операцію додавання. Усі її елементи містяться серед значень те-

рмів: (1+1), ((1+1)+1), (((1+1)+1)+1) тощо21.

Похідні операції алгебричної системи. Нехай A = (A;ΩF ;ΩP ) – до-

вільна алгебрична система. Окрім основних операцій і предикатів сис- теми, у ній розглядають похідні операції та предикати. Зазвичай до них відносять суперпозиції основних операцій і предикатів. Ми ж будемо трактувати їх розширено і вважати похідними всі регулярні n -арні операції та предикати, породжені основними операціями системи.

Похідні операції цікаві тим, що в узагальненому вигляді дозволя- ють подати різноманітні варіанти скінченних комбінацій застосувань основних операцій і предикатів. Класичними є операції, отримані за допомогою регулярних композицій перестановки, ототожнення й па- раметризації аргументів, введення фіктивних аргументів, суперпози- ції й розгалуження. Похідні операції та предикати подаються регуля- рними функціональними термами. Наприклад, терм

p1 → S(f 3,g12,g22,g32 )|{q2 → f11} подає похідну операцію, що є розга- луженням за певною унарною умовою відповідних суперпозиції та ітерації функцій. Регулярний терм S(f 3,g12,g22,g32 ) зазвичай запису-

ють у вигляді префіксного Ω -терму f 3 (g12,g22,g32 ).

Структурна індукція. Важливою властивістю замкнень алгебрич- ної системи є те, що вони припускають доведення методом структур-

ної індукції. Нехай P (x ) – певний предикат на замкненні B* .

Правило структурної індукції для замкнення B* : (Б) База індукції: x B : P (x ).

(І) Індуктивний перехід: для всіх основних операцій Fini

x1,...,xn B* : kn=1P (xk ) P (Fini (x1,...,xn )). (П) Повнота: x B* : P (x ).

21 Насправді достатньо часткового випадку додавання – збільшення числа на 1.

71

ПРОГРАМУВАННЯ

Лема 1.2 (про структурну індукцію). З бази індукції та індуктивно- го переходу правила структурної індукції випливає повнота.

Доведення. Дійсно, нехай R = {x B* : P (x )}, тоді з бази індукції

випливає B R , а за індуктивним переходом – B* R . Однак R B* , отже, R = B* ■

Таким чином, щоб установити повноту, достатньо перевірити базу індукції та правило індуктивного переходу. Звичайна математична індукція для натуральних чисел є частинним випадком структурної. Розглянемо приклад доведення за правилом структурної індукції. Ви-

значимо сукупність слів Σ* в алфавіті Σ = {a1,...,an } як замкнення по-

рожнього слова ε відносно операції pre : Σ× Σ* → Σ* – приписування

def

ліворуч літери до слова: pre(a,u) = au .

Структурна індукція для слів має вигляд: (Б) P (ε);

(І) w Σ*, a Σ : P (w)→ P (aw); (П) x Σ* : P (x ).

Приклад 1.11. Доведемо методом структурної індукції асоціатив- ність операції конкатенації. Покладемо

P (u) w,v Σ* : (u v ) w = u (v w).

Перевіримо спочатку базу індукції. Нехай w,v – довільні слова над

Таким чином, має місце індуктивний перехід, а отже, і повнота ■

72

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

1.4.2. МОДЕЛІ СИСТЕМ

Коли кажуть, що певна система є моделлю іншої (первісної) систе- ми, то мають на увазі. що її елементи копіюють (можливо, з деяким наближенням) первісні об'єкти, а основні операції та предикати імі- тують поведінку основних операцій і предикатів первісної системи. Уточнимо це поняття.

Ізоморфізми й гомоморфізми систем. Відображенням φ: A → B

системи A в (на) систему B називається відображення φ: A → B но- сія системи A в (на) носій системи B .

Ізоморфізмом системи A = (A;F1n1 ,F2n2 ,…;P1m1 ,P2m2 ,…) в ( на) одно-

типну систему B = (B;G1n1 ,G2n2 ,…;Q1m1 ,Qm2 2 ,K) називається взаємоодноз-

начне відображення φ : A → B , яке зберігає головні операції та предикати системи A , тобто для всіх a1,a2,... A та всіх i, j N :

Ізоморфізм системи на себе називається автоморфізмом.

Гомоморфізмом системи A в ( на) однотипну систему B називається відображення системи A в ( на) однотипну систему B , яке зберігає головні операції, і для всіх a1,a2,... A та кожного j N виконується

нтів у A , що Pjm j (a1,....,am j ).

73

ПРОГРАМУВАННЯ

ємооднозначним відображенням A на себе, то для деякого k степінь φk буде тотожним і Pjm j (a1,....,am j )=1.

Поняття моделі систем. Поняття ізоморфізму й гомоморфізму належать до фундаментальних понять алгебри та інформатики. На них базується поняття моделі систем.

Система B є наближеною моделлю системи A відносно функцій кодування й декодування φ і φ−1 , якщо φ є гомоморфізмом системи A в

систему B .

Взаємозв'язок між первісною системою A та її моделлю B ілюст- рує рис. 1.5, де a,b,c ,d – відповідні вектори-аргументи операцій.

Як бачимо, щоб знайти значення певної операції системи, достатньо закодувати її аргументи (перейти до моделі), застосувати до них відпові- дну модельну операцію й розкодувати результат. У випадку, коли гомо- морфізм φ сильний, говорять про сильну модель. Коли φ взаємоодноз-

начний, то про моделі говорять як про точні. Коли ж φ є бієкцією, а си- стема A , у свою чергу, – моделлю системи B відносно функції декоду- вання φ−1 , то говорять про еквівалентні, або ізоморфні, моделі.

Розглянемо кілька прикладів моделей систем. Кодування векторів елементів при моделюванні зводиться до кодування їхніх компонен- тів, тобто кодом вектора елементів є вектор кодів компонентів.

74

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

Приклад 1.12. Нехай Boolean = ({false,true};OR,AND,NOT,=,<) – бу-

левий тип мови програмування Pascal із відповідними логічними опера- ціями й відношенням false < true , B = {0,1}; , ,¬,=,< – двоелементна

булева алгебра з логічними операціями диз'юнкції, кон'юнкції, запере- чення, відношенням "менше", з найменшим (0) і найбільшим (1) елемен-

функцій кодування й декодування, що переводять десяткові числа в рівні їм двійкові, і навпаки ■

з операцією додавання. Вони еквівалентні відносно функцій коду-

цілочислового простору з операціями покоординатного додавання й віднімання точок, I4 = Q0;×,/,= – підсистема Q0 Q+ додатних раці- ональних чисел зі звичайними операціями множення й ділення, де Q0 = {2a ×3b ×5c : a,b,c Z}. Нескладно перевірити, що системи ізомо-

рфні відносно функцій кодування φ4 ( a,b,c )= 2a ×3b ×5c і декоду-

вання φ4−1. При цьому додавання моделюється операцією множення, а віднімання – операцією ділення.

Розглянемо дію 4,−1,2 + 2,2,2 у системі S4 та її аналог у моделіI4 : 4,−1,2 + 2,2,2 = 6,1,4 ;

(φ4 ( 4,−1,2 )× φ4 ( 2,2,2 ))= (243−152 ×223252 )= 263154 .

Рівність φ4 6,1,4 = 263154 показує, що відповідні обчислення в сис- темах узгоджені вірно. Зауважимо, що модель I4 на практиці може бути неефективною, оскільки потребує надвеликих цілих чисел ■

75

ПРОГРАМУВАННЯ

Приклад 1.16. Розглянемо алгебру S5 = 2A ; ,∩,¬, ;=, усіх під-

множин певної скінченної множини A = {a1,a2,...,an },n > 0 , зі зви-

чайними множинними операціями – об'єднанням, перетином, допов- ненням, порожньою множиною, предикатами рівності та включення

– і систему двійкових векторів довжиною n I5 = {0,1}n ; , ,¬,θ,=,< із

покоординатними операціями диз'юнкції, кон'юнкції й заперечення, нульовим вектором і бінарним предикатом, який повертає значення

за правилом e1 < e2 = ((e1 e2 )= e1 ). Зафіксуємо певний лінійний по-

φ5 (M )= (b1,b2,...,bn ) , де 1 ≤ i ≤ n(bi = (ai M →1|0) . Системи S5 та I5 еквівалентні. Модель I5 використовується в компіляторах мов про-

грамування для реалізації множинних типів ■ Моделі й конгруенції. У зв'язку з поняттям моделі цілком природ-

но постають питання: якою є сукупність усіх можливих моделей даної системи, чи є серед них моделі з тими чи іншими властивостями то- що? Спробуємо дати певну відповідь на ці й подібні запитання.

Кожна функція кодування φ : A → B породжує на елементах перві-

елемент a , будемо позначати [a]. Якщо кожному коду b B постави-

ти у відповідність повний його прообраз bφ−1 , то отримаємо каноніч- ні взаємооднозначні відображення типів A /σφ → B та B → A/σφ , ві-

ких, що 1 ≤ i ≤ n (ai σbi ), виконується F(a1,....,an )σ F(b1,....,bn ) . Стабі- льними є, зокрема, відношення рівності й тотальне відношення на A .

Еквівалентність σ у системі A називається конгруенцією, якщо вона

стабільна відносно кожної головної операції системи.

76

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

Нескладно впевнитись, що ядерна еквівалентність гомоморфізму

Означення F%i коректне. Дійсно, якщо розглянути інші представники класів a1′ [a1],....,an′i [ani ] , то результат операції b′ = Fini (a1′,....,an′i ) на них буде в тому самому фактор-класі, що й b = Fini (a1,....,ani ):

Fini (a1,....,ani )φ= Gni i (a1φ,....,ani φ) = Gni i (a1′φ,....,an′i φ)= Fini (a1′,....,an′i )φ.

Отримали bφ = b′ φ. Отже, має місце

Лема 1.3 (про ядерну еквівалентність гомоморфізму). Ядерна екві-

таке, що [a] φ = aφ , є гомоморфізмом фактор-системи A/ σφ на систе- му B , тобто B – наближена модель системи A/ σφ . Цей гомоморфізм є ізоморфізмом, а B – точною моделлю системи A/ σφ , якщо гомомор- фізм φ : A → B – сильний ■

Отже, кожній сильній моделі B системи A відповідає певна ізомо- рфна їй фактор-система системи A . Ураховуючи, що кожна фактор-

77

ПРОГРАМУВАННЯ

система A /σ за конгруенцією σ є сильною моделлю системи A , мо-

жемо зробити важливий висновок:

Лема 1.4. Сукупність усіх сильних моделей системи A з точністю до ізоморфізму вичерпується сукупністю всіх її фактор-систем за різ- ними конгруенціями.

Доведення. Випливає з наведеної вище леми 1.3 ■ Таким чином, задачі: 1) знайти з точністю до ізоморфізму всі силь-

ні моделі системи A ; 2) знайти всі конгруенції на A – рівносильні. Приклад 1.17. На кожній системі A є принаймні дві конгруенції –

є наближеною моделлю N + . Дійсно,

(n +m)φ = (−1)n +m = (−1)n ×(−1)m = nφ + mφ.

Сукупність N + /σφ двоелементна і складається з підмножин парних і

непарних чисел. Окрім ядерної конгруенції σφ на N + , існують інші конгруенції ■

1.4.3. БАГАТОСОРТНІ Ω -СИСТЕМИ

Ми ознайомилися з деякими абстрактними властивостями алгеб- ричних систем. Тепер розглянемо такі системи з практичнішого по- гляду. По-перше, нагадаємо, що реальні предметні області не є просто множинами елементів із певними співвідношеннями між ними. На- впаки, їхні елементи зазвичай згруповані в певні сорти подібних еле- ментів, і співвідношення між ними мають сенс тільки в межах таких сортів чи їхніх сукупностей. По-друге: якщо ми маємо алгебричну си- стему з певною сукупністю твірних, то як синтаксично подати дові- льний елемент такої системи?

Поняття багатосортної Ω -системи. Нехай U – довільна множина,

яку будемо називати універсумом, і A1,...,An +1 U . n -арна операція F n , область означення якої є підмножиною A1 ×...× An , а область зна-

78

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

чення – підмножиною An +1 , називається типізованою, вираз A1 ×...× An → An +1 – її типом, а підмножини A1,...,An +1 – сортами аргу- ментів і значень. Аналогічно визначається типізований предикат.

сумі U . Як уже зазначалося в підрозд. 1.1, для цього необхідно вибрати в U конкретні сорти для символів-сортів, константам сигнатури поста- вити у відповідність їхні фіксовані значення потрібного сорту, символам- змінним – відповідний тип, функціональним і предикатним символам – конкретні типізовані операції та предикати згідно з їхніми типами. Ви- беремо певну інтерпретацію сигнатури Ω і позначимо її I . Нехай I ς –

сукупності відповідно її констант, змінних, основних операцій і пре- дикатів.

Багатосортні Ω -системи задають семантику ПЧП із сигнатурою Ω . При розгляді конкретних Ω -систем інтерпретації сигнатури фіксу- ють, тому верхній індекс I в елементах таких систем зазвичай опус-

кають. Розглянемо кілька важливих прикладів Ω -систем.

Словарна Ω -система. Вище вже зазначалась роль слів у імену- ванні математичних об'єктів. Однак їхнє значення в інформатиці цим не вичерпується. Слова становлять основу вербальних ДС, до яких належать і всі традиційні мови програмування. Вони також відігра- ють особливу роль при конструюванні об'єктів. Як ми побачимо далі, внутрішня будова будь-якого з алгебричних об'єктів може бути пода- на у вигляді слова-терму. На словах діють усі операції та предикати, які визначені в підрозд. 1.2.3 на кортежах – конкатенація, припису- вання літери на початок і кінець слова, відношення префіксності, су- фіксності, закінчення тощо. Однак для них можуть бути визначені й власні операції та відношення. Насамперед, лінійна впорядкованість

79

ПРОГРАМУВАННЯ

літер усередині алфавіту X породжує лінійний лексикографічний по-

ΩC = {ε}, де ε – порожнє слово, операцій ΩF = {o,head,tail,app,pre} з операціями конкатенації, взяття голови й хвоста слова, приписуван- ня символу праворуч і ліворуч до слова та предикатів ΩP = {=,p} із

предикатами рівності й лексикографічного порядку. Для спрощення словарних Ω -термів опускають символи операцій конкатенації та приписування літер праворуч і ліворуч. Наприклад, замість термів u ov , pre(a,x) та app(a,x) уживають відповідно uv , ax та xa .

У підрозд. 2.6.2 наведено індуктивні означення всіх операцій сло- варної системи W .

Регулярні мови. Нехай n N . Зафіксуємо певний алфавіт Σ = {a1,...,an }. Довільні підмножини L Σ* слів у алфавіті Σ називають- ся мовами. Сигнатура регулярної Ω -системи мов має такий склад:

80