Информатика ЕГЭ — решения заданий ФИПИ с ответами

Функция равна 1 во всех трёх строках. Поэтому множитель $w$ должен быть равен 1 во всех строках. Единственный подходящий столбец — второй.

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

Функция является дизъюнкцией. Чтобы получить $F = 0$, оба слагаемых должны быть равны нулю, поэтому $y = 0$ и $w \to \neg(z \to x) = 0$.$$F = 0 \Rightarrow y = 0$$

Импликация ложна только тогда, когда её первый аргумент равен $1$, а второй — $0$. Следовательно, $w = 1$ и $\neg(z \to x) = 0$, то есть $z \to x = 1$.$$w \to \neg(z \to x) = 0 \Rightarrow w = 1,\ z \to x = 1$$

Так как во всех трёх строках $F = 1$, каждый множитель функции должен быть равен 1. В частности, $w = 1$ во всех строках.

Переменная $w$ не может соответствовать первому или четвёртому столбцу: в первом столбце есть значение 0, а четвёртый столбец содержит значения 1, неизвестное значение и 0. Следовательно, $w$ соответствует третьему столбцу.

Функция ложна, поэтому все части дизъюнкции равны нулю:$$\neg x = 0,\quad y = 0,\quad \neg z \land w = 0$$

Из условия $\neg x = 0$ получаем $x = 1$. Во всех трёх строках единица стоит во втором столбце, значит второй столбец соответствует переменной $x$.

Обозначим состояние на шаге $i$ парой $(x_i,y_i)$. Возможны состояния $00$, $01$, $10$, $11$.

Из условия $\bigl(x_i \to (x_{i+1} \land y_i)\bigr) \land (y_i \to y_{i+1})=1$ получаем переходы между состояниями: $00\to00,01,10,11$; $01\to01,11$; $10\to11$; $11\to11$.

Так как функция принимает значение 1, каждый множитель конъюнкции должен быть равен 1. В частности, $w=1$ во всех представленных строках.

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

Так как обе команды уменьшают число, траектория может содержать число 13 не более одного раза. Поэтому программы можно однозначно разделить на часть от 30 до 13 и часть от 13 до 1.

Подсчитаем количество способов попасть из 30 в 13. Возможны последовательные вычитания, а также переходы делением на 2 из чисел 30, 29, 28, 27 и 26. Динамическим подсчётом получаем 6 способов.$$N_{30\to13}=6$$

Раскроем импликации в логическом выражении.$$F = (x \land \neg y) \vee (\neg z \vee w) \vee \neg z$$

Проверим возможные соответствия переменных столбцам. Для каждой строки из фрагмента значение функции должно быть равно нулю, поэтому все указанные значения в строке должны согласовываться с выражением функции.

Внешняя импликация может быть ложной только при $x \in P$. Поэтому для всех $x \in P$ внутренняя импликация должна быть истинной.

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

Так как все команды увеличивают число, числа 10 и 12 в траектории встречаются именно в указанном порядке. Поэтому искомое количество программ является произведением числа способов пройти три участка.$$N(4,14;10,12)=N(4,10)\cdot N(10,12)\cdot N(12,14)$$

Посчитаем количество способов попасть из 4 в 10. Для каждого числа учитываются переходы из чисел на 1 и 2 меньше, а также из числа вдвое меньшего, если оно целое.$$N(4,10)=16$$

Обозначим через $f(n)$ число программ, переводящих число $n$ в число 1. Для каждого $n > 1$ последняя команда является либо вычитанием 1, либо делением на 2.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor),\quad f(1)=1$$

Последовательно вычисляя значения, получаем число программ от 9 до 1:$$f(2)=2,\ f(3)=3,\ f(4)=5,\ f(5)=7,\ f(6)=10,\ f(7)=13,\ f(8)=18,\ f(9)=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)$$