Рівносильні формули алгебри логіки

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

Равносильность формул будемо позначати знаком. а запис АВ означає, що формули A і В рав-носильними.

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

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

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

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

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

Ясно, що ставлення равносильности рефлексивно, симетрично і транзитивній.

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

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

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

Доведемо один із законів поглинання. Розглянемо формулу. Якщо в цій формулі а = 1 то, очевидно, і тоді як кон'юнк-ція двох справжніх висловлювань. Нехай тепер вфор-мулі А x = 0. Але тоді по визначенню операції кон'-юнкціі буде помилковою і кон'юнкція. Отже, у всіх випадках значення формули А збігаються зі зна-нями а, а тому Аx.

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

Ясно, що равносильности 5 і 6 виходять з рівносильно 3 і 4 відповідно, якщо від обох частин останніх взяти заперечення і скористатися законом зняття подвійного заперечення. Таким чином, в доказ-стве потребують перші чотири равносильности. Доведемо дві з них: першу і третю.

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

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

буде помилковою і кон'юнкція. Таким чином, в цьому випадку обидві частини равносильности мають однакові логічні значення.

Розглянемо равносильность 3. Якщо х і у принима-ють одночасно істинні значення, то буде істинної кон'юнкція ху і помилковим заперечення кон'юнкції. У той же час будуть помилковими і і. А поет-му буде помилковою і диз'юнкція.

Нехай тепер хоча б одна з змінних х або у приймає значення брехня. Тоді буде помилковою кон'юн-кція ху і істинної її заперечення. У той же час від-ріцаніе хоча б однієї з змінних буде істинним, а тому буде істинною і диз'юнкція.

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

Аналогічно доводяться равносильности 2 і 4.

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

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

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

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

Аналогічно може бути введена операція.

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

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

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

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

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

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

6. х (yz) (ХY) (X z) - дистрибутивность діз'-юнкціі щодо кон'юнкції.

Доведемо останній з перерахованих законів. Якщо х = 1, то будуть істинними формули х (у z), ху. x z. Але тоді буде істинною і кон'юнкція (ХY) (X z). Таким чином, при х = 1 обидві частини равносильности 6 приймають однакові логічні значення (справжні).

Нехай тепер х = 0. Тоді х (у z) yz, xуу і x z z, а тому і кон'юнкція х (yz) yz. Отже, тут обидві частини равносильности 6 одно-сильні однієї і тієї ж формулою Уz, і тому прини-мают однакові логічні значення.

§ 5. Рівносильні перетворення формул

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

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

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

1. Довести равносильность.

Використовуючи равносильности I, II і III груп запишемо ланцюжок рівносильних формул:

2. Спростити формулу.

Запишемо ланцюжок рівносильних формул:

Таке безліч М називається булевої алгеброю.

Якщо під основними елементами х, у, z. подрузі-Мева висловлювання, під операціями «+», «», «-» диз'юнкцію, кон'юнкцію, заперечення відповідно, а знак рівності розглядати як знак равносільнос-ти, то, як випливає з рівносильно I, II і III груп, все аксіоми булевої алгебри виконуються.

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

Значить, алгебра логіки є інтерпретацією бу-лівої алгебри. Алгебра Буля має і інші інтерпретації-ції. Наприклад, якщо під основними елементами х, у, z. безлічі М на увазі безлічі, під операци-ями «+», «», «-» об'єднання, перетин, доповнення відповідно, а під знаком рівності - знак рівності множин, то ми приходимо до алгебри множин. Неважкий-но переконатися, що в алгебрі множин все аксіоми алгебрами-ри Буля виконуються.

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

Функції алгебри логіки

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

Наприклад, формула є функцією

трьох змінних f (x, y, z). Особливістю цієї функції є та обставина, що її аргументи приймається-ють одне з двох значень: нуль або одиницю, і при цьому функція також приймає одне з двох значень: нуль або одиницю.

Определеніе.Функціей алгебри логіки га змін-них (або функцією Буля) називається функція га пере-сних, де кожна змінна приймає два зна-ня: 0 і 1, і при цьому функція може приймати толь-ко одне з двох значень: 0 або 1.

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

З'ясуємо, яке число функцій n змінних. Оче-видно, кожну функцію алгебри логіки (як і формулу алгебри логіки) можна задати за допомогою таблиці ис-тінності, яка буде містити 2 n рядків. Слідчий-но, кожна функція n змінних приймає 2 n зна-ний, що складаються з нулів і одиниць. Таким чином, фун-кція n змінних повністю залежать від зна-чень з нулів і одиниць довжини 2 n. (Загальне ж число на-борів, що складаються з нулів і одиниць, довжини 2 n одно. Значить, число різних функцій алгебри логіки п змінних одно.

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

Розглянемо таблицю істинності для різних функцій однієї змінної. Вона, очевидно, має вигляд: