2. Построение сднф и скнф функции

Кроме табличного задания функции алгебры логики применяются различные аналитические методы. К ним относятся – дизъюктивная и коньюктивная форма.

Набор значений переменных можно обобщенно представить, как последовательность констант .

Введем условное обозначение:

(6.1)

где совокупность – порождающие множества;

– первичный терм;

– число порождающих множеств.

Произведение вида называют элементарной конъюнкцией и записывают в векторной форме следующим образом:

(6.2)

В такой записи вектор переменных определяет, какие переменные образуют конъюнкцию, а набор задает порядок расстановки знаков инверсии (отрицания) над ними.

Формула вида , где - различные элементарные конъюнкции, называется дизъюнктивной нормальной формой (ДНФ).

При тождественно, ее можно представить в виде:

(6.3)

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

Длина СДНФ равна числу наборов, на которых функция .

Алгоритм построения СДНФ:

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

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

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

Соответственно выражение

(6.4)

где – какой-либо двоичный набор, причем среди переменных могут быть совпадающие, называется элементарной дизъюнкцией.

Формула вида , где - различные элементарные дизъюнкции, называется конъюнктивной нормальной формой (КНФ). Т.е. всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой, то есть КНФ.

При тождественно, ее можно представить в виде:

(6.5)

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

Так как существует взаимно однозначное соответствие между таблицей истинности и СДНФ (СКНФ) функции , то СДНФ (СКНФ) – единственна.

Пример: Построить СДНФ и СКНФ

x1	x2	x3
0	0	0	1
0	0	1	0
	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

СДНФ:

,

СКНФ:

.