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

Пусть (x₁,..., x_n) — набор логических переменных, Δ = (δ₁,,.., δ_п) — набор нулей и единиц.

Конституентой единицы набора Δ называется конъюнкт K¹(δ₁ ... δ_п) = .

Конституентой нуля набора Δ называется дизъюнкт K⁰(δ₁ … δ_п) = .

Отметим, что K¹(δ₁ ... δ_п) = 1, а K⁰(δ₁ … δ_п) = 0 тогда и только тогда, когда х₁ = δ₁, х₂ = δ₂, х_n = δ_n.

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

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

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

 

Пример. Формула есть конституента единицы К¹(1,0,1).

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

Формула — СДНФ.

Формула — СКНФ.

Формула не является СДНФ.