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

Понятие в математической логике

В логике функционально полный набор логических связок или булевых операторов — это тот, который можно использовать для выражения всех возможных таблиц истинности путем объединения членов набора в булево выражение . ^{[1] [2]} Хорошо известный полный набор связок — это { AND , NOT } . Каждый из синглетонных наборов { NAND } и { NOR } является функционально полным. Однако набор {AND, OR } является неполон из-за его неспособности выразить NOT.

Функционально завершенные ворота (или набор ворот) можно также назвать универсальными воротами (или универсальным набором ворот).

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

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

Введение

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

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

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

${\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

Из этого следует, что меньший набор также является функционально полным. (Его функциональная полнота также доказывается теоремой о дизъюнктивной нормальной форме .) ^[4] Но это все еще не минимально, поскольку может быть определено как ${\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 \{\land ,\lor ,\rightarrow \}}$ ${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

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

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

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

Другим естественным условием было бы, чтобы клон, сгенерированный F вместе с двумя константными функциями nullary, был функционально полным или, что эквивалентно, функционально полным в сильном смысле предыдущего параграфа. Пример булевой функции, заданной 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]

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

Когда один логический связной или булев оператор функционально завершен сам по себе, он называется функцией Шеффера ^[9] или иногда единственным достаточным оператором . Унарных операторов с таким свойством не существует . NAND и NOR , которые являются дуальными друг другу , являются единственными двумя бинарными функциями Шеффера. Они были открыты, но не опубликованы, Чарльзом Сандерсом Пирсом около 1880 года и независимо переоткрыты и опубликованы Генри М. Шеффером в 1913 году. ^[10] В терминологии цифровой электроники двоичный вентиль NAND (↑) и двоичный вентиль NOR (↓) являются единственными бинарными универсальными логическими вентилями .

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

Один элемент

{↑}, {↓}.

Два элемента

${\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 \}.}$

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

Примеры

• Примеры использования NAND(↑) полноты. Как показано в ^[12]
  • ¬ А ≡ А ↑ А
  • А ∧ В ≡ ¬( А ↑ В ) ≡ ( А ↑ В ) ↑ ( А ↑ В )
  • А ∨ В ≡ (¬ А ) ↑ (¬ Б ) ≡ ( А ↑ А ) ↑ ( Б ↑ Б )
• Примеры использования NOR(↓) полноты. Как показано в ^[13]
  • ¬ А ≡ А ↓ А
  • А ∨ В ≡ ¬( А ↓ В ) ≡ ( А ↓ В ) ↓ ( А ↓ В )
  • А ∧ Б ≡ (¬ А ) ↓ (¬ Б ) ≡ ( А ↓ А ) ↓ ( Б ↓ Б )

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

X ≡ ( А ↑ Б ); А ∧ Б ≡ X ↑ Б

В других доменах

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

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

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

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

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

Смотрите также

• Алгебра множеств  – тождества и отношения, включающие множества
• Булева алгебра  – Алгебраические манипуляции с «истиной» и «ложью»
• Полнота (логика)  – Характерна для некоторых логических систем.
• Двойственность конъюнкции/дизъюнкции  – свойства, связывающие логическую конъюнкцию и дизъюнкцию
• Список тем по булевой алгебре
• Логика NAND  – Логика, построенная только на вентилях NAND
• Логика NOR  – Создание других вентилей с использованием только вентилей NOR
• Компьютер с одним набором инструкций  – Абстрактная машина, которая использует только одну инструкцию.

Ссылки

1. Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press , ISBN 978-0-12-238452-3. («Полный набор логических связок»).
2. Нолт, Джон; Рохатин, Деннис; Варци, Ахилл (1998), Очерк теории и проблем логики Шаума (2-е изд.), Нью-Йорк: McGraw–Hill , ISBN 978-0-07-046649-4. («[Ф]ункциональная полнота [набора] логических операторов»).
3. Смит, Питер (2003), Введение в формальную логику , Cambridge University Press , ISBN 978-0-521-00804-4. (Определяет «выразительно адекватный», сокращенно до «адекватный набор связок» в заголовке раздела.)
4. Howson, Colin (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. 41. ISBN 978-0-415-13342-5.
5. Весселькампер, TC (1975), «Единственный достаточный оператор», Notre Dame Journal of Formal Logic , 16 : 86–88, doi : 10.1305/ndjfl/1093891614
6. Massey, GJ (1975), «Относительно предполагаемой функции Шеффера», Notre Dame Journal of Formal Logic , 16 (4): 549–550, doi : 10.1305/ndjfl/1093891898
7. Весселькампер, TC (1975), «Исправление к моей статье» A. Единственный достаточный оператор», Notre Dame Journal of Formal Logic , 16 (4): 551, doi : 10.1305/ndjfl/1093891899
8. Эмиль Леон Пост (1941). Двузначные итеративные системы математической логики. Annals of Mathematics studies. Том 5. Принстон: Princeton University Press. doi : 10.1515/9781400882366. ISBN 9781400882366.См. стр. 105 для теоремы, стр. 53, 59, 69, 70, 131 для определения классов A ₁ , L ₁ , C ₂ , C ₃ , D ₃ и стр. 35, 43 для определения условия [A:a] и функции α, β, γ.
9. Первоначально этот термин ограничивался бинарными операциями, но с конца 20-го века он используется более широко. Мартин, Н. М. (1989), Системы логики , Cambridge University Press, стр. 54, ISBN 978-0-521-36770-7.
10. Scharle, TW (1965), «Аксиоматизация исчисления высказываний с функторами Шеффера», Notre Dame J. Formal Logic , 6 (3): 209–217, doi : 10.1305/ndjfl/1093958259.
11. Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51 : 117–32. В своем списке на последней странице статьи Wernick не делает различий между ← и →, или между и . ${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$
12. «Операции вентиля NAND» на http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
13. «Операции с вентилями NOR» на http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html