Составители:
Рубрика:
15
Таким образом, получаем два функционально полных (базисных) на-
бора:
2) {&, };
3) {∨, }.
Русский математик Жегалкин показал, что любая булева функция
может быть представлена с использованием операций конъюнкции
(&) сложения по модулю 2 (⊕) и константы 1. Покажем, как извест-
ные функции набора 1) представить в виде декомпозиции функций
Жегалкина: A = A ⊕ 1; A ∨ B = ( A B) = (A ⊕ 1)(B ⊕ 1) ⊕ 1 =
= AB ⊕ A ⊕ B ⊕ 1 ⊕ 1 = AB ⊕ A ⊕ B.
Поэтому следующим функционально полным (базисным) набором
будет набор функций Жегалкина:
4) {&, ⊕ , 1 }.
Аналогично можно показать, что набор
5) {∨, ⊕ , 1} – базисный набор.
Выше было показано, что мажоритарная функция M(X, Y, Z) =
= XY ∨ XZ ∨ YZ. Если на один из входов, например Z, подать константу
1, то получим M(X, Y, 1) = XY ∨ X ∨ Y = X ∨ Y , а если на этот же вход Z
подать константу 0, то получим M(X, Y, 0) = XY. Поэтому получаем еще
два базисных набора:
6) {M, , 1};
7) {M, , 0}.
Когда говорят о “мажоритарном базисе” , то имеют в виду эти два
набора (или их объединение: {M, , 1, 0}), предполагая, что 1 и 0 реали-
зуются “без затрат”, а инверсия аргументов всегда присутствует, если
комбинационная схема подключается к триггерным устройствам (эле-
ментарным автоматам), которые имеют как прямой, так и инверсные
выходы.
На практике, как правило, используются базисные наборы, состоя-
щие только из одной функции (“штрих Шеффера” или “стрелка Пирса”):
8) {/};
9) {↓}.
Набор 8) реализует функцию (XY) =
XY
. Инверсия аргумента мо-
жет быть получена так: X = (XX). Конъюнкция XY = ( (XY) =
=
XY XY X
Y
=
. Дизъюнкция может быть реализована так: X ∨ Y =
= ( XY) =
XY XX Y
Y
=
.
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
