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

UptoLike

Составители: 

26
5. Пусть
nm
UUXX ,...,,,...,
11
произвольные формулы алгебры логики.
Доказать следующие эквивалентности:
1)
1212
1,...,
1,...,
......;
)
mnij
im
jn
XXXUUUXU

(
2)
()()
12m12nij
i-1,...,m
j=1,...,n
X.X...XUU...U=XU.
6. С помощью второго дистрибутивного закона преобразовать ДНФ в
КНФ:
1)
z
x
yz
y
x
Ú
Ú
2)
z
y
x
yz
x
xyz
Ú
Ú
3) .
2343221
xxxxxxx
Ú
Ú
Ú
5.3 Классификация ДНФ. Минимизация булевых функций
Проблема минимизации булевых функций состоит в том, чтобы по-
строить ДНФ, у которой число вхождений минимально по сравнению со
всеми другими ДНФ, реализующими булеву функцию.
Определение 1. ДНФ функции
f
называется кратчайшей, если она
имеет наименьшую длину среди всех эквивалентных ей ДНФ.
Определение 2. ДНФ функции
f
называется минимальной, если
она имеет наименьшее число вхождений букв
i
i
x
s
среди всех эквива-
лентных ДНФ.
Обозначим через
( )
å
=
=
S
i
iD
K
1
rr
сумму рангов э.к., входящих в
ДНФ. Число
D
r
называется сложностью ДНФ. Тогда ДНФ, у которой
сумма рангов
D
r
минимальна среди всех ее ДНФ, является минимальной.
Способ построения минимальной ДНФ дает следующая теорема.
Теорема. С помощью равносильных преобразований, применяя фор-
мулы:
1. Поглощения
1211
KKKK
=
Ú
;
2. Склеивания
;
XKXKK
=
3. Неполного склеивания
;
XKXKXKXKK

4. Обобщенного склеивания
212121
KKKXXKKXXK
Ú
Ú
=
Ú
,
из любой ДНФ функции
f
можно построить ДНФ, которая
а) либо совпадает с минимальной или кратчайшей,
б) либо минимальная (кратчайшая) получается из нее удалением одной или
нескольких элементарных конъюнкций.