Тавтологии и противоречия. Таблицы истинности - Построение алгебры высказываний - Краткий теоретический справочник

Информатика и ИКТ подготовка к ЕГЭ

Тавтологии и противоречия. Таблицы истинности - Построение алгебры высказываний - Краткий теоретический справочник

Определение. Формула 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