Среди множества формул, равносильных данной, выделяют формулы, имеющие ту или иную нормальные формы.

Дадим необходимые определения.

Определение. Литералом называется атомарная формула (кроме 1 и 0) или ее отрицание.

Элементарной конъюнкцией называется литерал или конъюнкция литералов.

Определение. Формула G имеет дизъюнктивную нормальную форму (сокращенно: ДНФ), если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций.

Например, формулы X,ØY,X&ØY,(X&ØY)Ú(ØX&Z) имеют ДНФ, а формулы Ø(X&Y), XÚYÚ1, X®Y не имеют.

Теорема 1.3. Для всякой формулы F существует формула G, равносильная F и имеющая дизъюнктивную нормальную форму.

Теорема легко следует из рассмотрения следующего алгоритма, который по данной формуле F выдает (одну из формул) G, удовлетворяющих условию теоремы.

Прежде, чем привести алгоритм, условимся не различать формулы, которые получаются одна из другой применением коммутативности и ассоциативности конъюнкции и дизъюнкции, т.е. законов 7-10.

Алгоритм приведения к ДНФ.

Шаг 1. Используя законы 21 и 20 исключить из исходной формулы эквиваленцию и импликацию.

Шаг 2. С помощью законов 17-19 занести отрицание к атомарным формулам.

Шаг 3. Если формула содержит подформулу вида

H₁&(H₂ÚH₃),

то заменить ее на равносильную формулу

(H₁&H₂)Ú(H₁&H₃).

Применение алгоритма проиллюстрируем на примере формулы

F=Ø(X«Y)&X.

Выполним первый шаг. Для этого, используя закон 21, заменим X«Y равносильной ей формулой (X®Y)&(Y®X). Затем в полученной формуле с помощью закона 20 исключим связку ®. Мы получим формулу

F₁=Ø[(ØXÚY)&(ØYÚX)]&X.

Перейдем ко второму шагу. Применение закона 17, приведет к формуле

F₂=[Ø(ØXÚY)ÚØ(ØYÚX)]&X.

Затем дважды воспользуемся законом 18 и снимем двойное отрицание (закон 19), получим формулу

F₃=[(X&ØY)Ú(Y&ØX)]&X.

Шаг 2 выполнен.

Выполнение шага 3 состоит из применения дистрибутивности к формуле F₃. Это дает нам формулу

F₄=(X&ØY&X)Ú(Y&ØX&X).

Алгоритм на этом завершен. Формула F₄ имеет дизъюнктивную нормальную форму. Но эту формулу можно упростить. Действительно, формула Y&ØX&X в силу законов 15 и 3 равносильна 0, а формула X&ØY&X равносильна X&ØY (закон 5). Следовательно, формула F₄ равносильна формуле

F₅=X&ØY.

Формула F₅, как и F₄, имеет ДНФ и равносильна исходной формуле F.

Рассмотренный пример показывает, что формула F может иметь не одну равносильную формулу, именющую ДНФ. Иногда это обстоятельство является неудобным. Чтобы его исключить, вводится более узкое понятие, нежели ДНФ.

Определение. Формула G имеет совершенную дизъюнктивную нормальную форму (сокращенно: СДНФ) относительно атомарных формул X₁,…,X_n, если выполнены следующие условия:

1) F=F(X1,…,Xn), т.е. в записи формулы участвуют только X1,…,Xn;

2) F имеет дизъюнктивную нормальную форму, т.е. F=C1ÚC2Ú…ÚCk, где C1,…,Ck – элементарные конъюнкции;

3) каждая элементарная конъюнкция содержит один и только один из литералов Xi или ØXi для любого i=1,…,n;

4) F не содержит одинаковых элементарных конъюнкций.

Например формулы X, ØX&Y, (ØX&Y)Ú(X&ØY) имеют СДНФ относительно содержащихся в них атомарных формул. Формулы Ø(X&Y), (X&Y)Ú(ØX&Z), (X&Y&X)&(ØX&ØY), (X&Y)Ú(X&ØY)&(Y&X) не имеют СДНФ (относительно содержащихся в них атомарных формул). Для первой формулы не выполняется второе условие, для второй и третьей – третье условие, для четвертой формулы не выполняется последнее условие из определения СДНФ.

Теорема 1.4. Для любой выполнимой формулы F существует равносильная ей формула G, имеющая совершенную дизъюнктивную нормальную форму.

Как и теорема 1.3, эта теорема легко следует из соответствующего алгоритма, который по формуле F выдает формулу G, удовлетворяющую условию теоремы 1.4.

Алгоритм приведения к СДНФ.

Шаг 1 – Шаг 3 – те же, что и в алгоритме приведения к ДНФ.

Шаг 4. Если элементарная конъюнкция С не содержит атомарной формулы X_i, ни ее отрицания для некоторого i=1,…,n, то заменить C на две элементарные конъюнкции (C&X)Ú(C&ØX_i).

Шаг 5. Если элементарная конъюнкция C содержит два вхождения одного литерала, то одно из них вычеркнуть. Если же С содержит X_i и ØX_i для некоторого i=1,…,n, то вычеркнуть всю элементарную конъюнкцию.

Шаг 6. Если формула содержит одинаковые элементарные конъюнкции, то вычеркнуть одну из них.

Напомним, что «одинаковость» понимается с точностью до коммутативности и ассоциативности конъюнкции и дизъюнкции.

В качестве примера рассмотрим ту же формулу F=Ø(X«Y)&X, что и в примере на предыдущий алгоритм. Как мы видели, выполнение шагов 1-3 приводит к формуле F₄. Эта формула имеет ДНФ, но не имеет СДНФ, поскольку для нее не выполняется третье условие. Если для F₄ выполнить шаг 4, то в первой элементарной конъюнкции будет зачеркнуто одно из вхождений литерала X, а вторая элементарная конъюнкция будет вычеркнута вся. В результате мы получим формулу F₅. Она имеет СДНФ относительно X и Y.

Рассмотрим второй пример. Пусть G=(X&Y)Ú(X&ØZ). Эта формула имеет ДНФ, поэтому выполнение алгоритма приведения к СДНФ начинается с шага 4. При выполнении этого шага элементарная конъюнкция X&Y будет заменена на (X&Y&Z)Ú(X&Y&ØZ), а X&ØZ – на (X&ØZ&Y)Ú(X&ØZ&ØY). В результате получим формулу

G₁=(X&Y&Z)Ú(X&Y&ØZ)Ú(X&ØZ&Y)Ú(X&ØZ&ØY).

Условия шага 5 для формулы G₁ ложны, поэтому этот шаг формулы G₁ не имеет. Формула G₁ содержит одинаковые элементарные конъюнкции – вторую и третью. При выполнении шестого шага будет зачеркнута одна из них и получится формула

G₂=(X&Y&Z)Ú(X&Y&ØZ)Ú(X&ØY&ØZ).

Это и есть формула, равносильная G и имеющая СДНФ относительно входящих в G атомарных формул.

Ответим на естественно возникающий вопрос о том, зачем в формулировке теоремы 1.4 требуется выполнимость формулы F? Нетрудно доказать, что если формула F невыполнима, т.е. при любой интерпретации j выполняется равенство j(F)=0, то после приведения F к ДНФ каждая элементарная конъюнкция будет содержать хотя бы одну пару противоположных литералов X и ØX. Но в таком случае на шаге 5 все элементарные конъюнкции будут вычеркнуты.

Имеется еще один способ приведения к СДНФ, основанный на построении таблицы истинности исходной формулы. Изложим этот способ на примере формулы

F=X₁&(X₂®X₃)

составим таблицу истинности формулы F (таблицу 1.5).

Таблица 1.5

Выделим строки, в которых в столбце F стоит 1. (Хотя бы одна такая строка должна быть, так как формула F выполнима.) Это будут первая, третья и четвертая строки. Каждой из выделенных строк поставим в соответствие элементарную конъюнкцию X₁^a1X₂^aaX₃^a3, где X_i^ai=X_i, если в столбце X_i этой строки стоит 1, и X_i^ai=ØX_i, если в столбце X_i этой строки стоит 0, где i=1,2,3. Так, первой строке будет поставлена в соответствие элементарная конъюнкция X₁&X₂&X₃, третьей – X₁&ØX₂&X₃, четвертой – X₁&ØX₂&ØX₃. Формула

G=(X₁&X₂&X₃)Ú(X₁&ØX₂&X₃)Ú(X₁&ØX₂&ØX₃)

имеет СДНФ относительно X₁,X₂,X₃. В то же время G имеет ту же таблицу истинности, что и F. Это означает, что G равносильна F. Следовательно, G – искомая формула.

Из других нормальных форм рассмотрим конъюнктивную нормальную форму. Она получается из ДНФ заменой & на Ú и Ú на &. Дадим точные определения.

Определение. Элементарной дизъюнкцией (или дизъюнктом) называется литерал или дизъюнкция литералов.

Определение. Формула G имеет конъюнктивную нормальную форму (сокращенно: КНФ)Б если она является элементарной дизъюнкцией или конъюнкцией элементарных дизъюнкций.

Например, формулы X,ØY, XÚØY, X&ØY, (XÚØY)&(XÚZ) имеют КНФ, а формулы X®Y, Ø(XÚY), (X&ØY)Ú(X&ØZ) не имеют.

Для конъюнктивных нормальных форм справедливо утверждение, аналогичное теореме 1.3.

Теорема 1.5 Для всякой формулы F существует формула G равносильная F и имеющая конъюнктивную нормальную форму.

Доказательство теоремы легко следует из анализа алгоритма приведения к КНФ, который в свою очередь получается из алгоритма приведения к ДНФ, если шаг 3 заменить на

Шаг 3^/. Если формула содержит подформулу вида

H₁Ú(H₂&H₃),

то заменить ее на равносильную ей формулу

(H₁ÚH₂)&(H₁ÚH₃).

В силу очевидной аналогии между ДНФ и КНФ примеров приведения к КНФ здесь приводить не будем.