Задание: Сколько существует различных наборов значений логических переменных x1, x2,… x5, y1, y2… y5, которые удовлетворяют всем перечисленным ниже условиям?
(¬x1 ˅ y1) ≡ (x2 ˄ ¬y2)
(¬x2 ˅ y2) ≡ (x3 ˄ ¬y3)
(¬x3 ˅ y3) ≡ (x4 ˄ ¬y4)
(¬x4 ˅ y4) ≡ (x5 ˄ ¬y5)
В ответе не нужно перечислять все наборы значений переменных x1, x2,… x5, y1, y2… y5, при которых выполнена данная система равенств. В качестве ответа нужно указать количество таких наборов.
Решение: Обратите внимание на первое уравнение. Скобки в уравнении независимы, то есть в первой скобке свои переменные, во второй — свои. Значит каждую мы можем заменить отдельной переменной.
Но скобки отличаются, нам нужно сделать их похожими.
Обратите внимание на выражение (¬x1 ˅ y1). По закону де Моргана мы можем его преобразовать к виду ¬(x1 ˄ ¬y1), и в этом случае у нас скобки будут уже идентичны:
¬(x1 ˄ ¬y1) ≡ (x2 ˄ ¬y2)
¬(x2 ˄ ¬y2) ≡ (x3 ˄ ¬y3)
¬(x3 ˄ ¬y3) ≡ (x4 ˄ ¬y4)
¬(x4 ˄ ¬y4) ≡ (x5 ˄ ¬y5)
Теперь мы можем заменить каждую скобку другой переменной:
¬a ≡ b
¬b ≡ c
¬c ≡ d
¬d ≡ e
Рассмотрим битовые цепочки для этой системы. В цепочке значений a-e не может быть двух единиц или двух нулей, так как в этом случае система будет ложна. Таким образом, для данной системы существует всего две цепочки решений:
a 0 1
b 1 0
c 0 1
d 1 0
e 0 1
Каждая из переменных a-e представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна в трёх, значит на каждый нуль в цепочке приходится три варианта значений, а на каждую единицу — один. Таким образом, для первой цепочки существует 33 = 27 наборов значений, а для второй — 32 = 9. Общее количество наборов — 27+9 = 36.
Ответ: 36