Викиконспекты - Вклад участника [ru]

2SAT

2019-01-07T01:40:13Z

176.59.15.115: /* Алгоритм решения */

{{Задача
|definition = <tex>\mathrm {2SAT}</tex> (2-satisfiability) выполнимость функции — задача распределения аргументов в булевой [[КНФ|КНФ]] функции, записанной в виде [[Специальные_формы_КНФ|2-КНФ (КНФ Крома)]], таким образом, чтобы результат данной функции был равен <tex> 1 </tex>.
}}

== Алгоритм решения ==

Рассмотрим любой дизъюнкт функции: <tex> a \vee b </tex>.
Несложно заметить, что это равнозначно записи <tex>(\overline a \to b \wedge \overline b \to a) </tex>.

Построим [[Основные_определения_теории_графов|ориентированный граф]], где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: <tex>\overline a \to b </tex> и <tex> \overline b \to a </tex> для каждого дизъюнкта функции <tex> a \vee b </tex>.

{{Теорема
|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>.
|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>(\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>O(N + M)</tex>, где <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>. Если это условие не выполняется, то вернуть решение не существует.
#Если <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>.

== Примеры решения 2SAT ==
=== Первый пример ===

Рассмотрим следующую функцию: <tex> (a \vee b) \wedge
(a \vee c) \wedge
(\overline b \vee c) \wedge
(\overline b \vee a) </tex>

Данная функция эквивалентна функции
<tex>
\overline a \to b \wedge
\overline b \to a \wedge
\overline a \to c \wedge
\overline c \to a \wedge
b \to c \wedge
\overline c \to \overline b \wedge
\overline a \to \overline b \wedge
a \to b
</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), (a, b)\}</tex>.

Рассмотрим в графе следующие пути:
* <tex> \overline a \to b \to a </tex>
* <tex> \overline a \to \overline b \to a </tex>
* <tex> \overline c \to a </tex>
* <tex> a \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> a \to c </tex> и <tex> a = 1 </tex>, то <tex> c = 1, \overline c = 0 </tex>.

Значения <tex> b </tex> может быть любым, т.к. все вершины, из которых можно добраться в <tex> b </tex> имеют значение ноль.

 Ответ: <tex> a = 1, b = 0, c = 1 </tex> или <tex> a = 1, b = 1, c = 1 </tex>.

=== Второй пример ===

Рассмотрим следующую функцию:
<tex>
(\overline a \vee c) \wedge
(\overline c \vee \overline a) \wedge
(a \vee b) \wedge
(\overline b \vee a)
</tex>

Данная функция эквивалентна функции
<tex>
a \to c \wedge
\overline c \to \overline a \wedge
c \to \overline a \wedge
a \to \overline c \wedge
\overline a \to b \wedge
\overline b \to a \wedge
b \to a \wedge
\overline b \to \overline 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>.

Следовательно по ранее доказанной теореме, у данной функции решений нет.

 Ответ: Решений нет.

== Использование 2SAT ==

Решение <tex>\mathrm {2SAT}</tex> может потребоваться в следующих задачах:
*латинские квадраты<ref> [https://ru.wikipedia.org/wiki/Латинский_квадрат Википедия — Латинские квадраты] </ref>,
*квазигруппы<ref>[https://ru.wikipedia.org/wiki/Квазигруппа_(социология) Википедия — Квазигруппы]</ref>,
*числа Рамсея<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>,
*система Штейнера<ref>[https://ru.wikipedia.org/wiki/Система_Штейнера Википедия — Система Штейнера]</ref>,
*проектирование протоколов (пример: для сетевых коммуникаций),
*электронная коммерция (Электронные аукционы и автоматизированные брокеры,
*теории кодирования, криптографии,
*проектирование и тестирование лекарств (мед. препаратов).

== См. также ==

*[[3CNFSAT | NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]

== Примечания ==
<references/>

== Источники информации ==

*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2SAT (2-CNF) ]
*[https://en.wikipedia.org/wiki/2-satisfiability Википедия — 2-satisfiability]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

Композиция отношений

2019-01-06T18:44:02Z

176.59.15.115: /* Степень отношений */

{{Определение
|definition=
'''Композицией''' (произведением, суперпозицией) бинарных отношений (англ. ''composition of binary relations'') <tex>R\subseteq A\times B</tex> и <tex>S\subseteq B\times C</tex> называется такое отношение <tex> (R \circ S) \subseteq A\times C</tex>, что:

<tex>\forall a \in A, c \in C : a (R \circ S) c \iff \exists b \in B : (a R b) \wedge (b S c) </tex>.
}}
Примером такого отношения может служить отношение на некотором множестве <tex>A</tex> населенных пунктов <tex>R\subseteq A\times A</tex> {{---}} отношение "можно доехать на поезде", а <tex>S\subseteq A\times A</tex> {{---}} отношение "можно доехать на автобусе". Тогда отношение <tex>R\circ S\subseteq A\times A</tex> {{---}} отношение "можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)".

== Степень отношений ==

{{Определение
|definition=
'''Степень отношения''' (англ. ''power of relation'') <tex>R^{n} \subseteq A\times A</tex>, определяется следующим образом:

* <tex> R^{n} = R^{n-1} \circ R; </tex>

* <tex> R^{1} = R; </tex>

* <tex> R^{0} = \{ (x, x) \mid x \in A \}</tex>;
}}

В связи с этим понятием, также вводятся обозначения:

<tex> R^{+} = \bigcup\limits^{\infty}_{i=1} R^{i} </tex> — [[Транзитивное замыкание]] (англ. ''transitive closure'') отношения <tex>R</tex>;

<tex> R^{*} = \bigcup\limits^{\infty}_{i=0} R^{i} </tex> — Транзитивно-рефлексивное замыкание отношения <tex>R</tex>

== Обратное отношение ==

{{Определение
|definition=
Отношение <tex>R^{-1} \subseteq B\times A</tex> называют '''обратным''' (англ. ''inverse relation'') для отношения <tex> R \subseteq A\times B</tex>, если:

<tex> bR^{-1}a \iff aRb </tex>
}}

{{Определение
|definition=
'''Ядром отношения''' (англ. ''kernel of relation'') <tex>R</tex> называется отношение <tex> R\circ R^{-1} </tex>
}}

== Свойства ==
Композиция отношений обладает следующими свойствами:

* Ядро отношения <tex> R </tex> [[Симметричное отношение|симметрично]]:   <tex>a (R \circ R^{-1}) b \iff b (R \circ R^{-1})a </tex>

* Композиция отношений [[Ассоциативная операция|ассоциативна]]:   <tex> (R \circ S) \circ T = R \circ (S \circ T) </tex>

* Обратное отношение для отношения, являющемуся обратным к <tex> R </tex> есть само <tex> R :</tex>   <tex> (R^{-1})^{-1} = R </tex>

* Обратное отношение к композиции отношений <tex>R </tex> и <tex>S </tex> есть композиция отношений, обратных к <tex>R </tex> и <tex>S : </tex>   <tex> (R \circ S) ^ {-1} = (S ^ {-1}) \circ (R ^ {-1}) </tex>

* Обратное отношение к объединению отношений <tex>R </tex> и <tex>S </tex> есть объединение отношений, обратных к <tex>R </tex> и <tex>S : </tex>  <tex> (R \cup S) ^ {-1} = (R^{-1}) \cup (S^{-1}) </tex>

* Обратное отношение к пересечению отношений <tex>R </tex> и <tex>S </tex> есть пересечение отношений, обратных к <tex>R </tex> и <tex>S : </tex>  <tex> (R \cap S) ^ {-1} = (R^{-1}) \cap (S^{-1}) </tex>

== См. также ==
* [[Бинарное_отношение|Бинарное отношение]]
* [[Транзитивное_замыкание|Транзитивное замыкание]]

==Источники информации==
* Новиков Ф. А. {{---}} Дискретная математика для программистов: Учебник для вузов. 3-е изд. {{---}} СПБ.: Питер, 2009 {{---}} 52 с.
* [http://en.wikipedia.org/wiki/Composition_of_relations Wikipedia {{---}} Composition of relations]
* [http://math2.uncc.edu/~hbreiter/m1165/Lecture10.pdf UNC Charlotte {{---}} Lectures in Discrete Mathematics: Composition of Relations and Directed Graphs.]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Отношения ]]