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

Логическое выражение с делимостью

Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наименьшего натурального числа $A$ формула…

1. 1
   Импликация $P \to Q$ ложна только при истинном $P$ и ложном $Q$. Поэтому первая часть формулы ложна, если $x$ делится на $3$ и одновременно делится на $5$.$$\mathrm{ДЕЛ}(x,3) \land \mathrm{ДЕЛ}(x,5)$$
2. 2
   Значит, $x$ должно быть кратно $15$. Наименьшее натуральное проблемное значение — $x=15$.

Ещё 3 шага — в полном решении

Сопоставление столбцов таблицы истинности

Миша заполнял таблицу истинности функции $(\neg x \land \neg y) \lor (x \equiv z) \lor \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…

1. 1
   Проверим соответствие столбцов порядку $x$, $w$, $z$, $y$. В первой строке имеем $x=0$, $w=1$, $z=1$, $y=1$.$$(\neg 0 \land \neg 1) \lor (0 \equiv 1) \lor \neg 1 = 0$$
2. 2
   Во второй строке при таком порядке получаем $x=1$, $w=1$, $z=0$, $y=0$.$$(\neg 1 \land \neg 0) \lor (1 \equiv 0) \lor \neg 1 = 0$$

Ещё 2 шага — в полном решении

Минимальный отрезок для логического выражения

На числовой прямой даны два отрезка $P = [17; 54]$ и $Q = [37; 83]$. Укажите наименьшую возможную длину такого отрезка $A$, что логическое выражение…

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

Ещё 2 шага — в полном решении

Восстановление таблицы истинности

Миша заполнял таблицу истинности функции $F=(\neg x \land \neg y) \lor (y \equiv z) \lor w$, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы…

1. 1
   Функция равна 0 во всех трёх строках. Так как в выражении есть дизъюнкция слагаемого $w$, во всех строках должно выполняться $w=0$. Нулевые значения во всех строках находятся в первом столбце, значит первый столбец — это $w$.$$w=0$$
2. 2
   Во второй и третьей строках второй столбец принимает значения 1 и 0, а третий столбец — значения 0 и 1 соответственно после восстановления пропуска. Эти столбцы должны соответствовать переменным $z$ и $y$, причём $y \ne z$.

Ещё 1 шаг — в полном решении

Подсчёт наборов логических переменных

Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным условиям? $x_1 \to y_1 = 1$…

1. 1
   Для первой пары $(x_1,y_1)$ условие $x_1 \to y_1=1$ исключает только комбинацию $(1,0)$. Поэтому возможны состояния $00$, $01$ и $11$.$$(a_1,b_1,c_1)=(1,1,1)$$
2. 2
   Для каждой следующей пары $(x_i,y_i)$ состояние $10$ невозможно. Состояние $00$ может следовать за любым состоянием, состояние $01$ — только за состояниями $01$ или $11$, а состояние $11$ — только за состоянием $11$.$$a_{i+1}=a_i+b_i+c_i,\quad b_{i+1}=b_i+c_i,\quad c_{i+1}=c_i$$

Ещё 2 шага — в полном решении

Соответствие столбцов переменным

Миша заполнял таблицу истинности функции $(x \land \neg y) \lor (y \equiv z) \lor \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…

1. 1
   Во всех трёх строках значение функции равно 0. Следовательно, для каждой строки необходимо, чтобы вся дизъюнкция $(x \land \neg y) \lor (y \equiv z) \lor \neg w$ имела значение 0.$$(x \land \neg y) = 0,\quad (y \equiv z) = 0,\quad \neg w = 0$$
2. 2
   Сопоставляем известные нули и единицы в трёх строках с этими условиями. Единственное соответствие, согласующее все строки фрагмента, имеет вид: первый столбец — $w$, второй — $z$, третий — $y$, четвёртый — $x$.$$1 \to w,\quad 2 \to z,\quad 3 \to y,\quad 4 \to x$$

Восстановление порядка переменных

Миша заполнял таблицу истинности функции $F = (\neg x \land \neg y) \lor (x \equiv z) \lor w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…

1. 1
   Так как значение функции во всех трёх строках равно 0, каждое из слагаемых дизъюнкции должно быть равно 0.$$F=0 \Rightarrow (\neg x\land\neg y)=0,\quad (x\equiv z)=0,\quad w=0$$
2. 2
   В третьей строке записаны значения $1$, $1$, пропуск, $0$. Если третий столбец соответствует $w$, то $w=0$, что согласуется с условием $F=0$. Поэтому третий столбец — это $w$.

Ещё 2 шага — в полном решении

Наибольшее значение параметра

Для какого наибольшего целого неотрицательного числа $A$ выражение $(x \cdot y > A) \lor (x > y) \lor (8 \ge x)$ тождественно истинно, то есть принимает значение $1$ при любых целых неотрицательных…

1. 1
   Чтобы всё выражение могло быть ложным, каждое из трёх высказываний должно быть ложным. Из условия $8 \ge x$ получаем $x > 8$, а из условия $x > y$ получаем $x \le y$.$$x \ge 9,\quad y \ge x$$
2. 2
   При таких неотрицательных целых $x$ и $y$ минимальное произведение достигается при $x = 9$ и $y = 9$.$$x \cdot y \ge 9 \cdot 9 = 81$$

Ещё 1 шаг — в полном решении

Определение переменных по таблице

Миша заполнял таблицу истинности функции $(x \lor \neg y) \land \neg(y \equiv z) \land \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы…

1. 1
   Так как значение функции равно 1, каждый из множителей должен быть равен 1. Поэтому $\neg w=1$, то есть $w=0$, а $\neg(y \equiv z)=1$, то есть $y$ и $z$ имеют разные значения.$$\neg w=1,\quad y\ne z$$
2. 2
   Во второй строке первый столбец равен 1, третий — 1, четвёртый — 0. Чтобы $y$ и $z$ были различны, при $z=1$ значение $y$ должно быть равно 0. Значит, второй столбец — это $y$, а первый — $z$.

Ещё 1 шаг — в полном решении

Определение столбцов таблицы истинности

Миша заполнял таблицу истинности функции $(x \lor \neg y) \land \neg(x \equiv z) \land w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…

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

Ещё 1 шаг — в полном решении

Минимальное значение параметра

Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наименьшего натурального числа $A$ формула…

1. 1
   Дизъюнкция может быть ложной только тогда, когда обе её части ложны. В частности, первая часть ложна, если импликация ложна.$$(\mathrm{ДЕЛ}(x,2) \to \neg\mathrm{ДЕЛ}(x,3)) = 0$$
2. 2
   Импликация ложна, когда её условие истинно, а заключение ложно: число $x$ должно делиться и на 2, и на 3. Значит, $x$ кратно 6.

Ещё 2 шага — в полном решении

Максимальное значение параметра

Для какого наибольшего целого неотрицательного числа $A$ выражение $(69 \ne y + 2x) \vee (A < x) \vee (A < y)$ тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных $x$…

1. 1
   Дизъюнкция может принимать значение 0 только тогда, когда все три её части ложны. Поэтому должны выполняться условия:$$y + 2x = 69,\quad x \leq A,\quad y \leq A$$
2. 2
   Чтобы выражение было тождественно истинным, нужно выбрать $A$ меньше минимально возможного значения $\max(x,y)$ среди неотрицательных решений уравнения $y + 2x = 69$.

Ещё 2 шага — в полном решении

Кто разбил окно

Восемь школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы: Соня: «Это…

1. 1
   Проверим вариант, при котором окно разбила Аня. Тогда высказывание Сони ложно, поскольку разбивал не Володя.
2. 2
   Высказывание Миши истинно: утверждение Сони действительно является ложью.

Ещё 3 шага — в полном решении

Количество наборов логических переменных

Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, которые удовлетворяют всем перечисленным ниже условиям?…

1. 1
   Обозначим $a_i = x_i \land y_i$. По закону де Моргана каждое условие имеет вид:$$a_i \equiv \lnot a_{i+1}$$
2. 2
   Следовательно, значения $a_1, a_2, \ldots, a_9$ должны чередоваться. Возможны два варианта последовательности: начинающаяся с $1$ и начинающаяся с $0$.

Ещё 2 шага — в полном решении

Минимальный делитель для тождества

Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наименьшего натурального числа $A$ логическое выражение…

1. 1
   Импликация ложна, когда её левая часть истинна, а правая — ложна.
2. 2
   Так как при истинности условия $\mathrm{ДЕЛ}(x,A)$ выражение $\neg\mathrm{ДЕЛ}(x,A)$ ложно, правая часть требует выполнения $\mathrm{ДЕЛ}(x,39)$.

Ещё 2 шага — в полном решении

Определение столбцов таблицы истинности

Логическая функция $F$ задаётся выражением $x \land \neg y \land (\neg z \lor w)$. На рисунке приведён фрагмент таблицы истинности функции $F$, содержащий все наборы аргументов, при которых функция…

1. 1
   Так как функция истинна, конъюнктивный множитель $x$ должен быть равен 1, а множитель $\neg y$ — также равен 1. Поэтому $x=1$, $y=0$ во всех строках.$$x=1,\quad y=0$$
2. 2
   Для оставшихся переменных рассмотрим условие $\neg z \lor w$. Оно ложно только при $z=1$ и $w=0$. Поэтому допустимые пары значений имеют вид $(z,w)=(0,0),(0,1),(1,1)$.

Ещё 2 шага — в полном решении

Соответствие столбцов переменным

Миша заполнял таблицу истинности функции $(\neg x \land \neg y) \lor (x \equiv z) \lor w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…

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

Ещё 2 шага — в полном решении

Восстановление столбцов таблицы истинности

Миша заполнял таблицу истинности логической функции $F = \neg(x \to w) \lor (y \to z) \lor \neg y$, но успел заполнить лишь фрагмент из трёх различных строк, не указав, какому столбцу таблицы…

1. 1
   Преобразуем логическое выражение функции:$$F = \neg(x \to w) \lor (y \to z) \lor \neg y = (x \land \neg w) \lor (\neg y \lor z)$$
2. 2
   Для каждой из приведённых строк значение $F$ равно $0$. Подставляя известные значения из фрагмента и перебирая соответствия четырёх столбцов переменным $w$, $x$, $y$, $z$, оставляем только соответствия, удовлетворяющие всем трём строкам.

Ещё 1 шаг — в полном решении

Определение столбцов таблицы истинности

Миша заполнял таблицу истинности функции $((x \land y) \lor (y \equiv z) \lor w)$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует…

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

Ещё 2 шага — в полном решении

Подсчёт наборов логических переменных

Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_6, y_1, y_2, \ldots, y_{10}$, которые удовлетворяют всем приведённым ниже условиям?…

1. 1
   Для каждой пары индексов $i<6$, $j<10$ условие является конъюнкцией двух импликаций. Оно нарушается только в случае, когда $x_i=y_j=1$, но $x_{i+1}=0$ или $y_{j+1}=0$.$$(x_i \land y_j) \Rightarrow (x_{i+1} \land y_{j+1})$$
2. 2
   Следовательно, перебираем двоичные наборы для переменных $x_1,\ldots,x_6$ и $y_1,\ldots,y_{10}$ и оставляем только те, в которых для всех $i=1,\ldots,5$ и $j=1,\ldots,9$ выполняется указанное условие.

Ещё 1 шаг — в полном решении