РЕШУ ЕГЭ — информатика

Задания

Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, у1, у2, уЗ, у4, у5, которые удовлетворяют всем перечисленным ниже условиям?

$левая круглая скобка x1\to x2 правая круглая скобка \wedge левая круглая скобка x2\to x3 правая круглая скобка \wedge левая круглая скобка x3\to x4 правая круглая скобка \wedge левая круглая скобка x4\to x5 правая круглая скобка =1$

$левая круглая скобка y2\to y1 правая круглая скобка \wedge левая круглая скобка y3\to y2 правая круглая скобка \wedge левая круглая скобка y4\to y3 правая круглая скобка \wedge левая круглая скобка y5\to y4 правая круглая скобка =1$

$x1\vee y1=1$

В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, у1, у2, уЗ, у4, у5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Заметим, что первые два уравнения связаны друг с другом только через третье.

Найдем количество решений первого уравнения. Каждая из переменных x1, ... , x5 может принимать только два значения. Импликация ложна только тогда, когда из истины следует ложь. Если записать значения переменных подряд, то можно увидеть, что для того, чтобы равенство выполнялось, необходимо, чтобы после "1" никогда не стоял "0". Следовательно, получаем такие решения: (x1,x2,x3,x4,x5) = 00000, 00001, 00011, 00111, 01111, 11111.

Во втором уравнении необходимо, чтобы после "0" никогда не стояла "1". Следовательно, получаем такие решения: (y1,y2,y3,y4,y5) = 00000, 10000, 11000, 11100, 11110, 11111. Таким образом, система из двух уравнений имеет 6·6  =  36 решений: для каждого набора переменных y существует 6 наборов переменных x.

00000	10000	11000	11100	11110	11111	(y1,y2,y3,y4,y5)

00000	00000	00000	00000	00000	00000	(x1,x2,x3,x4,x5)
00001	00001	00001	00001	00001	00001
00011	00011	00011	00011	00011	00011
00111	00111	00111	00111	00111	00111
01111	01111	01111	01111	01111	01111
11111	11111	11111	11111	11111	11111

Третье уравнение ложно, когда (x1,y1) = 00. Вычеркнем из нашей таблицы те решения, для которых (x1,y1) = 00.

00000	10000	11000	11100	11110	11111	(y1,y2,y3,y4,y5)

	00000	00000	00000	00000	00000	(x1,x2,x3,x4,x5)
	00001	00001	00001	00001	00001
	00011	00011	00011	00011	00011
	00111	00111	00111	00111	00111
	01111	01111	01111	01111	01111
11111	11111	11111	11111	11111	11111

Таким образом, имеется 31 набор переменных, удовлетворяющих системе.

№ п/п	№ задания	Ответ
1	5287	31

Ключ