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

Рассмотрим все перестановки переменных $w$, $x$, $y$, $z$ по четырём столбцам и для каждой проверим три строки таблицы.

При соответствии $y$, $x$, $z$, $w$ строки таблицы имеют вид $(y,x,z,w)=(?,0,1,0)$, $(0,?, ?,0)$ и $(?,1,1,?)$. В каждой из них значение выражения $F$ равно $0$ при подходящих неизвестных значениях.

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

Подставляем значения второй строки в логическое выражение.$$F=(0\land\neg 1)\lor(1\equiv 0)\lor 0=0$$

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

Из последнего равенства следует, что во всех приведённых строках $w = 0$. Значит, столбец со значениями $0, 0$ в известных ячейках — четвёртый.

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

Из первого равенства следует, что $z = 1$ и $x \equiv y = 0$, то есть $x$ и $y$ имеют различные значения. Из второго равенства следует $w \to x = 1$.

Во всех приведённых строках значение функции равно 0. Так как $F=A \lor \neg y$, необходимо $y=1$ и $A=0$, где $A=((w \equiv \neg x) \to \neg(z \to w))$.$$F=0 \Rightarrow y=1$$

Импликация $A$ равна 0 только тогда, когда её посылка истинна, а заключение ложно:$$w \equiv \neg x=1, \quad \neg(z \to w)=0$$

Проверим вариант 2: $X \land Y \land \neg Z$.

В первой строке $X=0$, поэтому значение выражения равно 0.$$0 \land 1 \land \neg 0 = 0$$

В таблице значение $F = 1$ указано только для набора $X = 0$, $Y = 1$, $Z = 1$.$$X = 0,\quad Y = 1,\quad Z = 1$$

Проверяем вариант 3: отрицание $X$ истинно при $X = 0$, а $Y$ и $Z$ истинны при соответствующих единичных значениях.$$\neg X \land Y \land Z = 1$$

Рассмотрим все возможные соответствия переменных $w$, $x$, $y$, $z$ четырём столбцам таблицы. Всего существует $4! = 24$ перестановки.$$F = \neg(w \to x) \lor (y \equiv z) \lor y$$

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

Поскольку во всех трёх строках $F=1$, конъюнкция с переменной $y$ требует, чтобы $y=1$ во всех этих строках. Сравнение заполненных значений показывает, что $y$ соответствует третьему столбцу.$$y=1$$

Для остальных переменных выражение $\neg((x \to w) \to (w \equiv z))$ должно быть равно $1$. Поэтому одновременно выполняются условия $x \to w=1$ и $w \ne z$.$$(x \to w)=1,\quad w\ne z$$

Проверим выражения по строкам таблицы истинности. В первой строке $X=0$, $Y=1$, $Z=0$, а $F=0$.

Вариант 4 даёт в первой строке значение $0$:$$X \lor \neg Y \lor Z = 0 \lor 0 \lor 0 = 0$$

Так как во всех трёх строках $F = 0$, дизъюнкция равна нулю. Следовательно, $w = 1$ и $(z \to x) \to (x \equiv y) = 0$.

Проверяем перестановки переменных по четырём столбцам с учётом известных значений в таблице. Единственная перестановка, при которой выражение принимает значение 0 во всех трёх строках, имеет вид: столбцы $1,2,3,4$ соответствуют переменным…

Заменим импликацию и преобразуем отрицание дизъюнкции:$$F = (\neg x \lor y) \lor \neg(\neg z \lor w) = (\neg x \lor y) \lor (z \land \neg w)$$

Для получения значения $F = 0$ оба слагаемых дизъюнкции должны быть равны нулю. Поэтому необходимо, чтобы $x = 1$, $y = 0$, а также $z \land \neg w = 0$.

Рассматриваем функцию $F = ((x \equiv \neg y) \to \neg(w \to x)) \lor \neg z$ и перебираем соответствия четырёх столбцов переменным $w$, $x$, $y$, $z$.

Подстановка известных значений во все три строки с условием $F = 0$ оставляет единственное соответствие: первому столбцу соответствует $w$, второму — $x$, третьему — $z$, четвёртому — $y$.$$1 \to w,\quad 2 \to x,\quad 3 \to z,\quad 4 \to y$$

Проверим соответствие столбцов: 1-й столбец — $y$, 2-й — $x$, 3-й — $w$, 4-й — $z$.$$y,\ x,\ w,\ z$$

Для первой строки получаем $x=0$, $w=1$, $z=0$, а значение $y$ не задано. Тогда $z \to x = 1$, а $w \to (x \equiv y)=0$, поэтому $F=1$.

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

Ложность импликации означает, что её левая часть истинна, а правая ложна: $x \equiv \neg y = 1$ и $\neg(z \to x) = 0$. Следовательно, $z \to x = 1$.

Так как во всех трёх строках значение функции равно единице, оба множителя выражения должны быть истинны. Условие $\neg(w \to (x \equiv y)) = 1$ означает $w = 1$ и $x \ne y$.$$\neg(w \to (x \equiv y)) = 1 \Longleftrightarrow w = 1 \land x \ne y$$

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

Проверим выражение $X \lor Y \lor Z$ в первой строке: все аргументы равны нулю, поэтому значение выражения равно нулю.$$0 \lor 0 \lor 0 = 0$$

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

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

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

Логическое выражение ложно только в том случае, если ложны все три части дизъюнкции.$$(69 \ne y + 2x) = 0,\quad (A > x) = 0,\quad (A > y) = 0$$

Следовательно, для проверки минимального значения $A$ нужно рассмотреть систему условий:$$y + 2x = 69,\quad x \ge A,\quad y \ge A$$

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

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