Совершенные ДНФ и КНФ

Конституентой единицы набора называется конъюнкт .

Конституентой нуля набора называется дизъюнкт

Отметим, что тогда и только тогда, когда .

Пример: Формула есть конституента единицы К¹ (1,0,1) (1 – без отрицания, 0 – отрицание);

Формула есть конституента нуля К⁰(0,0,1) (1 – отрицание, 0 – без отрицания).

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы;

Совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых.

Термин «совершенная» происходит от двух понятий:

1) Все переменные в каждой элементарной конъюнкции;

2) СДНФ (СКНФ) единственна.

[Подсказка: СКНФ – где 0 (скобки обязательны), СДНФ – где 1]

Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная x_i из набора {x_i,..., х_л} входит ровно один раз, причем входит либо сама x_i,либо ее отрицание |.

Пример: 1) формула – СДНФ,

2) формула – СКНФ,

3) формула не СДНФ, но ДНФ.

x1	х2	х3	f(x1, х2, х3)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

f(x₁, х₂, х₃) = – СДНФ;

f(x₁, х₂, х₃) = – СКНФ.