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

Импликация ложна только тогда, когда её левая часть истинна, а правая часть ложна.$$K \lor M = 1,\quad M \lor \lnot L \lor N = 0$$

Правая дизъюнкция равна нулю только в том случае, если все её переменные-условия равны нулю: $M=0$, $\lnot L=0$, $N=0$.$$M=0,\quad L=1,\quad N=0$$

Проверяем порядок столбцов $w$, $z$, $y$, $x$.

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

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

Во второй строке единицы стоят в первом и третьем столбцах. Если им соответствуют $x$ и $y$, а второй и четвёртый столбцы — $w$ и $z$, то получаем набор $x=1$, $w=0$, $y=1$, $z=1$, при котором функция равна 0.

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

Для состояния $00$ импликации истинны независимо от следующей пары, поэтому возможны все четыре перехода. Из состояния $01$ возможны переходы в $01$ и $11$. Из состояния $10$ возможен только переход в $11$. Из состояния $11$ также…

Во всех трёх строках значение функции равно 0. Дизъюнкция равна 0 только тогда, когда все её части равны 0.$$(x \land y)=0,\quad (y \equiv z)=0,\quad w=0$$

Условие $(y \equiv z)=0$ означает, что значения $y$ и $z$ различны.

Логическое выражение ложно только тогда, когда ложны все три дизъюнкта.$$y + 2x = 99,\quad A \ge x,\quad A \ge y$$

Чтобы найти наибольшее возможное значение $A$, рассмотрим минимально возможное максимальное значение чисел $x$ и $y$ при условии $y+2x=99$. Равенство $x=y$ даёт $3x=99$, поэтому $x=y=33$.

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

При условиях $x \geq 30$ и $y \geq x$ минимальные неотрицательные значения переменных равны $x = 30$ и $y = 30$.

Дизъюнкция ложна только тогда, когда ложны все её части:$$x \leq A,\quad y \leq A,\quad x+2y \geq 100$$

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

Функция является дизъюнкцией трёх выражений. Чтобы она была ложной, каждое из них должно быть ложно.$$\neg x=0,\quad y=0,\quad \neg z\land w=0$$

Из условия $\neg x=0$ следует $x=1$. Поэтому столбец со значениями $1,1,1$ — это переменная $x$.

Чтобы выражение не было тождественно истинным, необходимо найти условия, при которых все три высказывания ложны.$$(3x + 2y \leq A) \land (y \geq x) \land (x \geq 10)$$

Из условий $x \geq 10$ и $y \geq x$ следует, что минимальные возможные значения переменных: $x = 10$, $y = 10$.

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

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

При значении функции, равном 1, каждый множитель конъюнкции должен быть равен 1. Поэтому $w=1$, $x \ne z$ и $x \lor \neg y=1$.$$(x \lor \neg y) \land \neg(x \equiv z) \land w = 1$$

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

Чтобы функция была равна нулю, каждый член дизъюнкции должен быть равен нулю:$$F=0 \Rightarrow \neg(z\to w)=0,\quad x\to y=0,\quad \neg x=0$$

Из условия $\neg x=0$ получаем $x=1$. Импликация $x\to y$ при $x=1$ равна нулю только при $y=0$.$$x=1,\quad y=0$$

Условие $x_i \lor \neg x_{i+1}=1$ означает, что при $x_{i+1}=1$ обязательно $x_i=1$. Поэтому последовательность $x_1, x_2, \ldots, x_6$ не возрастает. Аналогично последовательность $y_1, y_2, \ldots, y_6$ не возрастает.$$x_i \geq x_{i+1},\quad y_i \geq y_{i+1}$$

Условия $x_i \lor \neg y_i=1$ и $x_6 \lor \neg y_6=1$ означают, что в каждой позиции значение $y_i=1$ возможно только при $x_i=1$.$$x_i \geq y_i\quad (i=1,\ldots,6)$$

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

Для первых двух строк первые два столбца имеют значения $0,0$ и $0,1$, а четвёртый — значение 1. При $y=0$ условие $\neg(y \equiv z)=1$ требует $z=1$. Значит, первый столбец — $y$, а четвёртый — $z$.

Так как функция принимает значение 1, множитель $\lnot w$ также равен 1. Следовательно, $w = 0$.

Множитель $\lnot(y \equiv z)$ равен 1 только тогда, когда значения $y$ и $z$ различны.

Дизъюнкция может принимать значение 0 только тогда, когда все три её части равны 0.$$(48 \ne y + 2x) = 0,\quad (A < x) = 0,\quad (A < y) = 0$$

Следовательно, для ложности выражения должны одновременно выполняться условия:$$y + 2x = 48,\quad x \leq A,\quad y \leq A$$

Выражение должно быть истинным при любых $x$ и $y$. Найдём условие, при котором оно ложно:$$\neg(x>A) \land \neg(y>A) \land \neg(x+2y<100)$$

С учётом целочисленных значений это означает:$$x \leq A,\quad y \leq A,\quad x+2y \geq 100$$

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

Если $x \notin B$, внешняя импликация будет истинной только тогда, когда внутренняя импликация истинна. Следовательно, для любого $x \in C$, не принадлежащего $A$, должно выполняться $x \in B$.

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

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