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

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

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

Спробуємо з'ясувати, коли істинна ця формула: $\phi=(p \wedge q) \vee \neg q$. Запишемо в таблицю пропозиційні змінні p і q:

$$\begin{array}{cc} p&q\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

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

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

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

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 1&1&1&0\\ 1&0&0&1\\ 0&1&0&0\\ 0&0&0&1 \end{array}$$

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

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 1&1&1&0&1\\ 1&0&0&1&1\\ 0&1&0&0&0\\ 0&0&0&1&1 \end{array}$$

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

Те саме завдання, інша формула: $\phi=(p \wedge \neg q) \Leftrightarrow (\neg p \Rightarrow q)$. Бачимо, що у формулі є пропозиційні змінні p і q та їхні заперечення. Тож спершу створимо таблицю з двома змінними та їхніми запереченнями:

$$\begin{array}{cccc} p&q&\neg p&\neg q\\ 1&1&0&0\\ 1&0&0&1\\ 0&1&1&0\\ 0&0&1&1 \end{array}$$

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

$$\begin{array}{cccccc} p&q&\neg p&\neg q&(p\wedge \neg q)&(\neg p\Rightarrow q)\\ 1&1&0&0&0&1\\ 1&0&0&1&1&1\\ 0&1&1&0&0&1\\ 0&0&1&1&0&0 \end{array}$$

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

$$\begin{array}{ccccccc} p&q&\neg p&\neg q&(p\wedge \neg q)&(\neg p\Rightarrow q)&\phi\\ 1&1&0&0&0&1&0\\ 1&0&0&1&1&1&1\\ 0&1&1&0&0&1&0\\ 0&0&1&1&0&0&1 \end{array}$$

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

Третій приклад буде трохи складнішим: спробуємо три пропозиційні змінні, через що обчислення таблиці ускладниться. Формула виглядатиме так: $\phi=(\neg(p\Rightarrow q)) \wedge (r\Leftrightarrow(\neg p \vee q))$.

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

$$\begin{array}{ccc} p&q&r\\ 1&1&1\\ 1&1&0\\ 1&0&1\\ 1&0&0\\ 0&1&1\\ 0&1&0\\ 0&0&1\\ 0&0&0 \end{array}$$

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

$$\begin{array}{ccccccccc} p&q&r&\neg p&(p\Rightarrow q)&(\neg p\vee q)&\neg (p\Rightarrow q)&(r\Leftrightarrow (\neg p\vee q))&\phi\\ 1&1&1&0&1&1&0&1&0\\ 1&1&0&0&1&1&0&0&0\\ 1&0&1&0&0&0&1&0&0\\ 1&0&0&0&0&0&1&1&1\\ 0&1&1&1&1&1&0&1&0\\ 0&1&0&1&1&1&0&0&0\\ 0&0&1&1&1&1&0&1&0\\ 0&0&0&1&1&1&0&0&0 \end{array}$$

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

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

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

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

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

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

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

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

$$\begin{array}{cccccc} M&B&P&(M\Rightarrow B)&(P\vee (M\Rightarrow \neg B))&(P\Leftrightarrow (\neg M\vee \neg B))\\ 1&1&1&1&1&0\\ 1&1&0&1&0&1\\ 1&0&1&0&1&1\\ 1&0&0&0&1&0\\ 0&1&1&1&1&1\\ 0&1&0&1&1&0\\ 0&0&1&1&1&1\\ 0&0&0&1&1&0 \end{array}$$

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

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

Це можна обчислити й інакше: додати до таблиці формулу $\phi$, яка буде кон'юнкцією всіх трьох умов. Тобто виглядатиме так: $\phi = ((M\Rightarrow B)\wedge (P\vee (M\Rightarrow \neg B))\wedge (P\Leftrightarrow (\neg M\vee \neg B)))$. Це відображає те, що ми хочемо, — щоб були виконані всі формули (всі умови). Тоді таблиця виглядала б так:

$$\begin{array}{ccccccc} M&B&P&(M\Rightarrow B)&(P\vee (M\Rightarrow \neg B))&(P\Leftrightarrow (\neg M\vee \neg B))&\phi\\ 1&1&1&1&1&0&0\\ 1&1&0&1&0&1&0\\ 1&0&1&0&1&1&0\\ 1&0&0&0&1&0&0\\ 0&1&1&1&1&1&1\\ 0&1&0&1&1&0&0\\ 0&0&1&1&1&1&1\\ 0&0&0&1&1&0&0 \end{array}$$

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

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

Формула: $((a\wedge \neg b)\vee (b\wedge (b\Rightarrow a)))$. Таблиця:

$$\begin{array}{ccccc} a&b&(a\wedge \neg b)&(b\wedge (b\Rightarrow a))&((a\wedge \neg b)\vee (b\wedge (b\Rightarrow a)))\\ 1&1&0&1&1\\ 1&0&1&0&1\\ 0&1&0&0&0\\ 0&0&0&0&0 \end{array}$$

Формула: $(a\vee \neg a)\Leftrightarrow (b\wedge \neg b)$. Таблиця:

$$\begin{array}{ccccc} a&b&(a\vee \neg a)&(b\wedge \neg b)&((a\vee \neg a)\Leftrightarrow (b\wedge \neg b))\\ 1&1&1&0&0\\ 1&0&1&0&0\\ 0&1&1&0&0\\ 0&0&1&0&0 \end{array}$$

Формула: $\neg (a\vee b)\Leftrightarrow (\neg b\wedge \neg a)$. Таблиця:

$$\begin{array}{ccccc} a&b&\neg (a\vee b)&(\neg b\wedge \neg a)&(\neg (a\vee b)\Leftrightarrow (\neg b\wedge \neg a))\\ 1&1&0&0&1\\ 1&0&0&0&1\\ 0&1&0&0&1\\ 0&0&1&1&1 \end{array}$$

Формула: $\phi=(\neg p \Leftrightarrow (q \wedge r)) \Rightarrow (p \vee \neg (p \wedge q))$. Таблиця:

$$\begin{array}{cccccccc} p&q&r&(q\wedge r)&\neg (p\wedge q)&(\neg p\Leftrightarrow (q\wedge r))&(p\vee \neg (p\wedge q))&\phi\\ 1&1&1&1&0&0&1&1\\ 1&1&0&0&0&1&1&1\\ 1&0&1&0&1&1&1&1\\ 1&0&0&0&1&1&1&1\\ 0&1&1&1&1&1&1&1\\ 0&1&0&0&1&0&1&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&0&1&0&1&1 \end{array}$$

Формула: $\phi=\neg(p\Leftrightarrow \neg q) \wedge (r \Rightarrow \neg p) \wedge (p \vee r)$. Таблиця:

$$\begin{array}{ccccccc} p&q&r&\neg (p\Leftrightarrow \neg q)&(r\Rightarrow \neg p)&(p\vee r)&\phi\\ 1&1&1&1&0&1&0\\ 1&1&0&1&1&1&1\\ 1&0&1&0&0&1&0\\ 1&0&0&0&1&1&0\\ 0&1&1&0&1&1&0\\ 0&1&0&0&1&0&0\\ 0&0&1&1&1&1&1\\ 0&0&0&1&1&0&0 \end{array}$$