Пример 1
Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w. Дан частично заполненный фрагмент таблицы истинности функции F; все строки фрагмента различны.
Определите, какому столбцу таблицы соответствует каждая из переменных x, y, z, w. В ответе напишите буквы в том порядке, в котором идут соответствующие им столбцы.
Показать решение и ответ
1. F — это «ИЛИ» трёх частей, поэтому F = 0, только если все части ложны: ¬w = 0 → w = 1; x ∧ ¬y = 0; y ≡ z = 0 → y ≠ z.
2. Выписываем все наборы с F = 0 (x, y, z, w): (0, 0, 1, 1), (0, 1, 0, 1), (1, 1, 0, 1). Их ровно три — значит, во фрагменте именно они, в каком-то порядке.
3. В этих наборах единиц: w — 3, y — 2, x — 1, z — 1.
4. В столбце 4 видны три единицы — это может быть только w. В столбце 1 видны две единицы — это y (у w все три уже заняты столбцом 4).
5. Во второй строке y = 0 — это набор (0, 0, 1, 1): x = 0, z = 1. Во второй строке столбца 2 стоит 0, значит столбец 2 — x, а столбец 3 — z.
6. Порядок столбцов: y, x, z, w.
Проверка перебором:
from itertools import permutations, product # перестановки столбцов и наборы значений
def f(x, y, z, w): # функция из условия
return (x and not y) or (y == z) or (not w) # ∧ → and, ∨ → or, ≡ → ==, ¬ → not
frag = [(1, None, None, 1), (None, 0, None, 1), (1, None, None, 1)] # фрагмент; None — пустая клетка
def fits(row, pattern): # совпадает ли строка с видимыми клетками
return all(c is None or c == v for v, c in zip(row, pattern))
for p in permutations('xyzw'): # пробуем все порядки переменных в столбцах
zeros = [r for r in product([0, 1], repeat=4) # все наборы значений в порядке столбцов p
if not f(**dict(zip(p, r)))] # оставляем те, где F = 0
for rows in permutations(zeros, 3): # раскладываем три разных набора по строкам
if all(fits(r, fr) for r, fr in zip(rows, frag)): # все видимые клетки совпали
print(''.join(p)) # подходящий порядок столбцов: yxzw
break # этот порядок уже найденОтвет: yxzw
