СНКФ определяется как произведение элементарных сумм, в которых каждая переменная встречается ровно один раз либо с отрицанием, либо без него

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

Нормальная каноническая форма отличается от нормальной формы тем, что всегда содержит термы только максимального ранга и дает однозначное представление функции.

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

Пример:

Получить для функции СДНФ и таблицу истинности.

,

необходимо дополнить каждое элементарное произведение недостающими переменными так, чтобы тождественность преобразования не была нарушена, т.е.

.

В первом случае элементарное произведение дополнилось сомножителем , равным единице, во втором - сомножителем .

После раскрытия скобок и приведения подобных членов получим функцию, записанную в СДНФ:

.

В полученном выражении:

каждая переменная (или ее отрицание) содержится по одному разу в каждом элементарном произведении. Полученная функция обращается в логическую единицу при трех различных комбинациях значений входных переменных:

А=1, В=0, С=1 - первая комбинация;

А=0, В=0, С=1 - вторая комбинация;

А=1, В=0, С=0 - третья комбинация.

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

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

Таблица 8.14.

Таблица истинности функции

Дата добавления: 2014-01-07