Совершенные нормальные формы.

СНДФ.

Рассмотрим конъюнкцию (1.29)

Набор < > двоичный и существует таких различных наборов. Т.о., число различных конъюнкций вида 1.29 также равно .

Сопоставим каждой конъюнкции (1.29) номер, определяемый номером набора < >. Тогда запись:

()

означает дизъюнкцию всех конъюнкций с номерами из множества .

Аналогично, запись () означает конъюнкцию всех дизъюнкций с номерами из множества .

Покажем, что =1 тогда и только тогда, когда выполняется равенство . Это вытекает из рассмотрения следующих четырех возможных случаев.

1. 3.

2. 4.

Таким образом, конъюнкция не обращается в нуль только в том случае, если одновременно выполняются следующие i равенств.

(1.30)

Из 1.30 вытекает, что ()= при условии, что

Тогда на основании теоремы 1.3 можно утверждать, что любая ФАЛ, кроме нуля, может быть представлена в виде:

¦()= () (1.31)

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

Алгоритм перехода из таблично заданной ФАЛ к СНДФ.

1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в единицу.

2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как 1, он выписывается без изменения в конъюнкцию, соответствующую данному набору. Если же =0, то в соответствующую конъюнкцию вписывается его отрицание.

3. Все полученные конъюнкции соединяются между собой знаками дизъюнкции.

Пример. Пусть имеем таблично заданную ФАЛ:

Табл. 1.5.1.

					¦(, , , )

и тогда имеем:

¦(, , , )= v v v v

v v v

Если вместо соотношения 1.23 воспользоваться соотношением 1.24, то получим совершенно нормальную полиноминальную форму СНПФ. СНПФ получается из СНДФ заменой знака V на Å. Так, в рассмотренном примере функция в СНПФ будет иметь вид:

¦(, , , )= Å Å Å Å Å

Å Å

Совершенная нормальная конъюктивная форма(СНКФ)

Теорема 1.5. Любая ФАЛ, кроме единицы, может быть представлена в виде:

(1.32.)

Символ означает, что & берется только по тем наборам ,

для которых выполняется равенство: =0.

Доказательство:

Имеем: или

.

Равенство не нарушается, если от обеих частей взять отрицание:

.

Применяя закон де - Моргана получаем:

На тех наборах, для которых , соответствующая дизъюнкция

.

И такие наборы на значение конъюнкции не влияют и ими можно пренебречь, и тогда:

Теорема доказана для всех .

Представление функции в виде 1.32 называется СНКФ – совершенной нормальной конъюктивной формой.

Из сравнения (1.26) и (1.32) вытекает, что ,

при условии, что .