Функциональная полнота - Functional completeness

В логике , А функционально полный набор логических связок или булевых операторов является тот , который может быть использован , чтобы выразить все возможные таблицы истинности пути объединения членов набора в логическое выражение . Хорошо известный полный набор связок - {И, НЕ}, состоящий из двоичного соединения и отрицания . Каждый из одноэлементных наборов { NAND } и { NOR } функционально завершен.

Ворота или калитки, являющиеся функционально законченными, также могут называться универсальными воротами.

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

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

С точки зрения цифровой электроники функциональная полнота означает, что каждый возможный логический элемент может быть реализован как сеть вентилей типов, предписанных набором. В частности, все логические вентили могут быть собраны либо только из бинарных вентилей И-НЕ , либо только из бинарных вентилей ИЛИ-НЕ .

Вступление

Современные тексты по логике обычно принимают в качестве примитивов некоторое подмножество связок: конъюнкция ( ); дизъюнкция ( ); отрицание ( ); материальный условный ( ); и, возможно, двусмысленный ( ). При желании можно определить другие связки, определяя их в терминах этих примитивов. Например, NOR (иногда обозначаемое как отрицание дизъюнкции) может быть выражено как соединение двух отрицаний: ${\ displaystyle \ land}$ ${\ Displaystyle \ lor}$ ${\ displaystyle \ neg}$ ${\ displaystyle \ to}$ ${\ displaystyle \ leftrightarrow}$ ${\ displaystyle \ downarrow}$

{\ displaystyle A \ downarrow B: = \ neg A \ land \ neg B}

Точно так же отрицание конъюнкции, И-НЕ (иногда обозначаемое как ), может быть определено в терминах дизъюнкции и отрицания. Оказывается, каждая бинарная связка может быть определена в терминах , поэтому этот набор является функционально полным. ${\ displaystyle \ uparrow}$ ${\ Displaystyle \ {\ neg, \ land, \ lor, \ to, \ leftrightarrow \}}$

Однако он по-прежнему содержит некоторую избыточность: этот набор не является минимальным функционально полным набором, потому что условное и биконусное могут быть определены в терминах других связок как

{\ displaystyle {\ begin {align} A \ to B &: = \ neg A \ lor B \\ A \ leftrightarrow B &: = (A \ to B) \ land (B \ to A). \ end {выравнивается}} }

Отсюда следует, что меньший набор также является функционально полным. Но это все же не минимально, что можно определить как ${\ Displaystyle \ {\ neg, \ land, \ lor \}}$ ${\ Displaystyle \ lor}$

{\ displaystyle A \ lor B: = \ neg (\ neg A \ land \ neg B).}

В качестве альтернативы, может быть определено в терминах аналогичным образом или может быть определено в терминах : ${\ displaystyle \ land}$ ${\ Displaystyle \ lor}$ ${\ Displaystyle \ lor}$ ${\ displaystyle \ rightarrow}$

{\ displaystyle \ A \ vee B: = \ neg A \ rightarrow B.}

Дальнейшие упрощения невозможны. Таким образом, каждый из двух элементов набора связок , содержащих и один из является минимальным функционально полным подмножеством из . ${\ displaystyle \ neg}$ ${\ Displaystyle \ {\ земля, \ lor, \ rightarrow \}}$ ${\ Displaystyle \ {\ neg, \ land, \ lor, \ to, \ leftrightarrow \}}$

Формальное определение

Принимая во внимание Логический домен В = {0,1}, множество Р функций булевых ƒ _I : B ^{п _я} → B является функционально полным , если клон на B , порожденный основные функциями ƒ _я содержу все функции ƒ : B ^н → B , для всех строго положительных чисел n ≥ 1 . Другими словами, набор является функционально полным, если каждая логическая функция, которая принимает хотя бы одну переменную, может быть выражена в терминах функций ƒ _i . Так как каждая булева функция по меньшей мере , одной переменных может быть выражена в терминах бинарных булевых функций, Р функционально полный , если и только если каждая двоичная булева функция может быть выражена в терминах функций в F .

Более естественным условием было бы то, что клон, сгенерированный F, состоял из всех функций ƒ : B ⁿ → B для всех целых чисел n ≥ 0 . Однако приведенные выше примеры не являются функционально полными в этом более сильном смысле, потому что невозможно написать нулевую функцию, то есть постоянное выражение, в терминах F, если F сам по себе не содержит хотя бы одной нулевой функции. С этим более сильным определением наименьшие функционально полные наборы будут иметь 2 элемента.

Другим естественным условием было бы то, что клон, сгенерированный F вместе с двумя нулевыми постоянными функциями, был бы функционально полным или, что то же самое, функционально полным в строгом смысле предыдущего абзаца. Пример булевой функции, заданной как S ( x , y , z ) = z, если x = y, и S ( x , y , z ) = x в противном случае, показывает, что это условие строго слабее, чем функциональная полнота.

Характеристика функциональной полноты

Эмиль Пост доказал, что набор логических связок является функционально полным тогда и только тогда, когда он не является подмножеством любого из следующих наборов связок:

В монотонных связках; изменение истинностного значения любых связанных переменных с F на T без изменения любого с T на F никогда не заставляет эти связки изменять свое возвращаемое значение с T на F , например . ${\ displaystyle \ vee, \ wedge, \ top, \ bot}$
В аффинных связках, таким образом, что каждый связные переменная всегда или никогда не влияет на значение истинности вернуть эти связки, например . ${\ displaystyle \ neg, \ top, \ bot, \ leftrightarrow, \ nleftrightarrow}$
В автодуальных связках, которые равны их собственные де Морган двойного ; если значения истинности всех переменных меняются местами, то же самое и значение истинности, возвращаемое этими связками, например , MAJ ( p , q , r ). ${\ displaystyle \ neg}$
В истинности сохраняющих связок; они возвращают значение истинности T при любой интерпретации, которая присваивает T всем переменным, например . ${\ displaystyle \ vee, \ wedge, \ top, \ rightarrow, \ leftrightarrow}$
В ложности сохраняющих связок; они возвращают значение истинности F при любой интерпретации, которая присваивает F всем переменным, например . ${\ displaystyle \ vee, \ wedge, \ bot, \ nrightarrow, \ nleftrightarrow}$

Фактически, Пост дал полное описание решетки всех клонов (наборов операций, замкнутых относительно композиции и содержащих все проекции) на двухэлементном множестве { T , F }, ныне называемом решеткой Поста , что подразумевает приведенный выше результат как простое следствие: пять упомянутых наборов связок являются в точности максимальными клонами.

Минимальные функционально полные операторы

Когда один логический связующий или логический оператор является функционально полным сам по себе, он называется функцией Шеффера или иногда единственным достаточным оператором . Там нет унарных операторов , обладающих этого свойством. NAND и NOR , которые являются двумя друг к другу , являются только две двоичные функции Шеффера. Они были обнаружены, но не опубликованы Чарльзом Сандерсом Пирсом примерно в 1880 году, были заново открыты независимо и опубликованы Генри М. Шеффером в 1913 году. В терминологии цифровой электроники двоичный логический элемент И-НЕ и двоичный логический элемент ИЛИ-НЕ являются единственными универсальными двоичными логическими элементами .

Ниже приведены минимальные функционально полные наборы логических связок с арностью ≤ 2:

Один элемент: {↑}, {↓}.
Два элемента: ${\ Displaystyle \ {\ vee, \ neg \}}$ , , , , , , , , , , , , , , , , , ${\ Displaystyle \ {\ клин, \ neg \}}$ ${\ Displaystyle \ {\ к, \ neg \}}$ ${\ Displaystyle \ {\ получает, \ neg \}}$ ${\ displaystyle \ {\ to, \ bot \}}$ ${\ Displaystyle \ {\ получает, \ бот \}}$ ${\ displaystyle \ {\ to, \ nleftrightarrow \}}$ ${\ displaystyle \ {\ gets, \ nleftrightarrow \}}$ ${\ displaystyle \ {\ to, \ nrightarrow \}}$ ${\ displaystyle \ {\ to, \ nleftarrow \}}$ ${\ Displaystyle \ {\ получает, \ nrightarrow \}}$ ${\ Displaystyle \ {\ получает, \ nleftarrow \}}$ ${\ Displaystyle \ {\ nrightarrow, \ neg \}}$ ${\ Displaystyle \ {\ nleftarrow, \ neg \}}$ ${\ displaystyle \ {\ nrightarrow, \ top \}}$ ${\ displaystyle \ {\ nleftarrow, \ top \}}$ ${\ displaystyle \ {\ nrightarrow, \ leftrightarrow \}}$ ${\ displaystyle \ {\ nleftarrow, \ leftrightarrow \}.}$
Три элемента: ${\ displaystyle \ {\ lor, \ leftrightarrow, \ bot \}}$ , , , , , ${\ displaystyle \ {\ lor, \ leftrightarrow, \ nleftrightarrow \}}$ ${\ displaystyle \ {\ lor, \ nleftrightarrow, \ top \}}$ ${\ Displaystyle \ {\ земля, \ leftrightarrow, \ bot \}}$ ${\ Displaystyle \ {\ земля, \ leftrightarrow, \ nleftrightarrow \}}$ ${\ displaystyle \ {\ land, \ nleftrightarrow, \ top \}.}$

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

Примеры

Примеры использования NAND(↑) полноты. Как проиллюстрировано,
- ¬A ≡ A ↑ A
- A ∧ B ≡ ¬ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
- A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
Примеры использования NOR(↓) полноты. Как проиллюстрировано,
- ¬A ≡ A ↓ A
- A ∨ B ≡ ¬ (A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
- A ∧ B ≡ (A ↓ A) ↓ (B ↓ B)

Обратите внимание, что электронная схема или программная функция могут быть оптимизированы путем повторного использования, чтобы уменьшить количество вентилей. Например, операция «A B», выраженная с помощью ↑ гейтов, реализуется с повторным использованием «A ↑ B»,

X ≡ (A ↑ B); А ∧ В ≡ X ↑ X

В других сферах

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

3-вход Фредкин затвора является функционально полной обратимым ворот само собой - единственным достаточным оператором. Есть много других универсальных логических вентилей с тремя входами, таких как вентиль Тоффоли .

В квантовых вычислениях , то ворота Адамар и Т ворот являются универсальными, хотя и с немного более ограничительным определением , чем функциональная полноты.

Теория множеств

Существует изоморфизм между алгеброй множеств и булевой алгеброй , то есть, они имеют ту же структуру . Затем, если мы отображаем логические операторы в операторы множеств, «переведенный» выше текст действителен также для множеств: существует множество «минимальных полных наборов операторов теории множеств», которые могут порождать любые другие отношения множеств. Наиболее популярными «минимальными полными наборами операторов» являются {¬, ∩} и {¬, ∪}. Если универсальный набор запрещен , операторы множества ограничиваются сохранением ложности (Ø) и не могут быть эквивалентны функционально полной булевой алгебре.

Languages

In other projects