Виходячи з таблиці відповідності, еквіваленцію (х1 óx2) можна також визначити як висловлювання, яке істинно тоді і тільки тоді, коли висловлювання x1 і х2 або обидва істинні, або обидва хибні.
Так само як і імплікація, операція еквіваленціі дуже часто застосовується при формулюванні різних теорем. На відміну від імплікації, еквіваленція визначає необхідні і достатні умови.
Запитання і завдання
3.14. Складіть складне висловлювання з використанням операції еквіваленціі з наступних простих висловлювань: "Сума квадратів двох сторін трикутника дорівнює квадрату третьої сторони", "Трикутник прямокутний". Перевірте результат за таблицею відповідності.
3.15. З використанням операції еквіваленціі сформулюйте складне висловлювання, яке описує спрацьовування запобіжника в електричному ланцюзі.
3.16. Наведіть приклад теореми, при формулюванні якої використовується операція еквіваленціі.
Принципи докази тотожностей. Таблиця операцій з двома логічними змінними
Виникає питання: як довести, що вираз дійсно є тотожністю? Є два шляхи:
1. Доказ на основі таблиці відповідності. Для обох частин передбачуваного тотожність будуються таблиці відповідності. Якщо ці таблиці виходять однаковими (тобто для кожного набору значень аргументів значення лівої і правої частини виразу збігаються), то тотожність вірно.
2. Доказ шляхом послідовних тотожних перетворень. Послідовно перетворюючи ліву і праву частини, необхідно привести їх до однакового виду. Правила, за якими проводяться тотожні перетворення будуть розглянуті в гл.5.
Всього існує 16 операцій з двома логічними (булеві) змінними (табл.3.6).
Очевидно, що одні операції можуть бути виражені через інші. Наприклад, диз'юнкція може бути виражена через кон'юнкцію і заперечення:
Існують дві операції (стрілка Пірса і штрих Шеффера), через будь-яку з яких може бути виражена будь-яка інша операція. наприклад:
Безліч всіх булевих функцій разом з операціями заперечення, кон'юнкції і диз'юнкції утворюють булеву алгебру.
Як видно з табл.5.1, значення лівої і правої частини (виділено жирним шрифтом) збігаються при всіх значеннях змінних, що і було потрібно довести.
Аналогічно, шляхом побудови таблиць відповідності, можуть бути доведені і інші наведені вище тотожності.
Ці властивості дозволяють отримати ряд інших важливих законів і тотожностей вже без звернення до таблиць відповідності:
1) закони де Моргана:
;
2) закони поглинання:
;
3) закони ідемпотентності:
.
Доведемо справедливість першого з законів де Моргана. Для цього рівність шляхом послідовних перетворень зведемо до очевидного тотожності.
З рівності і властивостей заперечення слід, що
Після розкриття дужок отримаємо наступне:
Так як і. а й. то попередній вираз можна представити в наступному вигляді:
Використовуючи властивості констант (...), Отримуємо
Таким чином, шляхом еквівалентних перетворень ми привели вираз першого закону де Моргана до тотожності і цим довели справедливість цього закону.
Другий закон де Моргана може бути легко отриманий на основі першого шляхом заперечення лівої і правої частини і відповідної заміни змінних. Запишемо перший закон де Моргана щодо змінних a і b:
.
Якщо рівні самі вирази, то рівні і їх заперечення:
.
З властивостей подвійного заперечення:
.
Зробимо заміну змінних:
Після заміни отримаємо:
,
тобто другий із законів де Моргана.
Також мають місце такі тотожності:
; ;
5.1. Доведіть за допомогою таблиці відповідності справедливість законів асоціативності і поглинання.
5.2. Шляхом послідовних перетворень перевірте, які з наступних виразів є вірними тотожністю:
Порівняйте отримані результати з результатами завдання 3.15.