Сколько существует различных наборов значений логических переменных x1, x2,… x9, y1, y2… y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬(x2 ≡ y2)) ≡ (x3 ≡ y3)

...

(¬(x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все наборы значений переменных x1, x2,… x9, y1, y2… y9, при которых выполнена данная система равенств. В качестве ответа нужно указать количество таких наборов.

Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.

В решении задания есть видеоразбор

Рассмотрим первое уравнение.

(¬(x1 ≡ y1)) ≡ (x2 ≡ y2)

В скобках у нас одинаковые выражения, отличаются только номера переменных. При этом скобки не связаны между собой, то есть в (x1 ≡ y1) и (x2 ≡ y2) разные переменные. Таким образом. мы можем заменить скобки переменными a, b, c и т.д:

¬A ≡ B
¬B ≡ C
¬C ≡ D
¬D ≡ E
¬E ≡ F
¬F ≡ G
¬G ≡ H
¬H ≡ I

Построим таблицу битовых цепочек для этой системы. Чтобы вся система была истинна, каждое уравнение должно быть истинным. Уравнение вида ¬A ≡ B может быть истинно только в том случае, если значения переменных A и B разные, то есть в цепочке не могут быть два рядом стоящих нуля или две рядом стоящих единицы. Выходит, для данной системы существует только две цепочки решений:

A 0 1
B 1 0
C 0 1
D 1 0
E 0 1
F 1 0
G 0 1
H 1 0
I 0 1

Теперь вернёмся к основной системе. Переменными A-J мы заменили скобки с тождеством внутри. Тождество может быть истинно в двух случаях, и ложно в двух случаях, то есть на каждый 0 в цепочках, которые мы построили, существует два набора значений, и на каждую 1 тоже два набора. Выходит, что на каждую цепочку приходится 2⁹ = 512 возможных решений.

Всего у нас две цепочки, то есть общее количество равно 512*2 = 1024

Ответ: 1024

Видеоразбор задания: