§ 8. Логічна рівносильність

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

Наприклад, висловлювання:

(1) “Я читала цю книгу і бачила цей фільм”

(2) “Невірно, що я не читала цю книгу або не бачила цей фільм” є рівносильними.

З метою перевірки, спочатку формалізуємо вислов­лювання (1)і (2). У результаті отримаємо дві формули:

Побудуємо для формул (1) і (2) таблиці істинності:

г

133

За допомогою рівносильностей можливо одні форму­ли перетворювати на інші. Такі перетворення можуть призводити до спрощення формул (їх мінімізації).

Розглянемо приклад.

Нехай ми маємо формулу Спочатку усунемо імплікацію. В результаті отримаємо:

Застосуємо до отриманої формули закон дистрибутив­ності:

Позаяклогічною суперечністю, то на підставі

закону виключення суперечення із диз’юнкції отримаємо:

b законом ідемпотентності Отже, можливо

МІйснити спрощення:

Змінимо порядок змінних у формулі на підставі закону комутативності:

Після застосування закону поглинання до перших двох членів диз’юнкціїотримаємо:

Ще раз застосуємо закон поглинання:

Розглянемо ще один приклад.

Командир оточеної ворогами фортеці надіслав три повідомлення:

(1) “Якщо ми отримаємо провіант, то нам не загро­жуватиме голодна смерть”;

(2) “Якщо ми не отримаємо провіант, то нам або за­грожуватиме голодна смерть, або ми спробуємо прорва­тись крізь оточення”;

(3) “Якщо нам загрожуватиме-голодна смерть, то ми спробуємо прорватись крізь оточення”.

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

Спочатку зафіксуємо ці повідомлення символічно:

д єднаємо щ формули за допомогою логічного спо­лучника “диз’юнкція” і спробуємо спростити складну но­воутворену формулу:

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