Сколько существует различных наборов значений логических переменных 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
x5 ∨ y1 = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких
наборов.
Заметим, что первое и второе уравнения не связаны между собой ни через какие переменные. Рассмотрим последнее уравнение. Логическое «И» истинно, когда истинны оба высказывания. Представим решения последнего уравнения в виде таблицы:
| y1 | x5 | |
|---|---|---|
| А) | 0 | 1 |
| Б) | 1 | 0 |
| В) | 1 | 1 |
Случай А). Рассмотрим второе уравнение. Для того, чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Импликация ложна только тогда, когда посылка истинна, а следствие ложно, следовательно, если y1 = 0, то y2 = 0 или 1. В случае, когда y2 = 1 все последующие переменные тоже должны быть равными 1, в случае, когда y2 = 0 имеем два варианта для y3. Таким образом, получаем 5 наборов переменных y1, y2, y3, y4, y5, которые решают первое уравнение.
Рассмотрим первое уравнение. Импликация Для того, чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. В случае, когда x5 = 1, скобка (x4 → x5) истинна при двух значениях переменной x4. В случае, когда x4 = 0, все предыдущие переменные должны быть равны 0, в случае, когда x4 = 1, предыдущая переменная может принимать два значения, и. т. д. Таким образом, получаем 5 наборов переменных x1, x2, x3, x4, x5, которые решают второе уравнение.
Всего в случае А) имеем 5 · 5 = 25 наборов переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств.
Случай Б). Рассмотрим второе уравнение. Поскольку y1 = 1, имеем 1 набор y1, y2, y3, y4, y5, который решает первое уравнение. Рассмотрим первое уравнение. Поскольку x5 = 0, все предыдущие переменные должны быть равными 0. Таким образом, имеем 1 набор переменных x1, x2, x3, x4, x5, который решает второе уравнение.
Всего в случае Б) имеем 1 · 1 = 1 набор переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при котором выполнена данная система равенств.
Случай В). Рассмотрим второе уравнение. Поскольку y1 = 1, имеем 1 набор y1, y2, y3, y4, y5, который решает первое уравнение (см. случай Б). Рассмотрим первое уравнение. Поскольку x5 = 1, имеем 5 наборов переменных x1, x2, x3, x4, x5, который решает второе уравнение (см. случай А).
Всего в случае В) имеем 5 · 1 = 5 наборов переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств.
Таким образом, получаем 25 + 1 + 5 = 31 наборов переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств.
Ответ: 31.