Специальные формы КНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(КНФ в форме Крома)
м
Строка 1: Строка 1:
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.
+
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов. Эти две формы интересны тем, что для них существует алгоритм, который может за полиномиальное время проверить, существует ли набор аргументов, на которых данная функция будет принимать значение <tex>1</tex>, в то время, как для обычной функции, не представленной данной формой, эта задача является [[Примеры NP-полных языков. Теорема Кука|NP-полной]].  
  
 
== КНФ в форме Крома ==
 
== КНФ в форме Крома ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}
+
'''Конъюнктивная нормальная форма (КНФ) в форме Крома (2-КНФ)''' (англ. ''2-SAT'') {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}
  
 
'''Пример :'''
 
'''Пример :'''
Строка 22: Строка 22:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}
+
'''Конъюнктивная нормальная форма (КНФ)в форме Хорна''' (англ. ''Horn clause'') {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}
  
 
'''Пример:'''
 
'''Пример:'''
Строка 41: Строка 41:
 
== См.также ==
 
== См.также ==
 
* [[СКНФ]]
 
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]
+
* [[2SAT]]
  
 
==Примечания==
 
==Примечания==
  
 
<references />
 
<references />
 +
 +
==Источники информации==
 +
*[https://en.wikipedia.org/wiki/Horn_clause| Wikipedia {{---}} Horn clause]
 +
*[https://en.wikipedia.org/wiki/2-satisfiability| Wikipedia {{---}} 2-satisfiability]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Булевы функции ]]
 
[[Категория: Булевы функции ]]

Версия 10:10, 20 января 2016

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в конъюнктивной нормальной форме, то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов. Эти две формы интересны тем, что для них существует алгоритм, который может за полиномиальное время проверить, существует ли набор аргументов, на которых данная функция будет принимать значение [math]1[/math], в то время, как для обычной функции, не представленной данной формой, эта задача является NP-полной.

КНФ в форме Крома

Определение:
Конъюнктивная нормальная форма (КНФ) в форме Крома (2-КНФ) (англ. 2-SAT) — это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.


Пример :

[math](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... [/math]

Утверждения:

  • Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Крома можно удовлетворить(т.е КНФ в форме Крома не является тождественным [math]0[/math]).
  • Функцию [math]F[/math] можно задать в форме Крома [math] \iff [/math] выполнено следующее следствие:

[math] F(x_1, ..., x_n)=F(y_1, ..., y_n)=F(z_1, ..., z_n)=1 \Rightarrow[/math] [math]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)[/math]

КНФ в форме Хорна

Определение:
Конъюнктивная нормальная форма (КНФ)в форме Хорна (англ. Horn clause) — это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.


Пример:

[math] (\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 ...[/math]

Каждая скобка представляет собой Дизъюнкт Хорна[1].

Любую формулу можно представить в виде КНФ в форме Хорна. Для этого формулу необходимо преобразовать в конъюнкцию элементарных дизъюнкций и далее каждую дизъюнкцию представить в форме дизьюнкта Хорна.

Утверждения:

  • Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
  • Функцию [math]F[/math] можно задать в форме Хорна [math] \iff [/math] выполнено следующее следствие:

[math] 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)[/math]

См.также

Примечания

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