§ 20. Приложение теории булевых функций к анализу и синтезу схем из функциональных элементов

Огромные скорости работы современных ЭВМ достигнуты из-за применения бесконтактных схем, работающих значительно быстрее, чем контактные схемы. В ЭВМ применяются электронные приборы, реализующие различные булевы функции, например можно рассмотреть устройства реализующие отрицание, конъюнкцию, дизъюнкцию и др.

Не касаясь структуры и физических основ этих устройств, называемых функциональными элементами, обозначим их условно следующим образом:

Ограничимся только этими устройствами, хотя на практике существуют функциональные элементы, реализующие и другие операции, например, отрицание конъюнкции и т.п. Но теоретически можно обойтись только перечисленными тремя устройствами, так как любую булеву функцию можно выразить, используя только ¬ , &, ∨.

Об этих устройствах (функциональных элементах) знаем лишь следующее:

Этих свойств элементов достаточно для решения задач синтеза и анализа схем из этих элементов.

Рассмотрим пример построения одноразрядного сумматора двоичных чисел. Заданы двоичные числа $а_1а_2…а_k…а_n и b_1b_2…b_k…b_n$. Требуется построить сумматор для k –го разряда. Задача состоит в конструировании схемы (рис. 3.5) с тремя входами x, y, z и двумя выходами S и Р, чтобы при подаче на входы x и y сигналов, изображающих двоичные цифры - слагаемые данного разряда, а на вход z - сигнала, изображающего значение переноса из соседнего младшего разряда, получить на выходе S значение суммы в данном разряде, а на выходе Р - значение переноса в соседний старший разряд.

Напомним, что сложение чисел в двоичной системе производится следующим образом: 0+0=0, 0+1=1+0=1, 1+1=10, 1+1+1=11 и т.д. Воспользовавшись этой таблицей сложения чисел в двоичной системе, получим таблицу:

Считая, что 0 и 1 есть значения булевой функции, и выбирая строки, оканчивающиеся на 1, получим:

$S=¬ x\&¬ y\&z∨¬ x\&y\&¬ z∨x\&¬ y\&¬ z∨ x\&y\&z$

$Р=¬ x\&y\&z∨x\&¬ y\&z∨x\&y\&¬ z ∨x\&y\&z$

Имея выражения (3.27), уже можно построить схему из функциональных элементов, выполняющих поставленную задачу. Но поскольку схема построена из функциональных элементов, выполняющих некоторые операции, то возникает задача такого упрощения, чтобы она содержала как можно меньше знаков операций. Можно показать, что

$Р∼ x\&y∨x\&z∨y\&z$

$S∼ x\&y\&z∨ (x∨y∨z)\&¬ Р$

Тогда получим схему (рис. 3.6), выполняющую поставленную задачу, причем схема содержит значительно меньше функциональных элементов по сравнению со схемой, которая получилась при ее построении по (3.27) без проведения преобразований.

Сложность (размер) схемы из функциональных элементов – это число функциональных элементов в этой схеме.

Приведённая на Рис. 3.6 схема имеет сложность (размер) 9.