Задание посвящено построению таблиц истинности и основам алгебры логики.
Логические операции
Вспомним основные понятия. Логическое высказывание — это утверждение, которое может быть истинным (1) или ложным (0). Рассмотрим основные логические операции:
- Конъюнкция (логическое умножение): Обозначается символами ∧ или «∩».
- 0 ∧ 0 = 0
- 0 ∧ 1 = 0
- 1 ∧ 0 = 0
- 1 ∧ 1 = 1
Результат истинен только если все входящие высказывания истинны.
- Дизъюнкция (логическое сложение): Обозначается символами ∨ или «+».
- 0 ∨ 0 = 0
- 0 ∨ 1 = 1
- 1 ∨ 0 = 1
- 1 ∨ 1 = 1
Результат ложен только если все входящие высказывания ложны.
- Инверсия (логическое отрицание): Обозначается символом ¬ или чертой сверху.
- ¬0 = 1
- ¬1 = 0
Инверсия меняет значение высказывания на противоположное.
- Импликация (логическое следование): Обозначается символом →.
- 0 → 0 = 1
- 0 → 1 = 1
- 1 → 0 = 0
- 1 → 1 = 1
Результат ложен только тогда, когда из истинного высказывания следует ложное.
- Эквивалентность (тождественность): Обозначается символами ↔︎ или ≡.
- 0 ↔︎ 0 = 1
- 0 ↔︎ 1 = 0
- 1 ↔︎ 0 = 0
- 1 ↔︎ 1 = 1
Результат истинен, если оба высказывания имеют одинаковое значение.
Практическое задание
Условие: Миша заполнял таблицу истинности функции x ∧ ¬y ∨ (x ↔︎ z) ∨ ¬w. Заполнен фрагмент из трех строк. Не указано, какому столбцу соответствует каждая переменная (w, x, y, z). Определите соответствие столбцов переменным. В ответе запишите буквы x, w, y, z в порядке соответствия столбцам.
Решение
Выражение во всех трех строках равно нулю, значит, оно всегда ложно. Между всеми высказываниями стоит дизъюнкция. По законам алгебры логики сложение дает ноль только если все слагаемые равны нулю.
- Определение переменной w: Переменная w находится под знаком инверсии (¬w). Для того чтобы ¬w равнялось нулю, w должна равняться единице. Смотрим столбец, где нет ни одного нуля — это второй столбец. Таким образом, w соответствует второму столбцу.
- Определение переменных x, y, z: Для получения нуля в первой скобке (x ∧ ¬y) необходимо, чтобы либо x равнялось нулю, либо ¬y равнялось нулю (то есть y равнялось единице). Для второй скобки (x ↔︎ z), чтобы получить ноль, x и z должны быть различными.
Проведем моделирование:
- Если x = 0, то y может быть как 0, так и 1. z должно быть равно 1.
- Если x = 1, то y = 1. z должно быть равно 0.
Сравнивая с таблицей, видим, что столбец с двумя нулями соответствует x. Строка с x = 1, y = 1, z = 0 совпадает со второй строкой таблицы. Следовательно, y соответствует третьему столбцу, а z — первому.
Проверка: Подставим найденные соответствия в выражение и проверим, что результат будет всегда нуль.
Ответ
xwzy