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

UptoLike

ВУЗ: 

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

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

Рубрика: 

22
мер, если из набора исключена &, то ее можно реализовать так: AB = ù(ùA
ÚùB). Если же из набора исключена функция Ú, то она может быть реали
зована так: X Ú Y = ù (ùX ùY). Таким образом, получаем два функциональ
но полных, причем базисных, набора: {&, ù } и {Ú, ù }.
Русский математик Жегалкин показал, что любая булева функция
может быть представлена с использованием операций конъюнкции (&),
сложения по модулю 2 (Å) и константы 1. Покажем, как функции набо
ра представить в виде декомпозиции функций Жегалкина: ù A = A Å 1;
A Ú B = ù(ùA ùB) = (A Å 1) (B Å 1) Å 1 = AB Å A Å B Å 1 Å 1 = AB Å A Å B.
Поэтому следующим функционально полным набором (базисным
набором) будет набор функций Жегалкина: {&, Å, 1 }.
Аналогично можно показать, что набор {Ú, Å, 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. Поэтому получаем еще два ба
зисных набора: {M, ù, 1} и {M, ù, 0}. Когда говорят о «мажоритарном
базисе», то имеют в виду эти два набора (или их объединение: {M, ù,
1, 0}, предполагая, что 1 и 0 реализуются «без затрат», а инверсия ар
гументов всегда присутствует, если комбинационная схема подключа
ется к триггерным устройствам (элементарным автоматам), которые
имеют как прямой, так и инверсные выходы.
На практике, как правило, используются базисные наборы, состо
ящие только из одной функции («штрих Шеффера» или «стрелка Пир
са»): {/} и {¯}.
Набор «штрих Шеффера » реализует функцию S(X, Y) = ù(XY). Ин
версия аргумента может быть получена с помощью элемента Шеффера
так: ùX = ù(XX). Конъюнкция требует использования двух элементов
Шеффера: XY = ù(ù(XY)). Дизъюнкция может быть реализована с по
мощью трех элементов Шеффера: X Ú Y = ù (ù XùY).
Набор «стрелка Пирса» реализует функцию P(X, Y) = ù(X Ú Y). Ин
версия аргумента может быть получена так: ù(X Ú X). Дизъюнкция мо
жет быть получена так: X Ú Y = ù(ù(X Ú Y)). Конъюнкция может быть
получена так: XY = ù(ùX Ú ùY).
Пример. Перевести в базис Шеффера и Пирса функцию, заданную в
дизъюнктивной нормальной форме: F = ùАB Ú AùСD Ú ùВD.
В базисе Шеффера функция будет иметь вид F = ù (ù(ùАB) Ú ù(AùСD) Ú
ù(ùВD)).
В базисе Пирса функция будет иметь вид F = ù ù(ù(А Ú ùB) Ú ù(ùA Ú С Ú
ùD) Úù(В Ú ùD)).

Страницы