ЕГЭ по информатике 2020, часть 1, № 23

ЕГЭ по информатике 2020, вариант Москва
Часть 1, № 23
Математическая логика
Задание взято с сайта
http://kotolis.ru/realegeinf_2020



Вот здесь эта задача решена, только для 5 иксов и 6 игреков.
https://vk.com/@inform_web-23-zadacha-2020

В записи местами отсутствуют индексы, но догадаться можно.

Можно прорешать эту задачу по предложенной схеме. Схема вроде правильная.

Сообщение отредактировано: swf - 22.07.20, 20:18

Решение.
Упростим выражение, избавившись от импликаций.
a → b = not(a) V b

xi & yj → xi & yj+1 = not(xi & yj) V xi & yj+1
xi & yj → xi+1 & yj = not(xi & yj) V xi+1 & yj+1
(xi & yj → xi & yj+1) & (xi & yj → xi+1 & yj) =
(not(xi & yj) V xi & yj+1) & not(xi & yj) V xi+1 & yj+1
not(xi & yj) V (xi+1 & yj+1)
not(xi & yj) V (xi+1 & yj+1) = 1 для всех i = 1…5, j = 1…6.
Или xi & yj = 0, или xi+1 & yj+1 = 1, или и то, и другое.

Подсчитаем количество наборов для
xi & yj = 0, i = 1…4, j = 1…5.

1) Все xi и yj равны 0
xi =0, yj = 0, i = 1…4, j = 1…5 – означенные переменные.
x5 и y6 – свободные переменные, могут принимать любые значения 2^2 = 4 способами.
4 набора.

2)Все xi равны 0, среди yj есть хотя бы одна 1, i = 1…4, j = 1…5 – означенные переменные.
У yj, j = 1…5, 2^5 = 32 возможных набора.
Из них один нулевой набор (все yj = 0), в оставшемся 31 наборе есть хотя бы одна 1.
x5 и y6 – свободные переменные.
31 * 4 = 124 набора

3) Теперь наоборот, все yj равны 0, среди xi есть хотя бы одна 1, i = 1…4, j = 1…5 – означенные переменные.
У xi, i = 1…4, 2^4 = 16 возможных наборов.
Из них один нулевой набор (все xi = 0), в оставшихся 15 наборах есть хотя бы одна 1.
x5 и y6 – свободные переменные.
15 * 4 = 60 наборов

И остаётся самый сложный случай.

4) Среди xi есть хотя бы одна 1 и среди yj есть хотя бы одна 1, i = 1…4, j = 1…5 – означенные переменные.
В каком-то уравнении эти единицы должны встретиться:
xi =1, yj = 1, i = 1…4, j = 1…5.
Тогда xi & yj = 1, поэтому, чтобы выражение всё же имело значение 1,
xi+1 & yj+1 должно быть равно 1.
Но, если xi+1 = 1 и yj+1 = 1, то xi+2 = 1 и yj+2 = 1 и так далее.
Поэтому, если в наборе x1...x5 какое-то xi = 1, то для всех номеров κ > i xk тоже должны быть равны 1.
Аналогично, если в наборе y1...y6 какой-то yj = 1, то все игреки с большими номерами тоже равны 1.

Эти наборы (для x1...x5 и y1...y6) удобно представить в виде двух таблиц.

x1	x2	x3	x4	x5
0	0	0	0	1
0	0	0	1	1
0	0	1	1	1
0	1	1	1	1
1	1	1	1	1

y1	y2	y3	y4	y5	y6
0	0	0	0	0	1
0	0	0	0	1	1
0	0	0	1	1	1
0	0	1	1	1	1
0	1	1	1	1	1
1	1	1	1	1	1

Получилось 5 наборов для x1 ... x5.
Но самый первый набор x1 = x2 = x3 = x4 = 0 и для игреков с хотя бы одной 1, и для всех нулевых игреков уже был подсчитан ранее.

Аналогично, получается 6 наборов для y1 ... y6.
Самый первый набор y1 = y2 = y3 = y4 = y5 = 0 и для иксов с хотя бы одной 1, и для всех нулевых иксов уже был подсчитан.

Остаются 4 набора для x1 ... x5 и 5 наборов для y1 ... y6, которые можно соединять друг с другом всеми способами:
4 * 5 = 20 наборов
Итого 4 + 124 +60 + 20 = 208.

Ответ: 208 .

Сообщение отредактировано: swf - 22.07.20, 20:26