![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть , будем считать, что
, если
и
, если
.
Конъюнкция и дизъюнкция являются ассоциативными операциями: и
). Поэтому определены выражения
и
, которые называются элементарной конъюнкцией и элементарной дизъюнкцией длины n соответственно. Заметим, что конъюнкция принимает значение 1 на единственном наборе значений переменных
, а на всех остальных наборах значений переменных обращается в 0. Дизъюнкция же, напротив, принимает значение 0 на единственном наборе значений переменных, а на всех остальных наборах значений переменных равна 1.
Это позволяет каждую булеву функцию представить в виде
или в виде
&
которые называются соответственно совершенной дизъюнктивной нормальной формой (д.н.ф.) и совершенный конъюнктивной нормальной формы (к.н.ф.) для функции ƒ.
В совершенных д.н.ф. и к.н.ф. все элементарные конъюнкции (э.к.) и элементарные дизъюнкции (э.д.) имеют одинаковую длину, равную числу переменных n. Может, однако, оказаться, что у некоторых э.к. в совершенной д.н.ф. может быть опущена часть букв, а другие э.к. могут быть одновременно вообще удалены, причем полученная д.н.ф. (уже не сокращенная) будет представлять ту же самую функцию. Тем самым иногда удается существенно упростить представление булевой функции в виде д.н.ф.. Аналогично может быть упрощена и к.н.ф.. В процессе упрощения могут использоваться свойства 1) – 9) булевой алгебры.
Дата публикования: 2015-03-26; Прочитано: 228 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!