161ФИПИ A73FF2№ 23Күрделі Для какого наибольшего целого неотрицательного числа $A$ выражение $(y + 3x > A) \lor (x < 20) \lor (y < 20)$ тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных $x$ и…
- 1
Выражение может быть ложным только тогда, когда все три части дизъюнкции ложны. Из условий $x < 20$ и $y < 20$ получаем $x \geq 20$ и $y \geq 20$.$$x \geq 20,\quad y \geq 20$$
- 2
При таких неотрицательных целых $x$ и $y$ минимальное значение левой части первого неравенства достигается при $x = 20$ и $y = 20.$$y + 3x \geq 20 + 3 \cdot 20 = 80$$
Ещё 1 қадам — толық шешімде
162ФИПИ ACD12F№ 23Күрделі Обозначим через $m \mathbin{\&} n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$. Так, например, $14 \mathbin{\&} 5 = 1110_2 \mathbin{\&} 0101_2 = 0100_2 = 4$. Для какого наименьшего…
- 1
Представим числа $42$ и $34$ в двоичной системе:$$42 = 101010_2, \qquad 34 = 100010_2$$
- 2
Условие $x \mathbin{\&} 34 = 0$ означает, что в числе $x$ не могут быть установлены разряды, соответствующие единицам числа $34$: разряды $2^1$ и $2^5$.
Ещё 2 қадам — толық шешімде
163ФИПИ AD945C№ 23Күрделі Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наибольшего натурального числа $A$ логическое выражение…
- 1
Импликация может быть ложной только тогда, когда её заключение ложно. Заключение $\neg\mathrm{ДЕЛ}(x,16) \lor \neg\mathrm{ДЕЛ}(x,24)$ ложно, если $x$ делится и на $16$, и на $24$.$$\operatorname{НОК}(16,24)=48$$
- 2
Следовательно, опасными являются все значения $x$, кратные $48$. Для них условие импликации должно быть ложным, то есть $x$ должно делиться на $A$.
Ещё 1 қадам — толық шешімде
164ФИПИ ADD016№ 23Күрделі Миша заполнял таблицу истинности функции $(x \land y) \lor (y \equiv z) \lor w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует…
- 1
Во всех трёх строках значение функции равно 0. Следовательно, $w=0$, $x \land y=0$, а $y \equiv z=0$, то есть $y$ и $z$ имеют разные значения.$$(x \land y) \lor (y \equiv z) \lor w = 0$$
- 2
В первой строке значения в столбцах 2 и 3 равны 1 и 0. Они должны соответствовать $z$ и $y$, поскольку эти значения различны. Сопоставление с другими строками показывает, что столбец 2 — это $z$, а столбец 3 — $y$.
Ещё 2 қадам — толық шешімде
165ФИПИ AE05AE№ 23Күрделі Миша заполнял таблицу истинности функции $(x \land \neg y) \lor (y \equiv z) \lor w$, но успел заполнить лишь фрагменты из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Проверим соответствие столбцов $w$, $y$, $x$, $z$. В первой строке получаем $w=0$, $y=1$, $x=1$, $z=0$.$$(x \land \neg y) \lor (y \equiv z) \lor w = (1 \land \neg 1) \lor (1 \equiv 0) \lor 0 = 0$$
- 2
Во второй строке известны $y=1$ и $x=0$. Чтобы значение функции было равно 0, необходимо $w=0$ и $z=0$.$$(0 \land \neg 1) \lor (1 \equiv 0) \lor 0 = 0$$
Ещё 2 қадам — толық шешімде
166ФИПИ B0D129№ 23Күрделі Миша заполнял таблицу истинности логической функции $F = \neg(w \to y) \mathbin{\lor} (x \to z) \mathbin{\lor} \neg x$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав…
- 1
Преобразуем условие $F = 0$. Дизъюнкция равна нулю только тогда, когда каждый её элемент равен нулю.$$F = (w \land \neg y) \lor (\neg x \lor z) \lor \neg x$$
- 2
Из равенства $\neg x = 0$ получаем $x = 1$. В таблице только первый столбец не содержит известных нулей, поэтому переменной $x$ соответствует первый столбец.
Ещё 2 қадам — толық шешімде
167ФИПИ B3B99C№ 23Күрделі На числовой прямой даны два отрезка: $P = [15; 40]$ и $Q = [21; 63]$. Укажите наименьшую возможную длину такого отрезка $A$, для которого логическое выражение…
- 1
Если $x \notin P$, первая импликация истинна автоматически. Поэтому достаточно рассмотреть точки $x \in P$.$$x \in P \Rightarrow (((x \in Q) \land \neg(x \in A)) \to \neg(x \in P))$$
- 2
При $x \in P$ заключение внутренней импликации $\neg(x \in P)$ ложно. Чтобы импликация была истинной, её условие должно быть ложным: точка не может одновременно принадлежать $Q$ и не принадлежать $A$.$$(x \in P) \land (x \in Q) \Rightarrow x \in A$$
Ещё 2 қадам — толық шешімде
168ФИПИ B52794№ 23Күрделі Для какого наименьшего целого неотрицательного числа $A$ выражение $(y + 2x < A) \lor (x > 25) \lor (y > 30)$ тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных $x$ и…
- 1
Чтобы дизъюнкция могла быть ложной, второе и третье высказывания должны быть ложными: $x \leq 25$ и $y \leq 30$.
- 2
При этих ограничениях максимальное значение выражения $y + 2x$ достигается при $x = 25$ и $y = 30$.$$y + 2x = 30 + 2 \cdot 25 = 80$$
Ещё 1 қадам — толық шешімде
169ФИПИ B572A7№ 23Күрделі Миша заполнял таблицу истинности функции $\neg(y \to (x \equiv w)) \land (z \to x)$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует…
- 1
Чтобы функция $\neg(y \to (x \equiv w)) \land (z \to x)$ была равна 1, оба множителя должны быть равны 1. Условие $\neg(y \to (x \equiv w))=1$ означает $y=1$ и $x \ne w$.
- 2
Рассмотрим третью строку фрагмента: значения во втором, третьем и четвёртом столбцах равны $0$, $1$, $0$. Так как $y=1$, третий столбец соответствует $y$. При этом второй столбец со значением $0$ должен соответствовать $x$, а первый…
Ещё 1 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = \neg(x \to z) \mathbin{\lor} (y \to w) \mathbin{\lor} \neg y$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав…
- 1
Преобразуем отрицание импликации и импликацию $y \to w$: $\neg(x \to z) = x \mathbin{\land} \neg z$, $y \to w = \neg y \mathbin{\lor} w$.$$\ F = (x \mathbin{\land} \neg z) \mathbin{\lor} \neg y \mathbin{\lor} w$$
- 2
Чтобы значение функции было равно нулю, необходимо, чтобы все три дизъюнкта были ложны. Поэтому $y = 1$, $w = 0$, а $x \mathbin{\land} \neg z = 0$, то есть $x = 0$ или $z = 1$.
Ещё 1 қадам — толық шешімде
171ФИПИ B5D233№ 23Күрделі Миша заполнял таблицу истинности логической функции $F = ((w \to z) \to x) \lor \lnot y$, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы соответствует…
- 1
Во всех указанных строках значение функции равно нулю. Обозначим $A = (w \to z) \to x$. Тогда $A \lor \lnot y = 0$ возможно только при $A = 0$ и $y = 1$.$$y = 1$$
- 2
Импликация $(w \to z) \to x$ равна нулю только тогда, когда её левая часть равна единице, а $x = 0$. Следовательно, в каждой из строк $x = 0$.$$w \to z = 1,\quad x = 0$$
Ещё 2 қадам — толық шешімде
172ФИПИ B60549№ 23Күрделі Миша заполнял таблицу истинности функции $(\neg x \land \neg y) \lor (y \equiv z) \lor w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Во всех трёх строках значение функции равно 0. Дизъюнкция может быть равна 0 только тогда, когда каждый её компонент равен 0.$$(\neg x \land \neg y)=0,\quad (y\equiv z)=0,\quad w=0$$
- 2
Переменная $w$ должна иметь значение 0 во всех трёх строках. Только второй столбец содержит известные нули во всех строках, значит, второй столбец соответствует $w$.$$w=0$$
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности функции $F=(x\lor\neg y)\land\neg(y\equiv z)\land w$, но успел заполнить лишь фрагмент из трёх различных её строк, не указав, какому столбцу таблицы соответствует…
- 1
Так как значение функции равно 1 во всех трёх строках, множитель $w$ должен быть равен 1 в каждой строке. Следовательно, столбец с постоянным значением 1 — второй.$$w=1$$
- 2
Условие $\neg(y\equiv z)=1$ означает, что значения $y$ и $z$ различаются. В первой строке после учёта $w=1$ имеем $x=0$, $y=0$, поэтому $z=0$. Во второй строке $z=1$, $y=0$, а в третьей строке $z=0$, $y=1$.$$\neg(y\equiv z)=1\iff y\ne z$$
Ещё 1 қадам — толық шешімде
174ФИПИ B7AB83№ 23Күрделі Миша заполнял таблицу истинности функции $ (\neg x \lor \neg y) \land \neg(y \equiv z) \land \neg w $, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу…
- 1
Во всех трёх строках функция равна 1, поэтому каждый множитель выражения истинен. Из $\neg w=1$ получаем $w=0$.
- 2
Из $\neg(y \equiv z)=1$ следует, что значения $y$ и $z$ различаются.
Ещё 2 қадам — толық шешімде
175ФИПИ BA3F5F№ 23Күрделі Для какого наибольшего целого неотрицательного числа $A$ логическое выражение $(2x+y\ne 50) \lor (x<y) \lor (A<x)$ истинно при любых целых неотрицательных $x$ и $y$?
- 1
Логическое выражение может быть ложным только тогда, когда ложны все три его части.$$(2x+y\ne 50)=0,\quad (x<y)=0,\quad (A<x)=0$$
- 2
Это равносильно системе условий:$$2x+y=50,\quad x\ge y,\quad A\ge x$$
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности функции $(x \lor \neg y) \land \neg(y \equiv z) \land w$, но успел заполнить лишь фрагменты из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Функция равна 1 во всех трёх строках. Поэтому множитель $w$ должен быть равен 1 во всех строках. Единственный подходящий столбец — второй.
- 2
Множитель $\neg(y \equiv z)$ равен 1, когда значения $y$ и $z$ различаются. В первой строке третий и четвёртый столбцы равны 0, поэтому первый из них должен содержать значение 1, а второй — значение 0.
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = (w \to \neg(z \to x)) \lor y$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 1
Функция является дизъюнкцией. Чтобы получить $F = 0$, оба слагаемых должны быть равны нулю, поэтому $y = 0$ и $w \to \neg(z \to x) = 0$.$$F = 0 \Rightarrow y = 0$$
- 2
Импликация ложна только тогда, когда её первый аргумент равен $1$, а второй — $0$. Следовательно, $w = 1$ и $\neg(z \to x) = 0$, то есть $z \to x = 1$.$$w \to \neg(z \to x) = 0 \Rightarrow w = 1,\ z \to x = 1$$
Ещё 2 қадам — толық шешімде
Миша заполнял таблицу истинности логической функции $F = (x \lor \neg y) \land \neg(y \equiv z) \land w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу…
- 1
Так как во всех трёх строках $F = 1$, каждый множитель функции должен быть равен 1. В частности, $w = 1$ во всех строках.
- 2
Переменная $w$ не может соответствовать первому или четвёртому столбцу: в первом столбце есть значение 0, а четвёртый столбец содержит значения 1, неизвестное значение и 0. Следовательно, $w$ соответствует третьему столбцу.
Ещё 2 қадам — толық шешімде
179ФИПИ BFA504№ 23Күрделі Логическая функция $F$ задаётся выражением $\neg x \lor y \lor (\neg z \land w)$. В таблице приведены все наборы аргументов, при которых функция $F$ ложна. Определите, какому столбцу таблицы…
- 1
Функция ложна, поэтому все части дизъюнкции равны нулю:$$\neg x = 0,\quad y = 0,\quad \neg z \land w = 0$$
- 2
Из условия $\neg x = 0$ получаем $x = 1$. Во всех трёх строках единица стоит во втором столбце, значит второй столбец соответствует переменной $x$.
Ещё 3 қадам — толық шешімде
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным условиям? Для каждого $i=1,2,\ldots,6$…
- 1
Обозначим состояние на шаге $i$ парой $(x_i,y_i)$. Возможны состояния $00$, $01$, $10$, $11$.
- 2
Из условия $\bigl(x_i \to (x_{i+1} \land y_i)\bigr) \land (y_i \to y_{i+1})=1$ получаем переходы между состояниями: $00\to00,01,10,11$; $01\to01,11$; $10\to11$; $11\to11$.
Ещё 2 қадам — толық шешімде