Специальные формы КНФ — различия между версиями
VVolochay (обсуждение | вклад) |
VVolochay (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций | + | Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], т.е имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов: |
| − | + | = КНФ в форме Крома = | |
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | '''Конъюнктивной нормальной формой(КНФ) в форме Крома''' - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию нескольких литералов,количество которых не превышает двух.}} | + | '''Конъюнктивной нормальной формой(КНФ) в форме Крома''' - это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}} |
| − | '''Пример:''' | + | '''Пример :''' |
<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> | <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> | ||
| + | '''Утверждения:''' | ||
| + | *Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Крома можно удовлетворить(т.е КНФ в форме Крома не является тождественным <tex>0</tex>). | ||
| − | == КНФ в форме Хорна | + | |
| + | *Функцию <tex>F</tex> можно задать в форме Крома, если выполнено следствие(верно и обратное): | ||
| + | |||
| + | <tex> F(x_1, ..., x_n)=F(y_1, ..., y_n)=F(z_1, ..., z_n)= 1 \Rightarrow F(<x_1, y_1, z_1>, <x_2, y_2, z_2>, ..., <x_n, y_n, z_n >) </tex> | ||
| + | |||
| + | |||
| + | = КНФ в форме Хорна = | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | '''Конъюнктивной нормальной формой(КНФ) в форме Хорна''' - это конъюнкция выражений в скобках,каждое из которых представляет собой дизъюнкцию литералов,в которой присутствует не более одного неотрицательного литерала.}} | + | '''Конъюнктивной нормальной формой(КНФ) в форме Хорна''' - это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного неотрицательного литерала.}} |
'''Пример:''' | '''Пример:''' | ||
| Строка 23: | Строка 31: | ||
| − | Каждая скобка представляет собой '' | + | Каждая скобка представляет собой [http://ru.wikipedia.org/wiki/Дизъюнкт_Хорна''Дизъюнкт Хорна'']. |
| + | |||
| + | Любую формулу можно представить в виде КНФ в форме Хорна. Для этого формулу необходимо преобразовать в конъюнкцию элементарных дизъюнкций и далее каждую дизъюнкцию представить в форме дизьюнкта Хорна. | ||
| + | |||
| + | '''Утверждения:''' | ||
| + | |||
| + | *Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить. | ||
| + | |||
| + | |||
| + | *Функцию <tex>F</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> | |
Версия 10:10, 15 октября 2010
Рассмотрим две формы, с помощью которых можно представить формулы, заданные в конъюнктивной нормальной форме, т.е имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов:
КНФ в форме Крома
| Определение: |
| Конъюнктивной нормальной формой(КНФ) в форме Крома - это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух. |
Пример :
Утверждения:
- Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Крома можно удовлетворить(т.е КНФ в форме Крома не является тождественным ).
- Функцию можно задать в форме Крома, если выполнено следствие(верно и обратное):
КНФ в форме Хорна
| Определение: |
| Конъюнктивной нормальной формой(КНФ) в форме Хорна - это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного неотрицательного литерала. |
Пример:
Каждая скобка представляет собой Дизъюнкт Хорна.
Любую формулу можно представить в виде КНФ в форме Хорна. Для этого формулу необходимо преобразовать в конъюнкцию элементарных дизъюнкций и далее каждую дизъюнкцию представить в форме дизьюнкта Хорна.
Утверждения:
- Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
- Функцию можно задать в форме Хрома, если выполнено следствие(верно и обратное):
