stringtranslate.com

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

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

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

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

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

Введение

Современные тексты по логике обычно принимают в качестве примитива некоторое подмножество связок: конъюнкция ( ); дизъюнкция ( ); отрицание ( ); материальное условное ( ); и, возможно, биусловное ( ). Дальнейшие связки могут быть определены, если это необходимо, путем определения их в терминах этих примитивов. Например, NOR (отрицание дизъюнкции, иногда обозначаемое ) может быть выражено как конъюнкция двух отрицаний:

Аналогично, отрицание конъюнкции, NAND (иногда обозначаемое как ), может быть определено в терминах дизъюнкции и отрицания. Каждая бинарная связка может быть определена в терминах , что означает, что множество является функционально полным. Однако оно содержит избыточность: это множество не является минимальным функционально полным множеством, поскольку условное и биусловное можно определить в терминах других связок как

Из этого следует, что меньший набор также является функционально полным. (Его функциональная полнота также доказывается теоремой о дизъюнктивной нормальной форме .) [4] Но это все еще не минимально, поскольку может быть определено как

В качестве альтернативы может быть определено в терминах аналогичным образом или может быть определено в терминах :

Дальнейшие упрощения невозможны. Следовательно, каждый двухэлементный набор связок, содержащий и один из является минимальным функционально полным подмножеством .

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

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

Более естественным условием было бы, чтобы клон, сгенерированный F, состоял из всех функций f  : B nB , для всех целых чисел 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] Чтобы сделать приведенные выше списки читабельными, операторы, игнорирующие один или несколько входов, были опущены. Например, оператор, игнорирующий первый вход и выдающий отрицание второго, можно заменить унарным отрицанием.

Примеры

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

X ≡ ( АБ ); АБXБ

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

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

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

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

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

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

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

Ссылки

  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 1 , L 1 , C 2 , C 3 , D 3 и стр. 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. ^ ab Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51 : 117–32. В своем списке на последней странице статьи Wernick не делает различий между ← и →, или между и .
  12. ^ «Операции вентиля NAND» на http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
  13. ^ «Операции с вентилями NOR» на http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html