Дискретная математика. Ерош И.Л - 13 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

13
– все полученные дизъюнкции объединяются знаками конъюнкции.
Возьмем, например, функцию F, представленную следующей таб
лицей истинности (табл. 2.4).
СДНФ этой функции представляет собой шесть конъюнкций ранга
3, объединенных знаками дизъюнкции, т. е. достаточно громоздкое вы
ражение. В то же время СКНФ этой функции будет выглядеть так:
F = (x
1
Ú x
2
Ú ùx
3
)(ùx
1
Ú x
2
Ú x
3
), (2.2)
т. е. содержит две дизъюнкции ранга 3, объединенные знаком конъ
юнкции.
2.4. Элементарные преобразования булевых выражений
Часто преобразование булевых выражений выполняется с целью
упрощения последних или, как говорят, с целью их минимизации. Лег
ко обосновываются следующие правила минимизации:
– поглощения: x Ú xy = x; x(x Ú y) = x;
– склеивания: xy Ú xùy = x;
– обобщенного склеивания: xz Ú yùz Ú xy = xz Ú yùz;
– x Ú ùxy = xÚy.
Покажем, как можно применить правило склеивания для миними
зации мажоритарной функции. Легко показать, что x Ú x = x. Это оз
начает, что, если функция представлена в дизъюнктивной форме, то
всегда можно добавить любой член, причем сколько угодно раз. Тогда
аналитическое выражение (2.1) можно переписать в следующем виде,
повторив четвертую конъюнкцию еще дважды:
M = ùx
1
x
2
x
3
Ú x
1
ùx
2
x
3
Ú x
1
x
2
ùx
3
Ú x
1
x
2
x
3
Ú x
1
x
2
x
3
Ú x
1
x
2
x
3
. (2.3)
Повторение конъюнкции x
1
x
2
x
3
не меняет значения функции М.
Тогда, склеивая 1й и 4й члены, 2й и 5й, 3й и 6й, получаем экви
валентное выражение
М = x
2
x
3
Ú x
1
x
3
Ú x
1
x
3
. (2.4)
Выражение (2.4) будет дизъюнктивной нормальной, но уже не со
вершенной формой функции, так как в каждую из конъюнкций вхо
дят не все аргументы функции.
Преобразование булевых выражений с помощью приведенных правил
поглощения, склеивания и обобщенного склеивания применяется доста
точно редко, так как имеется более эффективный способ минимизации
булевых функций, число аргументов которых не превышает 10.
Кроме того, также просто обосновывается преобразование, называ
емое правилами де Моргана:

Страницы