Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
76___.doc
Скачиваний:
1
Добавлен:
01.05.2025
Размер:
863 Кб
Скачать
☆

13. Сднф и скнф

ДНФ и КНФ имеют тот недостаток, что они не обладают свойством единственности, т.е. одна и та же формула имеет несколько ДНФ и КНФ. Этим недостатком не обладают совершенные нормальные формы.

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

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

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

Приведение к СДНФ:

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

ІІ метод: для данной формулы строим таблицу истинности, потом применяем правило, основанное на теореме Шеннона: СДНФ функции содержит столько элементарных конъюнкций, сколько единиц в столбце значений ; каждому единичному набору нулей и единиц соответствует элементарная конъюнкция всех переменных, в которой xi взята с отрицанием, если и без отрицания, если .

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

14. Минимизация в классе днф.

Под вхождением переменной понимается место, которое переменная занимает в формуле.

МДНФ - ДНФ с наименьшим числом вхождений переменных.     

Карты Карно (КК)

К К – это таблица, каждая клетка (ячейка) которой соответствует некоторой элементарной конъюнкции всех переменных. Для функции n переменных х1,х2,...,хn существует 2n возможных комбинаций их значений, состоящих из 0 и 1. То есть, например, для n=2 имеем 22 = 4 элементарные конъюнкции , которым соответствуют следующие наборы 0 и 1: (1,1), (1,0), (0,1), (0,0).

КК строятся в виде таблицы размером 2n-k x 2k, так, что её столбцы соответствуют значениям переменных х1,х2,...,хk, строки – хk+1,хk+2,...,хn (или наоборот).

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

П ример - СДНФ. Здесь блок из двух ячеек. Этому блоку соответствует одна переменная х, а именно та переменная, которая полностью «покрывает» этот блок. Формула упростилась φ1=х.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]