1. A, B и С – целые числа, для которых истинно высказывание

 
¬(А = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
 

Чему равно B, если A = 45 и C = 18?

Решение.

Логическое «И» истинно только тогда, когда истинны все высказывания.

 

Следовательно,

 
¬(А = B) = 1, (A > B)→(C = B) = 1, (B > A)→(C = A) = 1.
 

Из первого выясняем, что А ≠ B.

 

Применим преобразование импликации ко второму и третьему:

 
¬(A > B) ∨ (C = B) = 1, ¬(B > A) ∨ (C = A) = 1.
 

Обратим внимание на третье высказывание: (C = A) = 0, так как 45 ≠ 18. Следовательно, чтобы оно было истинным необходимо, чтобы ¬(B > A) = 1, то есть чтобы число B было не больше A.

 

Теперь рассмотрим ¬(A > B) ∨ (C = B) = 1. Возможны два случая:

 

1) ¬(A > B) = 1. Это что означает, что число А не больше В. Вместе с предыдущим это означает, что А = В = 40. Однако это противоречит тому, что А ≠ B.

 

2) (C = B) = 1, откуда В = 18.

 
 

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

 

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

((x3 ≡ x4) ∧ (x5 ≡ x6)) ∨ (¬(x3 ≡ x4) ∧ ¬(x5 ≡ x6)) = 0

((x9 ≡ x10) ∧ (x11 ≡ x12)) ∨ (¬(x9 ≡ x10) ∧ ¬(x11 ≡ x12)) = 0

 

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

Решение.

Построим древо решений первого уравнения:

 


 

Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.

 

Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:

 


 

Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2,…,x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.

 

Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:

 


 

Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2,…,x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.

 

Аналогично система из четырёх уравнений будет иметь 64 решения, система из пяти уравнений — 128.

 

Ответ: 128.

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

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

¬(x9 ≡ x10) ∧ ( (x9 ∧ ¬x11) ∨ (¬x9 ∧ x11) ) = 0
 

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

Решение.

Рассмотрим первое уравнение.

 

При x1 = 1 возможны два случая: x2 = 0 и x2 = 1. В первом случае x3 = 1. Во втором — x3 либо 0, либо 1. При x1 = 0 также возможны два случая: x2 = 0 и x2 = 1. В первом случае x3   либо 0, либо 1. Во втором — x3 = 0. Таким образом, уравнение имеет 6 решений (см. рисунок).

 


 

Рассмотрим систему из двух уравнений.

 

Пусть x1 = 1. При x2 = 0 возможен лишь один случай: x3 = 1, переменная x4 = 0. При x2 = 1 возможно два случая: x3 = 0 и x3 = 1. В первом случае x4 = 1, во втором — x4 либо 0, либо 1. Всего имеем 4 варианта.

 

Пусть x1 = 0. При x2 = 1 возможен лишь один случай: x3 = 0, переменная x4 = 1. При x2 = 0 возможно два случая: x3 = 0 и x3 = 1. В первом случае x4 либо 1, либо 0, во втором — x4 = 0. Всего имеем 4 варианта.

 

Таким образом, система из двух уравнений имеет 4 + 4 = 8 вариантов (см. рисунок).

 


 

Система из трёх уравнений будет иметь 10 решений, из четырёх — 12. Система из девяти уравнений будет иметь 22 решения.

 

Ответ: 22.

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

(¬ (x1 ≡ x2) ∨ ¬ (y1 ≡ y2) ) = 1

(¬ (x2 ≡ x3) ∨ ¬ (y2 ≡ y3) ) = 1

(¬ (x3 ≡ x4) ∨ ¬ (y3 ≡ y4) ) = 1

(¬ (x4 ≡ x5) ∨ ¬ (y4 ≡ y5) ) = 1

x5 ∨ y5 = 1

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

Решение.

Пятая строчка дает 3 варианта: либо x5=y5=1, либо x5=1, y5=0, либо x5=0, y5=1. Можно заметить, что для всех случаев будет по 3 доступных варианта в четвертой строчке. Дальше заметим, что каждой из выражений в 1−4 строчке не истина только тогда, когда обе эквивалентности выполнены. Поскольку для 2 переменных всего 4 варианта комбинаций, то одна из них будет не подходить, а три другие всегда подходить. Далее каждая из этих трех будет задавать неподходящий вариант для строчки выше. Значит, для трех изначальных вариантов в пятой строчке имеем:

 

3 · 3 · 3 · 3 + 3 · 3 · 3 · 3 + 3 · 3 · 3 · 3 = 243 варианта.

 

Ответ: 243.

5. Сколько существует различных наборов значений логических переменных x1x2, …, x6y1y2, …, y6, которые удовлетворяют всем перечисленным ниже условиям?

 

(x1 ∧ ¬y1) ∨ (y2 ∧ ¬x2) ∨ (x1 ∧ y2) = 0

(x2 ∧ ¬y2) ∨ (y3 ∧ ¬x3) ∨ (x2 ∧ y3) = 0

(x3 ∧ ¬y3) ∨ (y4 ∧ ¬x4) ∨ (x3 ∧ y4) = 0

(x4 ∧ ¬y4) ∨ (y5 ∧ ¬x5) ∨ (x4 ∧ y5) = 0

(x5 ∧ ¬y5) ∨ (y6 ∧ ¬x6) ∨ (x5 ∧ y6) = 0

x6 ∧ ¬y6 = 0

 

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

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1y1 и x2y2.

 

x1y1 x2y2
00 00
01 01
10 10
11 11

 

Для первой строки x1y1 ложь возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00, 10 и 11.

Для второй строки x1y1 ложь возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00, 10 и 11.

Для третьей строки x1y1 ложь невозможна.

Для четвёртой строки x1y1 ложь возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00 и 10.

 

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

 

x1y1 x2y2 x3y3 x4y4 x5y5 x6y6
00 1 3 5 8 13 21
01 1 0 0 0 0 0
10 1 3 5 8 13 21
11 1 2 3 5 8 13

 

Из последнего уравнение заключим, что третью строку таблицы учитывать не надо, поскольку когда x6y6 принимают значения 10, уравнение x6 ∧ ¬y6 будет истинным. Таким образом, количество решений будет равно 

 
Ответ: 34.

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

 

(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)

(x2 ∧ y2) ≡ (¬x3 ∨ ¬y3)

(x5 ∧ y5) ≡ (¬x6 ∨ ¬y6)

 

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

Решение.

Можно заметить, что ¬x2 ∨ ¬y2 (правая часть первого тождества) = ¬(x2 ∧ y2) (отрицание левой части второго неравенства) по закону Де Моргана. То есть значения выражений чередуются в каждой строчке. 0-1-0-1-0 или 1-0-1-0-1.

 

Пусть они чередуются 0-1-0-1-0. Тогда первая пара переменных может принимать три набора значений — (0, 0), (0, 1), (1, 0). Вторая пара только один набор — (1, 1). И дальше так же чередуется. Итого имеем  решений.

 

Пусть они чередуются 1-0-1-0-1. Тогда первая пара может принимать лишь один набор значений — (1, 1). Аналогично первому случаю количество здесь чередуется 1-3-1-3-1-3. Итого в этом случае имеем  решений.

 

Всего  решений.

7. Сколько существует различных наборов значений логических переменных 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) ∧ (x2→y2) =1.

 

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

Решение.

Рассмотрим первое уравнение, конъюнкция истинна тогда и только тогда, когда истинны все её переменные истинны. Импликация ложна только тогда, когда из истины следует ложь. Запишем все переменные x1, x2, x3, x4, x5 по порядку. Тогда, первое уравнение будет верно, если в данной строке справа от единиц нет нулей. То есть подходят строки 11111, 01111, 00111, 00011, 00001, 00000. Аналогичные решения имеет второе уравнение. Первое и второе уравнение не связаны какими-либо переменными, поэтому для системы, состоящей только из двух первых уравнений, каждому набору переменных одного уравнения соответствует 6 наборов переменных другого.

Теперь учтём третье уравнение. Это уравнение не выполняется для таких наборов переменных, в которых x1 = 1, а y1 = 0, либо x2 = 1, а y2 = 0. Это означает, что если записать какой-либо набор переменных x1, x2, x3, x4, x5 над набором переменных y1, y2, y3, y4, y5, то нужно исключить такие наборы, в которых под 1 на первом или втором местах стоят нули. То есть, набору переменных x1, x2, x3, x4, x5 11111 соответствует не 6 наборов y, а только один, а набору 01111 — 2. Таким образом, суммарное число возможных наборов: 1 + 2 + 4 · 6 = 27.

 
Ответ: 27.

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

 
 

(x1 ∨ y1) → (x2 ∧ y2) = 0

(x2 ∨ y2) → (x3 ∧ y3) = 0

(x5 ∨ y5) → (x6 ∧ y6) = 0

 

 
 

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

Решение.

Избавимся от импликаций в уравнениях, получим:

 

(¬ x1 ∧ ¬ y1) ∨ (x2 ∧ y2) = 0

(¬ x2 ∧ ¬ y2) ∨ (x3 ∧ y3) = 0

(¬ x5 ∧ ¬ y5) ∨ (x6 ∧ y6) = 0

 

 

Рассмотрим первое уравнение. Выражение истинно только если выполняется хотя бы одно из двух: либо x1 = y1 = 0, либо x2 = y2 = 1. Во всех остальных случаях оно ложно. А именно (x1y1) принимает одно из значений: (0, 1), (1, 0), (1, 1), а (x2y2) из: (0, 0), (0, 1), (1, 0). Решением же всего уравнения являются комбинации всех допустимых значений (x1y1) со всеми допустимыми значениями (x2y2). Несложно понять, что всего таких комбинаций будет 9.

 

Теперь рассмотрим второе уравнение. Аналогично с первым, оно будет иметь 9 решений.

 

Теперь рассмотрим систему из первого и второго уравнения. У них есть по 9 решений, решением же всей системы будут всевозможные комбинации решений первого уравнения и второго такие, что (x2y2) в них совпадают. Совпадают значения (0, 1) и (1, 0). Таким образом (x1y1) может принимать 3 значения, (x2y2) — 2 значения, а (x3y3) — 3. И всего получается  решений.

 

Поймём, что после добавления третьего уравнения, (x3y3) тоже сможет принимать только 2 значения, как и (x2y2), а (x1y1) и (x4y4) смогут принимать по 3 значения.

 

Таким образом, для всей системы решением будут такие значения переменных, где (x1y1) принимает значения (0, 1), (1, 0) или (1, 1), (x6y6) принимает значения (0, 0), (0, 1) или (1, 0), а все остальные — (0, 1) или (1, 0).

Всего таких комбинаций .

9. Каково наибольшее целое число X, при котором истинно высказывание (10 < X·(X+1)) → (10 > (X+1)·(X+2))?

Решение.

Уравнение является операцией импликации между двумя отношениями:

 

 и 

 

1) Конечно, здесь можно применить тот же способ, что и в примере 2208, однако при этом понадобится решать квадратные уравнения (не хочется…);

 

2) Заметим, что по условию нас интересуют только целые числа, поэтому можно попытаться как─то преобразовать исходное выражение, получив равносильное высказывание (точные значения корней нас совершенно не интересуют!);

 

3) Рассмотрим неравенство : очевидно, что  может быть как положительным, так и отрицательным числом;

 

4) Легко проверить, что в области  высказывание  истинно при всех целых , а в области  — при всех целых  (чтобы не запутаться, удобнее использовать нестрогие неравенства,  и , вместо  и );

 

5) Поэтому для целых  можно заменить  на равносильное выражение

 

;

 

6) область истинности выражения  — объединение двух бесконечных интервалов;

 

7) Теперь рассмотрим второе неравенство : очевидно, что  так же может быть как положительным, так и отрицательным числом;

 

8) В области  высказывание  истинно при всех целых , а в области  — при всех целых , поэтому для целых  можно заменить  на равносильное выражение

 

;

 

9) область истинности выражения  — закрытый интервал;

 

10) Заданное выражение истинно везде, кроме областей, где  и ;

 

11) Обратите внимание, что значение  уже не подходит, потому что там  и , то есть импликация дает 0;

 

12) При подставлении 2, (10<2 · (2+1)) → (10>(2+1) · (2+2)), или 0 → 0 что удовлетворяет условию.

 

Таким образом, ответ 2.

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

 

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

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

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

(x7 ∨ x8) ∧ (¬x7 ∨ y7) = 1

(¬x8 ∨ y8) = 1

 

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

Решение.

Из последнего уравнения находим, что возможны три варианта значений x8 и y8: 01, 00, 11. Построим древо вариантов для первой и второй пар значений.

 


 

Таким образом, имеем 16 наборов переменных.

Дерево вариантов для пары значений 11:

 


 

Получаем 45 вариантов. Таким образом, система будет иметь 45 + 16 = 61 различных наборов решений.

 

Ответ: 61.

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

 

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

 

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

Решение.

Произведём замену: y1 = x1 → x2; y2 = x3 → x4; y3 = x5 → x6; y4 = x7 → x8. Получим уравнение:

 

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

 

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

Импликация ложна только в случае, если из истинного следует ложное. Данная система уравнений описывает ряд переменных {y1, y2, y3, y4}. Заметим, что если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. То есть решения системы уравнений: 0000; 0001; 0011; 0111; 1111.

Уравнения вида xN → x{N+1} = 0 имеют одно решение, а уравнения вида xN → x{N+1} = 1 имеют три решения.

Найдём сколько наборов переменных x соответствуют каждому из решений y.

Решению y 0000 соответствует 1 · 1 · 1 · 1 = 1 решение.

Решению y 0001 соответствует 1 · 1 · 1 · 3 = 3 решения.

Решению y 0011 соответствует 1 · 1 · 3 · 3 = 9 решений.

Решению y 0111 соответствует 1 · 3 · 3 · 3 = 27 решений.

Решению y 1111 соответствует 3 · 3 · 3 · 3 = 81 решений.

Таким образом, суммарное число решений: 1 + 3 + 9 + 27 + 81 = 121.

 
Ответ: 121.

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

 

(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, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

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

 

 

Рассмотрим оставшиееся уравнения для первого набора 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.

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

 

(x1≡x2)—>(x2≡x3) = 1

(x2≡x3)—>(x3≡x4) = 1

(x6≡x7)—>(x7≡x8) = 1

 

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

Решение.

Запишем переменные в строчку: x1x2x3x4x5x6x7x8. Импликация ложна только в том случае, когда из истины следует ложь. Условие не выполняется, если в ряду после пары одинаковых цифр присутствует другая цифра. Например, «11101…», что означает невыполнение второго условия.

 

Рассмотрим комбинации переменных, удовлетворяющие всем условиям. Выпишем варианты, при которых все цифры чередуются, таких два: 10101010 и 01010101. Теперь для первого варианта, начиная с конца, будем увеличивать количество повторяющихся подряд цифр (настолько, насколько это возможно). Выпишем полученные комбинации: «1010 1011; 1010 1111; 1011 1111; 1111 1111; 1010 1000; 1010 0000; 1000 0000; 0000 0000» таких комбинаций девять, включая исходную. Аналогично для второго варианта: «0101 0101; 0101 0100; 0101 0000; 0100 0000; 0000 0000; 0101 0111; 0101 1111; 0111 1111; 1111 1111» — таких комбинаций также девять. Заметим, что комбинации 0000 0000 и 1111 1111 учтены дважды. Таким образом, получаем 9 + 9 − 2 = 16 решений.

 
Ответ: 16.

14. Сколько различных решений имеет уравнение:

 
¬((J → K) → (L ∧ M ∧ N)) ∨ ¬((L ∧ M ∧ N) → (¬J ∨ K)) ∨ (M ∧ J) = 0

Решение.

Используем формулу A → B = ¬A ∨ B

 

Рассмотрим первую подформулу:

 
¬((¬J ∨ K) → (M ∧ N ∧ L)) = ¬(¬(¬J ∨ K) ∨ (M ∧ N ∧ L)) = ¬((J ∧ ¬K) ∨ (M ∧ N ∧ L)) =
 

Учитывая, что ¬(А ∨ В) = ¬А ∧ ¬В,

 
= (¬J ∨ K) ∧ (¬M ∨ ¬N ∨ ¬L)
 

Рассмотрим вторую подформулу

 
¬((L ∧ M ∧ N) → (¬J ∨ K)) = ¬(¬(L ∧ M ∧ N) ∨ (¬J ∨ K)) = L ∧ M ∧ N ∧ J ∧ ¬K
 

Применим отрицание к левой и правой части уравнения, получится

 
[(J ∧ ¬K) ∨ (M ∧ N ∧ L)] ∧ [¬L ∨ ¬M ∨ ¬N ∨ ¬J ∨ K] ∧ [¬M ∨ ¬J] = 1
 

1) (¬M ∨ ¬J) = 1, следовательно,

 
а) M = 0 J = 0
 

0 ∧ ¬K ∧ ¬L ∨ ¬N ∨ K, следовательно, 0 решений.

 
б) M = 1 J = 0
[(0 ∧ ¬K) ∨ (1 ∧ N ∧ L)] ∧ [¬L ∨ 0 ∨ ¬N ∨ 1 ∨ K] ∧ [¬M ∨ 1] = N ∧ L ∧ ¬L ∨ ¬N ∨ 1 ∨ K = 1 => L=N=1, следовательно, 2 решения.
 
в) M = 0 J = 1
 
[(1 ∧ ¬K) ∨ (0 ∧ N ∧ L)] ∧ [¬L ∨ ¬0 ∨ ¬N ∨ ¬1∨ K] ∧ [¬0 ∨ ¬1] = 1, следовательно, 4 решения.
 

Ответ: 2 + 4 = 6.

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

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

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
(x7 ∨ y7) = 1
 

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

Решение.

Из последнего уравнения находим, что возможны варианты значений x7 и y7: 11, 01, 10 . Построим древо вариантов для каждого из вариантов значений x7 и y7. Для пары значений 11:

 


 

Имеем один вариант набора решений.

 

Для пары значений 01:

 


 

Каждая ветка расщепляется на три из которых только две опять расщепляются на три, а одна — нет.

Вот как выглядело бы начало древа решений, если бы каждая ветка расщеплялась только на две (см. рисунок слева). Тогда мы имели бы 2 · 2 · … · 2 = 2N решений, где N — количество уравнений в системе.

В нашем случае (см. рисунок справа) в каждой точке ветвления добавляется ещё по одному решению.

 


 

Тогда имеем 2N + 1 + 2 + 4 + … + 2N − 1 решений. Преобразуем данное выражение:

 


 

Полученное выражение — сумма первых N членов геометрической прогрессии с знаменателем 2 и первым членом равным единице. Поскольку в системе семь уравнений, количество решений равно

 


 

Для пары значений 10 переменных x7y7 также имеем 127 решений.

 

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

 

Ответ: 255.

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

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

 

Решение.

Рассмотрим первое уравнение. Выражение истинно, когда (x1x2x3) принимает значения (0, 1, 1), (1, 0, 1) или (1, 1, 0).

 

Теперь рассмотрим второе уравнение, оно будет иметь такие же решения.

 

Объединим первые два уравнения в систему. Решением такой системы будут комбинации всех допустимых значений переменных в первом уравнении со всеми допустимыми значениями во втором таких, что x2 и x3 в них совпадают. Всего комбинаций 9, но совпадают нужные переменные только в 3: (0, 1, 1, 0), (1, 0, 1, 1) и (1, 1, 0, 1).

 

Добавим третье уравнение к системе. Заметим, что как и при добавлении второго уравнения, у системы, к которой мы сейчас добавляем уравнение, уже имеется 3 решения такие, что последние две переменные принимают значения (0, 1), (1, 0) и (1, 1), а у текущего уравнения три решения, первые две переменные в которых принимают значения (0, 1), (1, 0) и (1, 1). Решением получившейся системы будет комбинация решений системы из первых двух уравнений и решений третьего уравнения. И аналогично предыдущему случаю будет всего 3 комбинации.

 

Становится ясно, что при добавлении нового уравнения в систему количество решений не меняется и остаётся всегда одним — 3. Значит, и после добавления последнего уравнения система будет иметь 3 решения.

17. Каково наибольшее целое число X, при котором истинно высказывание

 

(50 < X·X) → (50 > (X+1)·(X+1))?

 

Решение.

Применим преобразование импликации и преобразуем выражение:

 

(50 < X·X) → (50 > (X+1)·(X+1)) ⇔ ¬(X2 > 50) ∨ ((X+1)2 < 50) ⇔ (|X| ≤ ) ∨ (|X+1| < ).


 

Логическое ИЛИ истинно когда истинно хотя бы одно логическое высказывание. Решив оба неравенства и учитывая, что  видим, что наибольшее целое число, при котором выполняется хотя бы одно из них — 7 (на рисунке жёлтым изображено положительное решение второго неравенства, синим — первого).

 

Ответ: 7.

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

 

(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

 

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

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

Решение.

Рассмотрим первое уравнение. Ему удовлетворяют следующие наборы переменных x1, x2, x3, x4: 1111, 0111, 0011, 0001, 0000.

Рассмотрим оставшиеся уравнения для первого набора x1, x2, x3, x4: 1111. Во втором уравнении первая скобка будет равна 0. Из второй и третьей скобок ясно, что переменные y1 и z1 могут принимать значения 01 или 10. Имеем два набора решений второго уравнения. Аналогично для третьего, четвёртого и пятого уравнений. Таким образом, для набора x1, x2, x3, x4: 1111, получаем 16 наборов переменных y1, y2, y3, y4, z1, z2, z3, z4 (см. рис).

Рассмотрим второй набор переменных x1, x2, x3, x4: 0111. В этом случае из второго уравнения ясно, что переменные y1 и z1 могут принимать значения 11. Для оставшихся уравнений ситуация аналогична первому набору. Таким образом, для набора x1, x2, x3, x4: 0111, получаем 8 наборов переменных y1, y2, y3, y4, z1, z2, z3, z4 (см. рис).

Проведя аналогичные рассуждения для наборов 0011, 0001 и 0000, получаем, соответственно 4, 2 и 1 набор переменных y1, y2, y3, y4, z1, z2, z3, z4 соответственно.

Всего имеем 16 + 8 + 4 + 2 + 1 = 31 набор переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем уравнениям.

 

Ответ: 31.

19. Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, хб, х7, х8, которые удовлетворяют всем перечисленным ниже условиям?

 

(x1 —> х2) —> (хЗ—> х4) = 1

(хЗ —> х4) —> (х5 —> хб) = 1

(х5 —> хб) —> (х7 —> х8) = 1

 

В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, хб, х7, х8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

Сделаем замену переменных:

 

(x1 —> х2) = y1; (хЗ—> х4) = y2; (х5 —> хб) = y3; (х7 —> х8) = y4.

 

Тогда можно записать систему в виде одного уравнения:

 

(y1 —> y2) ∧ (y2 —> y3) ∧ (y3 —> y4) = 1.

 

Для того, чтобы это равенство было выполнено, ни одна из импликаций не должна быть ложной

Вот все возможные варианты значений «y» (ключевым является тот факт, что переменные y независимы):

 

y1 y2 y3 y4
0 0 0 0
0 0 0 1
0 0 1 1
0 1 1 1
1 1 1 1

 

Импликация x1 —> х2 дает «0» при одном наборе переменных и «1» при трех наборах переменных.

Поскольку каждая из переменных «y» независима от другой, для каждой строки полученной таблицы перемножаем количество вариантов комбинаций исходных переменных:

 

y1 y2 y3 y4 вариантов
0 0 0 0 1·1·1·1 = 1
0 0 0 1 1·1·1·3 = 3
0 0 1 1 1·1·3·3 = 9
0 1 1 1 1·3·3·3 = 27
1 1 1 1 3·3·3·3 = 81

 

Сложим количество вариантов: 1 + 3 + 9 + 27 + 81 = 121.

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

 

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

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

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

(x8 → y8) = 1

 

В ответе не нужно перечислять все различные наборы значений переменных x1x2, …, x8y1y2, …, y8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1y1 и x2y2.

 

x1y1 x2y2
00 00
01 01
10 10
11 11

 

Для первой строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00, 01, 10 и 11.

Для второй строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 01, 10 и 11.

Для третей строки x1y1 истина невозможна.

Для четвёртой строки x1y1 истина возможна тогда, когда пара x2y2 будет принимать значения 01, 10 и 11.

 

Применим это для остальных пар:

 

x1y1 x2y2 x3y3 x4y4 x5y5 x6y6 x7y7 x8y8
00 1 1 1 1 1 1 1 1
01 1 3 7 15 31 63 127 255
10 1 3 7 15 31 63 127 255
11 1 3 7 15 31 63 127 255

 

Третья строка не рассматривается.

Таким образом, количество решений будет равно 

 
Ответ: 511.

21. Сколько существует целых значений X, при которых ложно высказывание:

 

(|X| ≥ 5) ∨ (|X| < 1)

Решение.

Логическое ИЛИ ложно только в одном случае: когда оба выражения ложны.

 
|X| ≥ 5 = 0 и |X| < 1 = 0.
 

Решение первого неравенства: интервал [−∞; −5] и [5; +∞]. Второго — (−1;1).

Нам нужно чтобы они оба были ложны, следовательно, считаем количество целых значений X на интервалах (-5;-1] и [1;5). Таких чисел 8.

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

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

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

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

    x4 ∧ y4 ∧ z4 = 0

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

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

Решение.

x4 ∧ y4 ∧ z4 = 0

Решением этого уравнения являются наборы, в которых есть хотя бы один ноль, а именно: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0).

Теперь заметим, что первые три уравнения решаются аналогично.

Рассмотрим первое из них.

Пусть x4 = 0. Тогда все остальные переменные также равны нулю и уравнение имеет единственное решение.

Теперь пусть x4 = 1. Тогда решений будет 4: (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1) и (1, 1, 1, 1).

Теперь зафиксируем некоторый набор (x4, y4, z4).

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

И как мы уже выяснили, если последняя переменная равна нулю, то уравнение имеет 1 решение, а если равна единице, то 4 решения.

Итого для каждого набора количество решений равно 4a, где a — количество единиц в наборе.

Итого получаем: 42 + 42 + 42 + 41 + 41 + 41 + 40 = 16 + 16 + 16 + 4 + 4 + 4 + 1 = 61

23. Сколько различных решений имеет система логических уравнений

 
 

(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)

(x2 ∧ y2) ≡ (¬x3 ∨ ¬y3)

(x7 ∧ y7) ≡ (¬x8 ∨ ¬y8)

 

где x1x2, …, x8y1y2, …, y8 — логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1y1 и x2y2.

 

x1y1 x2y2
00 00
01 01
10 10
11 11

 

Для первой строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значение 11.

Для второй строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значение 11.

Для третей строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значение 11.

Для четвёртой строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00, 01 и 10.

 

Применим это для остальных пар:

 

x1y1 x2y2 x3y3 x4y4 x5y5 x6y6 x7y7 x8y8
00 1 1 3 3 9 9 27 27
01 1 1 3 3 9 9 27 27
10 1 1 3 3 9 9 27 27
11 1 3 3 9 9 27 27 81

 

Таким образом, количество решений будет равно 

 
Ответ: 162.

24. Сколько существует различных наборов значений логических переменных x1x2, … x7y1y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

 

(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)

(x2 ∧ y2) ≡ (¬x3 ∨ ¬y3)

(x6 ∧ y6) ≡ (¬x7 ∨ ¬y7)

 

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

Решение.

Предположим, что x1 ∧ y1 равно 1.

Тогда (¬x2 ∨ ¬y2) имеет 3 способа стать 1, но тогда x2 ∧ y2 однозначно 0, а значит, (¬x3 ∨ ¬y3) однозначно 0. Далее x3 ∧ y3 равно 1, т.е. вернулись в самое начало.

Такой повтор будет 3 раза, следовательно, существует 3 · 3 · 3 комбинации происходящего. Проделаем тоже самое для предположения x1 ∧ y1 = 0. Получим 3 · 3 · 3 · 3 варианта.

Итого:

 
Ответ: 108.

25. Сколько существует различных наборов значений логических переменных x1x2, … x9y1y2, … y9, которые удовлетворяют всем перечисленным ниже условиям:

 





 

В ответе не нужно перечислять все различные наборы значений переменных x1x2, … x9y1y2, … y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

Будем обозначать набор входных переменных уравнения кортежем из четырёх чисел .

 

Рассмотрим первое уравнение. Переберём все 16 наборов переменных, подойдут 7 из них:

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

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

То есть (0, 0) даст решения (0, 0, 0, 0), (0, 0, 1, 1), (0, 0, 0, 1), (0, 0, 1, 0). (0, 1) — (0, 1, 0, 1). (1, 0) — (1, 0, 1, 0). (1, 1) — (1, 1, 1, 1).

Посчитаем, сколько каких пар  получилось среди всех решений системы из первых двух уравнений. Получилось (0, 0) — 1, (0, 1) — 3, (1, 0) — 3, (1, 1) — 3.

Перейдя к следующему уравнению, получим (0, 0) — 1, (0, 1) — 4, (1, 0) — 4, (1, 1) — 4.

И так далее, с каждым уравнением количество решений будет увеличиваться на 3.

Изначально было 7 решений, плюс ещё 7 уравнений, каждое из которых добавляет по 3 решения.

Итого 

26. Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∨ (L ∧ K) ∨ ¬N

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.

Логическое «ИЛИ» ложно тогда и только тогда, когда ложны оба утверждения.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Применим преобразование импликации для первого выражения:

¬K ∨ M = 0 => K = 1, M = 0.

Рассмотрим второе выражение:

(L ∧ K) ∨ ¬N = 0 (см. результат первого выражения) => L ∨ ¬N = 0 => L = 0, N = 1.

 
Ответ: 1001.

27. Сколько существует различных наборов значений логических переменных x1x2, … x8y1y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?

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

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

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

(x8→y8) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1x2, … x8y1y2, … y8 при которых выполнена данная система равенств.

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

Решение.

Возьмем первое условие (x1→x2) ∧ (x1→y2) = 1. Преобразовав импликации, получим: (¬x1 ∨ x2) ∧ (¬x1 ∨ y1) = 1. Уравнение выполняется тогда и только тогда, когда (¬x1 ∨ x2) = 1 и (¬x1 ∨ y1) = 1.

Таким образом, в двух наборах из 8 цифр x1, x2, … x8, y1, y2, … y8, действуют правила:

1. После единицы идут только единицы.

2. После нуля идут нули или единицы.

 

Тогда получаем такой набор для x1, x2, … x8 для таких условий условий (x1→x2)=1; (x2→x3)=1 … (x7→x8)=1:


 

Остается найти возможные значения y после соответствующих значений x для таких условий (x1→y1)=1; (x2→y2)=1 … (x8→y8)=1:

Тут действуют те же два правила, а это значит, что в каждом наборе, где значение x = 0, соответствующий y может быть, либо 1, либо 0.

Поэтому, первому набору x: 0 0 0 0 0 0 0 0 соответствующий y может быть равен 1 или 0. Имеем 28 = 256 наборов y.

Набору 0 0 0 0 0 0 0 1 приходится 27 = 128 наборов y. Чтобы получить ответ, суммируем значения степеней двойки с восьми до нуля:

28 + 27 + 26 + 25 + 24 + 23 + 22 + 2 + 1 = 511.

 
Ответ: 511.

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

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

¬(x6 ≡ x7) ∧ (x6 ∨ x8) ∧ (¬x6 ∨ ¬x8) = 0
 

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

Решение.

Рассмотрим первое уравнение.

 

При x1 = 1 возможны два случая: x2 = 0 и x2 = 1. В первом случае x3 = 1. Во втором — x3 либо 0, либо 1. При x1 = 0 также возможны два случая: x2 = 0 и x2 = 1. В первом случае x3   либо 0, либо 1. Во втором — x3 = 0. Таким образом, уравнение имеет 6 решений (см. рисунок).

 


 

Рассмотрим систему из двух уравнений.

 

Пусть x1 = 1. При x2 = 0 возможен лишь один случай: x3 = 1, переменная x4 = 0. При x2 = 1 возможно два случая: x3 = 0 и x3 = 1. В первом случае x4 = 1, во втором — x4 либо 0, либо 1. Всего имеем 4 варианта.

 

Пусть x1 = 0. При x2 = 1 возможен лишь один случай: x3 = 0, переменная x4 = 1. При x2 = 0 возможно два случая: x3 = 0 и x3 = 1. В первом случае x4 либо 1, либо 0, во втором — x4 = 0. Всего имеем 4 варианта.

 

Таким образом, система из двух уравнений имеет 4 + 4 = 8 вариантов (см. рисунок).

 


 

Система из трёх уравнений будет иметь 10 решений, из четырёх — 12. Система из шести уравнений будет иметь 16 решений.

 

Ответ: 16.

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

 

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

      …

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

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

Решение.

Заметим, что если переменные одной пары x1, y1 равны, то в следующей паре переменные не равны и наоборот. Таким образом, если x1 = y1, (т. е. наборы 0, 0 и 1, 1) то получаем 29 наборов, так как у нас 9 пар переменных. Еще столько же наборов получим, если x1 ≠ y1. Итого, 29 · 2 = 210 = 1024 наборов.

 
Ответ: 1024.

30. Сколько существует различных наборов значений логических переменных 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, при которых выполнена данная система равенств.

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

Решение.

Возьмем первое условие (x1→x2) ∧ (y1→y2) = 1. Преобразовав импликации, получим: (¬x1 ∨ x2) ∧ (¬y1 ∨ y2) = 1. Уравнение выполняется тогда и только тогда, когда (¬x1 ∨ x2) = 1 и (¬y2 ∨ y3) = 1.

Таким образом, в двух наборах из 9 цифр x1, x2, … x9, y1, y2, … y9, действуют правила:

1. После единицы идут только единицы.

2. После нуля идут нули или единицы.

 

Тогда получаем такой набор для x1, x2, … x9 и для y1, y2, … y9:


 

Следовательно, количество наборов 10 * 10 = 100.

 
Ответ: 100.

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

 

((x1 ≡ x2) → (x2 ≡ x3)) /\ ((y1 ≡ y2) → (y2 ≡ y3)) = 1

((x2 ≡ x3) → (x3 ≡ x4)) /\ ((y2 ≡ y3) → (y3 ≡ y4)) = 1

((x6 ≡ x7) → (x7 ≡ x8)) /\ ((y6 ≡ y7) → (y7 ≡ y8)) = 1

 

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

Решение.

Существует 3 варианта выполнения первого уравнения системы:

 

1) x1 = x2 = x3. Тогда для выполнения следующего уравнения x3 должно быть равно x4, x4 = x5 в итоге получим, что все значения x равны. То есть либо x1, x2,…, x8 = 0, либо x1, x2,…, x8 = 1.

2) x1 <> x2, а x2 = x3. Тогда для выполнения следующего уравнения x3 должно быть равно x4 и т. д. Имеем либо x1=1 , x2,…, x8 = 0, либо x1=0, x2,…, x8 = 1.

3) x1 <> x2, x2 <> x3 (тогда x1=x3). Тогда x3 может быть равен x4 и не равен x4. Если они не равны, то тоже будет выполнено для пары xn и xn+1. Если же они равны, то все последующие уравнения однозначно определяются. Тогда будет 12 вариантов для данного случая.

 

Те же самые варианты подойдут и для части с y. Тогда общая формула имеет вид: (2 + 2 + 12) · ( 2 +2 +12) = 16 · 16 = 256.

 
Ответ: 256.

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

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

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

                        …

(y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1

y7 → x7 = 1

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

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1y1 и x2y2.

 

x1y1 x2y2
00 00
01 01
10 10
11 11

 

Для первой строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00, 01, 10 и 11.

Для второй строки x1y1 истина невозможна.

Для третей строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 10 и 11.

Для четвёртой строки x1y1 истина возможна тогда, когда пара x2y2 будет принимать значение 11.

 

Применим это для остальных пар:

 

x1y1 x2y2 x3y3 x4y4 x5y5 x6y6 x7y7
00 1 1 1 1 1 1 1
01 1 0 0 0 0 0 0
10 1 2 3 4 5 6 7
11 1 3 6 10 15 21 28

 

Вторая строка не рассматривается.

Таким образом, количество решений будет равно 

33. Сколько различных решений имеет уравнение

 

(K ∨ L) ∧ (M ∨ N) = 1

 
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

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

 

K ∨ L = 1, M ∨ N = 1.

 

Каждое из уравнений дает по 3 решения.

 

Рассмотрим уравнение А ∧ В = 1 если и А и В принимают истинные значения в трех случаях каждое, то в целом уравнение имеет 9 решений.

 

Следовательно ответ 9.

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

 

(x1 ∨ y1)≡¬(x2 ∨ y2) = 1

(x2 ∨ y2)≡¬(x3 ∨ y3) = 1

(x8 ∨ y8)≡¬(x9 ∨ y9) = 1

 

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

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1y1 и x2y2.

 

x1y1 x2y2
00 00
01 01
10 10
11 11

 

Для первой строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 01, 10 и 11.

Для второй, третей и четвёртой строк x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00.

 

x1y1 x2y2 x3y3 x4y4 x5y5 x6y6 x7y7 x8y8 x9y9
00 1 3 3 9 9 27 27 81 81
01 1 1 3 3 9 9 27 27 81
10 1 1 3 3 9 9 27 27 81
11 1 1 3 3 9 9 27 27 81

 

Таким образом, количество решений будет равно 

 
Ответ: 324.

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

 

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

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

((x6 ∨ y6) → (x7 ∨ y7)) ∧ (x6 → y6) = 1

(x7 → y7) = 1

 

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

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1y1 и x2y2.

 

x1y1 x2y2
00 00
01 01
10 10
11 11

 

Для первой строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 00, 01, 10 и 11.

Для второй строки x1y1 истина возможна тогда и только тогда, когда пара x2y2 будет принимать значения 01, 10 и 11.

Для третей строки x1y1 истина невозможна.

Для четвёртой строки x1y1 истина возможна тогда, когда пара x2y2 будет принимать значения 01, 10 и 11.

 

Применим это для остальных пар:

 

x1y1 x2y2 x3y3 x4y4 x5y5 x6y6 x7y7
00 1 1 1 1 1 1 1
01 1 3 7 15 31 63 127
10 1 3 7 15 31 63 127
11 1 3 7 15 31 63 127

 

Третья строка не рассматривается.

Таким образом, количество решений будет равно 

 
Ответ: 255.

36. Сколько различных решений имеет уравнение

 

((K ∨ L) → (L ∧ M ∧ N)) = 0

 
где K, L, M, N – логические переменные? В Ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве Ответа Вам нужно указать количество таких наборов.

Решение.

перепишем уравнение, используя более простые обозначения операций:

 

((K + L) → (L · M · N)) = 0

 

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

 

K + L = 1 и L · M · N = 0

 

2) из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая

 

3) если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения

 

4) если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

 

5) если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

 

6) всего получаем 4 + 3 + 3 = 10 решений.

 

Ответ: 10

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

 

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

(x3 ∨ x4) → (x5 ∧ x6) = 1

(x5 ∨ x6) → (x7 ∧ x8) = 1

 

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

Решение.

Решим задание методом отображений (Прочитать про метод отображений). Сначала рассмотрим пары x1x2 и x3x4.

 

x1x2 x3x4
00 00
01 01
10 10
11 11

 

Для первой строки x1x2 истина возможна тогда и только тогда, когда пара x3x4 будет принимать значения 00, 01, 10 и 11.

Для второй строки x1x2 истина возможна тогда и только тогда, когда пара x3x4 будет принимать значение 11.

Для третей строки x1x2 истина возможна тогда и только тогда, когда пара x3x4 будет принимать значение 11.

Для четвёртой строки x1x2 истина возможна тогда и только тогда, когда пара x3x4 будет принимать значение 11.

 

Применим это для остальных пар:

 

x1x2 x3x4 x5x6 x7x8
00 1 1 1 1
01 1 1 1 1
10 1 1 1 1
11 1 4 7 10

 

Третья строка не рассматривается.

Таким образом, количество решений будет равно 

 
Ответ: 13.

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

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

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

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

    x5 ∧ y5 ∧ z5 = 0

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

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

Решение.

x5 ∧ y5 ∧ z5 = 0

Решением этого уравнения являются наборы, в которых есть хотя бы один ноль, а именно: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0).

Теперь заметим, что первые три уравнения решаются аналогично.

Рассмотрим первое из них.

Пусть x5 = 0. Тогда все остальные переменные также равны нулю и уравнение имеет единственное решение.

Теперь пусть x5 = 1. Тогда решений будет 5: (0, 0, 0, 0, 1), (0, 0, 0, 1, 1), (0, 0, 1, 1, 1), (0, 1, 1, 1, 1) и (1, 1, 1, 1, 1).

Теперь зафиксируем некоторый набор (x5, y5, z5).

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

И как мы уже выяснили, если последняя переменная равна нулю, то уравнение имеет 1 решение, а если равна единице, то 5 решений.

Итого для каждого набора количество решений равно 5a, где a — количество единиц в наборе.

Итого получаем: 52 + 52 + 52 + 51 + 51 + 51 + 50 = 25 + 25 + 25 + 5 + 5 + 5 + 1 = 91

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

 

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

((x3 ≡ x4) ∨ (x5 ≡ x6)) ∧ (¬(x3 ≡ x4) ∨ ¬(x5 ≡ x6)) = 1

((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ (¬(x5 ≡ x6) ∨ ¬(x7 ≡ x8)) = 1

 

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

Решение.

Построим дерево решений первого уравнения:

 


 

Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.

 

Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:

 


 

Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2,…,x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.

 

Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:

 


 

Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2,…,x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.

 

Ответ: 32.

40. Сколько существует различных наборов значений логических переменных x1x2, … x8y1y2, … y8, которые удовлетворяют всем перечисленным ниже условиям:

 





 

В ответе не нужно перечислять все различные наборы значений переменных x1x2, … x8y1y2, … y8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

Будем обозначать набор входных переменных уравнения кортежем из четырёх чисел .

 

Рассмотрим первое уравнение. Переберём все 16 наборов переменных, подойдут 7 из них:

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

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

То есть (0, 0) даст решения (0, 0, 0, 0), (0, 0, 1, 1), (0, 0, 0, 1), (0, 0, 1, 0). (0, 1) — (0, 1, 0, 1). (1, 0) — (1, 0, 1, 0). (1, 1) — (1, 1, 1, 1).

Посчитаем, сколько каких пар  получилось среди всех решений системы из первых двух уравнений. Получилось (0, 0) — 1, (0, 1) — 3, (1, 0) — 3, (1, 1) — 3.

Перейдя к следующему уравнению, получим (0, 0) — 1, (0, 1) — 4, (1, 0) — 4, (1, 1) — 4.

И так далее, с каждым уравнением количество решений будет увеличиваться на 3.

Изначально было 7 решений, плюс ещё 6 уравнений, каждое из которых добавляет по 3 решения.

Итого .

 

Задание №23 ЕГЭ информатика. Логические уравнения.