Типологія формул за семантичними ознаками

За синтаксичними ознаками всю множину правильно побудованих формул (ППФ) в S¹ поділяють на прості (атомарні) і складні (молекулярні).

За семантичними ознаками ППФ в S¹ поділяють на:

— тотожно-істинні (або тавтології, або логічні тотож­ності, або логічні закони, або загальнозначущі формули);

— тотожно-хибні (або протиріччя, або не загально- значущі формули);

— виконувані формули.

Л. Витгенштейн. Логико-философський трактат. — М., 1958. — С. 13, 4, 461.

Таблиця істинності для кожної з цих формул і схожих з ними результатом матиме одне значення «х» («хибу»):

Тавтології і протиріччя називають L- детермінованими виразами (логічно детермінованими, логічно спричиненими), а виконувані формули L- недетермінованими (логічно недетермінованими).

Уміння розпізнавати і диференціювати формули за се­мантичними ознаками передує розгляду різноманітних відношень між формулами у системі S¹.

4. Рівносильні формули

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

Наприклад, візьмемо дві формули : (p ⊃ q) i (p ∨ q). По­будуємо для них таблиці істинності.

Ці формули (та їм подібні) називають р і в н о с и л ь - н и м и.

Дефініція. «Нехай А і В — формули, а х₁, х₂, х₃,... X_n список усіх пропозиційних змінних, що входять, в край­ньому разі, до складу однієї із них. При наявності цих вихідних даних вважається, що формули А і В — рів­носильні, якщо при будь-яких наборах значень х₁, х₂, х₃,... х_п логічні значення формул А і В співпадають».

З цього визначення випливає, що рівносильними будуть не тільки ті формули, до складу яких входять одні й ті са­мі пропозиційні змінні, але й такі, в яких пропозиційні змінні різняться. Наприклад:

Незважаючи на те, що формули 1 і 2 різняться змінни­ми q i r, їхні таблиці істинності співпадають. Це дає під­ставу стверджувати, що логічні значення формули А не залежать від пропозиційної змінної x_i, якщо для будь- якого набору логічних значень решти пропозиційних змін­них у таблиці істинності для А логічне значення А одне й те саме, коли x_i хибне і коли x_i істинне.

Для відношення рівносильності характерними є:

1) Рефлексивність (А рівносильне А);

2) Симетричність (якщо А рівносильне В, то В рівно­сильне А);

3) Транзитивність (якщо А рівносильне В і В рівно­сильне С, то А рівносильне С).

Термін «рівносильно» є виразом метамови. Якщо поєд­нати дві рівносильні формули знаком еквіваленції, то отримаємо тотожно-істинну формулу або закон логіки.

Тобто, якщо А і В рівносильні, то формула А^м В буде логічним законом, що записується так:

Законів логіки (тобто тавтологій) в S¹ може бути скіль­ки завгодно. Але можна виділити кілька десятків тавтоло- гій, за допомогою яких здійснюються всі дії в системі S¹. Ці вирази легко можна перевірити за допомогою таблиць істинності.

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

Розглянемо основні закони логіки висловлювань, які записані засобами метамови в S¹.

1. Закон подвійного заперечення:

2. Закон комутативності:

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

Властивість комутативності притаманна операціям & i V.

3. Закон асоціативності:

Назву цьому закону дає латинське слово associatio, що у перекладі означає з’єднання. Суть закону асоціативності полягає в тому, що при подвійному здійсненні операції над трьома висловлюваннями можна з’єднати (асоцію­вати) перше і друге висловлювання, виконати операцію над ними, а потім цю ж операцію провести над отри­маним результатом і третім висловлюванням. Рівно­цінним є й такий порядок здійснення операцій: з’єднати друге і третє висловлювання, провести операцію над ними, а потім цю ж операцію провести над отриманим результатом і першим висловлюванням.

Асоціативність властива для & i ∨.

4. Закон дистрибутивності:

Назва цього закону походить від латинського слова Aistributio, що у перекладі означає розміщення, розподі­лення. Із формули закону видно, що тут відбувається розподілення, розміщення першого висловлювання сто­совно другого, а потім першого відносно третього. Ре­зультати цього розміщення об’єднуються через (∨).

Існує два варіанти цього закону:

— «закон дистрибутивності кон’юнкції відносно диз’юнкції»:

5.

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

Розглянемо чотири закони відносно завжди істинних і завжди хибних формул.

6. Закон виключення тавтології із кон’юнкції.

Суть цього закону полягає в тому, що кон’юнктивне приєднання до виконуваної (нейтральної, або довільної) формули А тавтології не додає до цієї формули ніякої нової інформації. Тобто, згідно з природою (&), значення формули А & T цілком залежить від значень формули А:

7. Закон перетворення кон’юнкції в протиріччя.

Цей закон виражає, що в силу природи кон’юнкції, якщо один із кон’юнктів завжди хибний (⊥), то вся кон’юнкція стає завжди хибною:

8. Закон перетворення диз’юнкції в тавтологію.

Відомо, що коли один із диз’юнктів завжди істинний, то вся диз’юнкція зажди буде істинною (T):

9. Закон виключення протиріччя із диз’юнкції.

Якщо приєднати диз’юнктивно до довільної формули А завжди хибну формулу, то в силу природи диз’юнкції значення утвореної формули А ∨ ⊥ залежатиме від до­вільної формули А:

10. Перший закон де-Моргана, або заперечення кон’ю­нкції:

11. Другий закон де-Моргана, або заперечення диз’ю­нкції:

Суть законів де-Моргана полягає в перенесенні запе­речень, застосованих до складних висловлювань, на про­сті висловлювання, що їх складають.

12. Закон виразу кон’юнкції через диз’юнкцію:

13. Закон виразу диз’юнкції через кон’юнкцію:

14. Закон виключення імплікації:

15. Закон заміни еквіваленції:

16. Закон заміни сильної диз’юнкції:

«Закони виявлення»:

«Закони поглинання»:

«Нехай А — деяка формула, і А' отримується із А за­міною хоча б одного входження підформули В у форму­лу А на В'. Тоді, якщо В’ рівносильна В, то формула А' рівносильна А». Це правило називається «правилом за­міни рівносильності».

Застосовуючи це правило, можна переходити від одних формул до інших, які їм рівносильні.

Наведені закони 1—23 обгрунтовуються таблицями іс­тинності. Але, використовуючи ці закони, не звертаючись до таблиць істинності, а керуючись правилом заміни, мо­жна встановити рівносильність будь-якої формули.

Наприклад, візьмемо формулу

Відповідно до другого закону де-Моргана (11) замінимо у цій формулі антецедент:

Отримана формула рівносильна вихідній. Згідно з законом виключення імплікації (14) замінимо цю формулу рівно­сильною їй:

Підформулузамінимо згідно з першим законом

де-Моргана (10):

Тепер застосуємо закон подвійного заперечення (1):

В силу транзитивності відношення рівносильності отри­мана формула є рівносильною всім попереднім.

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

5.