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

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

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

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

				F
		0	0	1
	0	0		1
1		1	1	0

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

		F
0	1	0

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

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

xzyw

Пояснение

Решение:

Функция $F = x \land (y \rightarrow z) \land (\neg y \rightarrow (\neg z \equiv w))$ — это конъюнкция, поэтому разберём, когда она равна 1. Прежде всего обязательно $x = 1$ . Дальше два случая:

если $y = 1$ , то из $y \rightarrow z$ следует $z = 1$ , а третья скобка выполняется автоматически (её посылка $\neg y = 0$ );
если $y = 0$ , то вторая скобка истинна, а третья требует $w = \neg z$ , то есть $z$ и $w$ должны быть различны.

Значит, единица получается ровно в четырёх наборах $(x, y, z, w)$ : $(1,1,1,0)$ , $(1,1,1,1)$ , $(1,0,0,1)$ , $(1,0,1,0)$ .

Шаг 1. Находим столбец x. В первых двух строках фрагмента $F = 1$ , значит, в них $x = 1$ . В первой строке нули стоят в столбцах 3 и 4 — там $x$ стоять не может. Во второй строке нули стоят в столбцах 2 и 3 — там $x$ тоже стоять не может. Остаётся единственный вариант: $x$ — первый столбец.

Шаг 2. Находим столбец y. В первой строке фрагмента среди $y, z, w$ уже видно два нуля (столбцы 3 и 4), во второй — тоже два (столбцы 2 и 3). Из четырёх «единичных» наборов два нуля среди $y, z, w$ есть только у $(1,0,0,1)$ и $(1,0,1,0)$ . В первой строке фрагмента второй столбец равен 1, а во второй строке он равен 0, так что это разные наборы — то есть первая и вторая строки в каком-то порядке и есть эти два набора.

В обоих наборах $y = 0$ , а $z$ и $w$ принимают в них разные значения. Столбец 3 равен нулю в обеих строках, поэтому $y$ — третий столбец.

Шаг 3. Различаем z и w. Они стоят во втором и четвёртом столбцах. Используем третью строку фрагмента: там первый столбец равен 1 ( $x = 1$ ), третий равен 1 ( $y = 1$ ), четвёртый равен 1, и при этом $F = 0$ . Но при $x = 1$ и $y = 1$ функция равна нулю только если $z = 0$ . Значит, в четвёртом столбце стоит не $z$ , а $w$ ; тогда $z$ — второй столбец.

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

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

from itertools import permutations, product

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

frag = [((None, None, 0, 0), 1),
        ((None, 0, 0, None), 1),
        ((1, None, 1, 1), 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

Ответ: xzyw