For Informatics: КНФ и СКНФ

КНФ

Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов.

Любая булева формула может быть приведена к КНФ.

Формулы в КНФ:

\neg A \wedge (B \vee C)

(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)

A \wedge B

Формулы не в КНФ:

\neg (B \vee C)

(A \wedge B) \vee C

A \wedge (B \vee (D \wedge E)).

Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:

\neg B \wedge \neg C

(A \vee C) \wedge (B \vee C)

A \wedge (B \vee D) \wedge (B \vee E).

Алгоритм построения КНФ

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:

A \rightarrow B = \neg A \vee B

A \leftrightarrow B = (\neg A \vee B) \wedge (A \vee \neg B)

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

\neg (A \vee B) = \neg A \wedge \neg B

\neg (A \wedge B) = \neg A \vee \neg B

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Пример построения КНФ

Приведем к КНФ формулу

F = ( X \rightarrow Y ) \wedge (( \neg Y \rightarrow Z ) \rightarrow \neg X )

Преобразуем формулу F к формуле не содержащей → :

F = ( \neg X \vee Y ) \wedge ( \neg ( \neg Y \rightarrow Z ) \vee \neg X ) = ( \neg X \vee Y ) \wedge ( \neg ( \neg \neg Y \vee Z ) \vee \neg X )

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

F = ( \neg X \vee Y) \wedge ((\neg Y \wedge \neg Z) \vee \neg X)

По закону дистрибутивности получим КНФ:

F = (\neg X \vee Y) \wedge (\neg X \vee \neg Y) \wedge (\neg X \vee \neg Z)

СКНФ

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

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

Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. Возьмем таблицу истинности для 4 четырех переменных:

$x_1$	$x_2$	$x_3$	$x_4$	$f(x_1, x_2, x_3, x_4)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

В ячейках строки́

f(x_1, x_2, x_3, x_4)

отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

$x_1 = 0$
$x_2 = 0$
$x_3 = 1$
$x_4 = 1$

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:

x_1 \vee x_2 \vee \overline{x_3} \vee \overline{x_4}

Остальные члены СКНФ составляются по аналогии.

For Informatics

Главная

пятница, 26 декабря 2014 г.

КНФ и СКНФ

КНФ

Алгоритм построения КНФ

Пример построения КНФ

СКНФ

Комментариев нет:

Отправить комментарий

$x_1$	$x_2$	$x_3$	$x_4$	$f(x_1, x_2, x_3, x_4)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

$x_1$	$x_2$	$x_3$	$x_4$	$f(x_1, x_2, x_3, x_4)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

Главная

пятница, 26 декабря 2014 г.

КНФ и СКНФ

КНФ

Алгоритм построения КНФ

Пример построения КНФ

СКНФ

Комментариев нет:

Отправить комментарий

пятница, 26 декабря 2014 г.

$x_1$	$x_2$	$x_3$	$x_4$	$f(x_1, x_2, x_3, x_4)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1