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

Решение:

Функция $F = \neg(x \rightarrow y) \lor \neg z \lor w$ — это дизъюнкция, поэтому удобно смотреть, когда она равна 0: все три слагаемых должны быть нулями, то есть одновременно $x \rightarrow y = 1$, $z = 1$ и $w = 0$.

Во всех трёх строках фрагмента $F = 0$, значит, в каждой из них $z = 1$, $w = 0$ и не бывает $x = 1$ при $y = 0$.

Шаг 1. Находим столбец z. В столбце переменной $z$ должны стоять единицы во всех трёх строках. Третий столбец во всех строках равен 0 — не подходит. Четвёртый столбец равен 1, 0, 0 — не подходит. Второй столбец в третьей строке равен 0 — не подходит. Остаётся первый столбец: $z$ — первый столбец (и в нём всюду единицы).

Шаг 2. Находим столбец w. В столбце $w$ должны стоять нули во всех трёх строках. Четвёртый столбец содержит единицу, поэтому $w$ — это либо второй, либо третий столбец.

Шаг 3. Отбрасываем лишние варианты. Здесь важно, что Миша выписал три различные строки таблицы.

• Пусть $w$ — второй столбец. Тогда $x$ и $y$ стоят в третьем и четвёртом столбцах. Если $x$ — четвёртый, то в первой строке $x = 1$, а $y$ — третий столбец, там 0; получается $x \rightarrow y = 0$ и $F = 1$ — противоречие. Если же $x$ — третий столбец, а $y$ — четвёртый, то во второй и третьей строках все четыре значения оказываются равны 1, 0, 0, 0, то есть строки совпадают — тоже противоречие.
• Значит, $w$ — третий столбец, а $x$ и $y$ стоят во втором и четвёртом. Если $x$ — второй, а $y$ — четвёртый, то во второй строке $y = 0$, поэтому $x = 0$; в третьей строке тоже $y = 0$, а $x$ во втором столбце задан нулём. Обе строки снова превращаются в 1, 0, 0, 0 — совпадение, чего быть не может.

Остаётся единственный вариант: $x$ — четвёртый столбец, $y$ — второй. Проверим его: в первой строке $z = 1$, $x = 1$, значит, $y = 1$; во второй $x = 0$, и $y$ можно взять равным 1; в третьей $x = 0$, $y = 0$. Получаются три различные строки, и во всех $F = 0$.

Итого порядок столбцов: $z$, $y$, $w$, $x$.

Тот же ответ даёт короткая программа, перебирающая все 24 расстановки переменных по столбцам:

from itertools import permutations, product

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

frag = [((None, None, 0, 1), 0),
        ((None, None, 0, 0), 0),
        ((None, 0, 0, 0), 0)]

def fits(pat, row):
    return all(p is None or p == v for p, v in zip(pat, row))

for p in permutations('xyzw'):
    table = []
    for vals in product([0, 1], repeat=4):
        d = dict(zip(p, vals))
        table.append((vals, int(bool(F(d['x'], d['y'], d['z'], d['w'])))))
    for tri in permutations(table, 3):
        if all(fits(pat, row) and val == f
               for (pat, val), (row, f) in zip(frag, tri)):
            print(''.join(p))
            break

Ответ: zywx