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

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

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

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

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

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

Введение

Современные тексты по логике обычно принимают за примитивные некоторые подмножества связок: союз ( ); дизъюнкция ( ); отрицание ( ); материальное условное ( ); и, возможно, двуусловие ( ). При желании можно определить и другие связки, определяя их в терминах этих примитивов. Например, НО (отрицание дизъюнкции, иногда обозначаемое ) можно выразить как соединение двух отрицаний: ${\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{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

Отсюда следует, что меньший набор также является функционально полным. Но это все же не минимально, так как можно определить как ${\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  : Bn → B для всех целых чисел n ≥ 0 . Однако приведенные выше примеры не являются функционально полными в этом более строгом смысле, поскольку невозможно записать нулевую функцию, то есть постоянное выражение, в терминах F , если само F не содержит хотя бы одной нулевой функции. Согласно этому более строгому определению, наименьшие функционально полные множества будут состоять из двух элементов.

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

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

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

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

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

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

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

Один элемент

{↑}, {↓}.

Два элемента

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

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

Примеры

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

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

Икс ≡ ( А ↑ Б ); А ∧ Б ≡ Икс ↑ Икс

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

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

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

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

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

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

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

• Алгебра множеств  - Тождества и отношения с участием множеств.
• Булева алгебра  - алгебраическое манипулирование «истиной» и «ложью».
• Полнота (логика)  - характеристика некоторых логических систем.
• Список тем по булевой алгебре
• Логика И-НЕ  - логика, построенная только из вентилей И-НЕ.
• Логика ИЛИ-НЕ  — создание других вентилей, используя только вентили ИЛИ-НЕ.
• Компьютер с одним набором инструкций  - абстрактная машина, использующая только одну инструкцию.

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

1. Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press , ISBN 978-0-12-238452-3. («Полный набор логических связок»).
2. Нолт, Джон; Рогатин, Деннис; Варци, Ахилле (1998), Очерк теории и проблем логики Шаума (2-е изд.), Нью-Йорк: McGraw – Hill , ISBN 978-0-07-046649-4. («[F] функциональная полнота [a] набора логических операторов»).
3. Смит, Питер (2003), Введение в формальную логику , Cambridge University Press , ISBN 978-0-521-00804-4. (Определяет «выразительно адекватный», сокращенный до «адекватного набора связок» в заголовке раздела.)
4. Весселькампер, TC (1975), «Единственный достаточный оператор», Notre Dame Journal of Formal Logic , 16 : 86–88, doi : 10.1305/ndjfl/1093891614
5. Мэсси, GJ (1975), «Относительно предполагаемой функции Шеффера», Notre Dame Journal of Formal Logic , 16 (4): 549–550, doi : 10.1305/ndjfl/1093891898
6. Весселькампер, TC (1975), «Поправка к моей статье» А. Единственный достаточный оператор», Notre Dame Journal of Formal Logic , 16 (4): 551, doi : 10.1305/ndjfl/1093891899
7. Первоначально этот термин ограничивался двоичными операциями, но с конца 20 века он используется более широко.Мартин, Нью-Мексико (1989), Системы логики , издательство Кембриджского университета, стр. 54, ISBN 978-0-521-36770-7.
8. Шарл, TW (1965), «Аксиоматизация исчисления высказываний с функторами Шеффера», Notre Dame J. Formal Logic , 6 (3): 209–217, doi : 10.1305/ndjfl/1093958259.
9. Верник, Уильям (1942) «Полные наборы логических функций», Труды Американского математического общества 51 : 117–32. В своем списке на последней странице статьи Верник не делает различия между ← и → или между и . ${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$
10. «Операции NAND-ворот» на http://hyperphysicals.phy-astr.gsu.edu/hbase/electronic/nand.html.
11. «Операции ворот NOR» на http://hyperphysicals.phy-astr.gsu.edu/hbase/electronic/nor.html.