desktop/inf.jpg mobile/inf.jpg

Задание 23. Алгебра логики. Системы логических уравнений. ЕГЭ 2021 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 10 минут. Уровень сложности: высокий.
Средний процент выполнения: 25.4%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.

Задачи для практики

Задача 1

У исполнителя Увеличитель две команды, которым присвоены номера:

1. Прибавь 2,

2. Увеличь цифру в старшем разряде числа на 1.

Первая из них увеличивает данное число на 2, вторая — увеличивает цифру в старшем разряде числа на 1, например, число 34 с помощью этой команды превратится в число 44. Программа для исполнителя Увеличитель — это последовательность команд.

Определите количество программ, которые число 20 преобразуют в число 44.

Решение

Будем решать поставленную задачу последовательно для чисел 20, 21, 22, . . . , 44 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 20 в число n, будем обозначать через R(n). Будем считать, что R(20) = 1. Заметим, что команда 2 для чисел, меньших 90, соответствует условию «прибавь 10». С помощью каждой из команд 1 и 2, применяя их последовательно к числам, получаемым из числа 29, можно получить только чётные числа. Числа 20, 22, . . . , 28 можно получить из предыдущего числа только с помощью команды 1. Значит, количество искомых программ для каждого из таких чисел равно количеству программ для предыдущего числа: R(i) = R(i − 2), i—чётное, 22 ≤ i ≤ 28.

Получаем R(20) = R(22) = · · · = R(28) = 1. Для чисел, больших 28 и не превосходящих 44, вариантов последней команды два: прибавь 2 и прибавь 10, то есть R(i) = R(i − 2) + R(i − 10), i — чётное, 30 ≤ i ≤ 44. Заполним соответствующую таблицу по приведённым формулам слева направо:

20 22 24 26 28 30 32 34 36 38 40 42 44
1 1 1 1 1 2 3 4 5 6 8 11 15
Ответ: 15
Показать решение
Полный курс

Задача 2

У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 2,

2. умножь на 5.

Первая из них увеличивает данное число на 2, вторая — увеличивает его в 5 раз. Программа для исполнителя Удвоитель — это последовательность команд.

Определите количество программ, которые число 1 преобразуют в число 37.

Решение

Заметим, что все числа, получаемые с помощью заданных команд из числа 1, — нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 37 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 5, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i − 2), i — нечётное. Если число на 5 делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда R(i) = R(i−2)+R(i/5), i — нечётное. Заполним соответствующую таблицу по приведенным формулам слева направо:

1 3 5 7 9 11 13 15 17 19 21 23 25 27
1 1 2 2 2 2 2 3 3 3 3 3 5 5
29 31 33 35 37                  
5 5 5 7 7                  
Ответ: 7
Показать решение
Полный курс

Задача 3

Сколько существует различных наборов значений логических переменных $x_1, x_2, . . . x_{10}$, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\((x_1 ≡ x_2) ∧ (¬x_3 ≡ x_4)) ∨ ((¬x_1 ∧ ¬x_2) ∧ (¬x_3 ≡ x_4)) = 0; \((x_3 ≡ x_4) ∧ (¬x_5 ≡ x_6)) ∨ ((¬x_3 ∧ ¬x_4) ∧ (¬x_5 ≡ x_6)) = 0; \((x_5 ≡ x_6) ∧ (¬x_7 ≡ x_8)) ∨ ((¬x_5 ∧ ¬x_6) ∧ (¬x_7 ≡ x_8)) = 0; \((x_7 ≡ x_8) ∧ (¬x_9 ≡ x_{10})) ∨ ((¬x_7 ∧ ¬x_8) ∧ (¬x_9 ≡ x_10)) = 0;$

Решение

При рассмотрении решения задачи с целью исключения путаницы в качестве знака тождественного преобразования и тождественного равенства используется символ «=», а в качестве знака эквиваленции — «≡».

1. Преобразуем первое уравнение системы: $((x_1 ≡ x_2) ∧ (¬x_3 ≡ x_4)) ∨ ((¬x_1 ∧ ¬x_2) ∧ (¬x_3 ≡ x_4)) = 0.$

Применяя к этому уравнению дистрибутивный закон $F ∧ (G ∨ Q) = (F ∧ G) ∨ (F ∧ Q)$, получим:

$((x_1 ≡ x_2) ∨ (¬x_1 ∧ ¬x_2)) ∧ (¬x_3 ≡ x_4) = 0.$

2. Покажем, что $x_1 ≡ x_2 = (¬x_1 ∧ ¬x_2) ∨ (x_1 ∧ x_2)$.

На основании законов алгебры логики преобразуем левую часть этого выражения:

Преобразование левой части первого выражения Закон логики, применяемый к предыдущему выражению
$x_1 ≡ x_2 =$  
$(x_1 → x_2) ∧ (x_2 → x_1) =$ Правило исключения эквиваленции
$(¬x_1 ∨ x_2) ∧ (¬x_2 ∨ x_1) =$ Правило исключения импликации
$F → G = ¬F ∨ G$
$(¬x_1 ∧ ¬x_2) ∨ (x_2 ∧ ¬x_2) ∨ (¬x_1 ∧ x_1) ∨ (x_2 ∧ x_1) =$ Дистрибутивный закон
$F ∨ (G ∧ Q) = (F ∨ G) ∧ (F ∨ Q)$
$(¬x_1 ∧ ¬x_2) ∨ 0 ∨ 0 ∨ (x_2 ∨ x_1) =$ Закон противоречия
$F ∧ ¬F = 0$
$(¬x_1 ∧ ¬x_2) ∨ (x_2 ∨ x_1)$ Тождество
$F ∨ 0 = F$

3. Подставляя в выражение вместо $x_1 ≡ x_2$ правую часть выражения, получим $((¬x_1 ∧ ¬x_2) ∨ (x_1 ∧ x_2) ∨ (¬x_1 ∧ ¬x_2)) ∧ (¬x_3 ≡ x_4) = 0$.

Учитывая идемпотентность операции $∨ (F ∨ F = F)$, получим: $((¬x_1 ∧ ¬x_2) ∨ (x_1 ∧ x_2)) ∧ (¬x_3 ≡ x_4) = 0$.

Повторно применяя к этому выражению преобразование, находим, что первое уравнение исходной системы принимает вид: $(x_1 ≡ x_2) ∧ (¬x_3 ≡ x_4) = 0$.

3. Так как остальные уравнения отличаются от первого только индексами, то исходная система уравнений принимает вид:

$\{\table\(x_1 ≡ x_2) ∧ (¬x_3 ≡ x_4) = 0; /(x_3 ≡ x_4) ∧ (¬x_5 ≡ x_6) = 0; \(x_5 ≡ x_6) ∧ (¬x_7 ≡ x_8) = 0; \(x_7 ≡ x_8) ∧ (¬x_9 ≡ x_10) = 0;$

Далее для полученного уравнения представлены два способа решения.

Логическая переменная x1 может принимать одно из двух возможных значений: 0 или 1.

1) Рассмотрим для каждого из этих значений, какие значения могут принимать логические переменные x2, x3, x4, чтобы первое уравнение системы было ложным.

1.1) Если значения переменных x1 и x2 совпадают, то высказывание x1 ≡ x2 истинно. Значит, высказывание (x1 ≡ x2) ∧ (¬x3 ≡ x4) ложно только в случае, когда x3 = x4. Количество пар значений (x1; x2), у которых значения совпадают, равно 2: (0; 0), (1; 1).Следовательно, количество соответствующих им пар, содержащих переменные x3 и x4, равно 4 = 2·2: (0; 0; 0; 0), (0; 0; 1; 1), (1; 1; 0; 0), (1; 1; 1; 1).

1.2) Если же значения переменных x1 и x2 различны, то высказывание x1 ≡ x2 ложно, и значит (x1 ≡ x2) ∧ (¬x3 ≡ x4) ложно при любых значениях логических переменных x3 и x4. Количество пар значений (x1; x2), у которых значения различны, равно 2: (0; 1), (1; 0). Количество соответствующих им пар, содержащих переменные x3 и x4, увеличивается в 4 раза: 2 · 4 = 8.

Изобразим полученные значения в виде схемы:

Заметим, что количество пар значений (x3; x4), у которых значения совпадают, равно 2·4 = 8 — удвоенному количеству пар значений (x1; x2). А количество пар значений (x3; x4), у которых значения различны, равно 2 · 2 = 4 — удвоенному количеству пар различных значений (x1; x2).

Таким образом, для каждого набора значений логических переменных x1 и x2 количество наборов, содержащих переменные x3 и x4, равно 2 · 4 + 2 · 2 = 8 + 4 = 12.

2) Второе уравнение системы содержит две переменные x5 и x6, не входящие в первое уравнение. Это уравнение отличается от первого только тем, что индексы входящих в него переменных на два больше.

Поэтому все рассуждения, приведённые для первого уравнения, имеют место и для второго уравнения. А именно для каждого набора значений логических переменных x3 и x4 количество наборов, содержащих переменные x5 и x6, равно 2 · 12 + 2 · 4 = 24 + 8 = 32 (сумма удвоенного количества пар значений (x3; x4), у которых значения совпадают, и удвоенного количество пар значений (x3; x4), у которых значения различны,).

3) Третье и последующие уравнения системы отличаются от предыдущего только тем, что индексы входящих в них переменных на два больше, и каждое следующее уравнение системы содержит две переменные, не входящие в предыдущее уравнение.

Следовательно, количество различных наборов логических переменных, входящих в эти уравнения, изменяется по тем же правилам.

Количество пар, у которых значения: (x1; x2) (x3; x4) (x5; x6) (x7; x8) (x9; x10)
– совпадают 2 2 · 4 = 8 2 · 12 = 24 2 · 32 = 64 2 · 80 = 160
– различны 2 2 · 2 = 4 2 · 4 = 8 2 · 8 = 16 2 · 16 = 32
Всего наборов 4 12 32 80 192

Следовательно, количество различных наборов логических переменных, удовлетворяющих всем перечисленным в условии уравнениям, равно 192.

Ответ: 192
Показать решение
Полный курс

Задача 4

Сколько существует различных наборов значений логических переменных x1, x2, . . . , x10, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\¬(x_1 ≡ x_2) ∧ ((x_1 ∧ ¬x_3) ∨ (¬x_1 ∧ x_3)) = 0; \¬(x_2 ≡ x_3) ∧ ((x_2 ∧ ¬x_4) ∨ (¬x_2 ∧ x_4)) = 0; \. . .; \¬(x_8 ≡ x_9) ∧ ((x_8 ∧ ¬x_{10}) ∨ (¬x_8 ∧ x_{10})) = 0;$

В ответе не нужно перечислять все различные наборы значений x1, x2, . . . , x10, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение

1) На основании законов алгебры логики преобразуем левую часть первого выражения (с целью исключения путаницы в качестве знака тождественного преобразования используется символ «=»).

Преобразование левой части первого выражения Закон логики, применяемый к предыдущему выражению
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) =  
¬(x1 ≡ x2)∧¬¬((x1∧¬x3)∨(¬x1∧x3)) = Закон двойного отрицания
¬¬F ≡ F
¬(x1 ≡ x2)∧¬(¬(x1∧¬x3)∧¬(¬x1∧x3) = Закон де Моргана
¬(F ∨ G) ≡ ¬F ∧ ¬G
¬(x1 ≡ x2) ∧ ¬(¬x1 ∨ x3) ∧ (x1 ∨ ¬x3) = Закон де Моргана
¬(F ∧ G) ≡ ¬F ∨ ¬G
¬(x1 ≡ x2) ∧ ¬(¬x1 ∨ x3) ∧ (¬x3 ∨ x1) = Коммутативность операции ∧
F ∧ G ≡ G ∧ F
¬(x1 ≡ x2) ∧ ¬(x1 → x3) ∧ (x3 → x1) = Правило исключения импликации
F → G ≡ ¬F ∨ G
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = Правило исключения эквиваленции
F ↔ G ≡ (F → G) ∧ (G → F)
¬((x1 ≡ x2) ∨ (x1 ≡ x3)) Закон де Моргана
¬(F ∧ G) ≡ ¬F ∨ ¬G

Таким образом, первое уравнение принимает вид: ¬((x1 ≡ x2) ∨ (x1 ≡ x3)) = 0.

Применяя отрицание к обеим частям, получаем: ¬¬((x1 ≡ x2) ∨ (x1 ≡ x3)) = ¬0.

Отсюда, (x1 ≡ x2) ∨ (x1 ≡ x3) = 1.

Так как остальные уравнения отличаются от первого только индексами, то исходная система уравнений принимает вид:

(x1 ≡ x2) ∨ (x1 ≡ x3) = 1,

(x2 ≡ x3) ∨ (x2 ≡ x4) = 1,

. . .

(x8 ≡ x9) ∨ (x9 ≡ x10) = 1.

2) Первое уравнение системы представляет собой дизъюнкцию двух высказываний. Дизъюнкция истинна (равна единице) только в том случае, когда хотя бы одно из высказываний, связанных дизъюнкцией, истинно.

Значит, должно выполняться (x1 ≡ x2) = 1 или (x1 ≡ x3) = 1.

Если x1 = x2, то высказывание x1 ≡ x2 истинно. Следовательно, при любых значениях x3 истинно высказывание (x1 ≡ x2) ∨ (x1 ≡ x3).

Если x1 ≠ x2, то высказывание x1 ≡ x2 ложно. Следовательно, высказывание (x1 ≡ x2)∨(x1 ≡ x3) истинно, только в случае, когда x1 = x3. Изобразим полученные значения в виде схемы.

Таким образом, количество наборов логических переменных, удовлетворяющих первому уравнению рассматриваемой системы, равно 6 = 2 · 3 (где 3 — количество переменных, содержащихся в уравнении).

Так как следующие уравнения отличаются от первого только индексами (в каждом последующем уравнении индекс на 1 больше, чем в предыдущем), то мы видим, что для каждого последующего уравнения количество наборов переменных, удовлетворяющих рассматриваемому уравнению и предыдущим, увеличивается на 2.

Так, для второго уравнения количество наборов равно 8 (равно удвоенному индексу новой переменной).

Для третьего — 10 и т. д. Для восьмого — 20.

Ответ: 20
Показать решение
Полный курс

Задача 5

Сколько существует различных наборов значений логических переменных $x_1, x_2, . . . x_{10}$, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\((x_1 ≡ x_2 ) ∧ (¬x_3 ≡ x_4 )) ∨ ((¬x_1 ∧ ¬x_2) ∧ (¬x_3 ≡ x_4)) = 0; \((x_3 ≡ x_4) ∧ (¬x_5 ≡ x_6)) ∨ ((¬x_3 ∧ ¬x_4) ∧ (¬x_5 ≡ x_6)) = 0; \((x_5 ≡ x_6) ∧ (¬x_7 ≡ x_8)) ∨ ((¬x_5 ∧ ¬x_6) ∧ (¬x_7 ≡ x_8)) = 0; \((x_7 ≡ x_8) ∧ (¬x_9 ≡ x_{10})) ∨ ((¬x_7 ∧ ¬x_8) ∧ (¬x_9 ≡ x_{10})) = 0.;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2, . . . x_{10}$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение

При рассмотрении решения задачи с целью исключения путаницы в качестве знака тождественного преобразования и тождественного равенства используется символ «=», а в качестве знака эквиваленции — «≡». 1. Преобразуем первое уравнение системы:

((x1 ≡ x2) ∧ (¬x3 ≡ x4)) ∨ ((¬x1 ∧ ¬x2) ∧ (¬x3 ≡ x4)) = 0.

Применяя к этому уравнению дистрибутивный закон F ∧ (G ∨ Q) = (F ∧ G) ∨ (F ∧ Q), получим:

((x1 ≡ x2) ∨ (¬x1 ∧ ¬x2)) ∧ (¬x3 ≡ x4) = 0. (1)

2. Покажем, что

x1 ≡ x2 = (¬x1 ∧ ¬x2) ∨ (x1 ∧ x2). (2)

На основании законов алгебры логики преобразуем левую часть этого выражения:

Преобразование левой части первого выражения Закон логики, применяемый к предыдущему выражению
x1 ≡ x2 =  
(x1 → x2) ∧ (x2 → x1) = Правило исключения эквиваленции
(¬x1 ∨ x2) ∧ (¬x2 ∨ x1) = Правило исключения импликации
F → G = ¬F ∨ G
(¬x1 ∧ ¬x2) ∨ (x2 ∧ ¬x2)∨ (¬x1 ∧ x1) ∨ (x2 ∧ x1) = Дистрибутивный закон
F ∨ (G ∧ Q) = (F ∨ G) ∧ (F ∨ Q)
(¬x1 ∧ ¬x2) ∨ 0 ∨ 0 ∨ (x2 ∨ x1) = Закон противоречия F ∧ ¬F = 0
(¬x1 ∧ ¬x2) ∨ (x2 ∨ x1) Тождество
F ∨ 0 = F

3. Подставляя в выражение (1) вместо x1 ≡ x2 правую часть выражения (2), получим

((¬x1 ∧ ¬x2) ∨ (x1 ∧ x2) ∨ (¬x1 ∧ ¬x2)) ∧ (¬x3 ≡ x4) = 0.

Учитывая идемпотентность операции ∨ (F ∨ F = F), получим:

((¬x1 ∧ ¬x2) ∨ (x1 ∧ x2)) ∧ (¬x3 ≡ x4) = 0.

Повторно применяя к этому выражению преобразование (2), находим, что первое уравнение исходной системы принимает вид:

(x1 ≡ x2) ∧ (¬x3 ≡ x4) = 0.

4. Так как остальные уравнения отличаются от первого только индексами, то исходная система уравнений принимает вид:

$\{\table\(x_1 ≡ x_2) ∧ (¬x_3 ≡ x_4) = 0; \(x_3 ≡ x_4) ∧ (¬x_5 ≡ x_6) = 0; \(x_5 ≡ x_6) ∧ (¬x_7 ≡ x_8) = 0; \(x_7 ≡ x_8) ∧ (¬x_9 ≡ x_{10}) = 0;$

Далее для полученного уравнения представлены два способа решения.

Способ 1. Логическая переменная x1 может принимать одно из двух возможных значений: 0 или 1.

1) Рассмотрим для каждого из этих значений, какие значения могут принимать логические переменные x2, x3, x4, чтобы первое уравнение системы было ложным.

1.1) Если значения переменных x1 и x2 совпадают, то высказывание x1 ≡ x2 истинно. Значит, высказывание (x1 ≡ x2) ∧ (¬x3 ≡ x4) ложно только в случае, когда x3 = x4. Количество пар значений (x1; x2), у которых значения совпадают, равно 2: (0; 0), (1; 1). Следовательно, количество соответствующих им пар, содержащих переменные x3 и x4, равно 4 = 2 · 2: (0; 0; 0; 0), (0; 0; 1; 1), (1; 1; 0; 0), (1; 1; 1; 1).

1.2) Если же значения переменных x1 и x2 различны, то высказывание x1 ≡ x2 ложно, и значит (x1 ≡ x2) ∧ (¬x3 ≡ x4) ложно при любых значениях логических переменных x3 и x4. Количество пар значений (x1; x2), у которых значения различны, равно 2: (0; 1), (1; 0). Количество соответствующих им пар, содержащих переменные x3 и x4, увеличивается в 4 раза: 2 · 4 = 8.

Изобразим полученные значения в виде схемы 1:

Схема 1.

Заметим, что количество пар значений (x3; x4), у которых значения совпадают, равно 2 · 4 = 8 — удвоенному количеству пар значений (x1; x2). А количество пар значений (x3; x4), у которых значения различны, равно 2 · 2 = 4 — удвоенному количеству пар различных значений (x1; x2).

Таким образом, для каждого набора значений логических переменных x1 и x2 количество наборов, содержащих переменные x3 и x4, равно 2 · 4 + 2 · 2 = 8 + 4 = 12.

2) Второе уравнение системы содержит две переменные x5 и x6, не входящие в первое уравнение. Это уравнение отличается от первого только тем, что индексы входящих в него переменных на два больше.

Поэтому все рассуждения, приведённые для первого уравнения, имеют место и для второго уравнения. А именно для каждого набора значений логических переменных x3 и x4 количество наборов, содержащих переменные x5 и x6, равно 2 · 12 + 2 · 4 = 24 + 8 = 32 (сумма удвоенного количества пар значений (x3; x4), у которых значения совпадают, и удвоенного количество пар значений (x3; x4), у которых значения различны.

3) Третье и последующие уравнения системы отличаются от предыдущего только тем, что индексы входящих в них переменных на два больше, и каждое следующее уравнение системы содержит две переменные, не входящие в предыдущее уравнение.

Следовательно, количество различных наборов логических переменных, входящих в эти уравнения, изменяется по тем же правилам.

Количество пар, у которых значения: (x1; x2) (x3; x4) (x5; x6) (x7; x8) (x9; x10)
– совпадают 2 2 · 4 = 8 2 · 12 = 24 2 · 32 = 64 2 · 80 = 160
– различны 2 2 · 2 = 4 2 · 4 = 8 2 · 8 = 16 2 · 16 = 32
Всего наборов 4 12 32 80 192

Следовательно, количество различных наборов логических переменных, удовлетворяющих всем перечисленным в условии уравнениям, равно 192.

Ответ: 192
Показать решение
Полный курс

Задача 6

У исполнителя X157 три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 5

3. Умножь на 7

Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 20?

Решение
Ответ: 129
Показать решение
Полный курс

Задача 7

У исполнителя X135 три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 3

3. Умножь на 5

Первая из них увеличивает число на экране на 1, вторая — на 3, а третья — в 5 раз. Программа для исполнителя X135 — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 14?

Решение
Ответ: 110
Показать решение
Полный курс

Задача 8

Сколько существует различных наборов значений логических переменных $x_1, x_2$, . . . $x_6, x_7$, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\ ((x_1 ≡ x_2) ∧ (x_1 ≡ x_3)) ∨ ((x_2 ≡ x_3) ∧ (x_2 ≡ x_4)) = 0; \ ((x_2 ≡ x_3) ∧ (x_2 ≡ x_4)) ∨ ((x_3 ≡ x_4) ∧ (x_3 ≡ x_5)) = 0; \ ((x_3 ≡ x_4) ∧ (x_3 ≡ x_5)) ∨ ((x_4 ≡ x_5) ∧ (x_4 ≡ x_6)) = 0; \ ((x_4 ≡ x_5) ∧ (x_4 ≡ x_6)) ∨ ((x_5 ≡ x_6) ∧ (x_5 ≡ x_7)) = 0;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . $x_6, x_7$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 42
Показать решение
Полный курс

Задача 9

У исполнителя Увеличитель две команды, которым присвоены номера:

1. Прибавь 2

2. Умножь на 3

Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза. Программа для исполнителя Увеличитель—это последовательность команд.

Определите количество программ, которые число 1 преобразуют в число 37.

Решение
Ответ: 16
Показать решение
Полный курс

Задача 10

Сколько существует различных наборов значений логических переменных $x_1, x_2$, . . . $x_{10}$, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\ ((x_1 ≡ x_2) ∧ (¬x_3 ≡ x_4)) ∨ ((¬x_1 ∧ ¬x_2) ∧ (¬x_3 ≡ x_4)) = 0; \ ((x_3 ≡ x_4) ∧ (¬x_5 ≡ x_6)) ∨ ((¬x_3 ∧ ¬x_4) ∧ (¬x_5 ≡ x_6)) = 0; \ ((x_5 ≡ x_6) ∧ (¬x_7 ≡ x_8)) ∨ ((¬x_5 ∧ ¬x_6) ∧ (¬x_7 ≡ x_8)) = 0; \ ((x_7 ≡ x_8) ∧ (¬x_9 ≡ x_{10})) ∨ ((¬x_7 ∧ ¬x_8) ∧ (¬x_9 ≡ x_{10})) = 0;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . $x_{10}$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 192
Показать решение
Полный курс

Задача 11

Сколько существует различных наборов значений логических переменных $x_1, x_2$, . . . $x_7, x_8$, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\ ¬(x_1 ≡ x_2) ∧ (x_2 ∨ x_3) ∧ (¬x_2 ∨ ¬x_3) = 0; \ ¬(x_2 ≡ x_3) ∧ (x_3 ∨ x_4) ∧ (¬x_3 ∨ ¬x_4) = 0; \ . . .; \ ¬(x_6 ≡ x_7) ∧ (x_7 ∨ x_8) ∧ (¬x_7 ∨ ¬x_8) = 0;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . $x_7, x_8$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 68
Показать решение
Полный курс

Задача 12

У исполнителя X17 две команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 7

Первая из них увеличивает число на экране на 1, вторая — на 7. Программа для исполнителя X17—это последовательность команд.

Сколько существует программ, которые число 5 преобразуют в число 26, и при этом траектория вычислений содержит число 12?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1221 при исходном числе 3 траектория будет состоять из чисел 4, 11, 18, 19.

Решение
Ответ: 20
Показать решение
Полный курс

Задача 13

Сколько существует различных наборов значений логических переменных $x_1, x_2$, . . . , $x_{10}$, которые удовлетворяют всем перечисленным ниже условиям?

$\{\table\ ¬(x_1 ≡ x_2) ∧ ((x_1 ∧ ¬x_3) ∨ (¬x_1 ∧ x_3)) = 0; \ ¬(x_2 ≡ x_3) ∧ ((x_2 ∧ ¬x_4) ∨ (¬x_2 ∧ x_4)) = 0; \ . . .; \ ¬(x_8 ≡ x_9) ∧ ((x_8 ∧ ¬x_{10}) ∨ (¬x_8 ∧ x_{10})) = 0;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . , $x_{10}$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 20
Показать решение
Полный курс

Задача 14

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

$\{\table\ (y_1 ∧ (x_1 → y_2)) ∨ (x_1 ≡ x_2) = 1; \ (y_2 ∧ (x_2 → y_3)) ∨ (x_2 ≡ x_3) = 1; \ (y_3 ∧ (x_3 → y_4)) ∨ (x_3 ≡ x_4) = 1; \ (y_4 ∧ (x_4 → y_5)) ∨ (x_4 ≡ x_5) = 1;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . , $x_5, y_1, y_2$, . . . , $y_5$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 244
Показать решение
Полный курс

Задача 15

У исполнителя X125 три команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 2

3. Умножь на 5

Первая из них увеличивает число на экране на 1, вторая — в 2 раза, а третья — в 5 раз. Программа для исполнителя X125 — это последовательность команд.

Сколько существует программ, которые число 1 преобразуют в число 38, и при этом траектория вычислений содержит числа 10 и 20? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 2231 при исходном числе 5 траектория будет состоять из чисел 10, 20, 100, 101.

Решение
Ответ: 36
Показать решение
Полный курс

Задача 16

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

$\{\table\ (y_2 → (y_1 ∧ x_2)) ∧ (y_2 → x_1) = 1; \(y_3 → (y_2 ∧ x_3)) ∧ (y_3 → x_2) = 1; \(y_4 → (y_3 ∧ x_4)) ∧ (y_4 → x_3) = 1; \(y_5 → (y_4 ∧ x_5)) ∧ (y_5 → x_4) = 1;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . , $x_5, y_1, y_2$, . . . , $y_5$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 79
Показать решение
Полный курс

Задача 17

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

$\{\table\ (¬x_1 ∨ ¬x_2) ∧ ((x_1 ∧ x_2) → x_3) ∧ (¬x_3 ≡ y_1) = 1;\ (¬x_2 ∨ ¬x_3) ∧ ((x_2 ∧ x_3) → x_4) ∧ (¬x_4 ≡ y_2) = 1;\ . . .;\ (¬x_6 ∨ ¬x_7) ∧ ((x_6 ∧ x_7) → x_8) ∧ (¬x_8 ≡ y_6) = 1;\ (¬x_7 ∨ ¬x8) ∧ (¬y_7 ∨ y_8) = 1;$

В ответе не нужно перечислять все различные наборы значений $x_1, x_2$, . . . , $x_8, y_1, y_2$, . . . , $y_8$, при которых выполнима данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение
Ответ: 165
Показать решение
Полный курс

Задача 18

У исполнителя X132 три команды, которым присвоены номера:

1. Прибавь 1
2. Прибавь 3
3. Умножь на 2

Первая из них увеличивает число на экране на 1, вторая — на 3, а третья — в 2 раза. Программа для исполнителя X132— это последовательность команд.

Сколько существует программ, которые число 1 преобразуют в число 15, и при этом траектория вычислений содержит числа 6 и 10?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1323 при исходном числе 4 траектория будет состоять из чисел 5, 10, 13, 26.

Решение
Ответ: 132
Показать решение
Полный курс

Задача 19

У исполнителя A12M2 две команды, которым присвоены номера:

1. Прибавь 1
2. Прибавь 2
3. Умножь на 2

Программа для исполнителя A12M2 — это последовательность команд. Сколько существует программ, которые число 4 преобразуют в число 14, и при этом траектория вычислений содержит число 11?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 5, 6, 7.

Решение
Ответ: 75
Показать решение
Полный курс

Задача 20

У исполнителя А128 три команды, которым присвоены номера:

1. Прибавь 1
2. Прибавь 2
3. Прибавь 5

Первая из них увеличивает число на экране на 1, вторая — на 2, а третья — на 5. Программа для исполнителя A125 — это последовательность команд.

Сколько существует программ, которые число 10 преобразуют в число 19, и при этом траектория вычислений содержит число 15?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 231 при исходном числе 5 траектория будет состоять из чисел 7, 12, 13.

Решение
Ответ: 45
Показать решение
Полный курс
Показать еще

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе