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

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

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

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

				F
1		1	1	0
		0	0	1
	0	0		1

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

		$\neg x \lor y$
0	1	0

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

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

ywzx

Пояснение

Решение:

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

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

w	x	y	z	F
0	1	1	0	1
1	0	1	0	1
1	0	1	1	1
1	1	1	1	1

Значит, каждая строка фрагмента со значением $F = 1$ — это одна из этих четырёх строк, только с переставленными столбцами. А строка со значением $F = 0$ , наоборот, не должна совпадать ни с одной из них.

Отдельно обратим внимание на условие: строки фрагмента различны. Поэтому проверка расстановки такая: для каждой строки фрагмента находим все её дополнения, дающие нужное значение $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 (y <= (not (z <= w)))) and ((not z) <= ((not w) == x)))

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

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

Программа печатает единственную расстановку — ywzx. Проверим её вручную. Столбцы идут в порядке

y,\ w,\ z,\ x

; восстановим пустые клетки (восстановленные значения выделены курсивом):

y	w	z	x	F
1	0	1	1	0
1	1	0	0	1
1	0	0	1	1

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

Ответ: ywzx