ВУЗ:
Составители:
Рубрика:
20
Отсюда вытекает порядок построения СДНФ по функции,
заданной таблицей.
5. Построение СДНФ для функции, заданной таблицей.
Представление логических функций булевыми
формулами. Совершенная конъюнктивная нормальная
форма (СКНФ). Основные эквивалентные
преобразования.
Построение СДНФ для функции, заданной таблицей.
На предыдущей лекции была доказана теорема о разложении
функций по переменным. В качестве следствия из нее получено
разложение функций по всем переменным, являющееся СДНФ.
Данное следствие носит конструктивный характер, т.к. оно по
таблице функции позволяет построить формулу, являющуюся
СДНФ (если
0f ≡
/
). СДНФ функции f содержит ровно столько
конъюнкций, сколько единиц в таблице f; каждому «единичному»
набору (
δ
1
,…,
δ
n
), т.е. набору, на котором значение функции равно
1, соответствует конъюнкция всех переменных, в которой x
i
взято
с отрицанием, если
δ
i
=0, и без отрицания, если
δ
i
=1.
Пример 5.1. Записать СДНФ для функции x
1
→
x
2
.
x
1
x
2
x
1
→
x
2
Основная элементарная конъюнкция
0 0 1
12
x
x
0 1 1
1
xx
2
1 0 0
1 1 1 x
1
x
2
212121
1
2
1
1
1
2
0
1
0
2
0
121
xxxxxxxxxxxxxxf ∨∨=∨∨=),(.
Представление логических функций булевыми формулами.
Представить логическую функцию булевой формулой - это
значит представить f в виде формулы через отрицание,
конъюнкцию и дизъюнкцию.
Если
0xxf
n1
≡
/
),...,(
, то по следствию 4.2
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
