Задачи по тавтологии
Предварительные требования: Основы суждений, Законы
Предложение . Значение предложения в литературе - это идея, план или предложение, или предложение, истинность или ложность которого можно доказать. То же самое относится и к математическим предложениям. Это повествовательные предложения, которые могут быть истинными или ложными. Предложения являются фундаментальными строительными блоками логики.
Examples:
1. The magnetic lines emerge from the North and merge into South pole.
2. 2 + 1 = 3
3. ‘p’ is a vowel.
All of the above three sentences are proper propositions, where the first two are True and the third one is False.
Тавтология
Пропозициональная логика называется тавтологией, если она всегда истинна, независимо от истинности или ложности атомарных формул. Тавтология всегда «Истина». Чтобы проверить, является ли данная логика тавтологией, мы часто используем метод таблицы истинности. Хотя метод таблицы истинности неэффективен, когда логика содержит ряд атомарных формул.
Example:
Odd number = A
Even number = B
1. If we add one odd number and one even number then we get odd number.
Converting statement-1 into mathematical logic:
A ∧ B ⇒ A
Докажем, что приведенная выше логика является тавтологией. Чтобы построить таблицу истинности, нам нужно преобразовать логические утверждения в клаузальную форму.
Таблица истинности A ∧ B ⇒ A, клаузальная форма: ￢(A ∧ B)∨A
| А | Б | (А ∧ В) | ￢(А ∧ В) | ￢(А ∧ В)∨А |
|---|---|---|---|---|
| Т | Т | Т | Ф | Т |
| Т | Ф | Ф | Ф | Т |
| Ф | Т | Ф | Т | Т |
| Ф | Ф | Ф | Т | Т |
Все записи имеют значение True, независимо от значений True/False атомарных литералов. Итак, это тавтология.
Примеры тавтологии с логическими символами:
- ￢А∨А
- (П∨Q)⇒(П∨Q)
Математическое предложение состояло из логики. Предложение либо истинно, либо ложно. Предложение состоит из математической логики. Различные пропозициональные логики приведены ниже в порядке их приоритета:
- Отрицание (Нет)
- Союз (и)
- Дизъюнкция (или)
- Значение (⇒)
- Эквивалентность (⇔)
Тавтология – Утверждение, которое всегда верно. Таблица истинности оценивается для данного предложения, и если в каждом случае результат истинен, то это предложение называется тавтологией.
Таблица истинности
Это таблица, которая дает результат пропозициональной логики для каждого входного компонента. Результат является двоичным, либо True, либо False для каждой строки входных данных.
Задачи: выяснить, является ли данная логика высказываний тавтологией или нет.
1) П
Таблица истинности:
| п |
|---|
| Т |
| Ф |
Таблица истинности P содержит значение False. Таким образом, это не может быть тавтологией.
2) П⇒П
Нарисуем таблицу истинности для этого предложения.
Значение:
P⇒Q =￢P∨Q
Упрощенное выражение данного предложения: ￢P∨P
Таблица истинности:
| п | ￢П | ￢P∨P |
|---|---|---|
| Т | Ф | Т |
| Ф | Т | Т |
Таблица истинности ￢P∨P состоит только из истинных значений. Следовательно, P⇒P — тавтология.
3) (П ⇒ П) ⇒ П
Нарисуем таблицу истинности для этого предложения.
Значение:
P⇒Q=￢P∨Q
The simplified expression of the given proposition is:
(￢P∨P) ⇒ P
￢(￢P∨P)∨P
(￢(￢P) ∧ ￢P)∨P {By Demorgan’s Law}
(P ∧ ￢P) ∨P
(P ∧ ￢P)= False {Complement laws: – P∧￢P=F }
False ∨ P = P {Absorption law}
Thus, (P ⇒ P) ⇒ P is equivalent to P. We have already solved this in problem-1.
Therefore, this is not a Tautology.
4) (p → q) → [(p → q) → q]
Solving: (p → q) = ￢p∨q {Implication}
Solving: [(p → q) → q]
= [(￢p∨q) → q]
= [￢(￢p∨q)∨q]
= [(￢(￢p)∧￢q)∨q] {Demorgan’s Law}
= [(p∧￢q)∨q] {Involution law}
= [(p∨q)∧(￢q∨q)] {Distributive law}
= [(p∨q)∧T] {Complement law}
= (p∨q) {Absorption law}
Solving (p → q) → [(p → q) → q]
￢(￢p∨q)∨(p∨q)
[￢(￢p)∧(￢q)]∨(p∨q){Demorgan’s Law}
(p∧￢q)∨(p∨q) {Involution law}
Thus, final expression is: (p∧￢q)∨(p∨q)
Таблица истинности:
| п | д | ￢q | (p∧￢q) | (p∨q) | (p∧￢q)∨(p∨q) |
|---|---|---|---|---|---|
| Т | Т | Ф | Ф | Т | Т |
| Т | Ф | Т | Т | Т | Т |
| Ф | Т | Ф | Ф | Т | Т |
| Ф | Ф | Т | Ф | Ф | Ф |
Поскольку в таблице истинности есть запись False, это означает, что это не тавтология .
5) ((П⇒Q)∧П)⇒Q
Solving (P⇒Q): ￢P∨Q
Solving ((P⇒Q)∧P): ((￢P∨Q)∧P)
= (￢P∧P)∨(Q∧P) {Distributive Law}
= (F)∨(Q∧P) {Complement Law}
= (Q∧P) {Absorption Law}
Solving ((P⇒Q)∧P)⇒Q: (Q∧P)⇒Q
= ￢(Q∧P)∨Q
= (￢Q∨￢P)∨Q {Demorgan Law}
= (￢Q∨Q)∨￢P) {Associative Law}
= T∨(￢P) {Complement Law}
= T {Absorption Law}
Final CNF is: True
Here, no need of finding the Truth Table. Given logic is a tautology.