112
правок
Изменения
2SAT
,→Алгоритм решения
Рассмотрим любой дизъюнкт функции: <tex> a \vee b </tex>.
Несложно заметить, что это равнозначно записи <tex>(\overline a \to b \wedge \overline b \to \overline a) </tex>.
Построим [[Основные_определения_теории_графов|ориентированный граф]], где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: <tex>\overline a \to b </tex> и <tex> \overline b \to \overline a </tex> для каждого дизъюнкта функции <tex> a \vee b </tex>.
{{Теорема