Тавтології алгебри висловлень

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

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

Нехай треба довести істинність деякого твердження А. Припускається, що істинне його заперечення А. Потім доводиться, що має місце деяке твердження В, для якого істинними є твердження і . Доведення істинності цих імплікацій залежить від змісту висловлень А і В.

Нехай істинність тверджень і установлена. Одночасний вивід двох тверджень В і В - суперечність, абсурд. Тоді стверджуємо, що істинне висловлення А. Такий метод доведення називається методом зведення до суперечності (до абсурду).

Розглянемо основні тавтології на яких ґрунтуються деякі схеми математичних доведень.

Теорема 2.1. Наступні формули алгебри висловлень є тавтологіями:

а) закон виключення третього ;

б) закон заперечення суперечності ;

в) закон подвійного заперечення ;

г) закон тотожності ;

д) закон контрапозиції ',

е) закон силогіму (правило ланцюгового висновку)

;

ж) закон протилежності;

з) правило добавлення антецедента (”істина з чого завгодно”)

;

и) правило ”з хибного що завгодно” ;

к) правило “модус поненс” (modus ponens) ;

л) правило “модус толленс” (modus tollens) ;

м) правило перестановки посилок ;

н) правило об’єднання (і роз’єднання) посилок) ;

о) правило розбору випадків ;

л) правило приведення до абсурду

.

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

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

Покажемо, що ліва частина даної еквівалентності перетворюється в хибне висловлення тоді й тільки тоді, коли в хибне висловлення перетворюється формула, яка стоїть в правій частині еквівалентності. Дійсно, формула перетворюється в хибне висловлення лише тоді, коли = 1, = 0. У свою чергу = 0 тоді й тільки тоді, коли = 1 і = 0. Отже, = 0 лише в тому випадку, коли = 1, = 1, = 0. З іншого боку, формула перетворюється в хибне висловлення лише тоді, коли = 1 і = 0. У свою чергу = 1 лише за умов = 1 і = 1. Отже =0 тоді й тільки тоді, коли = 1, = 1 і 0. доведене означає, що права й ліва частина еквівалентності одночасно перетворюються або в істинне, або в хибне висловлення. Таким чином, згідно означення еквівалентності вся формула завжди є істинним висловленням.

Наведемо приклади тавтологій, які виражають властивості логічних операцій

Властивості кон’юнкції й диз’юнкції.

а) закони ідемпотентності ;

б) закони спрощення ;

в) закони комутативності

;

г)закони асоціативності

;

д) закони дистрибутивності

;

;

е) закони поглинання ;

ж) закони де Моргана

;

Властивості імплікації й еквівалентності.

а)

б) ;

в)

г)

д) ;

е) ;

ж)

з)

і)

к)

л)

м)

н)

о) ;

п)

р)

Вираження одних операцій через інші.

а)

б)

в)

г)

д)

е)

ж)