Операции над высказываниями и предикатами. Таблицы истинности
п.1. Отрицание
Обозначение отрицания \(\overline{A}\) читается «не A».
Если записать эту операцию с помощью таблицы истинности, где 0 обозначает «ложь», а 1 – «истина», получаем:
0
1
1
0
Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».
п.2. Конъюнкция
Конъюнкция является логическим умножением.
Обозначение конъюнкции A ∧ B, читается «А и В». Таблица истинности:
0
0
0
0
1
0
1
0
0
1
1
1
С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).
С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.
Например, запись \(\mathrm{(x^2-1\geq 0)\wedge \left(x\gt \frac12\right)}\) аналогична системе $$ \left\{ \begin{array}{ l } \mathrm{x^2-1\geq 0} & \\ \mathrm{x\gt\frac12} & \end{array}\right. \Leftrightarrow x\geq 1 $$
п.3. Дизъюнкция
Дизъюнкция является логическим сложением.
Обозначение дизъюнкции A ∨ B, читается «А или В». Таблица истинности:
0
0
0
0
1
1
1
0
1
1
1
1
С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).
С точки зрения записи условий, дизъюнкция аналогична совокупности с квадратной скобкой. Например, запись \(\mathrm{(x^2-1\geq 0)\vee \left(x\gt \frac12\right)}\) аналогична совокупности $$ \left[ \begin{array}{ l } \mathrm{x^2-1\geq 0} & \\ \mathrm{x\gt\frac12} & \end{array}\right. \Leftrightarrow x\leq -1 \cup x\gt\frac12 $$
п.4. Импликация
Обозначение импликации A → B, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:
0
0
1
0
1
1
1
0
0
1
1
1
п.5. Эквиваленция
Обозначение эквиваленции A ↔ B, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:
0
0
1
0
1
0
1
0
0
1
1
1
п.6. Законы де Моргана
Докажем эквивалентность с помощью таблиц истинности:
|
A
B
A ∧ B
\(\mathrm{\overline{A\wedge B}}\)
0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 |
A
B
\(\mathrm{\overline{A}}\)
\(\mathrm{\overline{B}}\)
\(\mathrm{\overline{A}\vee\overline{B}}\)
0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 |
Мы видим, что итоговые столбцы слева и справа полностью совпадают.
Значит, высказывания эквивалентны.
Докажем эквивалентность с помощью таблиц истинности:
|
A
B
A ∨ B
\(\mathrm{\overline{A\vee B}}\)
0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 |
A
B
\(\mathrm{\overline{A}}\)
\(\mathrm{\overline{B}}\)
\(\mathrm{\overline{A}\wedge\overline{B}}\)
0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 |
Высказывания слева и справа эквивалентны.
Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A~B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».
п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности
Шаг 1. Построить таблицу истинности для формулы слева от знака «=».
Шаг 2. Построить таблицу истинности для формулы справа от знака «=».
Шаг 3. Сравнить итоговые столбцы двух таблиц. Если столбцы полностью совпадают, формулы эквивалентны.
Например:
Докажем следующее свойство:
|
A
B
A → B
\(\mathrm{\overline{A\rightarrow B}}\)
0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 |
A
B
\(\mathrm{\overline{B}}\)
\(\mathrm{A\wedge\overline{B}}\)
0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 |
Столбцы совпадают. Значит, формулы эквивалентны.
Что и требовалось доказать.
п.8. Тавтология
Таблица истинности для тавтологии даёт итоговый столбец, заполненный только единицами.
Например: \(\mathrm{A \vee \overline{A}}\)
0
1
1
1
0
1
«Быть иль не быть» - это тавтология.
п.9. Примеры
Пример 1. Для формулы P(x, y)=(∃x∀y)(A(x,y)∧B(x,y))
сформулируйте предложения A и B, при которых:
а) формула всегда истинна; б) формула всегда ложна.
a) A(x,y): квадрат числа x больше y
B(x,y): куб числа x больше y
Пусть x = |y + 1|. Тогда x2 = (y + 1)2 > y – истинно ∀y
x3 = |y + 1|3 > y – ∀y
Таким образом, мы нашли x, при котором A(x,y) ∧ B(x,y) = 1 для любого y, т.е.
P(x,y) = 1.
б) A(x,y): x больше y
B(x,y): x меньше y
A(x,y)∧B(x,y) = 0 – ложно для любого y, т.к. не существует x, который одновременно был бы больше и меньше y.
P(x,y) = 0.
Пример 2. Составьте таблицу истинности для формулы \(P=(\overline{A}\rightarrow B)\vee (A\rightarrow \overline{B})\).
Является ли данная формула тавтологией?
0
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
0
1
Это – тавтология.
Пример 3*. Составьте таблицу истинности для формулы
P = (A → B) ∧ (B → C) → (A → C)
Является ли данная формула тавтологией?
∧
(B → C)
0
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
Это – тавтология.
