Тапсырма 23 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

Чтобы выражение могло быть ложным, должны быть ложны высказывания $x < 30$ и $y < 30$. Значит, $x \geq 30$ и $y \geq 30$.

В этой области минимальное значение выражения $y + 3x$ достигается при $x = 30$ и $y = 30$:$$y + 3x = 30 + 3 \cdot 30 = 120$$

Функция принимает значение 1, поэтому в каждой строке множитель $w$ должен быть равен 1. Единственным подходящим является первый столбец: во второй и третьей строках там стоят единицы, а в первой строке также должна стоять единица.$$w=1$$

В каждой строке должно выполняться условие $\lnot(x \equiv z)=1$, то есть значения $x$ и $z$ должны различаться. Во второй строке после первого столбца стоят значения $0,0,1$, поэтому $x$ и $z$ — это один из нулевых столбцов и четвёртый…

Раскроем импликации: $y \to z = \neg y \lor z$, $x \to w = \neg x \lor w$.$$F = \neg(\neg y \lor z) \lor (\neg x \lor w) \lor \neg x$$

После применения закона де Моргана выражение принимает вид:$$F = (y \land \neg z) \lor \neg x \lor w$$

Если $x \notin P$, внешняя импликация истинна. Поэтому рассматриваем только значения $x \in P$.

При $x \in P$ правая часть внутренней импликации, $\neg(x \in P)$, ложна. Чтобы импликация была истинной, её левая часть должна быть ложной: $x \in Q \land \neg(x \in A)$.

Вторая часть импликации $X < X - 1$ невозможна ни при каком числе $X$, поэтому она всегда ложна.$$X < X - 1 \text{ — ложь}$$

Импликация с ложным следствием истинна только тогда, когда её условие ложно.$$\neg(90 < X^2),\quad X^2 \leq 90$$

Чтобы исходная дизъюнкция была тождественно истинной, не должно существовать таких неотрицательных $x$ и $y$, при которых все три части ложны.$$(x \leq A) \land (y \leq x) \land (x + 2y \geq 110)$$

Из условий $x \leq A$ и $y \leq x$ следует, что максимальное значение суммы $x + 2y$ достигается при $x = y = A$.$$x + 2y \leq A + 2A = 3A$$

Так как значение функции в каждой приведённой строке равно 0, все три компонента дизъюнкции должны быть равны 0.$$(x \land \neg y)=0,\quad (x \equiv z)=0,\quad w=0$$

Третий столбец содержит нули во всех трёх строках, значит он соответствует переменной $w$.

Проверим перестановки переменных по четырём столбцам и оставим только те, при которых значение функции в каждой из трёх строк равно 0.$$F=((z \to (x \equiv w)) \lor \lnot(y \to w))=0$$

Единственное подходящее распределение переменных по столбцам: $x$, $w$, $z$, $y$.

Рассмотрим формулу при $x \in P$. Тогда левая часть внешней импликации истинна, поэтому должна быть истинной правая часть.$$((x \in Q) \land \neg(x \in A)) \to \neg(x \in P)$$

При $x \in P$ выражение $\neg(x \in P)$ ложно. Чтобы импликация с ложным следствием была истинной, её условие должно быть ложным.$$\neg\big((x \in Q) \land \neg(x \in A)\big)$$

Так как все команды увеличивают число, число 9 в траектории достигается ровно один раз. Поэтому программы можно разбить на две независимые части: от 2 до 9 и от 9 до 17.

Обозначим через $f(n)$ число программ, переводящих 2 в $n$. Для последнего шага возможны команды A, B и C, поэтому $f(n)=f(n-1)+f(n-2)+f(n/2)$ для чётного $n$, а для нечётного $n$ последнее слагаемое отсутствует.

Дизъюнкция ложна только тогда, когда ложны все три её части:$$(2x+y=100)\land(x\ge y)\land(A\ge x)$$

Из равенства $2x+y=100$ выразим $y$ и подставим в условие $x\ge y$:$$y=100-2x,\quad x\ge100-2x$$

Импликация ложна только тогда, когда её первое высказывание истинно, а второе ложно. Значит, $x$ должно делиться на $2$ и на $5 одновременно.$$10 \mid x$$

Наименьшее положительное значение $x$, кратное $10$, равно $10$.

Во второй строке значения четырёх столбцов равны $1, 1, 1, 0$, а значение функции равно 0. Перебираем соответствие переменных этим столбцам с учётом выражения $(x \land \neg y) \lor (x \equiv z) \lor \neg w$.

Подходит распределение: первый столбец — $y$, второй — $z$, третий — $w$, четвёртый — $x$. Во второй строке получаем $y=1$, $z=1$, $w=1$, $x=0$, поэтому все три части дизъюнкции равны 0.

Так как во всех трёх строках $F = 0$, оба слагаемых дизъюнкции должны быть равны нулю. Поэтому $\lnot z = 0$, то есть $z = 1$, а также $(w \to y) \to x = 0$.$$F = 0 \Rightarrow z = 1$$

В третьей строке значения в столбцах 2, 3 и 4 равны соответственно $1$, $0$, $0$, а во второй строке значение в столбце 2 равно $0$. Единственным возможным столбцом для $z$ является первый столбец.$$z = \text{столбец 1}$$

Каждую пару $(x_i,y_i)$ можно рассматривать как одно из четырёх состояний: $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$.

Импликация $(\neg x_i \lor y_i) \to (\neg x_{i+1} \land y_{i+1})$ ложна только при $x_i=1$ и $y_i=0$, когда первая часть истинна, а вторая часть для следующей пары должна быть истинной. Поэтому из состояний $(0,0)$, $(0,1)$ и $(1,1)$…

Так как значение функции равно 0, каждое слагаемое дизъюнкции должно быть равно 0: $x\land\neg y=0$, $y\equiv z=0$ и $w=0$.

Во второй строке значения в четырёх столбцах равны $0,0,0,1$. Переменная $w$ должна иметь значение 0, а для $y\equiv z=0$ значения $y$ и $z$ должны различаться. Поэтому последний столбец соответствует $y$, а первый из трёх нулевых — $z$.

Дизъюнкция может быть ложной только тогда, когда оба её выражения ложны. Первое выражение $\mathrm{ДЕЛ}(x,3) \to \neg\mathrm{ДЕЛ}(x,5)$ ложно, если $x$ делится на $3$ и одновременно делится на $5$.$$\mathrm{ДЕЛ}(x,3) \land \mathrm{ДЕЛ}(x,5)$$

Следовательно, достаточно рассмотреть положительные числа, кратные $15$. Наименьшее такое число — $x=15$.

Всего логических переменных двенадцать: $x_1,\ldots,x_7$ и $y_1,\ldots,y_5$. Поэтому полный перебор содержит $2^{12}=4096$ наборов.$$2^{7+5}=2^{12}=4096$$

Для каждого набора значений проверяем условия для всех $i=1,\ldots,6$ и $j=1,\ldots,4$. Всего проверяется $6\cdot4=24$ выражения.

Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для последнего шага программы возможны команды $A$, $B$ и $C$, поэтому учитываются переходы из $n-1$, $n-3$ и $n/3$.$$f(n)=f(n-1)+f(n-3)+f(n/3)$$

Последовательно вычисляя значения от 3 до 14, получаем количество программ, переводящих 3 в 14:$$f(14)=46$$

Внешняя импликация может быть ложной только при $x \in P$, когда её правая часть ложна.

Внутренняя импликация $((x \in Q) \land \neg(x \in A)) \to \neg(x \in P)$ ложна, если одновременно $x \in Q$, $x \notin A$ и $x \in P$.