Примеры нахождения СКНФ и СДНФ

Практическая работа 5

Тема:

Построение СДНФ и СКНФ по таблице истинности, моделирование логической схемы в конструкторе

Цель:

моделирование работы цифровых элементов, реализующих основные логические функции: И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ

 

Теоретическая часть

Построение СКНФ и СДНФ по таблице истинности

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

Нормальная форма существует в двух видах:

· конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, (A∨B¯∨C)∧(A∨C);

· дизъюнктивная нормальная форма (ДНФ) -- дизъюнкция нескольких конъюнкций, например, (A∧B¯∧C)∨(B∧C).

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

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

 

Правила построения СКНФ по таблице истинности

 

Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием

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

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

Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.

Примеры нахождения СКНФ и СДНФ

Пример 1 Записать логическую функцию по ее таблице истинности:

Решение: Воспользуемся правилом построения СДНФ:

Получим СДНФ:

F(x1, x2, x3)=(x1¯∧x2¯∧x3¯)∨(x1¯∧x2¯∧x3)∨(x1∧x2¯∧x3¯)∨(x1∧x2¯∧x3)∨(x1∧x2∧x3)

Воспользуемся правилом построения СКНФ:

 

Получим СКНФ: F(x1, x2, x3)=(x1∨x2¯∨x3)∧(x1∨x2¯∨x3¯)∧(x1¯∨x2¯∨x3)

Пример 2

Функция задана таблицей истинности:

Представить эту функцию в виде СДНФ и СКНФ.

Решение:

Запишем логическую функцию в СДНФ.

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

Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ: F(x1,x2,x3,x4)=(x¯∧y¯∧z∧f)∨(x1¯∧x2∧x3¯∧x4¯)∨(x1¯∧x2∧x3∧x4)∨(x1∧x2¯∧x3¯∧x4¯).

Запишем логическую функцию в СКНФ.

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

Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:

F(x1,x2,x3,x4)=(x1∨x2∨x3∨x4)∧(x1∨x2∨x3∨x4¯)∧(x1∨x2∨x3¯∨x4)∧(x1∨x2¯∨x3∨x4¯)∧(x1∨x2¯∨x3¯∨x4)∧(x1¯∨x2∨x3∨x4¯)∧(x1¯∨x2∨x3¯∨x4)∧(x1¯∨x2∨x3¯∨x4¯)∧(x1¯∨x2¯∨x3∨x4)∧(x1¯∨x2¯∨x3∨x4¯)∧(x1¯∨x2¯∨x3¯∨x4)∧(x1¯∨x2¯∨x3¯∨x4¯)