Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Дизъюнктивная и конъюнктивная нормальные формы



Аналитическое представление предполагает запись произвольной логической функции (ЛФ) в виде формул, переменными в которых являются известные ЛФ.

Дизъюнктивная нормальная форма(ДНФ) – это ЛФ, представляющая собой дизъюнкцию отдельных термов, каждый из которых есть некоторая ЛФ,

содержащая только конъюнкции и инверсии.

Например: 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; Прочитано: 513 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...