Елементи математичної логіки, формули алгебри логіки

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

Воно являє собою диз'юнкцію кон'юнкції х, у і висловлювання z.

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

Для спрощення запису формул прийнято низку угод. Дужки можна опускати, дотримуючись наступного порядку дій: кон'юнкція виконується раніше, ніж всі інші операції, диз'юнкція виконується раніше, ніж імплікація і еквівалентність. Якщо над формулою стоїть знак заперечення, то дужки теж опускаються.

Логічне значення формули алгебри логіки повністю визначається логічними значеннями входять до неї елементарних висловлювань. Наприклад, логічним значенням формули x y ®z в разі, якщо x = 1, у = 1, z = 0 буде брехня, тобто ху ®z = 0.

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

Наприклад, для формули x y ®y таблиця істинності має вигляд табл. 6.

Таблиця істинності для формули x y ®y

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

Розглянемо поняття равносільностіформул алгебри логіки - дві формули алгебри логіки А і В називаються рівносильними, якщо вони приймають однакові логічні значення на будь-якому наборі значень вхідних у формули елементарних висловлювань. Равносильность формул зазвичай позначається знаком º. а запис А º У означає, що формули А і В рівносильні.

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

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

Наприклад, тожественно істинна формула

Формула А називається тотожно хибною формулою. якщо вона приймає значення 0 при всіх значеннях вхідних в неї змінних.

Наприклад, тотожне помилкова формула

Ясно, що ставлення равносильности має властивості рефлексивності, симетричності і транзитивності. (Відношення

між двома об'єктами a

b називається рефлексивним, якщо a

a. симетричним, якщо з a

a, і транзитивним, якщо з a

Між поняттями равносильности і еквівалентності існує наступна зв'язок: якщо формули А і B рівносильні, то формула А «В - тавтологія, і назад, якщо формула А« В - тавтологія, то формули А і В рівносильні.

Найважливіші равносильности алгебри логіки можна розбити на три групи.

I. Основні равносильности:

2. x Úx ºx закони ідемпотентності.

4. x Úі º і.

5. x л º л.

7. - закон суперечності.

8. - закон виключеного третього.

9. - інволютивними заперечення.

11. x Ú (y x) º x - закони поглинання.

II. Равносильности, що виражають одні логічні операції через інші:

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

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

Однак існують операції, за допомогою яких може бути виражена будь-яка з п'яти логічних операцій, які використовувалися до сих пір. Такою операцією є, наприклад, операція «Штрих Шеффера». Ця операція позначається символом х | у і визначається таблицею істинності (табл. 7).

Таблиця істинності для операції «Штрих Шеффера»

Очевидно, мають місце равносильности:

З цих двох рівносильних слід, що будь-яка формула алгебри логіки може бути замінена равносильной формулою, що містить тільки операцію «Штрих Шеффера».

III. Равносильности, що виражають основні закони алгебри логіки:

1. хуºух - коммутативность кон'юнкції.

2. x Úy ºy Úx - коммутативность диз'юнкції.

3. x (у z) º (x у) z - асоціативність кон'юнкції.

4. х Ú(у Úz) º (x Úy) Úz - асоціативність диз'юнкції.

5. x (у Úz) º (ху) Ú (x z) - дистрибутивность кон'юнкції щодо диз'юнкції.

6. x Ú (у z) º (хÚу) (x Úz) - дистрибутивность диз'юнкції відносно кон'юнкції.

Використовуючи закони равносильности I. II і III груп можна частину формули або формулу замінити рівноцінною їй формулою. Такі перетворення формул на основі законів рівносильно називаються рівносильними перетвореннями.

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

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