Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_6, y_1, y_2, \ldots, y_6$, которые удовлетворяют всем перечисленным ниже условиям? $x_1 \to y_1 = 1$…
- 1
Импликация $a \to b$ истинна, если $a = 0$ или $b = 1$. Поэтому из условий для каждого $i \geq 2$ следует: если $x_i = 1$, то $x_{i-1} = 1$ и $y_i = 1$; если $y_i = 1$, то $y_{i-1} = 1$.
- 2
Следовательно, единицы в каждой последовательности идут только в начале. Последовательность $x$ определяется числом $a$ единиц, а последовательность $y$ — числом $b$ единиц, где $a,b \in \{0,1,\ldots,6\}$.
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = (x \lor y) \land \neg(y \equiv z) \land \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу…
- 1
Так как во всех приведённых строках $F = 1$, конъюнкция $\neg w$ должна быть истинной. Значит, $w = 0$ во всех строках. Единственный столбец, в котором в известных ячейках стоят только нули, — первый.$$w = 0$$
- 2
Условие $\neg(y \equiv z)$ означает, что значения $y$ и $z$ различны в каждой строке.
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = \neg(y \to w) \lor (x \to z) \lor \neg x$, но успел заполнить лишь фрагмент из трёх различных строк, не указав, какому столбцу таблицы…
- 1
Раскроем импликации: $y \to w = \neg y \lor w$, $x \to z = \neg x \lor z$.$$F = \neg(y \to w) \lor (x \to z) \lor \neg x = (y \land \neg w) \lor \neg x \lor z$$
- 2
Чтобы значение функции было равно нулю, должны выполняться условия $x = 1$, $z = 0$, а также $y \land \neg w = 0$.
Ещё 1 қадам — толық шешімде
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_6, y_1, y_2, \ldots, y_6$, которые удовлетворяют всем перечисленным ниже условиям?…
- 1
Для каждого $i=1,\ldots,5$ первое условие означает: если $x_i=1$, то $x_{i+1}=1$ и $y_i=1$. Поэтому после появления первой единицы среди $x_i$ все последующие $x_i$ также равны единице.
- 2
Если все $x_i=0$, то все переменные $y_i$ могут принимать произвольные значения. Получаем $2^6=64$ набора.
Ещё 3 қадам — толық шешімде
Миша заполнял таблицу истинности функции $(\neg x \land \neg y) \lor (x \equiv z) \lor w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Во всех трёх строках значение функции равно $0$. Поэтому дизъюнкция равна нулю, а значит, каждое её слагаемое равно нулю. В частности, $w=0$.$$w=0$$
- 2
Четвёртый столбец содержит значение $0$ в первой строке, где первые два значения равны $1$. Если бы четвёртый столбец не был столбцом $w$, условие $w=0$ не выполнялось бы для всех строк. Следовательно, четвёртый столбец — это $w$.
Ещё 2 қадам — толық шешімде
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_8, y_1, y_2, \ldots, y_8$, которые удовлетворяют всем условиям: $(x_1 \lor y_1) \to (x_2 \land y_2) = 1$…
- 1
Импликация $A \to B$ равна $1$, если $A=0$ или $B=1$. Поэтому если $(x_i,y_i)=(0,0)$, ограничений на следующую пару нет.
- 2
Если $(x_i,y_i)\ne(0,0)$, то $x_i\lor y_i=1$. Тогда необходимо, чтобы $x_{i+1}\land y_{i+1}=1$, то есть следующая пара должна быть $(1,1)$. После этого все последующие пары также обязаны быть $(1,1)$.
Ещё 3 қадам — толық шешімде
Обозначим через $m \mathbin{\&} n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$. Так, например, $14 \mathbin{\&} 5 = 1110_2 \mathbin{\&} 0101_2 = 0100_2 = 4$. Для какого наименьшего…
- 1
Запишем числа 52 и 36 в двоичной системе:$$52 = 110100_2, \quad 36 = 100100_2$$
- 2
Условие $x \mathbin{\&} 36 = 0$ запрещает единицы в разрядах $2^2$ и $2^5$ числа $x$. Поэтому из условия $x \mathbin{\&} 52 \ne 0$ может выполняться только единичность разряда $2^4$.$$52 = 2^5 + 2^4 + 2^2, \quad 36 = 2^5 + 2^2$$
Ещё 1 қадам — толық шешімде
Миша заполнял таблицу истинности функции $ (x \land \neg y) \lor (x \equiv z) \lor \neg w $, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы…
- 1
Значение функции равно $0$, поэтому каждое из трёх выражений в дизъюнкции должно быть равно $0$: $x \land \neg y = 0$, $x \equiv z = 0$, $\neg w = 0$.
- 2
Из условия $\neg w = 0$ следует $w=1$. В первой строке значения столбцов равны $0,1,1,0$, а в третьей — неизвестное значение, $1,0,1$. Проверка всех перестановок переменных показывает, что нулевое значение функции во всех трёх различных…
Ещё 1 қадам — толық шешімде
Миша заполнял таблицу истинности функции $ (\neg x \lor \neg y) \land \neg(y \equiv z) \land w $, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Рассмотрим функцию $F = (\neg x \lor \neg y) \land \neg(y \equiv z) \land w$. Так как во всех трёх строках значение функции равно 1, в каждой строке должно быть $w=1$.
- 2
В первой строке заполненные значения имеют вид $\_,0,0,1$. Следовательно, столбец переменной $w$ должен содержать 1 в этой строке. Аналогично проверяются значения в двух остальных строках.
Ещё 1 қадам — толық шешімде
На числовой прямой даны два отрезка: $P = [17; 54]$ и $Q = [37; 83]$. Укажите наименьшую возможную длину такого отрезка $A$, что логическое выражение…
- 1
Если $x \notin P$, внешняя импликация истинна автоматически. Поэтому достаточно рассмотреть $x \in P$.
- 2
При $x \in P$ высказывание $\neg(x \in P)$ ложно. Чтобы внутренняя импликация оставалась истинной, её левая часть должна быть ложной: $(x \in Q) \land \neg(x \in A) = 0$.$$(x \in P) \cap (x \in Q) \subseteq (x \in A)$$
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = \neg(y \to x) \lor (z \to w) \lor \neg z$, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы…
- 1
Преобразуем отрицание импликации:$$\neg(y \to x) = y \land \neg x$$
- 2
Тогда функция имеет вид:$$F = (y \land \neg x) \lor (\neg z \lor w) \lor \neg z$$
Ещё 3 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = (x \land \neg y) \lor (y \equiv z) \lor \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу…
- 1
Во всех трёх строках значение функции равно нулю. Поэтому каждое слагаемое выражения должно быть равно нулю, в частности $\neg w=0$. Значит, $w=1$ во всех строках, и переменной $w$ соответствует первый столбец.
- 2
Во второй строке значения во втором и четвёртом столбцах равны нулю, а в третьем столбце значение не указано. В третьей строке во втором столбце стоит 0, а в третьем — 1. Чтобы $y \equiv z=0$, переменные $y$ и $z$ должны занимать второй и…
Ещё 2 қадам — толық шешімде
Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наименьшего натурального числа $A$ логическое выражение…
- 1
Дизъюнкция истинна автоматически, если истинна первая часть. Первая часть является импликацией, которая ложна только в случае, когда её условие истинно, а заключение ложно.$$\mathrm{ДЕЛ}(x,2)=1 \quad\text{и}\quad \neg\mathrm{ДЕЛ}(x,5)=0$$
- 2
Следовательно, импликация ложна для чисел, делящихся одновременно на $2$ и на $5$, то есть для положительных чисел, кратных $10$.$$x=10k,\quad k\in\mathbb{N}$$
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности функции $(x \lor y) \land \neg(y \equiv z) \land \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Во всех трёх строках значение функции равно 1. Поэтому каждый множитель конъюнкции также должен быть равен 1.
- 2
Из условия $\neg w=1$ следует, что $w=0$. Столбец 4 содержит нули в двух заполненных строках, поэтому это столбец переменной $w$.
Ещё 2 қадам — толық шешімде
Даны целые числа $A$, $B$, $C$, для которых истинно высказывание $\neg(A=B) \land ((B<A) \to (2C>A)) \land ((A<B) \to (A>2C))$. Чему равно $A$, если $C=8$, $B=18$?
- 1
Подставим значения $C=8$ и $B=18$ в логическое выражение:$$\neg(A=18) \land ((18<A) \to (16>A)) \land ((A<18) \to (A>16))$$
- 2
Если $A>18$, то условие $18<A$ истинно, поэтому импликация требует $16>A$. Это невозможно, поскольку $A>18$.
Ещё 2 қадам — толық шешімде
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным ниже условиям?…
- 1
Обозначим $z_i = x_i \land y_i$. Правая часть каждого равенства преобразуется по закону де Моргана:$$\lnot x_{i+1} \lor \lnot y_{i+1} \equiv \lnot(x_{i+1} \land y_{i+1}) = \lnot z_{i+1}$$
- 2
Следовательно, система требует, чтобы соседние значения $z_i$ и $z_{i+1}$ были противоположными. Поэтому возможны только два чередующихся набора значений: $0101010$ и $1010101$.
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности функции $ (\neg x \land \neg y) \lor (x \equiv z) \lor w $, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Функция равна 0, поэтому каждое слагаемое дизъюнкции должно быть равно 0.$$(\neg x \land \neg y)=0,\quad (x\equiv z)=0,\quad w=0$$
- 2
Из условия $(x\equiv z)=0$ следует, что значения переменных $x$ и $z$ в каждой строке различаются. Условие $w=0$ позволяет найти столбец, содержащий нулевые значения во всех строках с учётом пропущенных ячеек.
Ещё 1 қадам — толық шешімде
На числовой прямой даны два отрезка: $D = [17; 58]$ и $C = [29; 80]$. Укажите наименьшую возможную длину такого отрезка $A$, для которого логическое выражение…
- 1
Если $x \notin D$, внешняя импликация истинна автоматически. Рассмотрим значения $x \in D$.$$x \in D \Rightarrow \neg(x \in D) = 0$$
- 2
Чтобы внутренняя импликация с ложным заключением была истинной, её условие должно быть ложным:$$\neg(x \in C) \land \neg(x \in A) = 0$$
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности функции $(x \lor \neg y) \land \neg(x \equiv z) \land \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Так как функция равна $1$ во всех трёх строках, множитель $\neg w$ должен быть равен $1$. Следовательно, $w=0$ во всех строках. Единственный столбец, в котором нет заданных единиц, — второй, поэтому второй столбец соответствует $w$.$$\neg w = 1 \Rightarrow w=0$$
- 2
Множитель $\neg(x \equiv z)$ равен $1$ только тогда, когда значения $x$ и $z$ различаются.$$\neg(x \equiv z)=1 \Rightarrow x \ne z$$
Ещё 2 қадам — толық шешімде
100ФИПИ 4CCB4D№ 23Күрделі Обозначим через ДЕЛ($n,m$) утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наибольшего натурального числа $A$ логическое выражение…
- 1
Импликация $P \to Q$ ложна только тогда, когда $P=1$, а $Q=0$. Внутренняя импликация ложна при одновременном выполнении условий $\mathrm{ДЕЛ}(x,14)$ и $\mathrm{ДЕЛ}(x,4)$.$$\mathrm{ДЕЛ}(x,14) \land \mathrm{ДЕЛ}(x,4)$$
- 2
Число $x$ должно делиться на наименьшее общее кратное чисел $14$ и $4$.$$\operatorname{НОК}(14,4)=28$$
Ещё 2 қадам — толық шешімде