Введение в схемы, автоматы и алгоритмы


Дизъюнктивные и конъюнктивные нормальные формы


Имеется ряд специальных подклассов формул, позволяющих задавать все булевы функции. В этом разделе мы определим два таких подкласса функций, использующих только операции

\wedge, \vee
и
\neg
.

Пусть

\mathbf{X}=\{X_1,\ldots, X_n\}
- это множество пропозициональных переменных. Введем для каждого
i=1,...,n
обозначения:
X_i^0= \neg X_i
и
X_i^1= X_i
. Формула
X_{i_1}^{\sigma_1}\wedge X_{i_2}^{\sigma_2}\wedge \ldots \wedge X_{i_k}^{\sigma_k}

(

X_{i_1}^{\sigma_1}\vee X_{i_2}^{\sigma_2}\vee \ldots \vee X_{i_k}^{\sigma_k}
), в которой
\sigma_{i_j} \in \{0,1\}
и все переменные разные, т.е.
X_{i_j} \neq X_{i_r}
при
j \neq r
, называется элементарной конъюнкцией (элементарной дизъюнкцией).

Определение 1.4.Формула

\mathcal{D}
называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид
\mathcal{D}= K_1 \vee K_2\vee \ldots \vee K_r,

где каждая формула

K_j\ ( j=1,...,r)
- это элементарная конъюнкция.
\mathcal{D}
называется совершенной ДНФ, если в каждую из ее конъюнкций
K_j
входят все
n
переменных из
\mathbf{X}.

Аналогично, формула

\mathcal{C}
называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е.
\mathcal{C}= D_1 \vee D_2\vee \ldots \vee D_r,

где каждая формула

D_j\ ( j=1,...,r)
- это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую
D_j
входят все
n
переменных из
\mathbf{X}.

Рассмотрим произвольную булеву функцию

f(X_1,\ldots,X_n)
, зависящую от переменных из
\mathbf{X}
. Oбозначим через
N_f^+

множество наборов значений переменных, на которых

f
принимает значение 1, а через
N_f^-

множество наборов, на которых

f
принимает значение 0, т.е.
N_f^+= \{(\sigma_1,\ldots, \sigma_n)\ |\ f(\sigma_1,\ldots, \sigma_n)=1\}
и
N_f^-= \{(\sigma_1,\ldots, \sigma_n)\ |\ f(\sigma_1,\ldots, \sigma_n)=0\}.

Определим по этим множествам две формулы:

\mathcal{D}_f = \bigvee_{(\sigma_1,\ldots, \sigma_n)\in N_f^+} (X_1^{\sigma_1}\wedge X_2^{\sigma_2}\wedge \ldots \wedge X_n^{\sigma_n})

и

\mathcal{C}_f = \bigwedge_{(\sigma_1,\ldots, \sigma_n)\in N_f^-} (X_1^{\neg\sigma_1}\vee X_2^{\neg\sigma_2}\vee \ldots \vee X_n^{\neg\sigma_n})

Теорема 1.1.

(1) Если функция

f
не равна тождественно 0, то формула
\mathcal{D}_f
- это совершенная ДНФ, задающая функцию
f
.

(2) Если функция

f
не равна тождественно 1, то формула
\mathcal{C}_f
- это совершенная КНФ, задающая функцию
f
.

Пример 1.2. Например, для функции

f_{\Phi_1}
, представленной в таблице 1.1

совершенная ДНФ равна

\mathcal{D}= (\neg X_1 \wedge \neg X_2 \wedge \neg X_3) \vee (\neg X_1 \wedge \neg X_2 \wedge X_3) \vee

(X_1 \wedge X_2 \wedge \neg X_3) \vee ( X_1 \wedge \neg X_2 \wedge \neg X_3) \vee ( X_1 \wedge X_2 \wedge X_3)
, а ее совершенная КНФ:
\mathcal{C}=(X_1 \vee \neg X_2 \vee X_3) \wedge (\neg X_1 \vee X_2 \vee \neg X_3) \wedge (\neg X_1 \vee \neg X_2 \vee X_3).

Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере

f_{\Phi_1}
может быть задана более простой ДНФ:
\mathcal{D}_1= (\neg X_1 \wedge \neg X_2 ) \vee ( X_2 \wedge X_3)\vee (X_1 \wedge \neg X_2 \wedge \neg X_3)
.




Начало  Назад  Вперед



Книжный магазин