 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Дизъюнктивная и конъюнктивная нормальные формы
|
|
Аналитическое представление предполагает запись произвольной логической функции (ЛФ) в виде формул, переменными в которых являются известные ЛФ.
Дизъюнктивная нормальная форма(ДНФ) – это ЛФ, представляющая собой дизъюнкцию отдельных термов, каждый из которых есть некоторая ЛФ,
содержащая только конъюнкции и инверсии.
Например: F(A,B,C) = 
Конъюнктивная нормальная форма (КНФ) - это ЛФ, предоставляющая собой конъюнкцию отдельных термов, каждый из которых есть ЛФ, содержащая только дизъюнктивную и инверсии.
Например: F (A,B,C)= 
(
)(
).
Для однозначного представления ЛФ используются совершенные дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ).
СДНФ - это дизъюнктивная форма, в которую входят конъюнкции только максимальные для данной ЛФ ранга.
Например, для функции трех переменных F(A,B,C) совершенной ДНФ будет представление:
F(A,B,C)= 
v 
v 
v 
v 
.
Где каждая элементарная конъюнкция содержит три буквы.
Аналогично определяется СКНФ.
При получении нормальных форм ЛФ, а также при переходе от нормальных форм к совершенным формам обычно пользуются:
1) известными свойствами элементарных функций И, ИЛИ, НЕ
x v x = x; x v 1 = 1; x v 0 = x; 
;
x * x = x; x * 1 = x; x * 0 = 0; 
.
2) законами:
ассоциативным (сочетательным):
x1 (x2x3) = (x1x2)x3 ,
x1 v (x2 v x3) = (x1 v x2) v x3 ;
коммутативным (переместительным):
x1x2 = x2x1
x1 v x2 = x2 v x1 ;
дистрибутивным (распределительным):
x1(x2 v x3) = (x1x2) v(x1x3),
x1 v (x2x3) = (x1 v x2) v(x1 v x3);
де Моргана:
,
склеивания и поглощения:
v x1x2 = x1,
(
) v x2 = x1 v x2.
Пример:
Упростить функцию в ДНФ:
F(x1,x2,x3) = 
.
Прежде всего, необходимо перевести эту функцию в СДНФ, т.к. только СДНФ дает единственное представление ЛФ, для чего воспользуемся свойствами дизъюнкции и конъюнкции.
x v x = 1; x * 1 = x; x v 1 = 1.
Две последних конъюнкции домножаем на (
) и (
) и приводим подобные члены:
F(x1,x2,x3) = 
=
= 
=
= 
=
= 
.
Задачи:
1. Упростить ЛФ четырех переменных:
F(x1,x2,x3,x4) = 
.
2. Доказать, что F1(x1,x2,x3) = F2(x1,x2,x3), если
F1(x1,x2,x3) = 
;
F2(x1,x2,x3) = x1 v x2.
3. Преобразовать в СДНФ и СКНФ следующие функции, представление в ДНФ и КНФ:
а) F1(x1,x2,x3) = 
;
б) F1(x1,x2,x3) = 
.
4. Представление ЛФ в ДНФ и КНФ:
а) F1(x1,x2,x3) = 
;
б) F1(x1,x2,x3 ) = 
.
5. Упростить ЛФ, используя свойства элементарных функций:
а) F1(x1,x2,x3) = 
;
б) F1(x1,x2,x3) = v1(1,2,3,4,5,6,7).
Дата публикования: 2015-04-07; Прочитано: 538 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
