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

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

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

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

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

Введение [ править ]

Современные тексты по логике обычно принимают за примитивное некоторое подмножество связок: союз ( $\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 \}$ также функционально завершен. (Его функциональная полнота также доказывается теоремой о дизъюнктивной нормальной форме .) ^[4] Но это все же не минимально, так как $\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 в противном случае показывает, что это условие строго слабее, чем функциональная полнота. ^[5]^[6]^[7]

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

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

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

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

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

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

Один элемент: {↑}, {↓}.
Два элемента: $\{\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 \}.$

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

Примеры [ править ]

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

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

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

В других доменах [ править ]

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

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

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

Теория множеств [ править ]

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

См. также [ править ]

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

Ссылки [ править ]

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

[Enderton2001-1] Эндертон, Герберт (2001), Математическое введение в логику (2-е изд.), Бостон, Массачусетс: Academic Press , ISBN 978-0-12-238452-3 . («Полный набор логических связок»).

[Nolt1998-2] Нолт, Джон; Рогатин, Деннис; Варци, Ахилле (1998), Очерк теории и проблем логики Шаума (2-е изд.), Нью-Йорк: McGraw – Hill , ISBN 978-0-07-046649-4 . («[F] функциональная полнота [a] набора логических операторов»).

[Smith2003-3] Смит, Питер (2003), Введение в формальную логику , Cambridge University Press , ISBN 978-0-521-00804-4 . (Определяет «выразительно адекватный», сокращенный до «адекватного набора связок» в заголовке раздела.)

[:13-4] Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Рутледж. п. 41. ИСБН 978-0-415-13342-5 .

[Wesselkamper1975a-5] Весселькампер, TC (1975), «Единственный достаточный оператор» , Notre Dame Journal of Formal Logic , 16 : 86–88, doi : 10.1305/ndjfl/1093891614

[Massey1975-6] Мэсси, Дж. Дж. (1975), «Относительно предполагаемой функции Шеффера» , Notre Dame Journal of Formal Logic , 16 (4): 549–550, doi : 10.1305/ndjfl/1093891898

[Wesselkamper1975b-7] Весселькампер, Т.К. (1975), «Поправка к моей статье «А. Единственный достаточный оператор» , , Notre Dame Journal of Formal Logic , 16 (4): 551, doi : 10.1305/ndjfl/1093891899

[Martin1989-8] Первоначально этот термин ограничивался бинарными операциями, но с конца 20 века он используется более широко. Мартин, Нью-Мексико (1989), Системы логики , издательство Кембриджского университета, стр. 54, ISBN 978-0-521-36770-7 .

[Scharle1965-9] Шарл, Т.В. (1965), «Аксиоматизация исчисления высказываний с помощью функторов Шеффера» , Notre Dame J. Formal Logic , 6 (3): 209–217, doi : 10.1305/ndjfl/1093958259 .

[Wernick-10] Перейти обратно: ^а ^б Верник, Уильям (1942) «Полные наборы логических функций», Труды Американского математического общества 51 : 117–32. В своем списке на последней странице статьи Верник не делает различия между ← и → или между $\nleftarrow$ и $\nrightarrow$ .

[11] «Операции NAND-ворот» на http://hyperphysicals.phy-astr.gsu.edu/hbase/electronic/nand.html.

[12] «Операции ворот NOR» на http://hyperphysicals.phy-astr.gsu.edu/hbase/electronic/nor.html.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]