Таблиці істинності формул і закони

Формула є словом, тобто послідовністю символів – імен пропозиційних змінних, знаків зв'язок і дужок. Це слово має певну структуру, обмежену правилами побудови формул. Підслово цього слова, яке є формулою, називається підформулою. Наприклад, у формулі ((A «B)&(Ø(A Ú B))) є підформули A, B, (A «B), (A Ú B), (Ø(A Ú B)).

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

Обчислимо значення формули, наприклад, (A ® B)&(B ® A) при всіх можливих наборах значень змінних A і B. Обчислення подамо такою таблицею:

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

Розглянемо узгодження, які дозволяють скорочувати запис формул. Пропозиційні зв'язки упорядковуються за " силою тяжіння до формул " подібно до знаків арифметичних операцій. Всі розуміють, що вираз 1+2´3 позначає суму 1 і 2´3, а не добуток 1+2 і 3, тобто знак множення "притягується" сильніше за знак додавання. Зв'язка Ø вважається найсильнішою, тобто Ø A Ù B є скороченням від (Ø A)Ù B, а не від Ø(A Ù B). Далі за спаданням "сили тяжіння" двомісні зв'язки ідуть у такому порядку: &, Ú, ®, º. Отже, формулу A Ú B Ù C можна розглядати, як скорочений запис формули A Ú(B Ù C), а формулу A º B ® C Ú A – як A º(B ®(C Ú A)).

Всі двомісні зв'язки мають властивість лівобічного зв'язування. Це означає, що якщо праворуч і ліворуч від підформули записано без дужок знаки двомісних зв'язок, "сила тяжіння" яких однакова, то першою до підформули застосовується ліва з них. Наприклад, A Ú B Ú C є скороченим записом формули (A Ú B)Ú C.

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

Наприклад, неважко переконатися, що за довільних формул A, B, C наступні рівносильності є законами (праворуч указано назви деяких з них):

(1) A Ù B º B Ù A, A Ú B º B Ú A – закони комутативності

(2) A Ù(B Ù C) º (A Ù B)Ù C, A Ú(B Ú C) º (A Ú B)Ú C – закони асоціативності

(3) A Ù(B Ú C) º (A Ù B)Ú(A Ù C), A Ú(B Ù C) º (A Ú B)Ù(A Ú C) – закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції

(4) A Ù A º A, A Ú A º A – закони ідемпотентності

(5) A Ú(A Ù B) º A, A Ù(A Ú B) º A

(6) Ø(A Ú B) º Ø A ÙØ B, Ø(A Ù B) º Ø A ÚØ B – закони Де Моргана

(7) ØØ A º A – закон подвійного заперечення

(8) A Ù0 º 0, A Ù1 º A, A Ú0 º A, A Ú1 º 1 – закони поглинання

(9) A ÚØ A º 1 – закон виключеного третього

(10) A ÙØ A º 0 – закон суперечності

(11) A ® B º Ø B ®Ø A – закон контрапозиції

Корисно також пам'ятати ще два закони:

(12) A ® B º Ø A Ú B

(13) A «B º (A ® B)Ù(B ® A).

На законах грунтуються так звані рівносильні перетворення формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула A Ú(Ø A ® B) має рівносильні формули A Ú(ØØ A Ú B), A Ú(A Ú B), (A Ú A)Ú B, A Ú B, що одержуються послідовним застосуванням законів (12), (7), (2), (4).