Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) ∨ (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) = 1
(x3 ∧ ¬x4) ∨ (¬x3 ∧ x4) ∨ (x5 ∧ x6) ∨ (¬x5 ∧ ¬x6) = 1
...
(x7 ∧ ¬x8) ∨ (¬x7 ∧ x8) ∨ (x9 ∧ x10) ∨ (¬x9 ∧ ¬x10) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений для первого уравнения.
Первое уравнение имеет 12 решений. Второе уравнение связано с первым только через переменные x3 и x4. На основании древа решений для первого уравнения выпишем пары значений переменных x3 и x4, которые удовлетворяют первому уравнению и укажем количество таких пар значений.
| Количество пар значений | x3 | x4 |
|---|---|---|
| ×4 | 1 | 1 |
| ×4 | 0 | 0 |
| ×2 | 1 | 0 |
| ×2 | 0 | 1 |
Поскольку уравнения идентичны с точностью до индексов переменных, древо решений второго уравнения аналогично первому. Следовательно, пара значений x3 = 1 и x4 = 1 порождает два набора переменных x3, ..., x6, удовлетворяющих второму уравнению. Поскольку среди наборов решений первого уравнения данных пар четыре, всего получаем 4 · 2 = 8 наборов переменных x1, ..., x6, удовлетворяющих системе из двух уравнений. Рассуждая аналогично для пары значений x3 = 0 и x4 = 0, получаем 8 наборов переменных x1, ..., x6. Пара x3 = 1 и x4 = 0 порождает четыре решения второго уравнения. Поскольку среди наборов решений первого уравнения данных пар две, получаем 2 · 4 = 8 наборов переменных x1, ..., x6, удовлетворяющих системе из двух уравнений. Аналогично для x3 = 0 и x4 = 1 — 8 наборов решений. Всего система из двух уравнений имеет 8 + 8 + 8 + 8 = 32 решения.
Проведя аналогичные рассуждения для системы из трёх уравнений, получаем 80 наборов переменных x1, ..., x8, удовлетворяющих системе. для системы из четырёх уравнений существует 192 набора переменных x1, ..., x10, удовлетворяющих системе.
Ответ: 192.
Пересчитывали 3 раза, получается, что после 2 уравнения 34 решения, а у вас 32, у нас 8+12+8+6, а у вас 8+8+8+8
Приведите ваше решение полностью. Напишите, каким образом вы получаете 12 и 6.
Вообще, можно решить эту задачу намного проще. Если заметить (x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) тождественно ¬(x1 == x2) и (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) тождественно (x3 == x4), то ,подставив в изначальное уравнение, получаем: ¬(x1 == x2) ∨ (x3 == x4) = 1. Однако и это выражение можно преобразовать и получить (x1 == x2) → (x3 == x4) = 1.
Преобразовав аналогичным образом все выражения получаем:
(x1 == x2) → (x3 == x4) = 1
(x3 == x4) → (x5 == x6) = 1
...
(x7 == x8) → (x9 == x10) = 1
Заменив (x1 == x2) на А1, (x3 == x4) на А3, ... , (x9 == x10) на А9 получаем наборы решений для А-итых:
А1 А3 А5 А7 А9
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
Каждому A-итому соответствует(вне зависимости от значения) пара пар значений i-того и i + 1 - ого x-сов => (2 * 2 * 2 * 2 * 2) * 6(так как шесть наборов решений для А-итых) = 192