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

Тотожно-хибні формули є протилежними тотожно-істин- ним формул. Це означає, що заперечення тотожно-істинної формули дає тотожно-хибну формулу і навпаки.

І, нарешті, третім видом формул за семантичними озна- ками є виконувані, або нейтральні, формули.

Виконуваною фомулою в S1 називається така форму- ла, яка при одних наборах значень пропозиційних змін- них є істинною, а при інших – хибною. Їх іноді назива- ють фактичними істинами.

Наприклад: p & (q r), p s , (p q) p, тощо. Пере-

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

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

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

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

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

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

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

н и м и.

Дефініція. «Нехай А і В – формули, а х1, х2, х3,... хn список усіх пропозиційних змінних, що входять, в край- ньому разі, до складу однієї із них. При наявності цих вихідних даних вважається, що формули А і В – рів- носильні, якщо при будь-яких наборах значень х1, х2, х3,... хn логічні значення формул А і В співпадають».

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

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

Для відношення рівносильності характерними є: 1) Рефлексивність (А рівносильне А);

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

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

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

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

|= А В (або #А В).

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

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

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

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

A ≡ A1 (читається: те, що не є не-А є те ж саме, що А).

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

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

тому, що результат операції з двома елементами не залежить від порядку, в якому беруться ці елементи.

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

A & B ≡ B & A

(читається: А і В є те саме, що й В і А)

А В ≡ В А

(читається: А або В є те саме, що й В або А).

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

Назву цьому закону дає латинське слово associatio, що у перекладі означає з’єднання. Суть закону асоціативності

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

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

(А & В) & С ≡ А & (В & С)

(читається: (А і В) і С є те саме, що й А і (В і С)).

(А В) С ≡ А (В С) (читається: (А або В) або С є те ж саме, що й А або (В або С)).

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

Назва цього закону походить від латинського слова distributio, що у перекладі означає розміщення, розподі-

лення. Із формули закону видно, що тут відбувається

розподілення, розміщення першого висловлювання сто- совно другого, а потім першого відносно третього. Ре- зультати цього розміщення об’єднуються через ( ).

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

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

диз’юнкції»:

A & (B C) ≡ (A & B) (A & C)

(читається: А і (В або С) є те саме, що й (А і В) або (А і С)).

«закон дистрибутивності диз’юнкції по відношен-

ню до кон’юнкції»:

А (В & С) ≡ (А В) & (А С)

(читається: А або (В і С) є те саме, що й (А або В) і (А або С)).

5. Закон ідемпотентності:

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

кон’юнкцією чи диз’юнкцією сполучаються дві однакові змінні, то одну змінну можна виключити:

А& А ≡ А (читається: А і А є те саме, що й А);

АА ≡ А (читається: А або А є те саме, що й А).

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

Завжди істинну формулу (або тавтологію) позначи- мо символом ( ), а завжди хибну формулу – ( ).

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

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

формули А & цілком залежить від значень формули А:

А& ≡ A.

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

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

кон’юнкція стає завжди хибною:

А& ≡ .

8.Закон перетворення диз’юнкції в тавтологію. Відомо, що коли один із диз’юнктів завжди істинний,

то вся диз’юнкція зажди буде істинною ( ):

А≡ .

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

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

вільної формули А:

А≡ А.

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

нкції:

A& B ≡ A B .

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

A B ≡ (A B).

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

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

A& B ≡ (A B).

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

A B ≡ (A & B).

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

А В ≡ A В.

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

АВ ≡ (А В) & (B A).

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

А В ≡ (А В) & ( A B ).

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

17. A & (B A) ≡ A & (B A)& B

18. A (B A) ≡ A (B A) B

19. (A B)& (A & C)≡ (A B)& (A C)& (B C) 20. (A& B) (A & C)≡ (A& B) (A & C) (B & C)

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

21.(A B)& (A B)≡ B

22.(A B)& A ≡ A

23.(A& B) A ≡ A

«Нехай А – деяка формула, і А′ отримується із А за-

міною хоча б одного входження підформули В у форму- лу А на В′. Тоді, якщо В′ рівносильна В, то формула А′

рівносильна А». Це правило називається «правилом за- міни рівносильності».

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

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

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

(A B) C.