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

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

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

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

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

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

Введение [ править ]

Современные тексты по логике обычно принимают в качестве примитивов некоторое подмножество связок: конъюнкция ( ); дизъюнкция ( ); отрицание ( ); материальный условный ( ); и, возможно, двусмысленный ( ). При желании можно определить другие связки, определяя их в терминах этих примитивов. Например, 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 \}}$

Формальное определение [ править ]

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

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

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

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

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

• В монотонных связках; изменение истинностного значения любых связанных переменных с 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 }, ныне называемом решеткой Поста , что подразумевает приведенный выше результат в виде простое следствие: пять упомянутых наборов связок являются в точности максимальными клонами.

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

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

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

Один элемент

{↑}, {↓}.

Два элемента

${\displaystyle \{\vee ,\neg \}}$, , , , , , , , , , , , , , , , ,${\displaystyle \{\wedge ,\neg \}}$${\displaystyle \{\to ,\neg \}}$${\displaystyle \{\gets ,\neg \}}$${\displaystyle \{\to ,\bot \}}$${\displaystyle \{\gets ,\bot \}}$${\displaystyle \{\to ,\nleftrightarrow \}}$${\displaystyle \{\gets ,\nleftrightarrow \}}$${\displaystyle \{\to ,\nrightarrow \}}$${\displaystyle \{\to ,\nleftarrow \}}$${\displaystyle \{\gets ,\nrightarrow \}}$${\displaystyle \{\gets ,\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 \{\land ,\leftrightarrow ,\bot \}}$${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\land ,\nleftrightarrow ,\top \}.}$

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

Примеры [ править ]

• Примеры использования NAND(↑) полноты. Как проиллюстрировано, ^[11]
  • ¬A ≡ A ↑ A
  • A ∧ B ≡ ¬ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
  • A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
• Примеры использования NOR(↓) полноты. Как показано в ^[12]
  • ¬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-вход Фредкин затвора является функционально полной обратимым ворот само собой - единственным достаточным оператором. Есть много других универсальных логических вентилей с тремя входами, таких как вентиль Тоффоли .

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

Теория множеств [ править ]

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

См. Также [ править ]

• Полнота (логика)
• Алгебра множеств
• Булева алгебра
• Логика NAND
• НИ логика
• Один компьютер с набором команд

Ссылки [ править ]