Дискретная математика. Булева алгебра, комбинационные схемы, преобразования двоичных последовательностей. Ерош И.Л. - 8 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

8
F = (x
1
∨ x
2
∨
3
x
) (
1
x
∨ x
2
∨ x
3
). (2)
В выражении (2) имеются две дизьюнкции, объединенные знаком
конъюнкции.
1.4. Элементарные преобразования булевых выражений
Часто преобразование булевых выражений выполняется с целью уп-
рощения последних или, как говорят, с целью их минимизации. Легко
обосновываются следующие правила минимизации:
– поглощения: x ∨ xy = x; x(x ∨ y) = x;
– склеивания: xy ∨ xy = x;
– обобщенного склеивания: xz ∨ yz ∨ xy = xz ∨ yz;
– x ∨ x y = x ∨ y.
Покажем, как можно применить правило склеивания для минимиза-
ции мажоритарной функции. Аналитическое выражение перепишем в
следующем виде:
F =
1
x
x
2
x
3
∨ x
1
2
x
x
3
∨ x
1
x
2
3
x
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
. (3)
Повторение конъюнкции x
1
x
2
x
3
не меняет значение функции, так как
Y ∨ Y = Y, где Y – любое булево выражение. Тогда, склеивая 1-й и 4-й
члены, 2-й и 5-й, 3-й и 6-й, получаем эквивалентное выражение
F = x
2
x
3
∨ x
1
x
3
∨ x
1
x
2
. (4)
Выражение (4) будет дизъюнктивной, нормальной формой функции, так
как в каждую из конъюнкций входят не все аргументы функции.
Преобразование булевых выражений с помощью приведенных пра-
вил поглощения, склеивания и обобщенного склеивания применяется
достаточно редко, так как имеется более эффективный способ миними-
зации булевых функций, число аргументов которых не превышает 11.
Кроме того, так же просто обосновывается преобразование, называе-
мое правилом де Моргана:
а)
12 1
2
xx x x=∨
;
б)
1212
xx xx
∨=
. (5)
Покажем, как применить правило де Моргана для вывода формулы
СКНФ. В табл. 4 имеется значение функции, инверсной к F, т. е.
F
. Эта
функция имеет только две единицы, поэтому СДНФ ее будет представлять
собой две конъюнкции, каждая ранга 3, объединенные знаком дизъюнкции:

Страницы