ВУЗ:
Составители:
Рубрика:
26
3) выбор минимальных ДНФ функции
f.
Порождение простых импликантов.
Определение. Элементарная конъюнкция
α
покрывается
элементарной конъюнкцией
β
, если каждая переменная, входящая
в
β
, входит в
α
(с учетом отрицания).
Пример 6.2.
Конъюнкция
α
= xyz покрывается конъюнкцией
β
= xy.
Конъюнкция
α
= x y z не покрывается конъюнкцией
β
= x z .
Определение.
Элементарная конъюнкция
α
называется
дополнением элементарной конъюнкции
β
по отношению к ДНФ
Φ
, если:
1)
конъюнкция
α
покрывается конъюнкцией
β
,
2)
в конъюнкцию
α
входят все переменные, входящие в
Φ
.
Пример 6.3.
Пусть
Φ
= xy z
∨
t
∨
zt
∨
y
x
. Тогда конъюнкции
α
1
=xyzt,
α
2
=xyz t,
α
3
=xy zt,
α
4
=xy tz являются дополнениями
конъюнкции
β
=xy по отношению к
Φ
.
Теорема 6.3.
Пусть
Φ
- СДНФ функции f. Если
β
- импликант f,
то все дополнения элементарной конъюнкции
β
по отношению к
Φ
входят в
Φ
.
Доказательство
. Пусть
m
m
2
2
1
1
iii
xxx
ρ
ρρ
β
...= - импликант функции f и
пусть
n21
n21
xxx
δδδ
α
...= является дополнением
β
по отношению к
Φ
.
Предположим, что
α
не входит в
Φ
. Рассмотрим такой набор
значений переменных, что
α
=1, т.е. положим x
i
=
δ
i
, i=1,…,n. Тогда
m1
imi1
δ
ρ
δ
ρ
== ,..., и
β
=1, а
Φ
=0 поскольку
α
по предположению
не входит в
Φ
. Но это противоречит тому, что
β
является
импликантом
f.
Из теоремы следует, что объединяя в СДНФ
Φ
функции f
соответствующим образом пары элементарных конъюнкций и
применяя последовательно равенство
γ
γ
γ
=
∨ xx , можно в
результате получить все простые импликанты функции
f.
Пример 6.4
.
Пусть
f=xyzt
∨
x tzy
∨
x yzt.
Страницы
- « первая
- ‹ предыдущая
- …
- 24
- 25
- 26
- 27
- 28
- …
- следующая ›
- последняя »
