✖

Приклади з логіки висловлювань

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

Перший приклад

Спробуємо з'ясувати, коли істинна ця формула: ϕ = (p ∧ q) ∨ ¬q. Запишемо в таблицю пропозиційні змінні p і q:

pq11100100

Далі допишемо в таблицю першу частину формули: (p ∧ q), заперечення ¬q і потім цілу формулу:

pqp∧q¬qϕ11100100

Тепер обчислимо значення для третього стовпця, це проста кон'юнкція, а також для заперечення — там просто підставляємо протилежні значення порівняно з тими, що в другому стовпчику:

pqp∧q¬qϕ1110100101000001

Нарешті обчислимо значення в останньому стовпці. Це ціла формула. З огляду на нашу таблицю обчислюємо диз'юнкцію «між третім і четвертим стовпцями». Результат:

pqp∧q¬qϕ11101100110100000011

Другий приклад

Те саме завдання, інша формула: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Бачимо, що у формулі є пропозиційні змінні p і q та їхні заперечення. Тож спершу створимо таблицю з двома змінними та їхніми запереченнями:

pq¬p¬q1100100101100011

Далі додамо формули p ∧ ¬q і ¬p ⇒ q, які ми вже легко можемо обчислити, бо в таблиці є і значення окремих висловлювань, і їхніх заперечень. Таблиця виглядає так:

pq¬p¬q(p∧¬q)(¬p⇒q)110001100111011001001100

Останнім лишилося обчислити цілу формулу, яка є еквіваленцією двох останніх стовпців:

pq¬p¬q(p∧¬q)(¬p⇒q)ϕ1100010100111101100100011001

Третій приклад

Третій приклад буде трохи складнішим: спробуємо три пропозиційні змінні, через що обчислення таблиці ускладниться. Формула виглядатиме так: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Оскільки там три пропозиційні змінні, загальна кількість усіх наборів значень дорівнюватиме восьми:

pqr111110101100011010001000

Далі діятимемо так само, як і в попередньому випадку: кожен стовпчик обчислюємо у всіх восьми рядках. Уся таблиця виглядатиме так:

pqr¬p(p⇒q)(¬p∨q)¬(p⇒q)(r⇔(¬p∨q))ϕ111011010110011000101000100100000111011111010010111000001111010000111000

Четвертий приклад

Цей приклад ми вже задамо не як звичайну формулу, а як текстову задачу. Три друзі хочуть піти на круту вечірку, де роздаватимуть морозиво, але не надто люблять один одного й ставлять умови, за яких підуть на вечірку. Їх звати Максим, Богдан і Петро. Правила такі:

  1. Якщо піде Максим, то піде й Богдан.
  2. На вечірку прийде Петро або, якщо там буде Максим, то Богдан не прийде.
  3. Петро прийде тоді й лише тоді, коли не прийде Максим або не прийде Богдан.

Питання: чи можуть усі прийти на вечірку? Якщо ні, хто може прийти на вечірку й не порушити жодних правил?

Спочатку нам потрібно переписати попередні словесні висловлювання у пропозиційні змінні та формули. Тож позначмо пропозиційні змінні M, B і P (Максим, Богдан, Петро), і кожна завжди означатиме висловлювання на кшталт «Максим піде на вечірку». Перше правило можна переписати так: M ⇒ B — «якщо M, то B», тобто «якщо Максим піде на вечірку, то Богдан піде на вечірку».

Друге правило перепишемо так. Правило починається реченням «На вечірку прийде Петро або…», тож, очевидно, нам потрібна диз'юнкція. Поки що запишемо це: P ∨ … Наступна частина речення каже: «якщо там буде Максим, то Богдан не прийде». Це імплікація, причому в правій частині ще потрібно застосувати заперечення. «Богдан не прийде» = ¬B. Уся імплікація виглядала б так: M ⇒ ¬B. Приєднаємо її до попередньої диз'юнкції: P ∨ (M ⇒ ¬B).

Третє правило перепишемо так: почнемо з «Петро прийде тоді й лише тоді». Це означає еквіваленцію: P ⇔ … Далі маємо «не прийде Максим або не прийде Богдан», що перепишемо так: ¬M ∨ ¬B. Складемо разом: (P ⇔ (¬M ∨ ¬B)).

Тепер усі формули вставимо в таблицю й обчислимо значення:

MBP(M⇒B)(P∨(M⇒¬B))(P⇔(¬M∨¬B))111110110101101011100010011111010110001111000110

Питання було, чи можуть усі троє хлопців піти на вечірку. Відповідь знайдемо в першому рядку. Він відповідає випадку, коли підуть усі хлопці — це сигналізують три одиниці в перших трьох стовпцях. Чи виконано всі умови? Перша — так (четвертий стовпець), друга — теж (п'ятий стовпець), а остання — ні (останній стовпець), там нуль. Це означає, що коли підуть усі троє, третя умова не виконуватиметься.

Тож шукаємо ті рядки, у яких на позиціях, що символізують умови (тобто в останніх трьох стовпцях), стоять самі одиниці. Одиниця означає, що умову виконано. Бачимо, що це трапляється у двох випадках. Коли підуть Богдан і Петро, а Максим ні, і коли піде тільки Петро.

Це можна обчислити й інакше: додати до таблиці формулу ϕ, яка буде кон'юнкцією всіх трьох умов. Тобто виглядатиме так: ϕ = ((M ⇒ B) ∧ (P ∨ (M ⇒ ¬B)) ∧ (P ⇔ (¬M ∨ ¬B))). Це відображає те, що ми хочемо, — щоб були виконані всі формули (всі умови). Тоді таблиця виглядала б так:

MBP(M⇒B)(P∨(M⇒¬B))(P⇔(¬M∨¬B))ϕ11111001101010101011010001000111111010110000111110001100

Кілька прикладів на табличний метод

Оскільки в мене є програма, яка вміє з даної формули автоматично побудувати всю таблицю, її слід гідно використати, тож далі ще кілька розв'язаних формул:

Формула: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Таблиця:

ab(a∧¬b)(b∧(b⇒a))((a∧¬b)∨(b∧(b⇒a)))11011101010100000000

Формула: (a ∨ ¬a) ⇔ (b ∧ ¬b). Таблиця:

ab(a∨¬a)(b∧¬b)((a∨¬a)⇔(b∧¬b))11100101000110000100

Формула: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Таблиця:

ab¬(a∨b)(¬b∧¬a)(¬(a∨b)⇔(¬b∧¬a))11001100010100100111

Формула: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Таблиця:

pqr(q∧r)¬(p∧q)(¬p⇔(q∧r))(p∨¬(p∧q))ϕ1111001111000111101011111000111101111111010010110010101100001011

Формула: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Таблиця:

pqr¬(p⇔¬q)(r⇒¬p)(p∨r)ϕ11110101101111101001010001100110110010010000111110001100

Розділи: Логіка висловлювань, Істинність формул, Приклади з логіки висловлювань