На числовой прямой даны два отрезка $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 шага — в полном решении
Исполнитель Вычислитель преобразует число, записанное на экране. Команды исполнителя: прибавить 1, прибавить 2 и умножить на 2. Сколько существует программ, которые исходное число 4 преобразуют в…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 4 в число $n$. Для перехода в $n$ последней могла быть команда прибавления 1, прибавления 2 или умножения на 2.$$f(n)=f(n-1)+f(n-2)+f(n/2)$$
- 2
Последнее слагаемое учитывается только для чётных $n$. Получаем значения до числа 11:$$f(4)=1,\ f(5)=1,\ f(6)=2,\ f(7)=3,\ f(8)=6,\ f(9)=9,\ f(10)=16,\ f(11)=25$$
Ещё 3 шага — в полном решении
Исполнитель преобразует число на экране. У исполнителя есть три команды: прибавить 1, умножить на 2 и умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует…
- 1
Введём динамическое программирование: для каждого числа считаем количество программ, которые приводят к нему. Последний шаг в такую точку мог быть выполнен командами $+1$, $\times 2$ или $\times 3$.
- 2
Посчитаем количество способов попасть из 1 в 11. Для числа $n$ учитываются переходы из $n-1$, $n/2$ и $n/3$, если соответствующие значения являются целыми.
Ещё 2 шага — в полном решении
Восемь школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы: Соня: «Это…
- 1
Проверим вариант, при котором окно разбила Аня. Тогда высказывание Сони ложно, поскольку разбивал не Володя.
- 2
Высказывание Миши истинно: утверждение Сони действительно является ложью.
Ещё 3 шага — в полном решении
Сколько существует различных наборов значений логических переменных $x_1, x_2, \ldots, x_9, y_1, y_2, \ldots, y_9$, которые удовлетворяют всем перечисленным ниже условиям?…
- 1
Обозначим $a_i = x_i \land y_i$. По закону де Моргана каждое условие имеет вид:$$a_i \equiv \lnot a_{i+1}$$
- 2
Следовательно, значения $a_1, a_2, \ldots, a_9$ должны чередоваться. Возможны два варианта последовательности: начинающаяся с $1$ и начинающаяся с $0$.
Ещё 2 шага — в полном решении
Обозначим через $\mathrm{ДЕЛ}(n,m)$ утверждение «натуральное число $n$ делится без остатка на натуральное число $m$». Для какого наименьшего натурального числа $A$ логическое выражение…
- 1
Импликация ложна, когда её левая часть истинна, а правая — ложна.
- 2
Так как при истинности условия $\mathrm{ДЕЛ}(x,A)$ выражение $\neg\mathrm{ДЕЛ}(x,A)$ ложно, правая часть требует выполнения $\mathrm{ДЕЛ}(x,39)$.
Ещё 2 шага — в полном решении
Исполнитель Вычислитель преобразует число на экране. Он выполняет две команды: прибавить 1 и умножить на 2. Программа для Вычислителя — это последовательность команд. Сколько существует программ…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 1 в число $n$. Для нечётного $n$ последняя команда может быть только «прибавить 1», а для чётного — также «умножить на 2». Поэтому используем рекуррентное правило.$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$
- 2
Последовательно получаем значения: $f(1)=1$, $f(2)=2$, $f(3)=2$, $f(4)=4$, $f(5)=4$, $f(6)=6$, $f(7)=6$, $f(8)=10$, $f(9)=10$, $f(10)=14$.
Ещё 2 шага — в полном решении
Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды: прибавить 1, прибавить 2 и умножить на 2. Программа для исполнителя К17 — это последовательность команд…
- 1
Поскольку каждая команда увеличивает число, программа, содержащая в траектории числа 9 и 11, сначала должна попасть в 9, затем в 11.
- 2
Посчитаем динамически число способов попасть из 3 в каждое число с помощью команд «+1», «+2» и «×2». Для чисел от 3 до 9 получаем: $1, 1, 2, 4, 6, 11, 17$. Значит, $N(3 \to 9)=17$.$$N(x)=N(x-1)+N(x-2)+[x\ \text{чётно}]N\left(\frac{x}{2}\right)$$
Ещё 3 шага — в полном решении
Исполнитель преобразует число на экране. У исполнителя есть три команды, обозначенные латинскими буквами: A — прибавить 1, B — прибавить 2, C — умножить на 2. Программа для исполнителя — это…
- 1
Обозначим через $f(n)$ число способов получить число $n$ из 4, не попадая в 6. Для числа 6 полагаем $f(6)=0$, так как траектория не должна содержать 6.
- 2
Последовательно получаем значения: $f(4)=1$, $f(5)=1$, $f(6)=0$, $f(7)=1$, $f(8)=2$, $f(9)=3$, $f(10)=6$, $f(11)=9$, $f(12)=15$, $f(13)=24$, $f(14)=40$, $f(15)=64$.
Ещё 2 шага — в полном решении
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — вычти 2; B — найди целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько…
- 1
Так как траектория должна содержать число 8, каждую подходящую программу можно единственным образом разделить на путь от 36 до 8 и путь от 8 до 2.
- 2
Обозначим через $f(n)$ количество способов попасть из числа $n$ в 8. Для $n > 8$ используем переходы по командам A и B: $f(n)=f(n-2)+f(\lfloor n/2\rfloor)$, при этом $f(8)=1$. Последовательное вычисление даёт $f(36)=10$.
Ещё 2 шага — в полном решении