Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ)
Если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией, то такая форма представления называется нормальной. Элементарная конъюнкция — конъюнкция конечного множества логических переменных и их инверсий. Элементарная дизъюнкция — дизъюнкция конечного множества логических переменных и их инверсий. Число аргументов, образующих элементарную дизъюнкцию или конъюнкцию, называется ее рангом. Пример 1. Х & Y & Z, Х &. Y & Z — элементарные конъюнкции третьего ранга. Х v Y, Х v Y — элементарные дизъюнкции второго ранга. Дизъюнктивная нормальная форма (ДНФ) содержит элементарные конъюнкции, связанные между собой операцией дизъюнкции. Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операцией конъюнкции. Одну и ту же логическую функцию можно представить разными ДНФ и КНФ. Пример 2. Нетрудно убедиться (построив таблицы истинности для каждой из логических формул или проведя преобразования на основании логических законов), что приведенные ниже формулы определяют одну и ту же логическую функцию F(X, Y, Z): 1) Ú Ú ; 2) Ú Ú .
Для исключения неоднозначности записи логические функции могут быть представлены в совершенных дизъюнктивной и конъюнктивной нормальных формах. Совершенная дизъюнктивная нормальная форма (СДНФ) отвечает следующим требованиям: 1) в ней нет двух одинаковых элементарных конъюнкций; 2) ни одна элементарная конъюнкция не содержит двух одинаковых переменных; 3) ни одна элементарная конъюнкция не содержит переменную вместе с ее инверсией; 4) все конъюнкции имеют один и тот же ранг. Аналогичным требованиям подчиняется и совершенная конъюнктивная нормальная форма (СКНФ). Пример 3. Если логическая функция содержит конъюнкции разных рангов, то для получения СДНФ следует повысить ранг младших конъюнкций, используя закон исключения третьего. Ú Ú Ú Ú Ú . СДНФ и СКНФ можно получить по табличному представлению логической функции.
5.5.1. Алгоритм образования СДНФ по таблице истинности 1. Выделить в таблице истинности все наборы переменных, на которых функция принимает единичные значения. 2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие без инверсии переменные, принимающие в соответствующем наборе значение 1 и с инверсией — 3. Соединить элементарные конъюнкции знаком дизъюнкции.
|