6.4. Базисы представления переключательных функций

Функционально полные системы переключательных функций представляют собой базис. Всего можно получить 17 различных минимальных базисов из логических функций двух переменных.

Имеются функции, обладающие всеми пятью отмеченными свойствами. Таковы функции и(см. табл. 25). Часто их называют соответственно ИЛИ-НЕ, И-НЕ. Таким образом, это базисы, состоящие из одной функции (базис Вебба и базис Шеффера). Этот факт очень важен при технической реализации дискретных устройств: достаточно иметь элементы, реализующие только одну из этих функций, чтобы построить любую, сколь угодно сложную схему.

Имеются базисы, состоящие из двух функций:

Иногда используется не минимальный базис – из трех функций:

Имеется и довольно экзотический базис Жегалкина:

В дальнейшем нам пригодится так называемый импликативный базис

Функционально полные толерантные базисы представления переключательных функций.

Если рассматривать переключательные функции большего числа аргументов, то можно поставить задачу отыскания базисов, не зависящих от некоторых модификаций соответствующих функций. Такие модификации могут быть, например, вызваны подстановкой констант 0, 1 и инверсией переменных, что происходит при некоторых отказах (дефектах) соответствующих логических элементов [34]. Такие базисы называют толерантными. Например, переключательная функция четырех переменных – толерантный базис – функционально полная толерантная функция, которая при подстановке констант вместо переменных или при инверсии переменных модифицируется также в базисную функцию: