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

Любая формула вида х или х над стандартным базисом, где х - произвольное переменное, называется литералом. Таким образом, литерал есть обозначение либо самого переменного х, либо его отрицания. Часто используют такое обозначение: для σ ∈ {0, 1} пишут х^σ, понимая под этим само переменное х, если σ = 1, и отрицание х, если σ = 0, т.е.

Подставляя в (6.8) 0 и 1 вместо х, получаем

Часто используют также обозначение х˜, понимая под этим любой из двух литералов - х или х.

Формула вида х˜₁х˜₂ ... х˜_m (соответственно вида х˜₁ ∨ х˜₂ ∨ ... ∨ х˜_m), где все фигурирующие в ней переменные попарно различны, называется элементарной конъюнкцией (соответственно элементарной дизъюнкцией).

Определение 6.4. Дизъюнктивная нормальная форма (ДНФ) от переменных х₁, ... , x_n - это формула вида К₁ ∨ ... ∨ К_m, где K_i, i = 1,m, - элементарная конъюнкция, содержащая некоторые из литералов х₁, ... , x_n. В том случае, когда в каждую конъюнкцию K_i для каждого номера j = 1,n входит в точности один из литералов х˜_j, ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Двойственным образом, т.е. с использованием принципа двойственности для булевых алгебр, определяются конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ).

Теорема 6.2. Любая булева функция, отличная от константы 0 ( соответственно от константы 1) пред ставима в виде СДНФ (соответственно в виде СКНФ).

◀ Докажем первое из двух (взаимно двойственных) утверждений теоремы. Для функции f ∈ P_2,n, не равной тождественно 0, рассмотрим множество С^1f = {α˜: f(α˜) = 1}. Каждый набор из С^1f называется конституентой единицы функции f. Так как по условию f ≠ 0 тождественно, то множество С^1f не пусто. Каждому набору α˜ ∈ С^1f поставим в соответствие элементарную конъюнкцию К_α˜ = x^α11 x^α22...x^α_nn, которую также называют конституентой единицы функции f. Ясно, что К_α˜ обращается в единицу только на наборе _{α˜. Тогда искомой СДНФ для функции f будет}

Согласно принципу двойственности, СКИФ для той же функции будет иметь вид

где множество наборов C^0f = {α˜: f(α˜) = 0}, и каждый набор α˜ из C^0f называют конституентной нуля функции f; при этом элементарная дизъюнкция D_α˜ сопоставляется конституенте нуля α˜ по следующему правилу:

т.е. если в наборе i-я компонента равна 0, то в D_α˜ ставим само переменное x_i, если иначе - отрицание переменногоx_i (таким образом, дизъюнкция D_α˜ обращается в нуль только на наборе α˜). ▶

Из доказанного следует, что любая булева функция может быть представлена в виде формулы над стандартным базисом (СДНФ или СКНФ), и, значит, стандартный базис есть полное множество булевых функций.

Рассмотрим в качестве примера построение СДНФ и СКНФ для мажоритарной функции (см. 6.1). Конституентами единицы для нее служат наборы: α˜₁ = (0, 1, 1), α˜₂ = (1, 0, 1), α˜₃= (1, 1, 0) и α˜₄ = (1, 1, 1). Им соответствуют элементарные конъюнкции: К_α˜1 = х₁х₂х₃, К_α˜2 = х₁х₂х₃, К_α˜3 = х₁х₂х₃, К_α˜4 = х₁х₂х₃. Тогда СДНФ, представляющая мажоритарную функцию, имеет вид

х₁х₂х₃ ∨ х₁х₂х₃ ∨ х₁х₂х₃ ∨ х₁х₂х₃    (6.9)

Для получения СКНФ для той же функции выпишем все конституенты нуля данной функции: (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0). Сопоставим им элементарные дизъюнкции: х₁ ∨ х₂ ∨ х₃, х₁ ∨ х₂ ∨ x₃, х₁ ∨ x₂ ∨ х₃ и x₁ ∨ х₂ ∨ х₃ соответственно.

В результате получим СКНФ для мажоритарной функции в виде

(х₁ ∨ х₂ ∨ x₃) (х₁ ∨ х₂ ∨ x ₃) (х₁ ∨ x ₂ ∨ x₃) (x ₁ ∨ х₂ ∨ x₃)     (6.10)

Заметим, что если в формуле СКНФ (6.10) мы раскроем скобки и преобразуем полученное выражение согласно законам булевой алгебры, проведя тем самым эквивалентные преобразования СКНФ, то придем к формуле СДНФ (6.9).