Задание №2. Восстановление столбцов таблицы истинности
Как определить переменные в столбцах, заполнить пропуски и проверить результат вручную или на Python.
В задании №2 дана логическая формула и таблица без подписей переменных. Нужно определить, какой переменной соответствует каждый столбец. Для этого подходят только те сочетания нулей и единиц, при которых формула даёт указанное в таблице значение F. Сравнение этих сочетаний с заполненными клетками помогает восстановить подписи.
Как читать условие
В каждой строке записан один набор значений переменных. Один столбец относится к одной и той же переменной во всех строках. Порядок букв в формуле может отличаться от порядка столбцов. Столбец F содержит результат вычисления, поэтому в ответ он не входит.
Пустая клетка означает неизвестное значение: 0 или 1. Если по условию строки различны, после заполнения пропусков они должны отличаться хотя бы в одном столбце переменных.
Например, даны строки 0 ? 1 и 0 1 ?, где «?» обозначает пропуск. Если в оба пропуска вписать 1, получатся две одинаковые строки 0 1 1. При требовании различных строк такое заполнение не подходит.
Встречаются и фрагменты с пропусками, и полностью заполненные строки. В условии может быть сказано, что показаны все наборы с F = 0 или все наборы с F = 1. Тогда после определения переменных в столбцах в таблице должны оказаться все найденные по формуле наборы. Порядок строк может отличаться. Если в условии этого нет, подходящих наборов может быть больше, чем показанных строк.
Что следует из значения F
Значение F — результат последней операции в формуле. Например, в F = (x \land y) \lor \neg z последней выполняется ИЛИ. Она соединяет две части: x \land y и \neg z. Отрицание \neg z выполняется раньше ИЛИ, как и операция внутри скобок.
Для краткости эти части можно обозначить буквами A и B: A = x \land y, B = \neg z. Тогда формула записывается как F = A \lor B. Если по условию F = 0, то A \lor B = 0. Операция ИЛИ даёт 0 только при A = 0 и B = 0. В исходной формуле это означает x \land y = 0 и \neg z = 0.
В таблице собраны такие же выводы для разных операций. A и B обозначают части соответствующей формулы: отдельные переменные или целые выражения.
| Формула и значение F | Что из этого следует |
|---|---|
| F = A \lor B F = 0 | A = 0 и B = 0 |
| F = A \land B F = 1 | A = 1 и B = 1 |
| F = A \to B F = 0 | A = 1 и B = 0 |
| F = A \equiv B F = 1 | A и B равны: оба 0 или оба 1 |
| F = A \equiv B F = 0 | A и B различаются |
Если A \lor B = 1, хотя бы одна часть равна 1, но другая может быть и 0, и 1. Если A \land B = 0, хотя бы одна часть равна 0; значение другой части тоже пока неизвестно.
Смысл операций и порядок их выполнения подробно разобраны в статье о логических выражениях.
Разбор фрагмента с пропусками
В задании EGE-02-0001 ↗ дана функция:
F = ((z \to x) \to (x \equiv y)) \lor \neg w.
Показаны три различные строки с F = 0. Для объяснения столбцы временно обозначены номерами, а неизвестные значения знаком «?». В исходном условии эти клетки пусты.
| Строка | 1 | 2 | 3 | 4 | F |
|---|---|---|---|---|---|
| Первая | ? | 0 | 1 | 0 | 0 |
| Вторая | 0 | ? | ? | 0 | 0 |
| Третья | ? | 1 | 1 | ? | 0 |
Две части формулы
Последней выполняется ИЛИ. Её результат F = 0, только если обе соединённые части равны 0:
\underbrace{((z \to x) \to (x \equiv y))}_{0} \lor \underbrace{\neg w}_{0} = 0.
Отрицание \neg w равно 0, когда само w равно 1:
\neg w = 0 \quad\Longrightarrow\quad \boxed{w = 1}.
Это верно для всех трёх строк. Поэтому w соответствует столбцу 3: в каждом из остальных столбцов уже есть хотя бы один ноль. Во второй строке столбца 3 пропущена единица.
Что следует из левой части
Здесь рассматривается внешняя импликация: она соединяет выражения z \to x и x \equiv y. Чтобы её результат был равен 0, первое выражение должно равняться 1, а второе — 0:
\underbrace{(z \to x)}_{1} \to \underbrace{(x \equiv y)}_{0} = 0.
Получены два условия:
(z \to x) = 1, \qquad (x \equiv y) = 0.
Второе условие означает, что x и y различаются: одно равно 0, другое 1. Первое поможет определить z.
Два случая для x
У x всего два значения: 0 и 1. Для каждого можно найти y, а затем проверить оба значения z.
При x = 0 из (x \equiv y) = 0 следует y = 1: значения должны различаться. В условие (z \to x) = 1 вместо x подставляется 0:
(z \to 0) = 1.
Какое значение z подходит:
(0 \to 0) = 1 — подходит;
(1 \to 0) = 0 — не подходит.
Значит, z = 0. С уже найденным w = 1 получается один набор.
При x = 1 из (x \equiv y) = 0 следует y = 0. Теперь условие для z имеет вид:
(z \to 1) = 1.
(0 \to 1) = 1 — подходит;
(1 \to 1) = 1 — тоже подходит.
Здесь допустимы оба значения z, поэтому получаются ещё два набора. Все три набора в порядке x, y, z, w:
| x | y | z | w |
|---|---|---|---|
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
Это все три набора с F = 0. В таблице условия тоже три различные строки, поэтому каждый из этих наборов должен встретиться ровно один раз. Порядок строк при этом может отличаться.
Как определить x и y
В исходной таблице уже определён столбец w и заполнен его пропуск:
| Строка | 1 | 2 | w | 4 | F |
|---|---|---|---|---|---|
| Первая | ? | 0 | 1 | 0 | 0 |
| Вторая | 0 | ? | 1 | 0 | 0 |
| Третья | ? | 1 | 1 | ? | 0 |
Для x, y и z остались столбцы 1, 2 и 4. В первой строке столбцы 2 и 4 содержат нули. Если назначить их переменным x и y, обе переменные окажутся равны 0, а их значения должны различаться. Значит, одна из переменных x и y находится в столбце 1.
Во второй строке нули стоят в столбцах 1 и 4. Поэтому x и y не могут занимать эту пару столбцов: одна из переменных должна быть в столбце 2. Вместе оба вывода означают, что x и y занимают столбцы 1 и 2, а z занимает столбец 4.
Остаются два порядка: xywz и yxwz. При порядке xywz столбец 2 соответствует y. В третьей строке тогда y = 1, значит, x = 0 и z = 0. В порядке столбцов x, y, w, z получится строка (0, 1, 1, 0).
Во второй строке уже стоят x = 0 и z = 0. Значения y и w должны быть равны 1. Получится та же строка (0, 1, 1, 0), хотя по условию строки различны. Поэтому порядок xywz не подходит.
Остаётся порядок yxwz: столбец 1 соответствует y, а столбец 2 — x. Полностью заполненная таблица:
| y | x | w | z | F |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
Числа из условия остались на своих местах, строки различаются, а в каждой строке формула даёт F = 0. Буквы записываются по столбцам слева направо. Ответ: yxwz.
Полностью заполненные строки
Иногда в формуле несколько скобок соединены операцией ИЛИ, а внутри каждой скобки стоит И. Для каждой части удобно отдельно выписать наборы, на которых она равна 1. Например:
F = (\neg x \land \neg y \land z) \lor (\neg x \land y \land z) \lor (x \land y \land z).
Первая часть равна 1 только на наборе (x, y, z) = (0, 0, 1), вторая на (0, 1, 1), третья на (1, 1, 1). Если в таблице приведены все строки с F = 1, в столбце x будет одна единица, в y две, в z три. Это позволяет узнать столбцы по числу единиц. Если показана только часть строк или числа единиц совпадают, одного такого признака недостаточно.
В этом примере каждая скобка задаёт значения всех трёх переменных, поэтому ей соответствует один набор. Если переменная в скобке не встречается, её значение может быть и 0, и 1 — наборов получится несколько. Задание с похожей записью формулы и тремя переменными: EGE-02-0105 ↗.
Другие формулировки условия
- Фрагмент с F = 1 и отрицанием импликации ↗. Последней выполняется операция И. Чтобы получить F = 1, обе части должны равняться 1. Для части \neg (A \to B) это означает, что внутри скобок должен получиться 0: A = 1, B = 0.
- Все строки с F = 0 ↗ и все строки с F = 1 ↗. Таблица уже заполнена, остаётся определить переменные в столбцах. После этого в таблице должны оказаться те же наборы, которые найдены по формуле. Порядок строк может отличаться.
Это несколько вариантов условия. Способ решения зависит и от формулы, и от показанных строк: есть ли пропуски, какое значение F указано и все ли подходящие наборы перечислены.
Проверка перебором на Python
Для четырёх переменных существует 2^4 = 16 наборов. Их можно перебрать и вывести только те, на которых функция принимает нужное значение. Для разобранного примера:
from itertools import product
print('x y z w')
for x, y, z, w in product((0, 1), repeat=4):
a = (not z) or x
b = (x == y)
f = ((not a) or b) or (not w)
if not f:
print(x, y, z, w)product перебирает все 16 сочетаний значений x, y, z и w. В a записывается результат z \to x, в b — результат сравнения x и y, а в f — значение всей формулы. Условие if not f оставляет строки с F = 0.
Программа выведет три набора из таблицы выше в порядке x, y, z, w. Это ещё не ответ: остаётся определить, какому столбцу исходной таблицы соответствует каждая переменная.
Для другой задачи заменяется формула; для отбора F = 1 используется if f. Для трёх переменных нужны repeat=3, три переменные в строке for и соответствующий вывод в обоих print.
Отрицание записывается через not, И через and, ИЛИ через or, эквивалентность через ==, а A \to B через ((not A) or B). Каждая составная часть заключается в скобки: приоритеты операций Python ↗ отличаются от математической записи. Перебор сочетаний описан в справке по itertools.product ↗.
Возможные ловушки
Пустая клетка принята за 0. В EGE-02-0198 ↗ первый столбец переменных полностью пуст. При этом формула заканчивается на \lor \neg w, а во всех строках требуется F = 0. Значит, w = 1: иначе \neg w = 1 сделает всю функцию равной 1. Пустые клетки нельзя заранее заполнять нулями.
Отрицание применено только к первой букве. В EGE-02-0145 ↗ встречается часть \neg(w \to x). Отрицание относится ко всей импликации. Запись (\neg w) \to x означает другое: при w = x = 1 исходная часть даёт 0, а изменённая — 1. Равносильное преобразование имеет вид \neg(w \to x) = w \land \neg x. В EGE-02-0004 ↗ есть другой случай: \neg(\neg z \lor w), где важно сохранить и внешнее, и внутреннее отрицание.
Проверена каждая строка, но не их различие. Неправильный порядок xywz в основном примере ↗ позволяет получить F = 0 в каждой строке, однако две строки совпадут. Поэтому одной проверки значений функции недостаточно. В EGE-02-0003 ↗ требование трёх различных строк также существенно: без него проходит лишний вариант расположения столбцов.
Подсчитаны единицы только в заполненных клетках. В EGE-02-0166 ↗ в первом столбце нет ни одной записанной единицы: все три клетки пусты. После восстановления в нём окажутся три единицы. Поэтому число видимых единиц не определяет итоговое число. Сравнивать количество единиц в найденных наборах и в таблице можно, когда пропусков нет и в условии перечислены все подходящие наборы.
В ответ записан порядок перебора. Порядок x, y, z, w в программе выбран для удобства. В ответе нужны буквы по столбцам исходной таблицы слева направо. Например, в EGE-02-0106 ↗ над столбцами стоят «???», а условие требует записать соответствующие буквы подряд, без разделителей. Это несколько возможных ошибок; список не исчерпывающий.