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

#69796Задание №2ФИПИ

Алгебра логики

Миша заполнял таблицу истинности функции F
$\neg ( x \rightarrow у ) \lor \neg z \lor w ,$
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, х, у, z:

			F
	0	1	0
	0	0	0
0	0	0	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, х, у, z. В ответе напишите буквы w, х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением $\neg x \lor y ,$ зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		F
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу - переменная х. В ответе следует написать: yx.

Правильный ответ

zywx

Пояснение

Решение:

Функция $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