Информатика и ИКТ подготовка к ЕГЭ
Тавтологии и противоречия. Таблицы истинности - Построение алгебры высказываний - Краткий теоретический справочник
Определение. Формула f называется тождественно истинной (тождественно ложной), или тавтологией (противоречием), и обозначается f ≡ 1 (f ≡ 0), если во всех логических возможностях она принимает одно и то же значение, равное 1 (равное 0). Запись │= f означает, что f — тавтология.
Для любых двух формул f и g истинно утверждение
Определение. Таблица, в которой приведён перечень всех логических возможностей формулы f (общих логических возможностей формул f1,...,fn) вместе с указанием значений f (значенийf1,...,fn) в каждой логической возможности (общей логической возможности), называется таблицей истинности формулы f (формул f1,...,fn).
Пример. Составьте таблицу истинности для формулы
Решение.
X |
Y |
Z |
Z ^ X |
Y → Z ^ X |
(Y → Z ^ X) → Z |
¬ ((Y → Z ^ X) → Z) |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |