Задание 2. Таблицы истинности

Как узнать: дана логическая функция F от переменных x, y, z, w и фрагмент её таблицы истинности, часть клеток пустая. Нужно понять, какому столбцу соответствует какая переменная, и записать буквы в порядке столбцов.

Решаем перебором: пробуем все способы расставить переменные по столбцам и все способы заполнить пустые клетки. Компьютеру это несколько тысяч проверок, мгновенно.

Сначала на двух переменных

Пусть F = x → y. Полная таблица:

F = 0 только в одной строке: x = 1, y = 0. Пусть в задании дан фрагмент «Перем. 1 = 0, Перем. 2 = 1, F = 0». Если первый столбец это x, получится строка x = 0, y = 1, а там F = 1. Не подходит. Значит, первый столбец это y, второй x, ответ yx.

С четырьмя переменными и пустыми клетками вариантов уже сотни, поэтому проверку поручаем программе. Шаги те же.

Шаг 1. Функция на Python

Переводим запись из задания по таблице из урока про логику: ∧ это and, ∨ это or, ¬ это not, → это <=, ≡ это ==. Пусть F = (x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w.

Шаг 2. Фрагмент таблицы

Записываем строки таблицы, на место пустых клеток ставим переменные a, b, c, d. Их значения переберём через product. Строки таблицы по условию разные, поэтому варианты с одинаковыми строками отбрасываем.

Шаг 3. Перебор

Что здесь происходит:

• permutations("xyzw") перебирает все 24 способа расставить переменные по столбцам.
• dict(zip(p, row)) склеивает порядок переменных со строкой таблицы: например, {"z": 0, "y": 0, "w": 1, "x": 1}. Две звёздочки ** передают такой словарь в функцию по именам параметров.
• all(...) проверяет, что F равна нужному значению во всех строках фрагмента.
• Ответ может найтись при разных заполнениях пустых клеток, поэтому собираем его в множество, а не печатаем сразу.

Ответ в задании пишется буквами подряд, без пробелов: например, zywx.