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

Розділ І

ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

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

1.1. Формальна мова першого порядку

¾Терми

¾Елементарні формули

¾Структуровані формули

Ключові слова: предметна константа, предметна змінна, тип операції, фун- кціональний символ, предикат, сигнатура, терм, підтерм, префіксний, постфіксний та інфіксний терми, ОПЗ, операнд, предикатний терм, умовний терм, формула, логічна зв'язка, квантор, пропозиційна змінна, пропозиційна формула, тавтологія, рівносильні пропозиційні формули.

Серед дескриптивних математичних засобів, що застосовуються в інформатиці, чільне місце посідає формальна мова першого порядку,

або мова прикладного числення предикатів (ПЧП)9. Її елементи стано-

влять основу мовних конструкцій мов програмування. Це також ос- новний на сьогодні засіб для формалізації й моделювання предметних областей у інформаційних системах. Усі неозначені тут поняття вва- жаються відомими. Однак із метою дотримання принципу замкнено- сті всі вони будуть строго визначені в наступних підрозділах.

9 У математичній логіці розглядають також мови вищих порядків, призначені для роботи з функціоналами – операціями та кванторами, визначеними на відображен- нях і предикатах.

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

1.1.1. ТЕРМИ

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

– сорти дійсних чисел, їхніх векторів і прямокутних матриць. Багато- сортність є також характерною рисою мов програмування.

Для подання об'єктів у формулах використовують спеціальні син- таксичні конструкції – терми10. Найпростішими з них є константи. Константи – це імена конкретних об'єктів, наприклад 0,1.25,π тощо.

y1y2...yn у ПЧП записують як у природній мові – без ком усередині. При

цьому записи однолітерного слова та його літери збігаються (їх розріз- няють за контекстом). Як імена констант та інших об'єктів ПЧП (типів, змінних, операцій і предикатів) використовують слова в певному фіксо- ваному алфавіті Σ. Слово, навантажене значенням (смислом), назива-

ється символом.. Отже, предметна константа – це символ, за яким за-

кріплено конкретне фіксоване значення. Предметна змінна – інший рі- зновид термів. Це теж символ, але її значення, на відміну від констант, не фіксоване, і вона може в різних контекстах позначати різні об'єкти. Останні можуть належати або одному фіксованому (сильна типізація), або різним типам (слабка типізація). Кажуть, що в даному контексті змінна набула такого-то конкретного значення. Для зручності імена змінних часто індексують: наприклад, x,y,...,x1,y1,....

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

складені терми, наприклад sin(π/2), cos30o, 1+ 3,x ×y тощо. Якщо f – операція, що має n аргументів (операндів), то результат її засто- сування до операндів t1,...,tn записують у вигляді виразів f (t1,...,tn )

10 В елементарній алгебрі терми відомі як алгебричні вирази.

22

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

або (t1,...,tn )f , які називаються відповідно префіксними й постфікс-

ними термами. Операндами можуть бути константи, змінні та інші терми. Вони називаються підтермами терму.

Операція f називається зовнішньою, або опорною, у термі. Дужки

в префіксних і постфіксних термах обов'язкові. У випадку бінарних операцій може застосовуватись також інфіксна форма термів у ви- гляді (t1 ft2 ), яку ми вже застосовували, але без дужок: 1+ 3,x ×y .

Стосовно відсутності в цих термах дужок необхідно зробити одне ва- жливе зауваження. Кінцева мета роботи математика – отримати той чи інший текст, що складається з конструкцій ПЧП (визначень, формул, тверджень, доведень) і пояснень до них, тобто така робота так чи інак- ше зводиться до роботи над текстами. Такі тексти можуть досягати зна- чних розмірів, тому дуже важливо, щоб мовні засоби для їхнього подан- ня були зручними, прозорими та якомога лаконічнішими. Подібні засоби називають метамовними відносно конструкцій ПЧП. Метамовні засоби в нашому випадку містять конструкції української мови й деякі полег- шені для сприймання варіанти мовних конструкцій ПЧП. Останні (як терми без дужок) не є синтаксично правильними, але за ними легко од- нозначно відновити первісну конструкцію ПЧП.

Наведені вище скорочені вирази cos30o та x ×y формально не є термами – вони належать метамові й замінюють "правильні" терми cos(30o) та (x ×y). При відновленні дужок у інфіксних термах може

враховуватися пріоритет операцій. За домовленістю, наприклад, спо- чатку виконуються мультиплікативні операції (×,/), а потім – адитив-

ні ( +,− ). Так, метавираз x ×y + x /y подає терм ((x ×y) + (x /y)) . Опе-

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

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

xy × x y / + . В ОПЗ, незалежно від пріоритету, операції виконуються

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

Вважається, що кожен з операндів операції f, як і змінні, має пев- ний фіксований тип. Це стосується й значення, яке повертає опера- ція. Такі операції називаються типізованими. Імена типізованих опе-

23

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

рацій будемо називати символами операцій, або функціональними символами. Наприклад, бінарна операція n x типізована, n набуває

натуральних значень, змінна х і результат – дійсні числа. Типи опера- ндів і результату складають тип операції. Якщо σ1,...,σn – типи опе-

рандів операції f , а σ – тип її результату, то тип операції f запису- ють як σ1 ×...× σn → σ . Так, функція sin має тип R → R , а вищезгада-

на операція кореня – тип N ×R → R . Щоб підкреслити тип операції, його можуть додавати в явному вигляді до символу операції. Напри- клад, пишуть f : σ1 ×...× σn → σ або f σ1×...×σn →σ . Однак у більшості ви-

падків у цьому немає потреби, оскільки зазвичай за символом опера- ції в конкретній ПЧП закріплюється той чи інший фіксований тип. Якщо це не так, то операцію називають поліморфною, а її конкрет- ний тип визначають шляхом аналізу типів її операндів у кожному конкретному термі. Типовими прикладами поліморфних операцій є арифметичні операції на числах: у термі 2 +3 йдеться про додавання цілих чисел, а в термі 2.0 + 3 – дійсних.

У мовах програмування випадки поліморфних операцій відомі під назвою перевантаження операцій. Кожний терм теж має свій тип – це тип його можливих значень. Він збігається з типом результатів йо- го опорного функціонального символу. Отже, якщо терм t має вигляд f σ1×...×σn →σ (t1,...,tn ) , то його типом є σ.

1.1.2. ЕЛЕМЕНТАРНІ ФОРМУЛИ

Формули подають математичні висловлювання і щось стверджують про об'єкти предметної області. Кажуть, що вони можуть бути істин- ними (виконуватись), хибними (не виконуватись) або беззмістовними (не мати сенсу). Наприклад, арифметичне твердження 2 + 3 = 5 істин-

не, 1 + 3 = 5 – хибне, а твердження (1/0) = 0 беззмістовне (частка від

ділення на 0 не існує). Істину, хибу й беззмістовність будемо познача- ти відповідно константами 1, 0 та # 11. Ці константи утворюють спе- ціальний логічний тип Bool.

Якщо σ1,...,σm позначають типи аргументів предиката p, то тип самого предиката записують σ1 ×...× σm → Bool, або просто σ1 ×...× σm . Щоб підкреслити тип предиката, його, як і у випадку операцій, мо-

11 Зазвичай у формальних системах беззмістовність явно не зображують – для її по- дання вдаються до метазасобів.

24

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

жуть додавати до символу предиката: наприклад, p : σ1 ×...× σm →

Bool або pσ1×...×σm . Унарний предикат p називається властивістю на типі σ1 . Властивості використовуються, щоб виділити ту чи іншу під- множину А типу σ1 . Вони називаються характеристичними власти- востями, або характеристичними функціями, відповідної підмножи-

тичною властивістю підмножини A , якщо χ (a ) = 1,a A . Вирази

A

#,a A

на зразок наведеного називаються умовними. Вони мають умову α і дві альтернативи – a та b – і повертають як результат одну з альтер- натив залежно від того, виконується умова чи беззмістовність (якщо умова беззмістовна).

Предикати, характеристичні й частково характеристичні функції становлять основу предикативних засобів опису множин та інших

def

елементів ПЧП. Введемо позначення " = " як скорочення фрази "по-

кладемо за означенням". Оскільки n-арні предикати – теж операції, то для подання їхніх значень теж використовуються префіксні та інфік- сні терми вигляду p(t1,...,tn ) , (t1pt2 ), де t1,...,tn – операнди відповід-

них типів. Такі терми називаються предикатними, або елементар-

ними формулами, наприклад 3 < 5 , sin(x) = sin(x + 2πn) тощо.

Увага! Останній приклад демонструє ще один варіант скорочення записів термів і формул. Як бачимо, у них можуть пропускатись на- віть символи окремих операцій. Однак треба розуміти, що йдеться про скорочений запис терму, а не сам терм. Вираз 2πn не є форма- льно термом, а лише скорочено подає терм ((2× π)×n) ►

Для умовних виразів введемо лінійну форму подання. Нехай p – предикатний терм, t1,t2 – терми. Тоді вираз

називається умовним термом.

Усі формули ПЧП поділяються на елементарні та структуровані. Структуровані формули будуються з елементарних за певними стандар-

25

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

тними правилами, однаковими для всіх теорій. Тому, щоб повністю ви- значити ПЧП конкретної теорії, необхідно й достатньо задати сукупність елементарних формул. Для цього треба визначати всі предикатні симво- ли, усі можливі терми й допоміжні символи. Серед останніх обов'язко- вими є символи "(", ")", ":", "→", "|". Введемо поняття сигнатури.

Сигнатура – це п'ятірка Ω = (Ωs ,Ωc ,Ωv ,Ωf ,Ωp ), де Ωs = {s1,s2,...},

Ωc = {c1 : σ1,c2 : σ2,...}, Ωv = {x1 : σ1,x2 : σ2,...}, Ωf = {f1 : τ1, f2 : τ2,...} та

Ωp = {p1 : ν1, p2 : ν2,...} – непорожні сукупності відповідно імен cортів, ти-

пізованих констант, змінних, функціональних і предикатних символів.

Трійка = (σ1,σ2,...;τ1,τ2,K;v1,v2,K) називається типом сигнатури

Ω , а терми й елементарні формули сигнатури Ω називають Ω -термами та Ω -формулами. Отже, кожна ПЧП має певну сигнату- ру Ω . Щоб надати значення елементарним формулам ПЧП, необхідно проінтерпретувати (оцінити) усі символи її сигнатури. Для цього ви- бираються конкретні множини для сортів елементів; константам, фу- нкціональним і предикатним символам ставляться у відповідність пе- вні фіксовані значення, конкретні операції та предикати згідно з їх- нім типом. Після інтерпретації елементарні формули, що не містять змінних, отримують конкретне істиннісне значення (стають істинни- ми, хибними або беззмістовними). Щоб елементарна формула зі змін- ними теж отримала значення, необхідно дати оцінку її змінним, тобто обрати для них відповідно до їхнього типу те чи інше конкретне зна- чення в інтерпретації. Як приклад розглянемо елементарну частину

ПЧП для натуральної арифметики = (N ,Bool,+,−,×,/,0 =,<).

Приклад 1.1. Елементарна частина ПЧП для натуральної арифме- тики . Сигнатура Ω арифметики має такий вигляд:

2)ΩC = {0 : σ} , де константи 0 : σ інтерпретуються як число 0;

3)сукупність індексованих змінних ΩV = {x : σ,x1 : σ,...,y : σ,y1 : σ,...};

12 Тут і далі 0 вважається натуральним числом.

26

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

операції додавання, віднімання, множення, ділення та взяття залиш- ку від ділення;

5) сукупність однотипних предикатних символів Ωp = {<, = : σ× σ → λ },

що інтерпретуються як арифметичні предикати "менше" та "дорівнює". Покладемо τ = σ× σ → σ , ν = σ× σ → λ . Типом сигнатури Ω є тип

= (σ;τ,τ,τ,τ;ν,ν). В арифметичних термах застосовується згаданий

вище пріоритет операцій, а в елементарних формулах символи опе- рацій старші, ніж предикатні. Наприклад, метаформула 2/3 = 0 по-

дає формулу ((2/3) = 0) і є істинною, формула x < 0 хибна в за

будь-якої оцінки змінної х, а формула 0 < x −1 істинна за всіх оцінок x , окрім двох: x = 0 та x =1. У першому випадку формула беззмісто- вна (результат віднімання 0 – 1 – не визначено), у другому – хибна ■

1.1.3. СТРУКТУРОВАНІ ФОРМУЛИ

Структуровані формули всіх ПЧП будуються однаково – за допомо- гою логічних зв'язок і кванторів. Зв'язки та квантори будемо тракту- вати як певні операції (композиції) на формулах, що дозволяють буду- вати нові формули з простіших. Нехай P та Q – формули. Класичними логічними зв'язками є:

1)(P & Q ) – кон'юнкція (логічне "і");

2)(P Q ) – диз'юнкція (логічне "або");

3)(P Q ) – імплікація (логічне "випливає");

4)(P ↔ Q ) – еквіваленція (логічне "тоді й тільки тоді");

5)(¬P ) – заперечення (логічне "ні").

У формулах 1)–3) P та Q називаються відповідно кон'юнктивними

та диз'юнктивними членами, засновком і висновком імплікації. При-

кладами структурованих формул є (P (¬P )), (((P Q ) Q ) Q ),

((¬P ) (¬Q )) тощо. Навпаки, вирази ( ¬P або (P ) не є формулами.

У першому випадку не вистачає закриваючої дужки, у другому – ви- сновку імплікації.

Правила обчислення значень структурних формул задає табл. 1.113. Зазначимо, що в класичних ПЧП логіка двозначна. У нашому варіанті

13 Це тільки один з можливих варіантів правил. Він відповідає практиці мов програ- мування.

27

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

ПЧП логічні зв'язки поширюються й на випадок беззмістовних зна- чень формул. Нагадаємо, що символи 1, 0 та # позначають відповідні істиннісні значення.

Згідно з табл. 1.1 формула P (¬Q ) для P = 0,Q = 0 та P =1,Q = # істинна, для P = 0,Q = # – беззмістовна.

Вивчення алгебричних властивостей елементарних формул зво- диться до вивчення так званих пропозиційних форм, які будуються з пропозиційних змінних за допомогою логічних зв'язок. Пропозиційні змінні – це змінні, які пробігають істиннісні значення 1, 0 та #. Про- позиційні форми Φ1 та Φ2 називаються рівносильними ( Φ1 Φ2 ), як-

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

Для пропозиційних форм існує багато повних систем форм-аксіом, які дозволяють отримати з них усі форми-тавтології за допомогою пе- вних правил виведення. Одну з таких систем наведено у вправі 19. Пропозиційні логіки використовуються для спрощення та еквівалент- них перетворень структурних формул ПЧП (див. вправу 26).

Нехай х – довільна змінна, P – формула. Квантор ("для всіх") утворює формулу ( xP ) , квантор ("існує") – формулу ( xP ). Кажуть,

що всі входження змінної x у формули ( xP ) ,( xP ) є зв'язаними. Пе- вне входження змінної х у довільну формулу Q називається вільним,

28

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

якщо воно не є зв'язаним. Формула може мати одночасно і зв'язані, і вільні входження однієї й тієї самої змінної.

Наприклад, у формулі ( y( z(( x(x >1))& x +y = z ))) (*) два перші вхо-

дження змінної x зв'язані, а третє – вільне, входження решти змінних – зв'язані. Формула ( xP ) істинна в інтерпретації, якщо формула P іс-

тинна в ній для всіх можливих оцінок змінних, що містять x . Формула ( xP ) істинна в інтерпретації, якщо формула P істинна в ній принаймні

для однієї оцінки змінних, що міститьx . І в першому, і в другому випа- дках оцінка впливає тільки на вільні входження x у формулу P .

Приклад 1.2. Істинність формул із кванторами в арифметиці .

Вона не містить вільних входжень х і описує існування суми двох на- туральних чисел, перший із доданків якої більший від 1 ■

Іноді можуть цікавити не всі оцінки змінних, а тільки ті, що задо- вольняють певну умову Q . Тоді застосовують обмежені квантори ви-

приклад, ( x > 0)P , x(x%2 = 0)P . Якщо необхідно гарантувати існу-

вання не більше одного елемента, що задовольняє певну умову P, то використовують квантор ( 1xP ).

Як і у випадку термів, існують певні домовленості про економне застосування дужок у структурованих формулах. По-перше, зазвичай опускають зовнішню пару дужок. По-друге, якщо формула містить входження тільки однієї бінарної зв'язки, то дужки взагалі не пи- шуться, а відновлюються, розпочинаючи справа наліво. По-третє, се- ред зв'язків установлено такий пріоритет: ← & ↔. Це означає, що спочатку відновлюються дужки праворуч від заперечень, а потім дужки, пов'язані з кон'юнкцією тощо.

Приклад 1.3. Відновлення дужок.

У формулі P ←Q R ↔ P дужки відновлюються таким чином:

P (←Q ) R ↔ P

(P (←Q )) R ↔ P

((P (←Q )) R )↔ P

29

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

(((P (←Q )) R )↔ P )■

мість формули ( x(A(x) B(x,y))) можна писати xA(x) B(x,y), а за-

мість формули (( x(A(x)) B(x,y)) – x(A(x) B(x,y).

Формули ПЧП дозволяють формально описувати математичні влас- тивості об'єктів предметної області.

Приклад 1.4. Формалізуємо твердження: "Для всякого натурально- го числа існує просте число, більше за нього".

Введемо до сигнатури Ω ПЧП натуральної арифметики унарний предикат рrime, який інтерпретується як "бути простим числом". Тоді твердження можна подати формулою n p(prime(p)& n < p)14 ■

У наступних підрозділах буде уточнено загальне поняття інтерпре- тації ПЧП і розглянуто деякі властивості інтерпретованих ПЧП.

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

*Література для CР: формальні мови – [56, 63, 69, 121];

формальна мова першого порядку – [63, 79, 84, 89, 94, 123]; пропозиційна логіка – [63, 84, 94, 123]; класична логіка як прикладна система – [89].

Контрольні запитання та вправи

1.Що таке предметна константа?

2.Що таке предметна змінна?

3.Що таке тип операції?

4.Навести приклади типізованих операцій.

5.Що таке функціональний (предикатний) символ? Проілюст- рувати прикладами.

6.Які елементи входять до складу сигнатури ПЧП?

14 Насправді предикат рrime(х) є арифметичним, тобто його можна виразити засоба- ми самої ПЧП натуральної арифметики, але це потребує певних технічних навичок.

30