Пропозиційна логика (продовження). Лекція №2

Course Title
Slide
І Математична логіка
Ця лекція про:
Введення в математичну логіку (продовження)
І.4 Рівність висловлювань
І.5 Тавтологія, протиріччя, здійсненне висловлювання
І.6 Логічний наслідок

І.4 Рівність висловлювань
Імплікація є найпотрібніша й найцікавіша операція пропозіційної логіки. Імплікація лежить в основі умовних пропозицій (умовних висловлювань).
Умовні висловлювання (імплікація, подвійна умова).
1. Імплікація
Висловлювання виду “A —> B“ читаємо таким чином: “якщо,
A то B“, або “A імплікує B“, або “В наслідує А”. Такі висловлювання називаються умовними.
Наприклад: “Якщо Василь мешкає в Куп’янську, тоді Василь мешкає
в Харківський області". Висловлювання A називається гіпотезою або припущенням (посилкою), а висловлювання B називається наслідком або висновком.
Пам’ятаємо, що A —> B є брехня тоді і тільки тоді, коли A — істина,
а B — брехня.
Таким чином, дані висловлювання є істинними:
“Якщо 2 < 4, тоді Париж є столиця Франції“ (true —> true = істина),
“Якщо Лондон є столиця Данії, тоді 2 < 4“ (false—> true = істина),
“Якщо 4 = 7, тоді Лондон розташовано у Данії“ (false —> false = істина).
Однак, наступне висловлювання є брехнею:
“Якщо 2 < 4, тоді Лондон є столицею Данії“ (true —> false = брехня).

2. Подвійна умова (еквівалентність)
Висловлювання виду “A ~ B” читаємо таким чином “A тоді
і тільки тоді, коли B“. Таке висловлювання називається подвійною умовою, або еквівалентністю. Воно є істина тоді, коли A і B мають однакові значення, A і B мають бути обидва істинними або обидва — брехнею.
A~B = (A —>B)&(B —>A)
Course Title
Slide
І.4 Рівність висловлювань
(продовження)

І.4.1 Узагальнення рівносильності
Два складні висловлювання F(A1, A2,…, An) і G(A1, A2, …, An), називають еквівалентними (ідентичними, рівносильними), якщо при будь-яких значеннях простих висловлювань A1, A2, …, An відповідні висловлювання F і G є однакові.
Приклад. Маємо складне висловлювання F=¬AVB і складне висловлювання G= A→B.
Побудуємо таблицю істинності для цих складних висловлювань.
Значення F і G збігаються, отже F еквівалентно G.

Нехай ми маємо вісловлювання А→B, (“Якщо Василь мешкає в Куп’янську (А), тоді Василь мешкає в Харківський області (В)"). Введемо два поняття для імплікації: зворотнє висловлювання (конверсія) і протилежне висловлювання:
1. Зворотнє висловлювання або конверсія вихідного є B→A (“Якщо Василь мешкає в Харківський області (B), тоді Василь мешкає у Куп’янську (A)”). Це може бути брехнею.
2. Протилежне висловлювання вихідного є ¬A→¬B ((“Якщо Василь не мешкає в Куп’янську (¬A), тоді Василь не мешкає в Харківський області (¬B)”). Це може бути брехнею.
3. Контрапозицією умовного висловлювання F=A —>B є висловлю-вання G=¬B—>¬A (протилежне його зворотньому).
4. Закон контрапозиції. Висловлювання F=A —>B і G=¬B—>¬A еквівалентні з точки зору логіки.
Приклад:
“Якщо Василь мешкає в Куп’янську, тоді Василь мешкає в Харківський області " теж саме, що “якщо Василь не мешкає в Харківський області, тоді Василь не мешкає в Куп’янську ".
І.4.2 Закон контрапозиції

Course Title
Slide
Таблиця істинності для закону контрапозиції
Значення F і G збігаються при всіх значеннях А і В.
Таким чином доведено закон контрапозиції.
Таблиця істинності — це один із методів доведення.
Побудуємо таблицю істинності для складних висловлювань
G=¬B→A і F=A→B.

Ми можемо довести еквівалентність двох висловлювань F(A, B) і G(A, B) іншим шляхом (методом міркувань):
Для цього необхідно показати, що кожного разу, коли F=1 (істина), G також є істиною; і навпаки, кожного разу, коли G=1 (істина), F також є іс-тиною (іншими словами: якщо F, то G, а якщо G, то F).
Або показати, що кожного разу, коли F=0 (брехня), G також є брех-нею; і навпаки, кожного разу коли G=0 (брехня), F також є брехнею (ін-шими словами: якщо F, то G, а якщо G, то F).
Теорема (закон контрапозиції). Висловлювання G= ¬B→¬A
і F= A→B є еквівалентними.
Доведення
Покажемо, що кожного разу, коли F=0 (брехня), G також є брехнею,
і навпаки, кожного разу, коли G=0 (брехня), F також є брехнею.
Нехай F= A→B=0, тоді, згідно з властивостями імплікації, маємо A=1, B=0, звідси ¬B=1, ¬A=0, таким чином G= ¬B→¬A=0 (згідно з визна-ченням імплікації).
Нехай G= ¬B→¬A=0, тоді, згідно з властивостями імплікації, маємо ¬B=1 і ¬A=0, отже B=0, A=1, таким чином F= A→B=0 (згідно з визначенням імплікації). •

Приклади еквівалентностей, які часто використовуються:
AVB= ¬(¬AΛ¬B) закон Де Морґана для диз’юнкції;
AΛB= ¬(¬AV¬B) закон Де Морґана для кон’юнкції;
¬¬A=A закон подвійного заперечення;
A→B=¬AVB перетворення імплікації на диз’юнкцію;
A~B=¬(A⊕B)= (A→B)&( B→A)= (¬AVB)&(AV¬B);
A⊕B=¬( A~B)= (¬A&B)V(A&¬B).

І.5 Тавтологія, протиріччя, висловлювання, що виконується, (здійсненне висловлювання)
Складне висловлювання називається тавтологією, якщо його значення завжди є істиною (1), незважаючи на істиннісні значення простих висловлювань, із яких воно складається.
Приклад: висловлювання (pV¬p) є тавтологією.
Складне висловлювання називається протиріччям якщо його значення завжди є брехнею (0), незважаючи на істиннісні значення простих висловлювань, із яких воно складається.
Приклад: висловлювання p&¬p є протиріччям.
Складне висловлювання, яке не є ні тавтологією, ні протиріччям називається висловлюванням, що виконується, або здійсненним висловлюванням
Щоб зрозуміти, чи є складне висловлювання тавтологією, достатньо побудувати для нього ТІ.
Скільки рядків буде в такої ТІ, якщо знаємо, зі скількох простих висловлювань воно побудоване?

Можливо також довести методом міркувань, що висловлювання
є тавтологією (або протиріччям).
Доведемо, що F=((A→B) →A) →A є тавтологія.
Нехай F=0, тоді, згідно з властивостями імплікації,
A=0, а (A→B) →A=1 (тільки в цьому випадку F може дорівнювати 0).
Підставимо значення А в першу частину висловлювання F. (0→B) →0.
Згідно з властивостями імплікації (0→B) →0=0, що конфліктує з нашим припущенням (0≠1).
Таким чином, F=((A→B) →A) →A є тавтологія, тобто F≡1.
Для цього застосовують метод “від супротивного”. Тобто припускаємо, що дане висловлювання не тавтологія, і намагаємося знайти комбінації значень простих висловлювань, при яких складне висловлювання буде мати значення 0, тобто “брехня”. Якщо знайдемо, F не є тавтологією, якщо їх немає, то F є тавтологією.
Оскільки протиріччя є запереченням тавтології, для доведення проти-річчя можна застосовувати ті ж методи, що й для доведення тавтології.

І.6 Логічний наслідок
Складне висловлювання G(A1, A2, …, An) називається логічним наслідком складного висловлювання F(A1, A2, …, An), якщо кожного разу, коли F є істина, G також є істина. Інакше кажучи, F успадковує істину G.
Щоб визначити, чи є G логічним наслідком F, потрібно побудувати таблицю істинності висловлювань і порівняти відповідні рядки (F≠G).
Наприклад:
Нехай F = A~B і G = B→A.
У цьому випадку, коли F = “істина”, G=”істина” також.
Таким чином, G є логічним наслідком F.

Приклад.
Маємо висловлювання G=AV(¬B), яке є логічним наслідком висловлювання F=AB V¬A ¬B. Покажемо, що висловлювання H=F→G є тавтологією. Інакше кажучи (AB V¬A ¬B)→(AV(¬B))≡1.
Доведення. Нехай висловлювання Н=(AB V¬A ¬B)→(AV¬B), не є тавтологією, тоді мають бути такі комбінації значень A і B, при яких H=0.
Тоді, за визначенням імплікації, (ABV¬A ¬B)=1, а (AV¬B)=0.
З останнього висловлювання маємо: A=1 і B=0 (за визначенням диз’юнкції).
Якщо підставити знайдені значення A і B до висловлювання F, отримаємо конфлікт із вихідним припущенням ((1&0)V(0&1)=1, що протирічить властивостям кон’юнкції та диз’юнкції), таким чином, вихідна гіпотеза не може бути істиною, отже Н≡1, а G є логічним наслідком F.
Можливо також довести методом міркувань, що одне складне висловлювання є логічним наслідком іншого:
Якщо G є логічним наслідком F, то висловлювання H=F→G має бути тавтологією за визначенням логічного наслідку.

Найвживаніши тавтології
A→A Закон визначення. Кожне висловлювання є логічним наслідком самого себе (якщо щось існує, то воно існує).
¬ (A&¬A) Закон протириччя. A і ¬A не можуть бути істинними одночасно.
AV¬A Закон виключення третьго. Або A є істина, або ¬A є істина.
¬¬A~A Закон подвійного заперечення. Подвійне заперечення висловлювання є тесаме висловлювання.
A→(B→A) Істина з чого завгодно. Якщо A=1, тоді B→A=1, незважаючи на значення В. B→A логічний наслідок A.
¬A→(A→B) Що завгодно з брехні. Якщо A=0, тоді A→ B =1, незважаючи на значення В. A→ B логічний наслідок ¬A.

Найвживаніши тавтології (продовження)
AΛ (A→B) →B Modus ponens. Правило розподілу. Якщо A є істина, а B є логічним наслідком A, тоді B є також істиною.
Приклад. A= “Іде сніг”. A→B=”Якщо зараз іде сніг, тоді зараз хмарно”. AΛ(A→B) →B=”зараз хмарно”.
(A→B) Λ (¬B) →¬A Modus tollens. Правило доказу від супротивного.
Приклад. A→B=” Якщо зараз іде сніг, тоді зараз хмарно”, ¬B=”Зараз не хмарно”, тоді “Зараз не іде сніг”.
9. (A—>B) Λ (B —> C) —>(A —> C) Закон силогізму.
Приклад
Не знайшлося цвяха — підкова відпала, (A1→A2)
Не стало підкови — кобила закульгала, (A2→A3)
Кобила закульгала — командира вбито, — (A3→A4)
Кіннота тікає, — армія розбита, (A4→A5)(A5→A6)
Всіх вбиває ворог на своєму шляху, (A6→A7)
Все тому, що вчасно не знайшлося цвяха! (A1→A7)

Course Title
Slide
Підсумок
Отже ви вивчили:
Рівність висловлювань;
Тавтологію, протиріччя, здійсненне висловлювання;
Логічний наслідок;
Базові логічні закони.