Операції над висловленнями
Однією з основних задач логіки висловлень є дослідження операцій, за допомогою яких з певних вихідних висловлень утворюють нові висловлення. Такі операції і називають логічними.
Означення кожної логічної операції задаватимемо відповідною матрицею (таблицею), в перших стовпчиках якої записуються всі можливі істинісні значення компонентів, а в останньому стовпчику — істинісне значення результату операції.
Визначення 2 Бінарну логічну операцію, яка відповідає зв’язці “і” звичайної мови, позначається символом “Ù” і задається наступною матрицею, називають кон'юнкцією, або логічним множенням.
| p | q | pÙq |
Вищенаведене табличне означення операції “кон'юнкція” рівнозначне такому словесному означенню: “Кон'юнкція pÙq істинна тоді і тільки тоді, коли обидва компоненти р і q є одночасно істинними”.
У схемах управління логічна операція кон'юнкція реалізується в схемі збіги, показаної на рис. 1.2.
Рис. 1.2 –Діаграма Венна (кон'юнкція)
Визначення 3 Бінарну логічну операцію, відповідну зв’язці “або нероздільне”, що позначається символом “Ú” і задається наступною таблицею, називають диз’юнкцією або логічним додаванням.
| p | q | pÚq |
Словесне означення диз'юнкції: “Диз’юнкція “pÚq” істинна тоді і тільки тоді, коли принаймні один з її компонентів р або q є істинним, у протилежному випадку диз’юнкція є хибною”.
Операція диз'юнкції часто називається логічним складанням, а також логічною операцією "АБО" (рис. 1.3). Схему, відтворюючу операцію логічного додавання зазвичай називають збиральної схемою.
Рис. 1.3 – Діаграма Венна (диз'юнкція)
Зауважимо, що A Ú 1 = 1; A Ú Ā = 1.
З двох простих висловлювань за допомогою логічних зв'язків можна утворити 16 логічних висловлювань. Але заперечення, кон'юнкція і диз'юнкція є основними логічними зв'язками, так як всі інші можна утворити з основних логічних зв'язків.
Визначення 4 Унарну операція, відповідну виразу “неправильно, що”, яку позначають символом “—“ і задають наступною таблицею, називають логічнимзапереченням. Вираз „ 
” читають “не р”.
| p |
|
Словесне означення заперечення: “Заперечення ` істинне тоді і тільки тоді, коли р — хибне, у протилежному випадку` — хибне” (рис. 1.4).
Рис. 1.4 – Діаграма Венна (заперечення)
Заперечення є найпростішою логічною операцією і єдиною логічною операцією, виконуваної над одним аргументом.
Зауважимо, що послідовне виконання двох операцій заперечення Ā призводить до вихідного значення А.
Визначення 5 Операцію, яка відповідає сполучнику “якщо..., то...”, позначається символом “®”, називають імплікацією. ЇЇ задають таблицею:
| p | q | p®q |
В імплікації р називають антецедентом або посиланням (умовою), q— консеквентомабо висновком.
Словесне означення операції “імплікація” таке: “Імплікація „p®q” хибна тоді і тільки тоді, коли її антецедент — істинний, а консеквент — хибний, в усіх інших випадках імплікація — істинна”.
Імплікацією висловлень А і В називається висловлювання, позначене символами А ® В, яке хибно тоді і тільки тоді, коли А істинно, а В хибно. Читається "А імплікує В". Імплікація - це логічна операція, відповідна союзу "якщо ... то". Запис А ® У означає те ж, що і вислів: "якщо А то В", "з А випливає В" "А є достатня умова для В", для того щоб А необхідно, щоб В "," В є необхідна умова для А "," для того щоб В, достатньо щоб А ". Порівняємо такі пропозиції:
1. Якщо число n ділиться на 4, то воно ділиться на 2.
2. Якщо Іванов захоплений математикою, то Петров нічим не цікавиться.
Очевидно, що сенс союзу "якщо ... то" в цих пропозиціях різний.
З визначення імплікації випливає, що:
1. Імплікація з помилковим антецедентом завжди істинна.
2. Імплікація з істинним консеквент завжди істинна.
3. Імплікація хибна тоді і тільки тоді, коли її антецендент істинний, а консеквент хибний.
Прийняте визначення імплікації відповідає вживанню союзу "якщо ... то" в пропозиції "Якщо буде гарна погода, то я прийду до тебе в гості", яке ви розціните як брехня в тому випадку, коли погода гарна, а приятель до вас не прийде.
Разом з тим визначення імплікації змушує вважати істинним пропозиції як "Якщо 2х2 = 4, то Москва столиця Росії"; "Якщо 2х2 = 5, то я найкрасивіша дівчина Росії". Це пов'язано з тим, що визначеннями логічних операцій сенс складових висловлень не враховується, вони розглядаються як об'єкти, що володіють єдиною властивістю - бути істинними або помилковими (рис. 1.5).
Рис. 1.5 – Діаграма Венна (імплікація)
Визначення 6 Бінарну логічну операцію, яка відповідає зв’язці “тоді і тільки тоді”, позначається символом “«”, називають еквіваленцією. Її табличне означення:
| p | q | p«q |
Словесне означення еквіваленції можна сформулювати так: “Еквіваленція “p«q” істинна тоді і тільки тоді, коли p і q набувають однакових значень істинності, в протилежному випадку еквіваленція — хибна”.
Логічна операція еквівалентності, відповідає союзу "тоді і тільки тоді, коли" і читається "А еквівалентно В", "Для того, щоб А необхідно і достатньо, щоб В".
Коли ми говоримо "А тільки тоді, коли В" то маємо на увазі, що обидві пропозиції А і В одночасно істинні, або одночасно хибні. Наприклад, говорячи: "Я поїду в Ленінград тоді і тільки тоді, коли ти поїдеш до Києва", ми стверджуємо, що-небудь станеться і те і інше, або ні того, ні іншого. Можна довести використовуючи таблицю істинності, що для будь-яких висловлювань А і В висловлювання (А Û В) = 1 тоді і тільки тоді, коли (А Þ У) = 1 і (В Þ А) = 1.
Це твердження використовується при доказі теорем виду А Û В. Одним із способів доказу істинності висловлювання А Û В є доказ істинності висловлювання А Þ У (необхідність) і істинності висловлювання У Þ А (достатність).
Висловлювання А і В називаються рівносильними. Якщо (А Û В) = 1 кажуть, що формули F 1 і F 2 рівносильні, якщо їх еквіваленції F1 Û F2 - тавтологія (тотожне істинне висловлювання, що на рис. 1.6).
Рис. 1.6 – Діаграма Венна (еквіваленції)
Запис F 1 º F 2 читається: "формула F 1 рівносильна формулою F 2"
А Û У º (А Þ В) Ù (В Þ А)
Рівносильність є відношення між формулами (також як рівність відношення між числами, паралельність - відношення між прямими). Ставлення равносильности володіє наступними властивостями:
а) рефлективності F º F
б) симетричності: якщо F 1 º F 2 то F 2 º F 1
в) транзитивності: якщо F 1 º F 2 і F 2 º F 3, то F 1 º F 3
Висловлення, які не містять логічних зв'язок, називають елементарними чи атомарними. Наприклад, висловлення “Рейк’явік — столиця Ісландії” і “3 — просте число” — елементарні висловлювання. Висловлення, яке містить хоча б одну логічну зв’язку,називають складним. Наприклад, висловлення “10 не є простим числом”.
Пропозиційні літери, символи логічних операцій та дужки – це вихідні символи алгебри висловлень.
Довільну послідовність вихідних символів називають виразом мови.
З множини виразів виділяють підмножину формул.
Формулами алгебри висловлень називають пропозиційні літери і вирази виду
`
F, F ÙG, FÚG, F®G, F«G,
де F,G – формули.
При цьому пропозиційні літери є елементарними (атомарними) формулами. Наприклад, (((p®( 
))Úr)Å s) – формула.
Дужки у формулі означають порядок виконання операції.
Символу кожної логічної операції відповідає пара дужок. Щоб запобігти громіздкості формул, використовують такі правила скорочення:
1) зовнішні дужки у записі кінцевої формули можна опустити;
2) всім логічним операціям приписують відповідний ранг, який знижується зліва на право: ` , Ù, Ú, ®, «.
Порядок старшинства логічних операцій наступний: Ø, &, Ù, ®, «.
Лівіша операція є сильнішою за правішу.
Знаючи ранг операції можна не використовувати дужки.
1.4 Таблиці істинності
У таблиці істинності формули f(p,q,r) кожному символу логічної операції в формулі f(p,q,r) відповідає окремий стовпчик таблиці, останній стовпчик відповідає істинісному значенню, яке визначається даною формулою (її головною операцією). Звернемо увагу на те, що кожен стовпчик таблиці істинності для формули f(p,q,r) відповідає певному кроку процесу її побудови або, як кажуть, певній підформулі f(p,q,r).
Наприклад, нехай задано функцію f(p,q,r)=( ®q Ú r )Ù(q®pÚ`r).
| p | q | r | `p | qÚr | `p ®qÚr | ` r | pÚ`r | q®pÚ`r | f(p,q,r) |
Часто таблицею істинності формули f(p1, ..., pn) називають скорочену таблицю, в якій з вищенаведеної залишають перших п стовпчиків (значень аргументів p1, ..., pn) і останній стовпчик.
Степінь складності таблиці істинності для формули f швидко зростає із збільшенням кількості різних пропозиційних букв, що входять до f. Так, при п = 3 кількість рядків таблиці дорівнює 23 = 8, при п = 4 воно становить 24= 16, при п= 5 дорівнює 25= 32, а при п = 10 — вже 1024. Практично побудувати таблицю істинності в останньому випадку вже неможливо.
Означення 7 Формули алгебри висловлень f (p1, ... , pn), які на всіх наборах (p1, …, pn), тобто при всіх можливих розподілах істинісних значень пропозиційних літер p1, ..., pn, набувають значення 1 (останній стовбець таблиці істинності - лише 1), називають тавтологіями, тотожно істинними формулами або законами алгебри висловлень.
Те, що формулаалгебри висловлень f є тавтологією, позначаютьтак: ⊨ f.
Означення 8 Формулу алгебри висловлень f (p1 , ¼, pn), яка набуває значення істинності 0 на всіх 2n наборах, називаютьсуперечністю. Найпростішим прикладом суперечності є формула pÙ 
.
Означення 9 Формулу алгебри висловлень, яка не є ні тавтологією, ні суперечністю, називають нейтральною. Прикладом нейтральної формули є p®q.
Множини тавтологій, суперечностей і нейтральних формул попарно не перетинаються і разом становлять множину всіх формул алгебри висловлень.
Означення 10 Формулу алгебри висловлень, якане є суперечністю, називають виконуваною.
Так, формула р®р — виконувана і формула р® теж виконувана при ½p½= 0; |p® |=1.
Означення 11 Висловлення називають логічно істинним (на базі алгебри висловлень) тоді і тільки тоді, коли його логічна структура є тавтологією.
Прикладом логічно істинного твердження є “Трикутник АВС — рівнобедрений або трикутник АВС — не рівнобедрений” (логічна структура цього твердження — рÚ ).
Означення 12 Формули алгебри висловлень f (p1 , ¼, pn) і g ( p1 , ¼, pn) називають рівносильнимиабологічно еквівалентними, якщо їх функції істинності |f| і |g| тотожно рівні, тобто, якщо їх значення на всіх 2n наборах збігаються.
Рівносильність формул f і g позначатимемо fºg Символ “º” не є символом операції алгебри висловлень, а означає певне відношення між формулами.
Основні рівносильності (закони) алгебри висловлень:
1. pÙqºqÙp – комутативність кон’юнкції.
2. pÚqºqÚp – комутативність диз’юнкції.
3. pÙ(qÙr)º(pÙq)Ùr – асоціативність кон’юнкції.
4. pÚ(qÚr)º(pÚq)Úr – асоціативність диз’юнкції.
5. pÙ(qÚr)ºpÙqÚpÙr – перший дистрибутивний закон.
6. pÚ(qÙr)º(pÚq)Ù(pÚr) – другий дистрибутивний закон.
7. 
(pÙq)º Ú 
закони
8. (pÚq)º 
Ù де Моргана.
9. p®qº Úq.
10. p«qº(p®q)Ù(q®p).
11. 
ºp – закон подвійного заперечення.
12. 
pÙpºp. закони
13. pÚpºp. ідемподентності.
14. p®qº ® .
15. 
pÚpÙqºp. закони
16. pÙ(pÚq)ºp. поглинання.
17. 
uÙ1ºu. правила
18. uÙ0º0. співвідно-
19. uÚ1º1. шення
20. uÚ0ºu. констант
21. pÚ º1 – закон виключення третього.
22. pÙ º0 – закон протиріччя.
1.5 Алгоритм побудови формули за таблицею істинності
1. Виділити ті рядки таблиці істинності, в останніх стовпчиках яких міститься величина функції 1.
2. Виписати для кожного такого виділеного рядка кон'юнкцію (логічне «і») таким чином: якщо величина змінної цьому рядку дорівнює 1, то в кон'юнкцію записати позначення цієї змінної, інакше — її заперечення.
3. Всі отримані на попередньому кроці кон'юнкції записати елементами диз'юнкції (логічного «або»).
Приклад скорочення логічних виразів (спрощення логічних формул):
.