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

Functional completeness

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

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

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

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

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

Вступление

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

Точно так же отрицание конъюнкции И-НЕ (иногда обозначается как ), можно определить в терминах дизъюнкции и отрицания. Оказывается, любую бинарную связку можно определить в терминах , так что этот набор является функционально полным.

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

Отсюда следует, что меньшее множество также является функционально полным. Но это все же не минимально, так как можно определить как

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

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

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

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

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

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

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

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

  • В монотонный связки; изменение значения истинности любых связанных переменных с F к Т без изменений из Т к F никогда не заставляет эти связки менять возвращаемое значение с Т к F, например .
  • В аффинный связки, так что каждая связанная переменная всегда или никогда не влияет на значение истинности, возвращаемое этими связками, например .
  • В самодвойственный связки, которые равны своим собственным де Морган двойственный; если значения истинности всех переменных меняются местами, то значение истинности возвращают эти связки, например , MAJ(п,q,р).
  • В сохраняющий истину связки; они возвращают значение истины Т при любой интерпретации, которая присваивает Т ко всем переменным, например .
  • В фальшивый связки; они возвращают значение истины F при любой интерпретации, которая присваивает F ко всем переменным, например .

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

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

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

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

Один элемент
{↑}, {↓}.
Два элемента
, , , , , , , , , , , , , , , , ,
Три элемента
, , , , ,

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

Примеры

  • Примеры использования NAND(↑) полнота. Как показано[10]
    • ¬A ≡ A ↑ A
    • A ∧ B ≡ ¬ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
    • A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
  • Примеры использования НИ(↓) полнота. Как показано[11]
    • ¬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

В других областях

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

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

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

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

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

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

Рекомендации

  1. ^ Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Академическая пресса, ISBN 978-0-12-238452-3. («Полный набор логических связок»).
  2. ^ Нолт, Джон; Рогатин, Денис; Варци, Ахилле (1998), Очерк теории и проблем логики Шаума (2-е изд.), Нью-Йорк: Макгроу-Хилл, ISBN 978-0-07-046649-4. («[F] функциональная полнота [a] набора логических операторов»).
  3. ^ Смит, Питер (2003), Введение в формальную логику, Издательство Кембриджского университета, ISBN 978-0-521-00804-4. (Определяет «выразительно адекватный», сокращенный до «адекватный набор связок» в заголовке раздела.)
  4. ^ Wesselkamper, T.C. (1975), «Единственный достаточный оператор», Журнал формальной логики Нотр-Дам, 16: 86–88, Дои:10.1305 / ndjfl / 1093891614
  5. ^ Мэсси, Г.Дж. (1975), «Относительно предполагаемой функции Шеффера», Журнал формальной логики Нотр-Дам, 16 (4): 549–550, Дои:10.1305 / ndjfl / 1093891898
  6. ^ Wesselkamper, T.C. (1975), "Поправка к моей статье" A. Единственный достаточный оператор ", Журнал формальной логики Нотр-Дам, 16 (4): 551, Дои:10.1305 / ndjfl / 1093891899
  7. ^ Срок изначально ограничивался двоичный операций, но с конца 20 века он используется более широко. Мартин, Н. М. (1989), Системы логики, Cambridge University Press, стр. 54, ISBN 978-0-521-36770-7.
  8. ^ Шарл, Т. (1965), «Аксиоматизация исчисления высказываний с функторами Шеффера», Нотр-Дам Дж. Формальная логика, 6 (3): 209–217, Дои:10.1305 / ndjfl / 1093958259.
  9. ^ а б Верник, Уильям (1942) "Полные наборы логических функций", Труды Американского математического общества 51: 117–32. В своем списке на последней странице статьи Верник не делает различий между ← и → или между и .
  10. ^ "Операции с воротами NAND" на http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
  11. ^ "NOR Gate Operations" в http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html