Изменения

Перейти к: навигация, поиск

2SAT

Нет изменений в размере, 21:51, 7 октября 2016
Алгоритм решения
Рассмотрим любой дизъюнкт функции: <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>.
{{Теорема
112
правок

Навигация