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

Что проверяет номер

Дана функция F от переменных x, y, z, w и несколько строк её таблицы истинности. Столбцы переменных не подписаны, часть клеток пустая. Нужно понять, какой столбец какой переменной соответствует. Ответ это буквы в порядке столбцов, например zxwy.

Вид задачи легко определить по последнему столбцу:

Бывает ещё фрагмент совсем без пустых клеток. Это та же задача, только перебирать заполнение не нужно.

Все виды решаются одним кодом. Компьютер пробует все способы заполнить пустые клетки и все порядки столбцов и печатает тот порядок, который подошёл.

Знаки логики на Python

Сначала условие надо перевести на Python. Таблица короткая, и её стоит выучить.

Запусти и убедись, что <= ведёт себя как импликация. Ноль получается только в строке 1 0:

print('a b  a→b')
for a in 0, 1:
    for b in 0, 1:
        print(a, b, ' ', int(a <= b))

Как записать функцию без ошибок

1. Скопируй выражение из условия к себе в код, чтобы не перепечатывать.
2. Замени знаки на Python, не трогая скобки.
3. Сверь скобки с условием один в один.
4. Перед каждой скобкой с отрицанием оставь not: not (y == z).

Например, F = ((x → y) ∧ ¬z) ∨ (w ≡ x) превращается в такую функцию:

def f(x, y, z, w):
    return ((x <= y) and (not z)) or (w == x)

Посмотри на это сам. Две записи ниже выглядят похоже, но на трёх наборах из восьми расходятся:

from itertools import product

for x, y, z in product([0, 1], repeat=3):
    wrong = x <= y == z         # цепочка: (x <= y) and (y == z)
    right = (x <= y) == z       # то, что написано в условии
    print(x, y, z, int(wrong), int(right), '' if wrong == right else '<- разные')

from itertools import product
k = 0
for x, y, z in product([0, 1], repeat=3):
    if ...:   # запиши функцию вместо многоточия
        k += 1
print(k)

Шаблон: F одинаковая во всех строках

Разберём шаблон на примере. Функция F = ((x → y) ∧ ¬z) ∨ (w ≡ x), дан фрагмент из трёх различных строк. Пустая клетка это значение, которое мы не знаем.

План такой:

1. Пишем функцию f(x, y, z, w).
2. Переписываем таблицу в код. Каждая пустая клетка становится своей переменной: a, b, c, d. Последнее число в строке это значение F.
3. product перебирает, чем заполнить пустые клетки.
4. Проверяем, что строки получились разные. В условии сказано, что строки различны.
5. permutations('xyzw') перебирает, какой столбец какая переменная.
6. Если на всех строках F совпала со значением в таблице, печатаем порядок.

from itertools import product, permutations

def f(x, y, z, w):
    return ((x <= y) and (not z)) or (w == x)

for a, b, c, d in product([0, 1], repeat=4):      # 4 пустые клетки
    t = (
        (1, 0, a, 0, 0),      # последнее число — значение F
        (b, 1, 0, c, 0),
        (0, d, 0, 0, 0),
    )
    if len(t) == len(set(t)):                     # строки должны быть разными
        for p in permutations('xyzw'):            # p — порядок столбцов, например ('z','x','w','y')
            if all(f(**dict(zip(p, line))) == line[-1] for line in t):
                print(''.join(p))

Ответ zxwy. Он напечатается два раза, потому что подходит при двух разных заполнениях пустых клеток. Это нормально. Вот если напечатались разные порядки, то ошибка в функции или таблице.

Что происходит в длинной строке

Строка с all выглядит страшно, но разбирается по кускам:

• zip(p, line) склеивает буквы порядка с числами строки: ('z', 1), ('x', 0) и так далее. Последнее число, значение F, отбрасывается само, потому что букв всего четыре.
• dict(...) превращает пары в словарь {'z': 1, 'x': 0, …}.
• f(**словарь) подставляет значения по именам: f(z=1, x=0, …).
• all(...) даёт True, только если условие выполнилось на всех строках.

Если так понятнее, ту же проверку можно написать длиннее, без ** и all. Ответ будет тот же:

for p in permutations('xyzw'):
    ok = True
    for line in t:
        v = dict(zip(p, line))                    # {'z': 1, 'x': 0, ...}
        if f(v['x'], v['y'], v['z'], v['w']) != line[-1]:
            ok = False
    if ok:
        print(''.join(p))

Сколько переменных в product, столько и пустых клеток. Если пустых клеток нет, product и проверка различия не нужны, остаётся только цикл по permutations.

Разные значения F и две функции

В столбце F и 0, и 1

Код менять не надо. Мы и так сравниваем F со значением своей строки, line[-1], а не с константой. Поэтому шаблон работает сразу. Попробуй на задаче.

from itertools import product, permutations
def f(x, y, z, w):
    return ...   # запиши функцию
for a, b, c in product([0, 1], repeat=3):   # 3 пустые клетки
    t = (
        (0, 0, a, 1, 1),
        (1, b, 1, 1, 0),
        (1, 0, c, 1, 1),
    )
    if len(t) == len(set(t)):
        for p in permutations('xyzw'):
            if all(f(**dict(zip(p, line))) == line[-1] for line in t):
                print(''.join(p))

Две функции в одной таблице

Справа два столбца значений, F1 и F2. Пишем две функции и проверяем обе. Значение F1 теперь предпоследнее в строке, line[-2], а F2 последнее, line[-1]. Лишние числа zip опять отбросит сам.

from itertools import product, permutations

def f1(x, y, z, w):
    return (x <= y) or (z and (not w))

def f2(x, y, z, w):
    return (y == w) <= (x or z)

for a, b, c, d in product([0, 1], repeat=4):
    t = (
        (1, a, 0, b, 1, 0),   # два последних числа — F1 и F2
        (0, 0, c, 0, 1, 0),
        (1, 1, 0, d, 0, 1),
    )
    if len(t) == len(set(t)):
        for p in permutations('xyzw'):
            if all(f1(**dict(zip(p, line))) == line[-2] and
                   f2(**dict(zip(p, line))) == line[-1] for line in t):
                print(''.join(p))

Ответ wxzy.

Как это решают руками

На экзамене руками долго, основной способ это код. Но идею стоит знать: она помогает понять, что вообще делает перебор, и проверить ответ.

Руками ищут вынужденные значения:

• если F = 0, а F это дизъюнкция (∨) нескольких скобок, то каждая скобка равна 0;
• если F = 1, а F это конъюнкция (∧), то каждая скобка равна 1.

Из этого получаются условия вида «x и w в каждой строке разные» или «z везде равна 1». Дальше ищем столбцы, которые подходят под эти условия во всех строках, и начинаем со строк, где пустых клеток меньше всего.

Пример из раздела 3 начинается так. F = 0, значит, (w ≡ x) = 0, и в каждой строке x и w противоположны. В третьей строке нули стоят в первом, третьем и четвёртом столбцах. Значит, одна из букв x и w точно во втором столбце.

Можно ещё вывести все строки, где F = 0, и сравнить их с фрагментом глазами:

from itertools import product

print('x y z w')
for x, y, z, w in product([0, 1], repeat=4):
    if not (((x <= y) and (not z)) or (w == x)):
        print(x, y, z, w)

Ловушки перед экзаменом