Модуль: Системы логических уравнений


Задача

1/36

Система логических уравнений - 1

Теория

В 23 задании требуется посчитать количество решений системы логических уравнений. Самый очевидный способ - составить список всех возможных значений всех переменных, по списку подставлять значения в систему и проверять, есть ли противоречие. Если нет, то прибавлять к ответу 1 решение.


 
Этот способ очень трудоемкий. Другой вариант - составить дерево всех возможных значений всех переменных. Теперь нужно подставлять значения переменных не во всю систему, а поочередно в каждое уравнение. Так, после подставления всех комбинаций х1 и х2 в первое уравнение, пары значений, которые при подстановке дают противоречие, исключатся, автоматически исключив ветку комбинаций далее в дереве, после чего их подставлять не нужно. Кол-во неисключившихся листов в дереве и будет ответом на задачу.


 
На одной высоте в дереве есть несколько одинаковых значений пар переменных (например, в данном дереве 3 такие пары переменных, что х3=1 и х4=0). Чтобы не подставлять их несколько раз, нужно предварительно сделать на каждое уравнение отдельное дерево, подставить значения переменных туда и исключить ненужные пары. Тогда при составлении главного дерева нужно будет лишь переносить результат со вспомогательных деревьев на главное. Если уравнения в системе являются однотипными, т. е. различаются только переменными (как в примере), то не требуется рисовать дерево для каждого, так как эти деревья будут идентичными.


 
Метод отображения - самый быстрый и менее объемный по оформлению способ решения многих систем логических уравнений. В нем вместо главного дерева возможных значений всех переменных строится таблица количества возможных значений всех переменных. В дереве из всех одинаковых значений одной переменной идут одинаковые ветки значений следующих переменных. Чтобы не перерисовывать идентичные ветки, можно "срастить" их в одну, при этом, чтобы кол-во решений оставалось корректным, добавим к каждой вершине k - коэффициент, равный кол-ву "срощенных" переменных. При этом исключенные переменные сращивать не нужно, так как они не влияют на ответ. Таблица - это "срощенное" дерево, в ячейках которой находятся полученные коэффициенты.



 
При решении методом отображения дерево не рисуется, сразу строится таблица, коэффициенты которой считаются с помощью «"срощенных" вспомогательных деревьев» (далее - стрелки). Значение в ячейке равно сумме значений в ячейках, из которых идет стрелка. Соответственно, в первом столбце значение в ячейках равно единице. Сумма значений последнего столбца - количество решений системы.


 
Как решать системы логических уравнений методом отображения?
1. Для неодинаковых уравнений сделать стрелки
2. Заполнить таблицу с помощью стрелок
3. Посчитать кол-во решений системы
 

Задача

Сколько различных решений имеет система логических уравнений?
x1+x2=1
x2+x3=1
x3+x4=1
x4+x5=1
x5+x6=1

Выберите правильный ответ, либо введите его в поле ввода

Комментарий учителя