Редактирование: Специальные формы КНФ

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
__TOC__
+
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов. Эти две формы интересны тем, что для них существует алгоритм, который может за полиномиальное время проверить, существует ли набор аргументов, на которых данная функция будет принимать значение <tex>1</tex>, в то время, как для обычной функции, не представленной данной формой, эта задача является [[Примеры NP-полных языков. Теорема Кука|NP-полной]]. Этот факт интересен потому, что, имея большое количество функций, которые можно свести к форме Хорна или Крома, мы сможем гарантированно вычислять необходимое нам условие за полиномиальное время, то есть обойти NP-полную задачу. Поэтому с помощью применения данных форм мы сможем решать очень быстро целый класс задач, например, задачи на графах, которые, как известно, имеют большое практическое применение. Именно поэтому полиномиальные алгоритмы в данной области очень интересны.
 
 
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов. Для двух этих форм существует алгоритм, который может за полиномиальное время проверить, существует ли набор аргументов, на которых данная функция будет принимать значение <tex>1</tex>, в то время, как для обычной функции, не представленной данной формой, эта задача является [[Примеры NP-полных языков. Теорема Кука|<tex>\mathrm{NP}</tex>-полной]]. Этот факт интересен потому, что, имея большое количество функций, которые можно свести к форме Хорна или Крома, мы сможем гарантированно вычислять необходимое нам условие за полиномиальное время. Поэтому с помощью применения данных форм мы сможем решать очень быстро целый класс задач, например, задачи на графах, которые, как известно, имеют большое практическое применение.
 
  
 
== КНФ в форме Крома ==
 
== КНФ в форме Крома ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Конъюнктивная нормальная форма '''(англ. ''conjunctive normal form, CNF'') '''в форме Крома, 2-КНФ<ref>[https://en.wikipedia.org/wiki/2-satisfiability Wikipedia {{---}} 2-satisfiability]</ref>''' (англ. ''2-CNF'') {{---}} конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию ровно двух литералов.}}
+
'''Конъюнктивная нормальная форма '''(англ. ''conjunctive normal form, CNF'') '''в форме Крома, 2-КНФ<ref>[https://en.wikipedia.org/wiki/2-satisfiability Wikipedia {{---}} 2-satisfiability]</ref>.''' (англ. ''2-CNF'') {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}
  
 
'''Пример :'''
 
'''Пример :'''
  
<tex>(x_1\vee\overline x_2)  \wedge (\overline x_1 \vee x_3 ) \wedge (\overline x_3 \vee x_2 ) \wedge (\overline x_1 \vee \overline x_2) \wedge\ldots </tex>
+
<tex>(x_1\vee\overline x_2)  \wedge (\overline x_1 \vee x_3 ) \wedge (\overline x_3 \vee x_2 ) \wedge (\overline x_1 \vee \overline x_2) \wedge... </tex>
  
 
{{Утверждение
 
{{Утверждение
Строка 18: Строка 16:
  
 
{{Утверждение
 
{{Утверждение
|statement=Функцию <tex>F</tex> можно задать в форме Крома <tex> \iff </tex> выполнено следующее следствие : <tex> F(x_1, \ldots, x_n)=F(y_1, \ldots, y_n)=F(z_1, \ldots, z_n)=1 \Rightarrow</tex>  <tex>F(\langle x_1, y_1, z_1 \rangle, \langle x_2, y_2, z_2 \rangle, \ldots, \langle x_n, y_n, z_n \rangle)</tex>
+
|statement=Функцию <tex>\mathbb{F}</tex> можно задать в форме Крома <tex> \iff </tex> выполнено следующее следствие : <tex> F(x_1, ..., x_n)=F(y_1, ..., y_n)=F(z_1, ..., z_n)=1 \Rightarrow</tex>  <tex>F(\langle x_1, y_1, z_1 \rangle, \langle x_2, y_2, z_2 \rangle, ..., \langle x_n, y_n, z_n \rangle)</tex>
 
}}
 
}}
  
== КНФ в форме Хорна ==
+
= КНФ в форме Хорна =
  
 
{{Определение
 
{{Определение
Строка 29: Строка 27:
 
'''Пример:'''
 
'''Пример:'''
  
<tex> (\overline x_1 \vee \overline x_2 \vee \ldots \vee \overline x_n ) \wedge (x_1  \vee \overline x_2  \vee \ldots \vee \overline x_n)\wedge \ldots</tex>
+
<tex> (\overline x_1 \vee \overline x_2 \vee ... \vee \overline x_n ) \wedge (x_1  \vee \overline x_2  \vee ... \vee \overline x_n)\wedge ...</tex>
  
 
Каждая скобка представляет собой Дизъюнкт Хорна<ref>[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B7%D1%8A%D1%8E%D0%BD%D0%BA%D1%82_%D0%A5%D0%BE%D1%80%D0%BD%D0%B0 Википедия {{---}} Дизъюнкт Хорна]</ref>.
 
Каждая скобка представляет собой Дизъюнкт Хорна<ref>[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B7%D1%8A%D1%8E%D0%BD%D0%BA%D1%82_%D0%A5%D0%BE%D1%80%D0%BD%D0%B0 Википедия {{---}} Дизъюнкт Хорна]</ref>.
Строка 41: Строка 39:
 
*#:Присвоим всем таким переменным значение <tex> 1 </tex>, если переменная входит без отрицания и <tex>0</tex> иначе, так как в конъюнкции они должны дать <tex>1</tex>. Заметим, что если какая-либо скобка после этого обратилась в <tex> 0 </tex>, то решения не существует.  
 
*#:Присвоим всем таким переменным значение <tex> 1 </tex>, если переменная входит без отрицания и <tex>0</tex> иначе, так как в конъюнкции они должны дать <tex>1</tex>. Заметим, что если какая-либо скобка после этого обратилась в <tex> 0 </tex>, то решения не существует.  
 
*# Отсутствуют одиночно стоящие переменные.  
 
*# Отсутствуют одиночно стоящие переменные.  
*#:Всем переменным надо присвоить значение <tex> 0 </tex> и булева формула разрешится. Это следует из того, что в каждом дизъюнкте есть хотя бы одна переменная с отрицанием, подставив в нее значение <tex>0</tex> мы получим <tex> 1</tex> в результате дизъюнкции. В итоге мы получим выражение вида: <tex>1\wedge 1 \wedge \ldots \wedge 1</tex>, что в результате даст нам <tex> 1</tex>. В таком случае дальнейшие шаги выполнять не нужно.
+
*#:Всем переменным надо присвоить значение <tex> 0 </tex> и булева формула разрешится. Это следует из того, что в каждом дизъюнкте есть хотя бы одна переменная с отрицанием, подставив в нее значение <tex>0</tex> мы получим <tex> 1</tex> в результате дизъюнкции. В итоге мы получим выражение вида: <tex>1\wedge 1 \wedge ... \wedge 1</tex>, что в результате даст нам <tex> 1</tex>. В таком случае дальнейшие шаги выполнять не нужно.
  
 
*'''Шаг 2.'''  
 
*'''Шаг 2.'''  
*:Опустим одиночно стоящие переменные и скобки, в которых значение стало равным <tex>1</tex>. Перейдём к <tex>1</tex> шагу алгоритма. По определению формы Хорна, в каждой из скобок, где мы опустили переменную, не больше <tex>1</tex> переменной без отрицания. Либо какая-то из переменных внутри скобки будет иметь отрицание, т.е. при подстановке <tex>0</tex> станет равна <tex>1</tex>, либо мы рассмотрим переменную без отрицания как отдельно стоящую переменную. Значит <tex>1</tex> шаг алгоритма выполнится верно. Будем проделывать алгоритм, начиная сначала, пока <tex>1</tex> шаг не найдёт ответ.
+
*:Опустим одиночно стоящие переменные и скобки, в которых значение стало равным <tex>1</tex>. Перейдём к <tex>1</tex> шагу алгоритма. По определению формы Хорна, в каждой из скобок, где мы опустили переменную не больше <tex>1</tex> переменной без отрицания. Либо какая-то из переменных внутри скобки будет иметь отрицание, т.е. при подстановке <tex>0</tex> станет равна <tex>1</tex>, либо мы рассмотрим переменную без отрицания как отдельно стоящую переменную. Значит <tex>1</tex> шаг алгоритма выполнится верно. Будем проделывать алгоритм, начиная сначала, пока <tex>1</tex> шаг не найдёт ответ.
  
 
Обозначим за <tex>N</tex> число вхождений переменных в формулу.
 
Обозначим за <tex>N</tex> число вхождений переменных в формулу.
Строка 50: Строка 48:
 
}}
 
}}
 
{{Утверждение
 
{{Утверждение
|statement=Функцию <tex>F</tex> можно задать в форме Хорна <tex>  \iff </tex> выполнено следующее следствие:<tex> F(x_1, \ldots, x_n)=F(y_1, \ldots, y_n)=1  \Rightarrow  F(x_1 \wedge y_1, x_2  \wedge  y_2, \ldots, x_n \wedge y_n)</tex>
+
|statement=Функцию <tex>F</tex> можно задать в форме Хорна <tex>  \iff </tex> выполнено следующее следствие:<tex> F(x_1, ..., x_n)=F(y_1, ..., y_n)=1  \Rightarrow  F(x_1 \wedge y_1, x_2  \wedge  y_2, ..., x_n \wedge y_n)</tex>
 
}}
 
}}
  
Строка 62: Строка 60:
 
<references />
 
<references />
  
==Источники информации==
 
*[https://en.wikipedia.org/wiki/Conjunctive_normal_form Wikipedia {{---}} CNF]
 
  
  

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

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

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