ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ

В цифровых устройствах информация кодируется наборами цифр, которые, в свою очередь, представляют собой электрические сигналы различного уровня, соответствующего той или иной цифре. Пусть некоторое устройство имеет n входов, сигналы на которых обозначаются переменными , , и m выходов, на которых появляются сигналы, обозначаемые , . Будем называть алфавитом переменной множество значений, которые она может принимать, а элементы этого множества будем называть буквами алфавита или просто буквами. В цифровых вычислительных машинах традиционно используется двоичный алфавит . Конечные упорядоченные последовательности букв будем называть словами в данном алфавите.

Следует различать алфавит переменной и входной или выходной алфавиты схемы, представляющие сбой наборы вида , , в которых элементами являются буквы алфавитов соответствующих входных переменных. Таким образом, если число букв в алфавитах входных переменных равно , , а в алфавитах выходных переменных , , то число букв R во входном и Q в выходном алфавитах схемы будет равно

и .

Ясно, что в случае двоичных алфавитов переменных , .

Поскольку число входов и выходов цифровых схем, а также число букв в алфавитах переменных конечно, то алфавиты таких схем также будут конечными.

Если значения выходных переменных схемы зависят только от значений входных переменных и наборы выходных переменных однозначно определяются соответствующими наборами входных переменных, такие схемы называются комбинационными схемами (КС) или схемами прямого распространения (автоматами без памяти).

Зависимость выходных реакций КС от входного воздействия описывается функциями специального вида, называемыми логическими или переключательными функциями (ПФ).

Исходными данными для выполнения процедуры логического синтеза комбинационной схемы являются: совокупность логических функций, реализуемых синтезируемой КС, и набор логических элементов, используемых для построения устройства. Результатом синтеза является схема соединения логических элементов, реализующая заданную совокупность логических функций.

В дальнейшем по умолчанию будем рассматривать логические функции и их аргументы, могущие принимать дискретные значения 0 и 1. Такие логические функции называются двоичными функциями или булевыми функциями. Таким образом, для любой рассматриваемой далее ПФ и ее аргументов справедливо: , , если иное не оговорено отдельно.