ЕГЭ: Задание 23 - Системы логических уравнений.

Задание 23


Пример

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

(x1 ≡ x2) ∨ (x3 ≡ x4) ∧ (¬(x1 ≡ x2) ∨ ¬(x3 ≡ x4)) = 1
(x3 ≡ x4) ∨ (x5 ≡ x6) ∧ (¬(x3 ≡ x4) ∨ ¬(x5 ≡ x6)) = 1
...
(x7 ≡ x8) ∨ (x9 ≡ x10) ∧ (¬(x7 ≡ x8) ∨ ¬(x9 ≡ x10)) = 1


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

Решение:

В первую очередь найдем количество наборов x1, x2, x3, x4, для которых выполняется первое равенство. Очевидно, что равенство верно только тогда, когда одновременно истинны два выражения (x1 ≡ x2) ∨ (x3 ≡ x4) и (¬(x1 ≡ x2) ∨ ¬(x3 ≡ x4)).

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

Отсюда следует, что либо (x1 ≡ x2) и (x3 x4), либо (x1 x2) и (x3 ≡ x4). Таких наборов 4*2 = 8 (Для любой пары значений переменных x1, x2 подходят только 2 пары значений переменных x3, x4).

Во втором равенстве (x3 ≡ x4) ∨ (x5 ≡ x6) ∧ (¬(x3 ≡ x4) ∨ ¬(x5 ≡ x6)) = 1 добавляются переменные x5, x6. Рассуждая так же, как и раньше, получим, что либо (x3 x4) и (x5 x6), либо (x3 ≡ x4) и (x5 ≡ x6). Следовательно, если определено значение переменных x3, x4, то существует 2 подходящих варианта значений переменных x5, x6. Отсюда находим, что первым двум равенствам удовлетворяет 8*2=16 различных наборов переменных x1, x2, ... , x6.

Рассуждая аналогично, получим 16*2=32 наборов переменных x1, x2, ... , x8, удовлетворяющих первым трем равенствам и 32*2=64 набора переменных x1, x2, ... , x10, при которых выполнены все четыре равенства.


Ответ: 64


Праздники России

Рейтинг