Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 31 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
77
1)
(
)
;......
,...,
,...,
ji
nj
mi
nm
UXUUUXXX
=
=
=
1
1
2121
2)
(
)
(
)
;......
,...,
,...,
ji
nj
mi
nm
UXUUUXXX
1
1
2121
=
=
6. С помощью второго дистрибутивного закона преобразовать ДНФ в
КНФ :
1)
;
z
x
yz
x
2)
;
z
x
yz
x
xyz
3) .
2343221
xxxxxxx
5.3 Классификация ДНФ . Минимизация булевых функций
Проблема минимизации булевых функций состоит в том, чтобы по -
строить ДНФ , у которой число вхождений минимально по сравнению со
всеми другими ДНФ , реализующими булеву функцию .
Определение 1. ДНФ функции
f
называется кратчайшей, если она
имеет наименьшую длину среди всех эквивалентных ей ДНФ .
Определение 2. ДНФ функции
f
называется минимальной, если
она имеет наименьшее число вхождений букв
i
i
x
σ
среди всех эквива -
лентных ДНФ .
Обозначим через
()
=
=
S
i
iD
K
1
ρρ сумму рангов э.к., входящих в
ДНФ . Число
D
ρ
называется сложностью ДНФ . Тогда ДНФ , у которой
сумма рангов
D
ρ
минимальна среди всех ее ДНФ , является минимальной.
Способ построения минимальной ДНФ дает следующая теорема.
Теорема. С помощью равносильных преобразований, применяя фор-
мулы:
1. Поглощения
1211
KKKK
=
;
1. Склеивания
K
K
X
XK
=
;
2. Неполного склеивания
K
K
X
XK
K
X
XK
=
;
3. Обобщенного склеивания
212121
KKKXXKKXXK =∨ ,
из любой ДНФ функции
f
можно построить ДНФ , которая
а ) либо совпадает с минимальной или кратчайшей,
б) либо минимальная (кратчайшая) получается из нее удалением одной или
нескольких элементарных конъюнкций.