Редактирование: 2SAT

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
|definition = <b><tex>\mathrm {2SAT}</tex></b> (2-satisfiability) выполнимость функции — задача распределения аргументов в булевой [[КНФ|КНФ]] функции, записанной в виде [[Специальные_формы_КНФ|2-КНФ (КНФ Крома)]], таким образом, чтобы результат данной функции был равен <tex> 1 </tex>.
+
|definition = <b>2-SAT </b> (2-satisfiability) выполнимость функции — задача распределения аргументов в булевой [[КНФ|КНФ]] функции, записанной в виде [[Специальные_формы_КНФ|2-КНФ (КНФ Крома)]], таким образом, чтобы результат данной функции был равен <tex> 1 </tex>.
 
}}
 
}}
  
Строка 7: Строка 7:
  
 
Рассмотрим любой дизъюнкт функции: <tex> a \vee b </tex>.
 
Рассмотрим любой дизъюнкт функции: <tex> a \vee b </tex>.
Несложно заметить, что это равнозначно записи <tex>(\overline a \to b \wedge \overline b \to a) </tex>.
+
Несложно заметить, что это равнозначно записи <tex>(\overline a \to b \wedge b \to \overline a) </tex>.
  
Построим [[Основные_определения_теории_графов|ориентированный граф]], где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: <tex>\overline a \to b </tex> и <tex> \overline b \to a </tex> для каждого дизъюнкта функции <tex> a \vee b </tex>.
+
Построим [[Основные_определения_теории_графов|ориентированный граф]], где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: <tex>\overline a \to b </tex> и <tex> b \to \overline a </tex> для каждого дизъюнкта функции <tex> a \vee b </tex>.
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для того, чтобы данная задача <tex>\mathrm {2SAT}</tex> имела решение, необходимо и достаточно, чтобы для любой переменной <tex> x </tex> из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> нельзя достичь <tex> x </tex> одновременно. <tex>(\overline x \to x) \wedge (x \to \overline x) </tex>.
+
Для того, чтобы данная задача <tex>\mathrm 2SAT</tex> имела решение, необходимо и достаточно, чтобы для любой переменной <tex> x </tex> из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> нельзя достичь <tex> x </tex> одновременно. <tex>(\overline x \to x \wedge x \to \overline x) </tex>.
 
|proof=
 
|proof=
<tex>(\Rightarrow)</tex>Докажем достаточность: Пусть <tex>\mathrm {2SAT}</tex>  имеет решение. Докажем, что не может быть такого, чтобы для любой переменной <tex> x </tex> из вершины <tex> x </tex> можно достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> можно достичь <tex> x </tex> одновременно. <tex>((\overline x \to x) \wedge (x \to \overline x)) </tex>. Тогда чтобы из <tex> \overline x </tex> достичь <tex> x </tex> <tex> (\overline x \to x </tex> было верным), <tex> x </tex> должен быть равен <tex> 1 </tex>. С другой стороны для того, чтобы из <tex> x </tex> достичь <tex> \overline x </tex> <tex> (x \to \overline x </tex> было верным), <tex> x </tex> должен быть равен 0. Отсюда следует противоречие.
+
<tex>(\Rightarrow)</tex>Докажем достаточность: Пусть <tex>\mathrm 2SAT</tex>  имеет решение. Докажем, что не может быть такого, чтобы для любой переменной <tex> x </tex> из вершины <tex> x </tex> можно достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> можно достичь <tex> x </tex> одновременно. <tex>(\overline x \to x \wedge x \to \overline x) </tex>. Тогда чтобы из <tex> \overline x </tex> достичь <tex> x </tex> <tex> (\overline x \to x </tex> было верным), <tex> x </tex> должен быть равен <tex> 1 </tex>. С другой стороны для того, чтобы из <tex> x </tex> достичь <tex> \overline x </tex> <tex> (\overline x \to x </tex> было верным), <tex> x </tex> должен быть равен 0. Отсюда следует противоречие.
  
<tex>(\Leftarrow)</tex>Докажем необходимость: Пусть для любой переменной <tex> x </tex> из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> нельзя достичь <tex> x </tex> одновременно. Докажем, что этого достаточно, чтобы <tex>\mathrm {2SAT}</tex>  имело решение. Пусть из <tex> \overline x </tex> можно достичь <tex> x </tex>, но из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex>. Докажем, что из <tex> x </tex> не достижимо такой <tex> y </tex>, что из <tex> y </tex> достижимо <tex> \overline y </tex>. (т.е. <tex> x \to y \to \overline y\, (x = 1, y = 0)) </tex>. Если из <tex> x \to y </tex>, то <tex> \overline x \vee y </tex>, отсюда следует <tex> \overline y \to \overline x </tex>. Тогда <tex> x \to y \to \overline y \to \overline x </tex>. Следовательно <tex> x \to \overline x </tex>. Противоречие.
+
<tex>(\Leftarrow)</tex>Докажем необходимость: Пусть для любой переменной <tex> x </tex> из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex> и из вершины <tex> \overline x </tex> нельзя достичь <tex> x </tex> одновременно. Докажем, что этого достаточно, чтобы <tex>\mathrm 2SAT</tex>  имело решение. Пусть из <tex> \overline x </tex> можно достичь <tex> x </tex>, но из вершины <tex> x </tex> нельзя достичь <tex> \overline x </tex>. Докажем, что из <tex> x </tex> не достижимо такой <tex> y </tex>, что из <tex> y </tex> достижимо <tex> \overline y </tex>. (т.е. <tex> x \to y \to \overline y (x = 1, y = 0)) </tex>. Если из <tex> x \to y </tex>, то <tex> \overline x \vee y </tex>, отсюда следует <tex> \overline y \to \overline x </tex>. Тогда <tex> x \to y \to \overline y \to \overline x </tex>. Следовательно <tex> x \to \overline x </tex>. Противоречие.
 
}}
 
}}
  
Строка 23: Строка 23:
  
 
#Построим граф импликаций.  
 
#Построим граф импликаций.  
#<i>Найдём в этом графе [[Отношение_связности,_компоненты_связности#Сильная связность | компоненты сильной связности]] за время <tex>O(N + M)</tex></i>, где <tex> N </tex> количество вершин в графе (удвоенное количество переменных), а <tex> M </tex> количество ребер графа (удвоенное количество дизъюнктов).
+
#<i>Найдём в этом графе [[Отношение_связности,_компоненты_связности#Сильная связность | компоненты сильной связности]] за время <tex>O(N + M)</tex></i>, где <tex> N </tex> - количество вершин в графе (количество переменных), а <tex> M </tex> - количество ребер графа (удвоенное количество дизъюнктов).
#Пусть <tex>comp[v]</tex> — это номер компоненты сильной связности, которой принадлежит вершине <tex>v</tex>. Проверим, что для каждой переменной <tex>x</tex> вершины <tex>x</tex> и <tex>\overline x</tex> лежат в разных компонентах, т.е. <tex>comp[x] \ne comp[\overline x]</tex>. Если это условие не выполняется, то вернуть <i>решение не существует</i>.  
+
#Пусть <tex>comp[v]</tex> — это номер компоненты сильной связности, которой принадлежит вершине <tex>v</tex>. Проверим, что для каждой переменной <tex>x</tex> вершины <tex>x</tex> и <tex>\overline x</tex> лежат в разных компонентах, т.е. <tex>comp[x] \ne comp[\overline x]</tex>. Если это условие не выполняется, то вернуть "решение не существует".  
#Если <tex>comp[x] > comp[\overline x]</tex>, то переменной <tex>x</tex> выбираем значение <tex> \mathtt {true}</tex>, иначе <tex> \mathtt {false}</tex>.
+
#Если <tex>comp[x] > comp[\overline x]</tex>, то переменной <tex>x</tex> выбираем значение <tex> \mathtt true</tex>, иначе - <tex> \mathtt false</tex>.
  
 
Компоненты сильной связности найдем за <tex>O(N + M)</tex>, затем проверим каждую из <tex>N</tex> переменных за <tex>O(N)</tex>. Следовательно асимптотика <tex>O(N + M)</tex>.
 
Компоненты сильной связности найдем за <tex>O(N + M)</tex>, затем проверим каждую из <tex>N</tex> переменных за <tex>O(N)</tex>. Следовательно асимптотика <tex>O(N + M)</tex>.
  
== Примеры решения 2SAT  ==  
+
== Примеры решения 2-SAT ==  
 
=== Первый пример ===
 
=== Первый пример ===
  
Строка 47: Строка 47:
 
\overline a \to \overline b \wedge
 
\overline a \to \overline b \wedge
 
a \to b
 
a \to b
</tex>.
+
</tex>
  
Построим ориентированный граф со следующими множествами вершинам и ребер:
+
Построим граф и рассмотрим пути:
множество вершин <tex> V = \{a, b, c, \overline a, \overline b, \overline c\}, </tex>
 
множество ребер <tex> E = \{(\overline a, b), (\overline b, a), (\overline a, c), (\overline c, a), (b, c), (\overline c, \overline b), (\overline a, \overline b), (b, a)\}</tex>.
 
 
 
Рассмотрим в графе следующие пути:
 
 
* <tex> \overline a \to b \to a </tex>
 
* <tex> \overline a \to b \to a </tex>
 
* <tex> \overline a \to \overline b \to a </tex>
 
* <tex> \overline a \to \overline b \to a </tex>
 
* <tex> \overline c \to a </tex>
 
* <tex> \overline c \to a </tex>
 
* <tex> a \to c </tex>
 
* <tex> a \to c </tex>
* <tex> \overline a \to b \to c </tex>.
+
* <tex> \overline a \to b \to c </tex>
  
Т.к. <tex> \overline a \to a </tex>, то <tex> a = 1, \overline a = 0 </tex>.
+
Т.к. <tex> \overline a \to a </tex>, то <tex> a = 1, \overline a = 0 </tex>
  
Т.к. <tex> a \to c </tex> и <tex> a = 1 </tex>, то <tex> c = 1, \overline c = 0 </tex>.
+
Т.к. <tex> a \to c </tex> и <tex> a = 1 </tex>, то <tex> c = 1, \overline c = 0 </tex>
  
Значения <tex> b </tex> может быть любым, т.к. все вершины, из которых можно добраться в <tex> b </tex> имеют значение ноль.
+
Значения <tex> b </tex> может быть любым, т.к. все вершины, из которых можно добраться в <tex> b </tex> имеют значение ноль
  
<b> Ответ: </b> <tex> a = 1, b = 0, c = 1 </tex> или <tex> a = 1, b = 1, c = 1 </tex>.
+
<b> Ответ: </b> <tex> a = 1, b = 0, c = 1 </tex> или <tex> a = 1, b = 1, c = 1 </tex>
  
 
=== Второй пример ===
 
=== Второй пример ===
Строка 90: Строка 86:
 
</tex>
 
</tex>
  
Построим ориентированный граф со следующими множествами вершинам и ребер:
+
Заметим следующий путь: <tex> a \to c \to \overline a \to b \to a </tex>
множество вершин V = <tex>\{a, b, c, \overline a, \overline b, \overline c\}, </tex>
 
множество ребер <tex> E = \{(a, c), (\overline c, \overline a), (c, \overline a), (a, \overline c), (\overline a, b), (\overline b, a), (b, a), (\overline b, \overline a)\}</tex>.
 
  
Заметим следующий путь: <tex> a \to c \to \overline a \to b \to a </tex>.
+
Отсюда следует, что <tex> a \to \overline a \to a </tex>
  
Отсюда следует, что <tex> a \to \overline a \to a </tex>.
+
Следовательно по ранее доказанной теореме, у данной функции решений нет
  
Следовательно по ранее доказанной теореме, у данной функции решений нет.
+
<b> Ответ: </b> Решений нет
  
<b> Ответ: </b> Решений нет.
 
  
== Использование 2SAT  ==
+
== Использование 2-SAT ==
  
Решение <tex>\mathrm {2SAT}</tex> может потребоваться в следующих задачах:
+
*[https://ru.wikipedia.org/wiki/Латинский_квадрат Латинские квадраты]
*латинские квадраты<ref> [https://ru.wikipedia.org/wiki/Латинский_квадрат Википедия — Латинские квадраты] </ref>,
+
*[https://ru.wikipedia.org/wiki/Квазигруппа_(социология) Квазигруппы]
*квазигруппы<ref>[https://ru.wikipedia.org/wiki/Квазигруппа_(социология) Википедия — Квазигруппы]</ref>,
+
*[https://ru.wikipedia.org/wiki/Теорема_Рамсея#.D0.A7.D0.B8.D1.81.D0.BB.D0.B0_.D0.A0.D0.B0.D0.BC.D1.81.D0.B5.D1.8F Числа Рамсея]
*числа Рамсея<ref>[https://ru.wikipedia.org/wiki/Теорема_Рамсея#.D0.A7.D0.B8.D1.81.D0.BB.D0.B0_.D0.A0.D0.B0.D0.BC.D1.81.D0.B5.D1.8F Википедия — Числа Рамсея]</ref>,
+
*[https://ru.wikipedia.org/wiki/Система_Штейнера Система Штейнера]
*система Штейнера<ref>[https://ru.wikipedia.org/wiki/Система_Штейнера Википедия — Система Штейнера]</ref>,
+
*Проектирование протоколов (пример: для сетевых коммуникаций)
*проектирование протоколов (пример: для сетевых коммуникаций),
+
*Электронная коммерция (Электронные аукционы и автоматизированные брокеры
*электронная коммерция (Электронные аукционы и автоматизированные брокеры,
+
*Теории кодирования, криптографии
*теории кодирования, криптографии,
+
*Проектирование и тестирование лекарств (мед. препаратов)
*проектирование и тестирование лекарств (мед. препаратов).
 
  
 
== См. также ==
 
== См. также ==
  
 
*[[3CNFSAT | NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]
 
*[[3CNFSAT | NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]
 
== Примечания ==
 
<references/>
 
  
 
== Источники информации ==
 
== Источники информации ==
  
*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2SAT (2-CNF) ]
+
*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2-SAT (2-CNF) ]
*[https://en.wikipedia.org/wiki/2-satisfiability Википедия — 2-satisfiability]
+
*[https://en.wikipedia.org/wiki/2-satisfiability 2-satisfiability — Википедия]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Булевы функции ]]
 
[[Категория: Булевы функции ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: