Аннотация:
Дискретные устройства, синтезированные с использованием различных базисов двоичной логики, могут иметь различную сложность технической реализации в зависимости от технологии изготовления элементной базы. Какие из элементарных функций алгебры логики образуют базис, определяет теорема Поста – Яблонского. Однако возникает задача определения общего количества неизбыточных базисов, т. е. таких базисов, удаление из которых хотя бы одной функции нарушает их функциональную полноту. Эта задача интересна не только с математической точки зрения, но и с точки зрения разработчика – он может выбрать наиболее приемлемый способ технической реализации дискретного устройства из существующих способов. В данной работе рассматривается задача перечисления неизбыточных базисов классической двоичной логики. Приводятся формулы, определяющие соответствие между функциями основного базиса {И; ИЛИ; НЕ} и функциями неизбыточных базисов. Дается пример практического использования неизбыточных базисов для построения логических устройств автоматики.
Дискретные устройства, синтезированные с использованием различных базисов двоичной логики, могут иметь различную сложность технической реализации в зависимости от технологии изготовления элементной базы. Какие из элементарных функций алгебры логики образуют базис, определяет теорема Поста – Яблонского. Однако возникает задача определения общего количества неизбыточных базисов, т. е. таких базисов, удаление из которых хотя бы одной функции нарушает их функциональную полноту. Эта задача интересна не только с математической точки зрения, но и с точки зрения разработчика – он может выбрать наиболее приемлемый способ технической реализации дискретного устройства из существующих способов. В данной работе рассматривается задача перечисления неизбыточных базисов классической двоичной логики. Приводятся формулы, определяющие соответствие между функциями основного базиса {И; ИЛИ; НЕ} и функциями неизбыточных базисов. Дается пример практического использования неизбыточных базисов для построения логических устройств автоматики.
Ключевые слова:
булева функция; функционально полная система; базис; особенный класс функций