Задание №2 — Построение таблицы истинности

Решение:

Функция $F = \neg ( x \rightarrow y ) \lor ( x \equiv z ) \lor w$ зависит от четырёх переменных, поэтому её полная таблица истинности содержит $2^4 = 16$ строк, а расставить переменные w, x, y, z по четырём столбцам можно $4! = 24$ способами.

Найдём все наборы, на которых $F = 0$. Таких наборов всего три (значения записаны в «алфавитном» порядке $w,\ x,\ y,\ z$):

Значит, каждая строка фрагмента — это одна из этих трёх строк, только с переставленными столбцами. Но в каком порядке идут сами строки фрагмента, неизвестно, поэтому соответствие «столбец → переменная» надёжнее всего установить перебором всех 24 расстановок.

Отдельно обратим внимание на условие: строки фрагмента различны. Это не украшение: если его не учитывать, подходящих расстановок получается 2. Поэтому проверка расстановки такая: для каждой строки фрагмента находим все её дополнения, дающие нужное значение $F$, и убеждаемся, что из этих дополнений можно выбрать попарно различные строки.

Всё это удобно поручить программе. В Python импликация $a \rightarrow b$ — это a <= b, а эквиваленция $a \equiv b$ — это a == b.

from itertools import product, permutations

def F(w, x, y, z):
    return int(((not (x <= y)) or (x == z)) or w)

# фрагмент таблицы: '.' — незаполненная клетка, второе число — значение F
frag = [('10.1', 0),
        ('..11', 0),
        ('..1.', 0)]

def fits(mask, vals):
    return all(m == '.' or int(m) == v for m, v in zip(mask, vals))

for p in permutations('wxyz'):
    # для каждой строки фрагмента — все её допустимые дополнения
    variants = []
    for mask, f in frag:
        variants.append([vals for vals in product((0, 1), repeat=4)
                         if fits(mask, vals) and F(**dict(zip(p, vals))) == f])
    # строки фрагмента должны быть попарно различны
    for lines in product(*variants):
        if len(set(lines)) == len(lines):
            print(''.join(p))
            break

Программа печатает единственную расстановку — xwzy. Проверим её вручную. Столбцы идут в порядке $x,\ w,\ z,\ y$; восстановим пустые клетки (восстановленные значения выделены курсивом):

Все строки различны, известные клетки совпадают с фрагментом, и функция на них принимает требуемые значения — расстановка найдена верно.

Ответ: xwzy