Решения заданий ФИПИ ЕГЭ по информатике: «Логика и булева алгебра» — с ответами

Если $x \in B$, то первая часть внешней импликации ложна, поэтому вся формула истинна автоматически.

Рассмотрим точки, для которых $x \notin B$. Тогда внешняя импликация истинна только в том случае, если истинна внутренняя импликация.

Чтобы дизъюнкция была ложной, все её части должны быть ложными одновременно:$$x \leq A,\quad y \leq A,\quad x+2y \geq 110$$

При условиях $x \leq A$ и $y \leq A$ наибольшее возможное значение суммы $x+2y$ достигается при $x=A$ и $y=A$:$$x+2y \leq A+2A=3A$$

Рассмотрим каждую пару $(x_i, y_i)$ как одно состояние. Выражение $\neg x_i \lor y_i$ ложно только в состоянии $(1, 0)$.

Выражение $\neg x_{i+1} \land y_{i+1}$ истинно только в состоянии $(0, 1)$. Импликация нарушается, когда её левая часть истинна, а правая ложна.

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

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

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

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

Обозначим состояние пары $(x_i,y_i)$ одним из четырёх кодов: $00$, $10$, $01$, $11$.

Условия перехода между соседними парами дают следующие возможности: $00 \to 00,10,01,11$; $10 \to 11$; $01 \to 01,11$; $11 \to 11$.

Раскроем отрицание импликации.$$\neg(x \to w) = x \land \neg w$$

Так как во всех трёх строках $F=0$, дизъюнкция равна нулю. Следовательно, каждый её член должен быть равен нулю: $x \land \neg w=0$, $y \equiv z=0$ и $y=0$. Однако при $y=0$ условие $y \equiv z=0$ даёт $z=1$.

Чтобы дизъюнкция могла быть ложной, второе и третье высказывания должны быть ложными одновременно. Значит, $x \le 25$ и $y \le 25$.

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

Чтобы дизъюнкция была ложной, все три её части должны быть ложными. Значит, должны выполняться условия $x + 2y \geq A$, $y \leq x$ и $x \leq 60$.

При $y \leq x$ и $x \leq 60$ максимальное значение $x + 2y$ достигается при $x = 60$ и $y = 60$.$$x + 2y \leq 60 + 2 \cdot 60 = 180$$

Если $x \notin B$, то условие $x \in B$ ложно, поэтому импликация истинна. Рассмотрим только $x \in [50; 60]$.

Импликация $(x \in B) \to \neg\mathrm{ДЕЛ}(x,13)$ ложна, когда $x$ принадлежит отрезку $B$ и делится на $13$.

Чтобы выражение могло быть ложным, все три высказывания должны быть ложными. Второе и третье высказывания ложны при условиях:$$y \leq x,\quad x \leq 30$$

Так как $x$ и $y$ — неотрицательные целые числа, при этих условиях максимальное значение выражения $x + 2y$ достигается при $x = 30$ и $y = 30$.$$x + 2y \leq 30 + 2 \cdot 30 = 90$$

Дизъюнкция будет ложной только тогда, когда одновременно ложно первое слагаемое и ложно второе слагаемое.

Импликация $(x \in B) \to \neg\mathrm{ДЕЛ}(x,15)$ ложна, если $x \in B$ и число $x$ делится на $15$.

Во всех трёх строках значение функции равно нулю. Поэтому оба слагаемых дизъюнкции должны быть равны нулю: $\neg z = 0$, а значит, $z = 1$.$$F = 0 \Rightarrow z = 1$$

Для ложности импликации $(w \to y) \to (x \equiv y)$ необходимо, чтобы её посылка была истинной, а заключение ложным.$$w \to y = 1, \quad x \equiv y = 0$$

Выражение может быть ложным только тогда, когда ложны все три высказывания:$$x \cdot y \geq A,\quad x \geq y,\quad x < 8$$

Так как $x$ и $y$ — неотрицательные целые числа, из условий $x < 8$ и $x \geq y$ следует, что $x \leq 7$ и $y \leq 7$.

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

Условие $\neg(x\equiv z)=1$ означает, что значения $x$ и $z$ в каждой строке различаются. Перебор оставшихся вариантов размещения переменных с учётом трёх строк таблицы оставляет единственный вариант: первый столбец — $x$, третий — $z$…$$x\ne z$$

Так как значение функции в каждой из трёх строк равно 1, каждый набор должен удовлетворять всем условиям произведения логических выражений.$$w=1,\quad x\ne z,\quad (x=0)\lor(y=0)$$

Во второй строке единицы стоят в третьем и четвёртом столбцах. Эти столбцы должны соответствовать $w$ и одной из переменных $x,z$. Сопоставление всех трёх строк с условием $x\ne z$ даёт третий столбец $w$, а второй и четвёртый — $x$ и $z$.

Обозначим пару значений на позиции $i$ как $(x_i,y_i)$. Если эта пара равна $(0,0)$, то левая часть импликации ложна, поэтому следующая пара может быть любой из четырёх.

Если пара не равна $(0,0)$, то $x_i \lor y_i = 1$. Чтобы импликация была истинной, необходимо $x_{i+1} \land y_{i+1}=1$, то есть следующая пара обязана быть $(1,1)$.

Если среди $y_1,\ldots,y_7$ есть хотя бы одна единица, то при наличии единицы среди $x_1,\ldots,x_5$ все значения $x$ от первой такой единицы до $x_6$ должны быть равны единице. Если же среди $x_1,\ldots,x_5$ есть единица, то аналогичное…

Случай 1: в обеих группах есть единицы — среди $x_1,\ldots,x_5$ и среди $y_1,\ldots,y_7$. Последовательность $x$ имеет 5 вариантов расположения первой единицы, а последовательность $y$ — 7 вариантов. Получаем $5\cdot7=35$ наборов.

Представим каждую пару $(x_i,y_j)$ как клетку таблицы. При $x_i \land y_j = 1$ первое условие требует выполнения $x_i \land y_{j+1}$, а второе — $x_{i+1} \land y_j$.

Таким образом, при переборе наборов значений нужно исключать все конфигурации, в которых из клетки $(i,j)$ со значением $1$ можно перейти вправо или вниз в клетку со значением $0$.

Чтобы исходное выражение было ложным, все три высказывания должны быть ложными. Второе и третье высказывания ложны при $x \leq 15$ и $y \leq 30$.$$x \leq 15,\quad y \leq 30$$

При этих ограничениях максимальное значение выражения $y + 2x$ достигается при $x = 15$ и $y = 30$.$$y + 2x = 30 + 2 \cdot 15 = 60$$