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

Специальные формы КНФ

2015-01-07T08:06:22Z

91.205.162.27: /* КНФ в форме Крома */

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.

== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}

'''Пример :'''

<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> \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>

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

{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}

'''Пример:'''

<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>.

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

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

*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <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>

== См.также ==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]

==Примечания==

<references />

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

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

Специальные формы КНФ

2015-01-07T08:01:52Z

91.205.162.27: /* КНФ в форме Хорна */

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.

== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}

'''Пример :'''

<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> \iff </tex> выполнено следующее следствие:

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

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

{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}

'''Пример:'''

<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>.

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

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

*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <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>

== См.также ==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]

==Примечания==

<references />

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

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

Специальные формы КНФ

2015-01-07T07:59:41Z

91.205.162.27: /* См.также */

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.

== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}

'''Пример :'''

<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> \iff </tex> выполнено следующее следствие:

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

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

{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}

'''Пример:'''

<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>.

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

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

*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <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>

== См.также ==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]

==Примечания==

<references />

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

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

Специальные формы КНФ

2015-01-07T07:59:25Z

91.205.162.27: /* КНФ в форме Хорна */

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.

== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}

'''Пример :'''

<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> \iff </tex> выполнено следующее следствие:

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

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

{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}

'''Пример:'''

<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>.

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

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

*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <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>

== См.также ==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]

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

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

Специальные формы КНФ

2015-01-07T07:57:04Z

91.205.162.27: /* КНФ в форме Хорна */

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.

== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}

'''Пример :'''

<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> \iff </tex> выполнено следующее следствие:

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

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

{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}

'''Пример:'''

<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>

Каждая скобка представляет собой [http://ru.wikipedia.org/wiki/Дизъюнкт_Хорна''Дизъюнкт Хорна''].

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

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

*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <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>

== См.также ==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]

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

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

Специальные формы КНФ

2015-01-07T07:54:17Z

91.205.162.27: /* КНФ в форме Крома */

Рассмотрим две формы, с помощью которых можно представить формулы, заданные в [[Определение булевой функции#Представление булевых функций|конъюнктивной нормальной форме]], то есть имеющей вид конъюнкции выражений в скобках, каждое из которых представляет собой дизъюнкцию одного или нескольких литералов.

== КНФ в форме Крома ==
{{Определение
|definition=
'''Конъюнктивная нормальная форма (КНФ)''' (англ. ''conjunctive normal form'') '''в форме Крома (2-КНФ)''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию нескольких литералов, количество которых не превышает двух.}}

'''Пример :'''

<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> \iff </tex> выполнено следующее следствие:

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

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

{{Определение
|definition=
'''Конъюнктивная нормальная форма(КНФ) в форме Хорна''' {{---}} это конъюнкция выражений в скобках, каждое из которых представляет собой дизъюнкцию литералов, в которой присутствует не более одного литерала без отрицания.}}

'''Пример:'''

<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>

Каждая скобка представляет собой [http://ru.wikipedia.org/wiki/Дизъюнкт_Хорна''Дизъюнкт Хорна''].

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

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

*Существует алгоритм, который за полиномиальное время проверяет, что функцию, заданную в форме Хорна можно удовлетворить.
*Функцию <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>

== См.также ==
* [[СКНФ]]
* [http://en.wikipedia.org/wiki/2-satisfiability 2-SAT(КНФ в форме Крома)]

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

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