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

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

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

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

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

Введение

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

$A\downarrow B:=\neg A\land \neg B$

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

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

Отсюда следует, что меньший набор $\{\neg ,\land ,\lor \}$ также функционально завершен. (Его функциональная полнота также доказывается теоремой о дизъюнктивной нормальной форме .) Но это все же не минимально, так как $\lor$ может быть определен как

$A\lor B:=\neg (\neg A\land \neg B).$

Альтернативно, $\land$ может быть определен с точки зрения $\lor$ аналогичным образом или $\lor$ может быть определен с точки зрения $\rightarrow$:

$\ A\vee B:=\neg A\rightarrow B.$

Дальнейшие упрощения невозможны. Следовательно, каждое двухэлементное множество связок, содержащее $\neg$ и один из $\{\land ,\lor ,\rightarrow \}$ является минимальным функционально подмножеством полным $\{\neg ,\land ,\lor ,\to ,\leftrightarrow \}$.

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

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

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

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

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

Дополнительная информация: Решетка Поста.

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

• Монотонные связки ; изменение истинного значения любой связанной переменной с F на T без изменения какой-либо из T на F никогда не приводит к тому, что эти связки меняют свое возвращаемое значение с T на F , например $\vee ,\wedge ,\top ,\bot$.
• Аффинные связки, такие, что каждая связанная переменная либо всегда, либо никогда не влияет на значение истинности, возвращаемое этими связками, например $\neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow$.
• Самодвойственные двойственной по связки, равные своей собственной Де Моргану связке ; если значения истинности всех переменных меняются местами, то же самое и значение истинности, возвращаемое этими связками, например $\neg$, май ( п , q , р ) .
• Истинносохраняющие связки ; они возвращают значение истинности T при любой интерпретации, которая присваивает T всем переменным, например $\vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow$.
• Связки , сохраняющие ложность ; они возвращают значение истинности F при любой интерпретации, которая присваивает F всем переменным, например $\vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow$.

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

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

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

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

Один элемент

{↑}, {↓}.

Два элемента

$\{\vee ,\neg \}$, $\{\wedge ,\neg \}$, $\{\to ,\neg \}$, $\{\gets ,\neg \}$, $\{\to ,\bot \}$, $\{\gets ,\bot \}$, $\{\to ,\nleftrightarrow \}$, $\{\gets ,\nleftrightarrow \}$, $\{\to ,\nrightarrow \}$, $\{\to ,\nleftarrow \}$, $\{\gets ,\nrightarrow \}$, $\{\gets ,\nleftarrow \}$, $\{\nrightarrow ,\neg \}$, $\{\nleftarrow ,\neg \}$, $\{\nrightarrow ,\top \}$, $\{\nleftarrow ,\top \}$, $\{\nrightarrow ,\leftrightarrow \}$, $\{\nleftarrow ,\leftrightarrow \}.$

Три элемента

$\{\lor ,\leftrightarrow ,\bot \}$, $\{\lor ,\leftrightarrow ,\nleftrightarrow \}$, $\{\lor ,\nleftrightarrow ,\top \}$, $\{\land ,\leftrightarrow ,\bot \}$, $\{\land ,\leftrightarrow ,\nleftrightarrow \}$, $\{\land ,\nleftrightarrow ,\top \}.$

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

Примеры

• Примеры использования NAND (↑) полнота. Как иллюстрирует,
  • ¬ А ≡ А ↑ А
  • А ∧ B ≡ ¬( А ↑ B ) ≡ ( А ↑ B ) ↑ ( А ↑ B )
  • А ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( А ↑ А ) ↑ ( B ↑ B )
• Примеры использования NOR (↓) полнота. Как иллюстрирует,
  • ¬ А ≡ А ↓ А
  • А ∨ B ≡ ¬( А ↓ B ) ≡ ( А ↓ B ) ↓ ( А ↓ B )
  • А ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( А ↓ А ) ↓ ( B ↓ B )

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

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

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

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

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

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

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

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

См. также

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