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