Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма
Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма - раздел Образование, Понятие равносильности формул
Элементарной Конъюнкцией N Переменных Называется Конъю...
Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.
Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.
Для любой формулы алгебры логики путем равносильных преобразований можно получить ее ДНФ, причем не единственную.
Например, для формулы А = х Ù (х ® y) имеем:
А = х Ù (Ø х Ú y) = (х Ù Ø х) Ú (х Ù y) = х Ù y, то есть
ДНФ А = (х Ù Ø х) Ú (х Ù y) и
ДНФ А = х Ù y.
Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства. Такая ДНФ А называется совершенной дизъюнктивной нормальной формой формулы А (СДНФ А).
Как уже указывалось, СДНФ А может быть получена с помощью таблицы истинности.
Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:
путем равносильных преобразований формулы А получают одну из ДНФ А.
если в полученной ДНФ А входящая в нее элементарная конъюнкция В не содержит переменную xi, то, используя закон B Ù (xi Ú Ø xi) = B, элементарную конъюнкцию B заменяют на две элементарных конъюнкции (B Ù xi) и (B Ù Ø xi), каждая из которых содержит переменную xi.
если в ДНФ А входят две одинаковых элементарных конъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью В Ú В = В.
если некоторая элементарная конъюнкция В, входящая в ДНФ А, содержит переменную xiи ее отрицание Ø xi, то, на основании закона xi Ù Ø xi = 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой член дизъюнкции.
если некоторая элементарная конъюнкция, входящая в ДНФ А, содержит переменную xiдважды, то одну переменную можно отбросить, пользуясь законом xi Ù xi = xi.
Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = x Ú y Ù (x Ú Ø y)ДНФ А = x Ú (x Ù y) Ú (y Ù Ø y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (x Ù y)и (x Ù Ø y),В результате получим ДНФ А = x Ù y Ú x Ù Ø y Ú x Ù y Ú y Ù Ø y.
Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции x Ù y,то отбросим лишнюю. В результате получим ДНФ A = x Ù y Ú x Ù Ø y Ú y Ù Ø y.
Так как элементарная конъюнкция y Ù Ø y содержит переменную у и ее отрицание, то y Ù Ø y =0, и ее можно отбросить как нулевой член дизъюнкции.
Если функция f задана формулой построенной с помощью amp и переменных то по теореме о суперпозиции двойственных функций и ввиду того... Дизъюнктивная нормальная форма и совершенная дизъюнктивная...
Булева алгебра
Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями
Функции алгебры логики
Значение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в нее элементарных высказываний. Н
Сокращенная ДНФ
Определение:
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:
§ Любые два слагаемых различаются как минимум в двух позициях
§ Ни о
Минимальная ДНФ
Определение:
Минимальная ДНФ — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.
Каждая миним
Метод Квайна
Метод применим к СДНФ и основывается на применении двух основных соотношений:
1. склеивание
Метод Квайна-Мак-Класки
Метод формализован на этапе нахождения простых импликант. Формализация проводится таким образом:
1) Все конституэнты "1" из СДНФ булевой функции
Метод диаграмм Вейча
Метод получает МДНФ булевой функции небольшого числа переменных. Булевы функции задаются в виде специальных диаграмм. Для функции 2-х переменных и 3-х переменных:
Минимизация частично определенных булевых функций
В реальных задачах часто бывает так, что значение булевой функции на некоторых наборах не определено и может доопределяться произвольно. Тогда доопределение функции целесообразно проводить так, что
Новости и инфо для студентов