ВУЗ:
Составители:
Рубрика:
22
1
1
*
1
*
1
1
,...,
( ,..., ) 1
( ,..., )
n
n
n
nn
f
f
xx xx
δ
δ
δδ
δδ
=
=∨
Из принципа двойственности следует, что
1
1
*
1
**
1
1
,...,
( ,..., ) 1
( ,..., ) & ...
n
n
n
nn
f
f
xx x x
δ
δ
δδ
δδ
=
=∨∨. (5.1)
Левая часть равенства (5.1) есть f(x
1
,…,x
n
), а правая может
быть преобразована следующим образом:
....&
...&...&
),...,(
,...,
),...,(
,...,
),...,(
,...,
*
n
1
n1
n1
n
1
n1
n1
n
1
n1
n1
n1
0f
n1
0f
n1
1f
xx
xxxx
δ
δ
δδ
δδ
δ
δ
δδ
δδ
δ
δ
δδ
δδ
∨∨=
=∨∨=∨∨
=
=
=
Таким образом, получаем разложение
n1
n1
n1
n1
0f
n1
xxxxf
δ
δ
δδ
δδ
∨∨=
=
...&),...,(
),...,(
,...,
(5.2)
Данная формула носит конструктивный характер, т.к. она по
таблице функции позволяет построить формулу, являющуюся
СКНФ (если 1f ≡
/
).
СКНФ функции f содержит ровно столько дизъюнкций, сколько
нулей в таблице f. Каждому «нулевому» набору (
δ
1
,…,
δ
n
) значений
переменных, т.е. набору, на котором значение функции равно 0,
соответствует дизъюнкция всех переменных, в которых x
i
взято с
отрицанием, если
δ
i
=1 и без отрицания, если
δ
i
=0.
Пример 5.5.
Записать СКНФ для функции
.21
xx →
x
1
x
i
x
1
→
x
2
Основная элементарная дизъюнкция
0 0 1
0 1 1
1 0 0
1
x
∨
x
2
1 1 1
21
1
2
0
121
xxxxxxf ∨=∨=),(.
Основные эквивалентные преобразования.
В лекции 3 был изучен один из методов проверки
эквивалентности функций, заключающийся в построении и
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
