Сколько существует различных наборов значений логических переменных $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 қадам — толық шешімде
Исполнитель Вычислитель преобразует число, записанное на экране. Он умеет выполнять команды: прибавить 1, прибавить 2 и умножить на 3. Программа для Вычислителя — это последовательность команд…
- 1
Обозначим через $f(n)$ число программ, переводящих число 1 в число $n$. В число $n$ можно попасть командами «прибавить 1» и «прибавить 2», а также командой умножения на 3, если $n$ делится на 3.$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/3),& n\mathbin{\vdots}3\\0,& n\text{ не делится на }3\end{cases}$$
- 2
Последовательно вычисляя значения, получаем: $f(1)=1$, $f(2)=1$, $f(3)=3$, $f(4)=4$, $f(5)=7$, $f(6)=12$, $f(7)=19$, $f(8)=31$, $f(9)=53$.
Ещё 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 қадам — толық шешімде
Обозначим через ДЕЛ($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 қадам — толық шешімде
Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наименьшего натурального числа $A$ формула…
- 1
Импликация $P \to Q$ ложна только при истинном $P$ и ложном $Q$. Поэтому первая часть формулы ложна, если $x$ делится на $3$ и одновременно делится на $5$.$$\mathrm{ДЕЛ}(x,3) \land \mathrm{ДЕЛ}(x,5)$$
- 2
Значит, $x$ должно быть кратно $15$. Наименьшее натуральное проблемное значение — $x=15$.
Ещё 3 қадам — толық шешімде
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды: умножить число на 3, прибавить 2, прибавить 3. Программа для Вычислителя — это последовательность…
- 1
Поскольку все команды увеличивают число, число 12 в траектории может встретиться только один раз. Поэтому число искомых программ равно произведению числа программ из 2 в 12 и числа программ из 12 в 21.$$N = N_{2\to12} \cdot N_{12\to21}$$
- 2
Для подсчёта используем динамическое программирование. Для каждой точки складываем количества способов попасть в неё командами «прибавить 2», «прибавить 3» и «умножить на 3», если соответствующий переход возможен.$$f(x)=f(x-2)+f(x-3)+\begin{cases}f(x/3),&x\mathrel{\vdots}3\\0,&\text{иначе}\end{cases}$$
Ещё 3 қадам — толық шешімде
Миша заполнял таблицу истинности функции $(\neg x \land \neg y) \lor (x \equiv z) \lor \neg w$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…
- 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
Во второй строке при таком порядке получаем $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
Если $x \notin P$, внешняя импликация истинна автоматически. Поэтому рассматриваем только значения $x \in P$.$$x \in P$$
- 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
Функция равна 0 во всех трёх строках. Так как в выражении есть дизъюнкция слагаемого $w$, во всех строках должно выполняться $w=0$. Нулевые значения во всех строках находятся в первом столбце, значит первый столбец — это $w$.$$w=0$$
- 2
Во второй и третьей строках второй столбец принимает значения 1 и 0, а третий столбец — значения 0 и 1 соответственно после восстановления пропуска. Эти столбцы должны соответствовать переменным $z$ и $y$, причём $y \ne z$.
Ещё 1 қадам — толық шешімде
Исполнитель Плюс преобразует число на экране. У исполнителя есть две команды: прибавить 2 и прибавить 5. Программа для исполнителя Плюс — это последовательность команд. Сколько существует программ…
- 1
Общая величина увеличения числа должна составить $20 - 1 = 19$.
- 2
Пусть команда «прибавить 2» выполнена $a$ раз, а команда «прибавить 5» — $b$ раз. Тогда $2a + 5b = 19$.
Ещё 4 қадам — толық шешімде
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_7, y_1, y_2, \ldots, y_7$, которые удовлетворяют всем перечисленным условиям? $x_1 \to y_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
Для каждой следующей пары $(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
Во всех трёх строках значение функции равно 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
Сопоставляем известные нули и единицы в трёх строках с этими условиями. Единственное соответствие, согласующее все строки фрагмента, имеет вид: первый столбец — $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
Так как значение функции во всех трёх строках равно 0, каждое из слагаемых дизъюнкции должно быть равно 0.$$F=0 \Rightarrow (\neg x\land\neg y)=0,\quad (x\equiv z)=0,\quad w=0$$
- 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
Чтобы всё выражение могло быть ложным, каждое из трёх высказываний должно быть ложным. Из условия $8 \ge x$ получаем $x > 8$, а из условия $x > y$ получаем $x \le y$.$$x \ge 9,\quad y \ge x$$
- 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. Поэтому $\neg w=1$, то есть $w=0$, а $\neg(y \equiv z)=1$, то есть $y$ и $z$ имеют разные значения.$$\neg w=1,\quad y\ne z$$
- 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.$$(x \lor \neg y) = 1,\quad \neg(x \equiv z) = 1,\quad w = 1$$
- 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
Дизъюнкция может быть ложной только тогда, когда обе её части ложны. В частности, первая часть ложна, если импликация ложна.$$(\mathrm{ДЕЛ}(x,2) \to \neg\mathrm{ДЕЛ}(x,3)) = 0$$
- 2
Импликация ложна, когда её условие истинно, а заключение ложно: число $x$ должно делиться и на 2, и на 3. Значит, $x$ кратно 6.
Ещё 2 қадам — толық шешімде
Для какого наибольшего целого неотрицательного числа $A$ выражение $(69 \ne y + 2x) \vee (A < x) \vee (A < y)$ тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных $x$…
- 1
Дизъюнкция может принимать значение 0 только тогда, когда все три её части ложны. Поэтому должны выполняться условия:$$y + 2x = 69,\quad x \leq A,\quad y \leq A$$
- 2
Чтобы выражение было тождественно истинным, нужно выбрать $A$ меньше минимально возможного значения $\max(x,y)$ среди неотрицательных решений уравнения $y + 2x = 69$.
Ещё 2 қадам — толық шешімде