1.6: Тавтології та протиріччя

Тавтології та протиріччя

Більшість тверджень вірні в одних ситуаціях, а помилкові в інших. Але одні твердження вірні у всіх ситуаціях, а інші - помилкові у всіх ситуаціях.

Визначення\(1.6.1\).

• Тавтологія - це твердження Пропозиційної логіки, що вірно у всіх ситуаціях; тобто це вірно для всіх можливих значень його змінних.
• Протиріччя - це твердження логіки пропозиції, яке є помилковим у всіх ситуаціях; тобто воно є хибним для всіх можливих значень його змінних.

Приклад\(1.6.2\).

Твердження\(A \lor B\) є істинним, коли\(A\) є істинним (або\(B\) є істинним), але воно є хибним, коли\(A\) і\(B\) є хибним. Таким чином, твердження іноді є істинним, а іноді помилковим; це ні протиріччя, ні тавтологія.

Приклад\(1.6.3\).

Покажіть, що твердження не\(\bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q)\) є ні тавтологією, ні протиріччям.

Подряпини.

Нам потрібно знайти значення змінних, які роблять твердження істинним, та інші значення, які роблять твердження помилковим.

Легко зробити твердження правдивим, тому що підтекст вірний, коли його висновок вірний, тому нам просто потрібно зробити\(P \Rightarrow \lnot Q\) правду. І ми можемо зробити це правдою, зробивши\(\lnot Q\) правду. Таким чином, ми дозволяємо\(Q\) бути помилковим. Тоді ми можемо дозволити\(P\) і\(R\) бути все, що ми хочемо: це, мабуть, найпростіший, щоб вони обидва були помилковими (так само, як\(Q\)).

Щоб зробити твердження помилковим, нам потрібно зробити його гіпотезу правдивою, а висновок помилковим.

• Почнемо з висновку\(P \Rightarrow \lnot Q\). Щоб зробити це помилковим, нам потрібно зробити\(P\) true і\(\lnot Q\) false. Таким чином, ми дозволимо\(P = \mathsf{T}\) і\(Q = \mathsf{T}\).
• Тепер розглянемо гіпотезу\(P \& (\lnot Q \lor \lnot R)\). На щастя, ми вже вирішили зробити\(P\) правду, але нам також потрібно зробити\(\lnot Q \lor \lnot R\) правду. Оскільки ми вже вирішили зробити\(Q\) правду, нам потрібно зробити\(\lnot R\) правду, так що ми дозволяємо\(R = \mathsf{F}\).

Рішення

Якщо\(P\)\(Q\), і\(R\) всі помилкові, то\[\begin{aligned} \bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q) & \quad = \quad \bigl( \mathsf{F} \& (\lnot \mathsf{F} \lor \lnot \mathsf{F}) \bigr) \Rightarrow (\mathsf{F} \Rightarrow \lnot \mathsf{F}) \\& \quad = \quad \bigl( \mathsf{F} \& (\mathsf{T} \lor \mathsf{T}) \bigr) \Rightarrow (\mathsf{F} \Rightarrow \mathsf{T}) \\& \quad = \quad \bigl( \mathsf{F} \& \mathsf{T} \bigr) \Rightarrow (\mathsf{T}) \\& \quad = \quad \mathsf{F} \Rightarrow \mathsf{T} \\& \quad = \quad \mathsf{T} , \end{aligned}\]
тоді як якщо\(P\) і\(Q\) є істинними, але\(R\) є помилковими, то\[\begin{aligned} \bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q) & \quad = \quad \bigl( \mathsf{T} \& (\lnot \mathsf{T} \lor \lnot \mathsf{F}) \bigr) \Rightarrow (\mathsf{T} \Rightarrow \lnot \mathsf{T}) \\& \quad = \quad \bigl( \mathsf{T} \& (\mathsf{F} \lor \mathsf{T}) \bigr) \Rightarrow (\mathsf{T} \Rightarrow \mathsf{F}) \\& \quad = \quad \bigl( \mathsf{T} \& \mathsf{T} \bigr) \Rightarrow (\mathsf{F}) \\& \quad = \quad \mathsf{T} \Rightarrow \mathsf{F} \\& \quad = \quad \mathsf{F} . \end{aligned}\]
таким чином, твердження іноді істинний і іноді помилковий, тому це ні тавтологія, ні протиріччя.

Вправа\(1.6.4\).

Покажіть, що кожне з наступних тверджень не є ні тавтологією, ні протиріччям.

1. \(A \Rightarrow (A \& B)\)
2. \((A \lor B) \Rightarrow A\)
3. \((A \Leftrightarrow B) \lor (A \& \lnot B)\)
4. \((X \Rightarrow Z) \Rightarrow (Y \Rightarrow Z)\)
5. \(\bigl( P \& \lnot(Q \& R) \bigr) \lor (Q {\Rightarrow} R)\)

Приклад\(1.6.5\) (Law of Excluded Middle).

Легко помітити, що твердження\(A \lor \lnot A\) є істинним, коли\(A\) є істинним, а також коли\(A\) помилковим. Таким чином, твердження вірно для обох можливих значень змінної\(A\), тому це тавтологія:

Рішення

\[\begin{aligned} A \lor \lnot A \text{ is a tautology} \end{aligned}\]

Зауваження\(1.6.6\).

Наведена вище тавтологія називається «Законом виключеного середнього», оскільки вона говорить, що кожне твердження є або істинним, або хибним: немає золотого середини, де твердження частково істинно і частково помилкове.

Приклад\(1.6.7\).

Легко помітити, що твердження\(A \& \lnot A\) є помилковим, коли\(A\) істинно, а також коли\(A\) є помилковим. Таким чином, твердження є помилковим для обох можливих значень змінної\(A\), тому воно є протиріччям:

Рішення

\[\begin{aligned} A \& \lnot A \text{ is a contradiction} \end{aligned}\]

Зауваження\(1.6.8\).

Твердження\(A \lor \lnot A\) і\(A \& \lnot A\) є найважливішими (і найпоширенішими) прикладами тавтологій і протиріч. Однак вони зазвичай виникають з деяким іншим виразом, підключеним до змінної\(A\). Наприклад, дозволяючи\(A\) бути твердженням\((P \lor Q) \Rightarrow R\), ми отримуємо тавтологію,\[\bigl( (P \lor Q) \Rightarrow R \bigr) \lor \lnot \bigl( (P \lor Q) \Rightarrow R \bigr) ,\]
яка є більш складним прикладом Закону виключеного середнього, і ми також отримуємо протиріччя.\[\bigl( (P \lor Q) \Rightarrow R \bigr) \& \lnot \bigl( (P \lor Q) \Rightarrow R \bigr) .\]

Приклад\(1.6.9\).

Ми також можемо навести приклади англійською мовою, а не символами; розглянемо ці твердження:

27. Йде дощ.
28. Або йде дощ, або ні.
29. Йде і дощ, і не дощ.

Для того, щоб дізнатися, чи є Assertion 27 істинним, вам потрібно буде перевірити погоду. Логічно кажучи, це може бути або істинним, або помилковим, тому це ні тавтологія, ні протиріччя.

Твердження 28 буває різним. Не потрібно дивитися на вулицю, щоб знати, що це правда, незалежно від того, яка погода. Так що це тавтологія.

Вам також не потрібно перевіряти погоду, щоб знати про Assertion 29. Він повинен бути помилковим, просто як справа логіки. Тут може бути дощ, а не дощ по всьому місту, або може бути дощ зараз, але припиніть дощ, навіть коли ви читаєте це, але неможливо, щоб це було як дощ, так і не дощ в будь-якій ситуації (в будь-який конкретний час і місце). Таким чином, третє твердження є помилковим у всіх можливих ситуаціях; це протиріччя.

Вправа\(1.6.10\).

Які з перелічених нижче можливих? Для тих, які можливі, наведемо приклад. Для тих, хто не є, поясніть, чому.

1. Дійсний відрахування, висновок якого є протиріччям.
2. Дійсний відрахування, висновок якого є тавтологією.
3. Дійсний вирахування, який має тавтологію як одну зі своїх гіпотез.
4. Дійсний відрахування, який має протиріччя як одну з його гіпотез.
5. Недійсний відрахування, висновок якого є протиріччям.
6. Недійсний відрахування, висновок якого є тавтологією.
7. Недійсний вирахування, який має тавтологію як одну зі своїх гіпотез.
8. Недійсний відрахування, що має протиріччя як одну зі своїх гіпотез.