РЕШУ ЕГЭ — информатика

Системы логических уравнений со слабо связанными рядами

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5 ) = 1

x1 ∨ y1 = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. 1)  Из последнего уравнения следует, что глобально мы имеем три варианта - x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.

2)  Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.

3)  Уравнение (1) описывает ряд переменных {x1, x2, x3, x4, x5}. Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, слева будут нули, а справа - единицы.

4)  Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.

5)  Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 5 комбинаций, так как в ряде x может быть от 1 до 5 нолей включительно.

6)  Последний вариант рассмотрим аналогично предыдущему. Там существует всего 5 комбинаций.

Правильный ответ: 5+5+1=11 комбинаций.

Ответ: 11.

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

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1

(¬y1 ∨ y2) ∧ (¬y2 ∨ y3) ∧ (¬y3 ∨ y4) = 1

(y1 → x1) ∧ (y2 → x2) ∧ (y3 → x3) ∧ (y4 → x4) = 1

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

Сколько существует различных наборов значений логических переменных x₁, x₂, x₃, x₄, y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) ∧ (x2→x3) ∧ (x3→x4) = 1

(¬x1 ∧ y1 ∧ z1) ∨ (x1 ∧ ¬y1 ∧ z1) ∨ (x1 ∧ y1 ∧ ¬z1) = 1

(¬x2 ∧ y2 ∧ z2) ∨ (x2 ∧ ¬y2 ∧ z2) ∨ (x2 ∧ y2 ∧ ¬z2) = 1

(¬x3 ∧ y3 ∧ z3) ∨ (x3 ∧ ¬y3 ∧ z3) ∨ (x3 ∧ y3 ∧ ¬z3) = 1

(¬x4 ∧ y4 ∧ z4) ∨ (x4 ∧ ¬y4 ∧ z4) ∨ (x4 ∧ y4 ∧ ¬z4) = 1

В ответе не нужно перечислять все различные наборы значений переменных

x₁, x₂, x₃, x₄, y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Рассмотрим первое уравнение. Ему удовлетворяют следующие наборы переменных x₁, x₂, x₃, x₄: 1111, 0111, 0011, 0001, 0000.

Рассмотрим оставшиеся уравнения для первого набора x₁, x₂, x₃, x₄: 1111. Во втором уравнении первая скобка будет равна 0. Из второй и третьей скобок ясно, что переменные y₁ и z₁ могут принимать значения 01 или 10. Имеем два набора решений второго уравнения. Аналогично для третьего, четвёртого и пятого уравнений. Таким образом, для набора x₁, x₂, x₃, x₄: 1111, получаем 16 наборов переменных y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄ (см. рис).

Рассмотрим второй набор переменных x₁, x₂, x₃, x₄: 0111. В этом случае из второго уравнения ясно, что переменные y₁ и z₁ могут принимать значения 11. Для оставшихся уравнений ситуация аналогична первому набору. Таким образом, для набора x₁, x₂, x₃, x₄: 0111, получаем 8 наборов переменных y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄ (см. рис).

Проведя аналогичные рассуждения для наборов 0011, 0001 и 0000, получаем, соответственно 4, 2 и 1 набор переменных y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄ соответственно.

Всего имеем 16 + 8 + 4 + 2 + 1 = 31 набор переменных x₁, x₂, x₃, x₄, y₁, y₂, y₃, y₄, z₁, z₂, z₃, z₄, которые удовлетворяют всем уравнениям.

Ответ: 31.

(x1→x2) ∧ (x2→x3) ∧ (x3→x4) ∧ (x4→x5) = 1

(x1→y1) ∧ (x2→y2) ∧ (x3→y3) ∧ (x4→y4) ∧ (x5→y5) = 1

Решение. Рассмотрим первое уравнение. Логическое «И» истинно, когда истинны все высказывания. Для того, чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Импликация ложна только тогда, когда посылка истинна, а следствие ложно. Представим решения этого уравнения в виде дерева:

Рассмотрим оставшиееся уравнения для первого набора x1, x2, x3, x4, x5: 11111. Импликация ложна тогда, когда из истинны следует ложь. В данном случае, все x равны 1, следовательно, все y также должны быть равны 1.

Рассмотрим второй набор переменных x1, x2, x3, x4, x5: 01111. Заметим, что все y, кроме первого могут принимать только значения 1, y1 может быть равен 0 или 1. Таким образом, второму набору x соответствует 2 · 1  =  2 набора y.

Рассмотрим третий набор переменных x1, x2, x3, x4, x5: 00111. Заметим, что все y, кроме первого и второго могут принимать только значения 1, y1 и y2 может быть равен 0 или 1. Таким образом, второму набору x соответствует 2 · 2 · 1  =  4 набора y.

Проведя аналогичные рассуждения для наборов x 00011, 00001, 00000, получаем, соответственно 8, 16 и 32 набора y.

Таким образом, получаем 1 + 2 + 4 + 8 + 16 +32 = 63 набора переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств.

Ответ: 63.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, y1, y2, y3, y4, y5, y6, которые удовлетворяют всем перечисленным ниже условиям

(x1→x2) ∧ (x2→x3) ∧ (x3→x4) ∧ (x4→x5) ∧ (x5→x6) = 1

(y2→y1) ∧ (y3→y2) ∧ (y4→y3) ∧ (y5→y4) ∧ (y6→y5) = 1

x6→y6 = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, y1, y2, y3, y4, y5, y6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Заметим, что первое и второе уравнения не связаны между собой ни через какие переменные. Рассмотрим последнее уравнение.

Рассмотрим первое уравнение. Для того, чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Импликация ложна только тогда, когда посылка истинна, а следствие ложно. Представим решение этого уравнения в виде дерева.

Рассмотрим второе уравнение. Для того, чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Дерево для решения этого уравнения будет выглядеть так:

Теперь рассмотрим третье уравнение. Импликация ложна только тогда, когда посылка истинна, а следствие ложно. Представим решения последнего уравнения в виде таблицы:

	x6	y6
А)	0	0
Б)	0	1
В)	1	1

Случай А). Согласно деревьям решений получим 7 наборов решений для переменных x и 7 наборов переменных y, но x6  =  0 и y6  =  0, следовательно, из набора решений для x подойдёт один, а из набора решений для y  — 6. Суммарное число наборов: 1 · 6  =  6.

Случай Б). Аналогично случаю А получим 1 набор переменных x и 1 набор переменных y, суммарное число наборов 1 · 1  =  1.

Случай В). Аналогично случаю А получим 6 наборов переменных x и 1 набор переменных y, суммарное число наборов 6 · 1  =  6.

Таким образом, получаем 6 + 1 + 6 = 13 наборов переменных x1, x2, x3, x4, x5, x6, y1, y2, y3, y4, y5, y6, при которых выполнена данная система равенств.

Ответ: 13.

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

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) ∧ (x5→ x6) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1

(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) ∧ (z4→ z5) ∧ (z5 → z6) = 1

x1 ∨ y1 ∨ z1 = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ..., x6, y1, y2, ..., y6, z1, z2, ..., z6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Из последнего уравнения следует, что глобально мы имеем семь вариантов  — любые комбинации x1, y1, z1 кроме 000.

Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.

Первое уравнени описывает ряд переменных {x1, x2, x3, x4, x5, x6}. Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для второго и третьего это также справедливо. Иначе говоря, если записать переменные x в порядке возрастания их номеров, слева будут нули, а справа  — единицы. То есть возможны семь наборов: 111 111, 011 111, 001 111, 000 111, 000 011, 000 001, 000 000.

Для набора переменных x1, y1, z1 001 будет 6 · 6 · 1  =  36 комбинаций. Для наборов переменных x1, y1, z1 010 и 100 также будет 36 комбинаций.

Для набора переменных x1, y1, z1 011 будет 6 · 1 · 1 · 1=6 комбинаций. Для наборов 101 и 110 также будет 6 комбинаций.

Для набора переменных x1, y1, z1 111 будет одна комбинация.

Общее число полученных наборов: 3 · 36+ 3 · 6 + 1 = 127.

Ответ: 127.

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) ∧ (x5→ x6) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1

(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) ∧ (z4→ z5) ∧ (z5 → z6) = 1

x6 ∧ y6 ∧ z6 = 0

Решение. Заметим, что первые три уравнения однотипны. Если последняя переменная (x6, y6 или z6) равна нулю, то предыдущая переменная в данном уравнении тоже должна равняться нулю. Аналогично для всех предыдущих выражений в уравнении: если следствие равно нулю, то посылка также равна нулю, а если следствие равно единице, то посылка либо 0, либо 1. Таким образом, получаем древо решений, которое ветвится в тех случаях, когда следствие равно 1 (см. рис.).

Исходя из структуры дерева, делаем вывод, что количество решений уравнения из пяти выражений равно 6, если последняя переменная равна единице. Если же последняя переменная равна нулю, то имеем единственное решение уравнения.

Из последнего уравнения находим, что возможны семь вариантов значений x6, y6 и z6 (все, кроме 111). Выпишем количество решений для каждой комбинации x6, y6 и z6:

x6, y6 и z6	Количество решений
110	6 · 6 · 1 = 36
101
011
100	6 · 1 · 1 = 6
010
001
000	1

Таким образом, система уравнений имеет 3 · 36 + 3 · 6 + 1 = 127 наборов решений.

Ответ: 127.

Сколько существует различных наборов значений логических переменных x₁, ..., x₄, y₁, ..., y₄, z₁,..., z₄, которые удовлетворяют всем перечисленным ниже условиям?

(x₁ → x₂) ∧ (x₂ → x₃) ∧ (x₃ → x₄) = 1

(y₁ → y₂) ∧ (y₂ → y₃) ∧ (y₃ → y₄) = 1

(z₁ → z₂) ∧ (z₂→ z₃) ∧ (z₃ → z₄) = 1

    x₄ ∧ y₄ ∧ z₄ = 0

В ответе не нужно перечислять все различные наборы значений переменных x₁, ..., x₄, y₁, ..., y₄, z₁, ..., z₄, при которых выполнена данная система равенств.

В качестве ответа Вам нужно указать количество таких наборов.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, y1, y2, y3, y4, y5, y6, которые удовлетворяют всем перечисленным ниже условиям?

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) ∧ (x5 → x6 ) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5 ) ∧ (y5 → y6 ) = 1

x1 → y1= 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, y1, y2, y3, y4, y5, y6 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. 1)  Из последнего уравнения следует, что глобально мы имеем три варианта - x1=1, y1=1; x1=0, y1=1; x1=0, y1=0.

3)  Уравнение (1) описывает ряд переменных {x1, x2, x3, x4, x5, x6}. Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут единицы, а слева  — нули.

5)  Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 6 комбинаций, так как в ряде x может быть от 1 до 6 нолей включительно.

6)  Последний вариант рассмотрим аналогично предыдущему. Там существует всего 36 комбинаций.

Правильный ответ: 36+6+1=43 комбинации.

Ответ: 43.

10.  

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

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) ∧ (x5 → x6) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1

(¬x1 ∨ y1) ∧ (¬x2 ∨ y2) ∧ (¬x3 ∨ y3) ∧ (¬ x4 ∨ y4) ∧ (¬x5 ∨ y5) ∧ (¬x6 ∨ y6) = 1

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

Решение. Заметим, что первое и второе уравнения не связаны между собой ни через какие переменные.

Рассмотрим второе уравнение. Чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Дерево для решения этого уравнения будет выглядеть так:

Теперь рассмотрим третье уравнение. Конъюнкция истинна только, если все операнды истинны. Каждое уравнения вида ¬xN ∨ yN = 1 имеет три решения: 01, 00, 11. То есть для каждой пары xN, yN запрещены решения вида 10.

Будем представлять решения уравнений в виде набора нулей и единиц, например, решение x1 = 0, x2 = x3 =x4, = x5= x6 = 1 имеет вид 011 111. Заметим, что для первых двух уравнений в наборах решений после единицы могут стоять только единицы. То есть разрешены решения вида 001 111.

Также заметим, что если yN = 0, то xN обязательно равно единице.

Таким образом, получаем, что набору yN 111 111, могут соответствовать наборы xN: 111 111, 011 111, 001 111, 000 111, 000 011, 000 001, 000 000. Всего семь наборов.

Аналогично, набору yN 011 111 соответствует шесть наборов и так далее. Всего получаем:

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 наборов.

Ответ: 28.

11.  

Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₃, y₁, y₂, ... y₅, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x₁ ≡ x₂) ∨ ¬ (y₁ ≡ y₂) ) = 1

(¬ (x₂ ≡ x₃) ∨ ¬ (y₂ ≡ y₃) ) = 1

(¬ (x₃ ≡ x₄) ∨ ¬ (y₃ ≡ y₄) ) = 1

(¬ (x₄ ≡ x₅) ∨ ¬ (y₄ ≡ y₅) ) = 1

x₅ ≡ y₅ = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₅, y₁, y₂, ... y₅, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

12.  

(¬ (x₁ ≡ x₂) ∨ ¬ (y₁ ≡ y₂) ) = 1

(¬ (x₂ ≡ x₃) ∨ ¬ (y₂ ≡ y₃) ) = 1

(¬ (x₃ ≡ x₄) ∨ ¬ (y₃ ≡ y₄) ) = 1

(¬ (x₄ ≡ x₅) ∨ ¬ (y₄ ≡ y₅) ) = 1

x₅ ∨ y₅ = 1

13.  

Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₉, y₁, y₂, ... y₉, которые удовлетворяют всем перечисленным ниже условиям?

(x₁→x₂) ∧ (y₁→y₂) ∧ (y₁→x₁) = 1

(x₂→x₃) ∧ (y₂→y₃) ∧ (y₂→x₂) = 1

…

(x₈→x₉) ∧ (y₈→y₉) ∧ (y₈→x₈) = 1

(y₉→x₉) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₉, y₁, y₂, ... y₉, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

14.  

Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₈, y₁, y₂, ... y₈, которые удовлетворяют всем перечисленным ниже условиям?

(x₁→x₂) ∧ (y₁→y₂) ∧ (y₁→x₁) = 1

(x₂→x₃) ∧ (y₂→y₃) ∧ (y₂→x₂) = 1

…

(x₇→x₈) ∧ (y₇→y₈) ∧ (y₇→x₇) = 1

(y₈→x₈) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₈, y₁, y₂, ... y₈, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

15.  

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

(x1→x2) ∧ (y1→y2) = 1

(x2→x3) ∧ (y2→y3) = 1

…

(x7→x8) ∧ (y7→y8) = 1

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

В качестве ответа Вам нужно указать количество таких наборов.

16.  

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

(x1→x2) ∧ (y1→y2) = 1

(x2→x3) ∧ (y2→y3) = 1

…

(x8→x9) ∧ (y8→y9) = 1

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

В качестве ответа Вам нужно указать количество таких наборов.

17.  

(x1→x2) ∧ (x1→y1) = 1

(x2→x3) ∧ (x2→y2) = 1

…

(x7→x8) ∧ (x7→y7) = 1

(x8→y8) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₈, y₁, y₂, ... y₈ при которых выполнена данная система равенств.

В качестве ответа Вам нужно указать количество таких наборов.

18.  

Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₇, y₁, y₂, ... y₇, которые удовлетворяют всем перечисленным ниже условиям?

(x₁→x₂) ∧ (x₁→y₁) = 1

(x₂→x₃) ∧ (x₂→y₂) = 1

…

(x₆→x₇) ∧ (x₆→y₆) = 1

(x₇→y₇) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₇, y₁, y₂, ... y₇ при которых выполнена данная система равенств.

В качестве ответа Вам нужно указать количество таких наборов.

19.  

Сколько существует различных наборов значений логических переменных x₁, x₂,…, x₆, y₁, y₂, ..., y₆, которые удовлетворяют всем перечисленным ниже условиям?

(x₁ ∨ ¬x₂) ∧ (x₂ ∨ ¬x₃) ∧ (x₃ ∨ ¬x₄) ∧ (x₄ ∨ ¬x₅) ∧ (x₅ ∨ ¬x₆) = 1

(¬y₁ ∨ y₂) ∧ (¬y₂ ∨ y₃) ∧ (¬y₃ ∨ y₄) ∧ (¬y₄ ∨ y₅) ∧ (¬y₅ ∨ y₆) = 1

x₁ ∨ y₁ = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ..., x₆, y₁, y₂, ..., y₆ при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Преобразуем первое и второе уравнения:

(x₂→x₁) ∧ (x₃→x₂) ∧ (x₄→x₃) ∧ (x₅→x₄) ∧ (x₆→x₅) = 1

(y₁→y₂) ∧ (y₂→y₃) ∧ (y₃→y₄) ∧ (y₄→y₅) ∧ (y₅→y₆) = 1

Заметим, что первое и второе уравнения не связаны между собой ни через какие переменные.

Представим решения последнего уравнения в виде таблицы:

	x₁	y₁
А	1	1
Б	1	0
В	0	1

Случай А. Согласно деревьям решений получим 7 наборов решений для переменных x и 7 наборов переменных y, но x1  =  1 и y1  =  1, следовательно, из набора решений для x подойдёт шесть, а из набора решений для y  — 1. Суммарное число наборов: 1 · 6  =  6.

Случай Б. Аналогично случаю А получим 6 наборов переменных x и 6 наборов переменных y, суммарное число наборов 6 · 6  =  36.

Случай В. Аналогично случаю А получим 1 набор переменных x и 1 набор переменных y, суммарное число наборов 1 · 1  =  1.

Таким образом, получаем 36 + 6 + 1 = 43 набора переменных x1, x2, x3, x4, x5, x6, y1, y2, y3, y4, y5, y6, при которых выполнена данная система равенств.

Ответ: 43.

20.  

Сколько существует различных наборов значений логических переменных x₁, x₂,…, x₅, y₁, y₂, ..., y₅, которые удовлетворяют всем перечисленным ниже условиям?

(x₁ ∨ ¬x₂) ∧ (x₂ ∨ ¬x₃) ∧ (x₃ ∨ ¬x₄) ∧ (x₄ ∨ ¬x₅) = 1

(¬y₁ ∨ y₂) ∧ (¬y₂ ∨ y₃) ∧ (¬y₃ ∨ y₄) ∧ (¬y₄ ∨ y₅) = 1

x₁ ∨ y₁ = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ..., x₅, y₁, y₂, ..., y₅ при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Преобразуем первое и второе уравнения:

(x₂→x₁) ∧ (x₃→x₂) ∧ (x₄→x₃) ∧ (x₅→x₄) = 1

(y₁→y₂) ∧ (y₂→y₃) ∧ (y₃→y₄) ∧ (y₄→y₅) = 1

Заметим, что первое и второе уравнения не связаны между собой ни через какие переменные.

Представим решения последнего уравнения в виде таблицы:

	x₁	y₁
А	1	1
Б	1	0
В	0	1

Случай А. Согласно деревьям решений получим 6 наборов решений для переменных x и 6 наборов переменных y, но x1  =  1 и y1  =  1, следовательно, из набора решений для x подойдёт пять, а из набора решений для y  — 1. Суммарное число наборов: 1 · 5  =  5.

Случай Б. Аналогично случаю А получим 5 наборов переменных x и 5 наборов переменных y, суммарное число наборов 5 · 5  =  25.

Таким образом, получаем 25 + 5 + 1 = 31 набор переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств.

Ответ: 31.

21.  

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

(x1 ∨ x2) ∧ (¬x1 ∨ ¬x2) ∧ (¬x1 ∨ y1) = 1

(x2 ∨ x3) ∧ (¬x2 ∨ ¬x3) ∧ (¬x2 ∨ y2) = 1

...

(x6 ∨ x7) ∧ (¬x6 ∨ ¬x7) ∧ (¬x6 ∨ y6) = 1

(¬x7 ∨ y7) = 1

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

№ п/п	№ задания	Ответ
1	3822	11
2	4567	15
3	6788	31
4	6967	63
5	7317	13
6	7680	127
7	7934	127
8	9207	61
9	9773	43
10	11124	28
11	13419	162
12	13472	243
13	13499	55
14	13526	45
15	14238	81
16	14282	100
17	14709	511
18	14784	255
19	15808	43
20	15835	31
21	15863	24

Ключ