Таблицы истинности

В задании 2 дана логическая формула и несколько строк её таблицы истинности. Над столбцами не написано, какой столбец какой переменной принадлежит, а часть клеток пустая. Вот задача, которую мы будем решать всю тему: формула F = ¬x ∧ (y ∨ z) ∧ (z → w), а ниже — три разные строки её таблицы, в каждой F = 1.

Нужно определить, какой переменной соответствует каждый столбец, и записать буквы в порядке столбцов слева направо — например, zyxw. В таблицах истинности 1 означает истину, 0 — ложь. Пустая клетка — не третье значение: в ней стоит 0 или 1, просто его не показали.

Для этого нужны три умения — каждому посвящена своя подтема, а в четвёртой те же наборы получим программой. У каждой подтемы своя страница, идём по ним по порядку:

1. Логические операции — ты сейчас здесь: когда истинна каждая операция.
2. Формула и её таблица — при каких значениях переменных формула равна 1.
3. Фрагмент и порядок столбцов — как подобрать столбцы, и ответ задачи темы.
4. Решение программой — те же наборы — программой на Python.

Отрицание меняет значение на противоположное. Записывается ¬A и читается «не A»: если A — «число чётное», то ¬A — «число нечётное». Два отрицания возвращают исходное значение: ¬¬A = A.

Скобки показывают, что именно отрицается. В ¬(x ∧ y) сначала вычисляют x ∧ y, а потом меняют результат; в ¬x ∧ y меняют только x. При x = 0, y = 0 первое выражение равно 1, второе — 0. Иногда отрицание пишут чертой сверху — тогда смотри, над какой частью она проходит.

И (конъюнкция, A ∧ B) истинно, только когда истинны обе части. Например, для прохода нужны и пропуск, и разрешение: без любого из них пройти нельзя.

Поэтому из A ∧ B = 1 следует сразу A = 1 и B = 1, а из A ∧ B = 0 — только то, что хотя бы одна часть равна 0. Частей может быть больше: A ∧ B ∧ C = 1, только если все три равны 1.

ИЛИ (дизъюнкция, A ∨ B) истинно, когда истинна хотя бы одна часть. Условие «предъяви паспорт или загранпаспорт» выполнено, если есть хотя бы один документ, — и тем более если есть оба.

В речи «или» иногда значит «одно из двух, но не оба»; в логике две единицы тоже дают 1. Из A ∨ B = 0 следует, что обе части равны 0, а из A ∨ B = 1 — только то, что хотя бы одна равна 1. A ∨ B ∨ C = 0, только если все три равны 0.

Импликация A → B ложна в единственном случае: A = 1, B = 0. Её читают «если A, то B»: A — условие, B — требование. Возьмём правило «если участник набрал проходной балл, его допускают к следующему этапу»: A — балл набран, B — допуск.

Запомни одну запрещённую пару 1 → 0 — остальные три дают 1. У стрелки есть направление: A → B и B → A — разные выражения. При A = 0, B = 1 первое равно 1, а второе — 0.

Равнозначность A ≡ B истинна, когда значения одинаковы — два нуля тоже. Её ещё называют эквивалентностью. Результат 1 означает «одинаковы», 0 — «различаются».

Из A ≡ B = 1 нельзя заключить, что A = B = 1: подходит и пара 0, 0. Все четыре операции с двумя частями — на одной схеме:

• ¬Aменяет 0 на 1 и 1 на 0; у ¬(…) сначала скобка
• A ∧ B1 только при двух единицах
• A ∨ B0 только при двух нулях
• A → B0 только при 1 → 0; направление не меняют
• A ≡ B1, когда значения одинаковы, 0 ≡ 0 тоже
• Пустая клеткаскрывает 0 или 1