В логике функционально полный набор логических связок или булевых операторов — это тот, который можно использовать для выражения всех возможных таблиц истинности путем объединения членов набора в булево выражение . [1] [2] Хорошо известный полный набор связок — это { AND , NOT } . Каждый из синглетонных наборов { NAND } и { NOR } является функционально полным. Однако набор {AND, OR } является неполон из-за его неспособности выразить NOT.
Функционально завершенные ворота (или набор ворот) можно также назвать универсальными воротами (или универсальным набором ворот).
В контексте пропозициональной логики функционально полные наборы связок также называются ( выразительно ) адекватными . [3]
С точки зрения цифровой электроники функциональная полнота означает, что каждый возможный логический вентиль может быть реализован как сеть вентилей типов, предписанных набором. В частности, все логические вентили могут быть собраны либо только из двоичных вентилей NAND , либо только из двоичных вентилей NOR .
Современные тексты по логике обычно принимают в качестве примитива некоторое подмножество связок: конъюнкция ( ); дизъюнкция ( ); отрицание ( ); материальное условное ( ); и, возможно, биусловное ( ). Дальнейшие связки могут быть определены, если это необходимо, путем определения их в терминах этих примитивов. Например, NOR (отрицание дизъюнкции, иногда обозначаемое ) может быть выражено как конъюнкция двух отрицаний:
Аналогично, отрицание конъюнкции, NAND (иногда обозначаемое как ), может быть определено в терминах дизъюнкции и отрицания. Каждая бинарная связка может быть определена в терминах , что означает, что множество является функционально полным. Однако оно содержит избыточность: это множество не является минимальным функционально полным множеством, поскольку условное и биусловное можно определить в терминах других связок как
Из этого следует, что меньший набор также является функционально полным. (Его функциональная полнота также доказывается теоремой о дизъюнктивной нормальной форме .) [4] Но это все еще не минимально, поскольку может быть определено как
В качестве альтернативы может быть определено в терминах аналогичным образом или может быть определено в терминах :
Дальнейшие упрощения невозможны. Следовательно, каждый двухэлементный набор связок, содержащий и один из является минимальным функционально полным подмножеством .
При заданной булевой области B = {0, 1} множество F булевых функций f i : B n i → B является функционально полным , если клон на B, сгенерированный базовыми функциями f i , содержит все функции f : B n → B для всех строго положительных целых чисел n ≥ 1. Другими словами, множество является функционально полным, если каждая булева функция, которая принимает хотя бы одну переменную, может быть выражена через функции f i . Поскольку каждая булева функция хотя бы одной переменной может быть выражена через бинарные булевы функции, F является функционально полным тогда и только тогда, когда каждая бинарная булева функция может быть выражена через функции из F .
Более естественным условием было бы, чтобы клон, сгенерированный F, состоял из всех функций f : B n → B , для всех целых чисел n ≥ 0 . Однако приведенные выше примеры не являются функционально полными в этом более сильном смысле, поскольку невозможно записать нулевую функцию, т. е. константное выражение, в терминах F , если само F не содержит хотя бы одну нулевую функцию. При таком более сильном определении наименьшие функционально полные множества имели бы 2 элемента.
Другим естественным условием было бы, чтобы клон, сгенерированный F вместе с двумя константными функциями nullary, был функционально полным или, что эквивалентно, функционально полным в сильном смысле предыдущего параграфа. Пример булевой функции, заданной S ( x , y , z ) = z , если x = y и S ( x , y , z ) = x в противном случае показывает, что это условие строго слабее функциональной полноты. [5] [6] [7]
Эмиль Пост доказал, что набор логических связок является функционально полным тогда и только тогда, когда он не является подмножеством ни одного из следующих наборов связок:
Пост дал полное описание решетки всех клонов ( множеств операций, замкнутых относительно композиции и содержащих все проекции) на двухэлементном множестве { T , F } , ныне называемом решеткой Поста , из чего следует приведенный выше результат как простое следствие: пять упомянутых множеств связок являются в точности максимальными нетривиальными клонами. [8]
Когда один логический связной или булев оператор функционально завершен сам по себе, он называется функцией Шеффера [9] или иногда единственным достаточным оператором . Унарных операторов с таким свойством не существует . NAND и NOR , которые являются дуальными друг другу , являются единственными двумя бинарными функциями Шеффера. Они были открыты, но не опубликованы, Чарльзом Сандерсом Пирсом около 1880 года и независимо переоткрыты и опубликованы Генри М. Шеффером в 1913 году. [10] В терминологии цифровой электроники двоичный вентиль NAND (↑) и двоичный вентиль NOR (↓) являются единственными бинарными универсальными логическими вентилями .
Ниже приведены минимальные функционально полные наборы логических связок с арностью ≤ 2: [11]
Не существует минимальных функционально полных наборов из более чем трех не более чем бинарных логических связок. [11] Чтобы сделать приведенные выше списки читабельными, операторы, игнорирующие один или несколько входов, были опущены. Например, оператор, игнорирующий первый вход и выдающий отрицание второго, можно заменить унарным отрицанием.
NAND
(↑) полноты. Как показано в [12]NOR
(↓) полноты. Как показано в [13]Обратите внимание, что электронная схема или функция программного обеспечения могут быть оптимизированы путем повторного использования, чтобы сократить количество вентилей. Например, операция " A ∧ B ", выраженная ↑ вентилями, реализуется с помощью повторного использования " A ↑ B ",
Помимо логических связок (булевых операторов), функциональная полнота может быть введена в других областях. Например, набор обратимых вентилей называется функционально полным, если он может выразить каждый обратимый оператор.
3-входовой вентиль Фредкина сам по себе является функционально полным обратимым вентилем – единственным достаточным оператором. Существует много других 3-входовых универсальных логических вентилей, таких как вентиль Тоффоли .
В квантовых вычислениях вентиль Адамара и вентиль T являются универсальными, хотя и с несколько более строгим определением, чем определение функциональной полноты.
Между алгеброй множеств и булевой алгеброй существует изоморфизм , то есть они имеют одинаковую структуру . Тогда, если мы отобразим булевы операторы в операторы множеств, «переведенный» выше текст будет действителен также для множеств: существует множество «минимальных полных наборов операторов теории множеств», которые могут генерировать любые другие отношения множеств. Более популярными «минимальными полными наборами операторов» являются {¬, ∩} и {¬, ∪} . Если универсальное множество запрещено , операторы множеств ограничены сохранением ложности (Ø) и не могут быть эквивалентны функционально полной булевой алгебре.