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

Задания

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

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

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

$x1\vee y1=1$

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

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

Найдем количество решений первого уравнения. Каждая из переменных x1, ... , x6 может принимать только два значения. Импликация ложна только тогда, когда из истины следует ложь. Если записать значения переменных подряд, то можно увидеть, что для того, чтобы равенство выполнялось, необходимо, чтобы после "1" никогда не стоял "0". Следовательно, получаем такие решения: (x1,x2,x3,x4,x5, x6) = 000000, 000001, 000011, 000111, 001111, 011111, 111111.

Во втором уравнении необходимо, чтобы после "0" никогда не стояла "1". Следовательно, получаем такие решения: (y1,y2,y3,y4,y5, y6) = 000000, 100000, 110000, 11100, 111100, 111110, 111111. Таким образом, система из двух уравнений имеет 7·7  =  49 решений: для каждого набора переменных y существует 7 наборов переменных x.

000000	100000	110000	111000	111100	111110	111111	(y1,y2,y3,y4,y5, y6)

000000	000000	000000	000000	000000	000000	000000	(x1,x2,x3,x4,x5, x6)
000001	000001	000001	000001	000001	000001	000001
000011	000011	000011	000011	000011	000011	000011
000111	000111	000111	000111	000111	000111	000111
001111	001111	001111	001111	001111	001111	001111
011111	011111	011111	011111	011111	011111	011111
111111	111111	111111	111111	111111	111111	111111

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

000000	100000	110000	111000	111100	111110	111111	(y1,y2,y3,y4,y5, y6)

	000000	000000	000000	000000	000000	000000	(x1,x2,x3,x4,x5, x6)
	000001	000001	000001	000001	000001	000001
	000011	000011	000011	000011	000011	000011
	000111	000111	000111	000111	000111	000111
	001111	001111	001111	001111	001111	001111
	011111	011111	011111	011111	011111	011111
111111	111111	111111	111111	111111	111111	111111

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

№ п/п	№ задания	Ответ
1	5319	43

Ключ