Логіка висловлювань і доведення: задачі з покроковими розв’язками
Безкоштовні задачі з теми Логіка висловлювань і доведення з рисунками, підказками й повними розв’язками. Щоразу нові значення, трьох рівнів: таблиці істинності, еквівалентності та методи доведення, квантори та міркування.
Вивчайте тему «Логіка висловлювань і доведення» з нуля
1Висловлювання та зв’язники
Висловлювання — це твердження, яке є або істинним, або хибним, наприклад «7 — просте число». Ми позначаємо його літерою, p або q, а його значення істинності — 1 (істина) або 0 (хибність).
Зв’язники будують більші формули з менших:
¬p (не p) змінює значення на протилежне.
p ∧ q (і) дорівнює 1 лише тоді, коли обидва дорівнюють 1.
p ∨ q (або) дорівнює 0 лише тоді, коли обидва дорівнюють 0. Це нерозділювальне «або»: обидва можуть бути істинними.
p → q (якщо p, то q) дорівнює 0 лише тоді, коли p = 1 і q = 0.
p ↔ q (тоді й лише тоді) дорівнює 1, коли p і q мають однакове значення.
Імплікація дивує багатьох студентів: коли p хибне, p → q істинне за будь-якого q. Обіцянка «якщо піде дощ, я візьму парасольку» порушується лише в дощовий день без парасольки.
Самоперевірка p = 0 і q = 1. Яке значення p → q?
0
1
Залежить від контексту
Не визначено
Відповідь: 1. Імплікація хибна лише тоді, коли умова виконується, а висновок ні (p = 1, q = 0). За p = 0 вона істинна за будь-якого q.
2Таблиці істинності
Таблиця істинності перелічує всі комбінації значень істинності змінних. Для n різних змінних маємо 2ⁿ рядків: 4 для двох змінних, 8 для трьох, 16 для чотирьох. Змінна, що трапляється двічі, все одно рахується один раз.
Працюйте зсередини назовні. Дайте кожній підформулі власний стовпець, щоб для кожного нового стовпця було достатньо застосувати один зв’язник до вже наявних стовпців.
Випишіть змінні й усі 2ⁿ комбінацій, починаючи з усіх одиниць.
Додайте стовпець для кожної підформули, починаючи з найвнутрішньої.
Заповніть кожен стовпець за правилом його головного зв’язника.
Зчитайте відповідь з останнього стовпця: порахуйте одиниці або знайдіть потрібний рядок.
Самоперевірка Скільки рядків має таблиця істинності для (p ∧ q) → (r ∨ p)?
16
4
6
8
Відповідь: 8. Формула має три різні змінні, p, q і r, тож 2³ = 8 рядків. Змінна p трапляється двічі, але це одна змінна; 16 було б 2⁴ для чотирьох входжень.
3Розв’язаний приклад
Простежте кожен крок. Спробуйте передбачити наступний, перш ніж його відкрити.
Розв’язаний приклад
У скількох рядках таблиці істинності формула (p → q) ∧ ¬q істинна?
1
Змінні та рядки
Дві змінні, p і q, тож 4 рядки: (1, 1), (1, 0), (0, 1), (0, 0).
2
Стовпець p → q
Він дорівнює 0 лише в рядку p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Стовпець ¬q
¬q: 0, 1, 0, 1
4
Кон’юнкція
Обидва стовпці мають дорівнювати 1. Це трапляється лише в останньому рядку, p = 0 і q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Відповідь
Формула істинна в 1 рядку, де p = 0, q = 0. Саме тому p → q разом із ¬q дають ¬p (modus tollens).
4Еквівалентності та методи доведення
Дві формули еквівалентні (≡), коли їхні стовпці в таблиці істинності однакові. Тавтологія дорівнює 1 у кожному рядку, суперечність — 0 у кожному рядку, а випадкова формула — ні те, ні інше.
Закони, якими ви користуватиметеся найчастіше:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Ці закони лежать в основі методів доведення. Доведення від контрапозиції для p → q доводить натомість ¬q → ¬p, що еквівалентно. Доведення від супротивного припускає p ∧ ¬q — єдиний спосіб, яким імплікація може бути хибною, — і виводить щось неможливе.
Будьте уважні: обернена імплікація q → p та протилежна імплікація ¬p → ¬q не еквівалентні p → q.
Самоперевірка Яка формула еквівалентна ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Відповідь: ¬p ∨ ¬q. За законом де Моргана ∧ стає ∨, а обидві частини заперечуються. ¬p ∧ ¬q — це заперечення p ∨ q, інше твердження: воно хибне, коли істинне рівно одне з p і q, тоді як ¬(p ∧ q) істинне.
5Квантори та коректні міркування
Для змінних над областю ∀x P(x) означає «P виконується для кожного x», а ∃x P(x) — «P виконується принаймні для одного x». Заперечення міняє квантор:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Переносьте заперечення досередини крок за кроком; усередині користуйтеся законами логіки висловлювань. Наприклад, ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): «не кожне P є Q» означає «деяке P не є Q».
Міркування коректне, коли висновок дорівнює 1 у кожному рядку, де всі передумови дорівнюють 1. Класичні коректні форми — modus ponens (p → q, p, отже q), modus tollens (p → q, ¬q, отже ¬p) і гіпотетичний силогізм (p → q, q → r, отже p → r).
Рядок, де всі передумови дорівнюють 1, а висновок 0, — це контрприклад. Підтвердження наслідку (p → q, q, отже p) некоректне: рядок p = 0, q = 1 є контрприкладом.
Самоперевірка Яке заперечення твердження «кожен студент склав», ∀x P(x)?
¬P(x) для одного фіксованого студента x
∀x ¬P(x): жоден студент не склав
∃x P(x): деякий студент склав
∃x ¬P(x): деякий студент не склав
Відповідь: ∃x ¬P(x): деякий студент не склав. Одного студента, який не склав, досить, щоб твердження «кожен студент склав» стало хибним. «Жоден студент не склав» значно сильніше за заперечення.
6Типові помилки
Вважати p → q хибним, коли p хибне. Воно хибне лише за p = 1 і q = 0.
Рахувати повторювану змінну двічі, визначаючи кількість рядків.
Плутати контрапозицію ¬q → ¬p з оберненою імплікацією q → p або протилежною ¬p → ¬q.
Заперечувати ∀x P(x) як ∀x ¬P(x): квантор має змінитися на ∃.
Записувати ¬(p ∧ q) як ¬p ∧ ¬q: закон де Моргана також міняє зв’язник.
Самоперевірка Яке твердження є контрапозицією до «якщо n² парне, то n парне»?
n² парне, а n непарне
Якщо n непарне, то n² непарне
Якщо n парне, то n² парне
Якщо n² непарне, то n непарне
Відповідь: Якщо n непарне, то n² непарне. Поміняйте обидві частини місцями й заперечте обидві: не (n парне) → не (n² парне). «Якщо n парне, то n² парне» — це обернена імплікація; останній варіант — те, що припускають у доведенні від супротивного.
7Як виглядають екзаменаційні запитання
Легкий: таблиці істинності. Ви знаходите кількість рядків, рахуєте рядки, у яких формула істинна, або клікаєте єдиний рядок, що робить формулу істинною чи хибною.
Середній: еквівалентності та методи доведення. Ви визначаєте, чи є формула тавтологією, суперечністю чи випадковою формулою, обираєте еквівалентну формулу або твердження, яке треба довести від контрапозиції чи від супротивного.
Складний: квантори та міркування. Ви заперечуєте твердження з кванторами, обираєте висновок, що випливає з передумов, клікаєте рядок-контрприклад некоректного міркування або рахуєте істинні рядки в таблиці з чотирма змінними.
Рівно один рядок таблиці істинності робить ¬(p ∨ q) → q хибним. Клікніть цей рядок.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Показати підказки
a → b дорівнює 0 лише тоді, коли a = 1 і b = 0. ¬a змінює значення на протилежне. a ∨ b дорівнює 0 лише тоді, коли обидва дорівнюють 0.
Спершу визначте головний зв’язник: якими мають бути його дві частини, щоб уся формула була 0?
Дайте кожній частині власний стовпець: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Показати відповідь і пояснення
Таблиці істинності: формула з n різними змінними має 2ⁿ рядків, по одному для кожної комбінації значень істинності (1 = істина, 0 = хибність). Працюйте зсередини назовні й дайте кожній підформулі власний стовпець. ¬a змінює значення; a ∧ b дорівнює 1 лише тоді, коли обидва дорівнюють 1; a ∨ b дорівнює 0 лише тоді, коли обидва дорівнюють 0; a → b дорівнює 0 лише тоді, коли a = 1 і b = 0; a ↔ b дорівнює 1, коли обидві частини рівні.
Яка формула логічно еквівалентна (b ∧ c) → a? Клікніть її.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Показати підказки
Еквівалентні формули збігаються в кожному рядку таблиці істинності. Один рядок, де вони відрізняються, виключає варіант.
Спробуйте рядок, що робить (b ∧ c) → a рівним 0, і перевірте, які варіанти там теж дорівнюють 0.
Експортація: (a ∧ b) → c ≡ a → (b → c). Обидві дорівнюють 0 лише за a = 1, b = 1 і c = 0.
Показати відповідь і пояснення
Логічна еквівалентність: дві формули еквівалентні (≡), коли мають однакове значення в кожному рядку таблиці істинності. Тавтологія дорівнює 1 у кожному рядку, суперечність — 0 у кожному рядку, а випадкова формула — ні те, ні інше. Корисні закони: закони де Моргана, ¬(a ∧ b) ≡ ¬a ∨ ¬b і ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (контрапозиція); ¬(a → b) ≡ a ∧ ¬b; а також закони дистрибутивності, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Закон
Експортація: (a ∧ b) → c ≡ a → (b → c). Обидві дорівнюють 0 лише за a = 1, b = 1 і c = 0.
(b ∧ c) → a ≡ b → (c → a)
Перевірте за таблицею істинності
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Відповідь
b → (c → a)
Стовпці після риски — це варіанти в показаному порядку.
Приклад 3Складна
Задано передумови (q ∧ p) → r; q; ¬r. Який висновок з них випливає? Клікніть його.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Показати підказки
Висновок випливає, коли він дорівнює 1 у кожному рядку, де всі передумови дорівнюють 1.
Знайдіть рядки, де всі передумови дорівнюють 1, а потім перевірте кожен варіант у цих рядках.
Це стандартне правило: modus tollens із кон’юнкцією.
Показати відповідь і пояснення
Квантори та міркування: ¬∀x P(x) ≡ ∃x ¬P(x) і ¬∃x P(x) ≡ ∀x ¬P(x). Переносьте заперечення досередини, міняйте кожен квантор, який воно проходить, і заперечуйте внутрішню формулу за законами логіки висловлювань, наприклад ¬(a → b) ≡ a ∧ ¬b. Міркування коректне, коли висновок дорівнює 1 у кожному рядку, де всі передумови дорівнюють 1. Один рядок з істинними передумовами та хибним висновком — це контрприклад, який показує, що міркування некоректне.
Рядки, де всі передумови істинні
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Висновок
¬p (modus tollens із кон’юнкцією)
Відповідь
¬p
Запитання й відповіді
Логіка висловлювань і доведення: що це?
Зв’язники будують більші формули з менших:
Імплікація дивує багатьох студентів: коли p хибне, p → q істинне за будь-якого q. Обіцянка «якщо піде дощ, я візьму парасольку» порушується лише в дощовий день без парасольки.
Логіка висловлювань і доведення: як розв’язувати задачі крок за кроком?
Порахуйте різні змінні: таблиця істинності має 2ⁿ рядків, і починається вона з рядка, де всі змінні дорівнюють 1.
Дайте кожній підформулі власний стовпець і заповнюйте стовпці зсередини назовні.
Застосовуйте правило кожного зв’язника: → дорівнює 0 лише для 1 → 0, ↔ дорівнює 1, коли обидві частини збігаються.
Для еквівалентностей порівнюйте останні стовпці рядок за рядком; для міркування дивіться лише на рядки, де кожна передумова дорівнює 1.
Щоб заперечити твердження з квантором, перенесіть ¬ досередини, поміняйте ∀ і ∃ та заперечте внутрішню формулу.
Логіка висловлювань і доведення: які помилки найпоширеніші?
Вважати p → q хибним, коли p хибне.
Рахувати повторювану змінну двічі, визначаючи кількість рядків.
Плутати контрапозицію ¬q → ¬p з оберненою імплікацією q → p.
Заперечувати ∀x P(x) як ∀x ¬P(x) замість ∃x ¬P(x).
Застосовувати закони де Моргана, не помінявши ∧ і ∨.
Логіка висловлювань і доведення: що ви тренуєте?
Легка: таблиці істинності
Середня: еквівалентності та методи доведення
Складна: квантори та міркування
Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь. Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.
Як проходить тренування
Кожна задача має нові значення, тож ви вивчаєте метод, а не відповідь.
Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.
Ваш прогрес, помилки та збережені задачі зберігаються, тож перед іспитом ви зможете все повторити.