Введение
Концепция в математической логике В логике функционально полный набор логических соединителей или булевых операторов - это тот, который может быть использован для выражения всех возможных таблиц истинности путем объединения членов множества в булевое выражение. Хорошо известный полный набор соединителей - это каждый из одиночных наборов и функционально полный. Однако набор неполный, из-за его невозможности выразить НЕ. Врата (или набор ворот), которые функционально завершены, также могут называться универсальными воротами (или универсальным набором ворот). В контексте логики предложений функционально полные наборы соединителей также называются (экспрессивно) адекватными. С точки зрения цифровой электроники функциональная полнота означает, что каждый возможный логический шлюз может быть реализован как сеть шлюзов типов, предписанных набором. В частности, все логические шлюзы могут быть собраны либо только из бинарных NAND- шлюзов, либо только из бинарных NOR- шлюзов.
In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well known complete set of connectives is Each of the singleton sets and is functionally complete. However, the set is incomplete, due to its inability to express NOT. A gate (or set of gates) that is functionally complete can also be called a universal gate (or a universal set of gates). In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate. From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates.
Введение
Современные тексты по логике обычно принимают за примитивные некоторые подмножества соединительных: соединение; разъединение; отрицание; материальный условный; и, возможно, двухусловной. Дальнейшие соединительные могут быть определены, если того пожелают, путем их определения с точки зрения этих примитивных. Например, NOR (отрицание дисъюнкции, иногда обозначаемое как ) может быть выражено как соединение двух отрицаний: Аналогичным образом, отрицание соединения, NAND (иногда обозначаемое как ), может быть определено с точки зрения дисъюнкции и отрицания. Каждый двоичный соединитель может быть определен в терминах , что означает, что множество функционально полно. Однако в ней содержится избыточность: это множество не является минимальным функционально полным множеством, потому что условное и двуобусловленное могут быть определены с точки зрения других соединителей, как следует из этого, что меньшее множество также функционально полно. (Его функциональная полнота также доказана теоремой о дизъюнктивной нормальной форме.) Но это все еще не минимально, как можно определить как альтернативно, может быть определено в терминах в аналогичной манере, или может быть определено в терминах: Следовательно, каждый двухэлементный набор соединителей, содержащий и один из, является минимальным функционально полным подмножеством .
Similarly, the negation of the conjunction, NAND (sometimes denoted as ), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of , which means that set is functionally complete. However, it contains redundancy: this set is not a minimal functionally complete set, because the conditional and biconditional can be defined in terms of the other connectives as
It follows that the smaller set is also functionally complete. (Its functional completeness is also proved by the Disjunctive Normal Form Theorem.) But this is still not minimal, as can be defined as
Alternatively, may be defined in terms of in a similar manner, or may be defined in terms of :
No further simplifications are possible. Hence, every two element set of connectives containing and one of is a minimal functionally complete subset of .
Формальное определение
При наличии булевой области множество F булевых функций fi: Bni → B функционально полно, если клон на B, генерируемый базовыми функциями fi, содержит все функции f: Bn → B, для всех строго положительных целых чисел n ≥ 1. Другими словами, множество функционально полно, если каждая булева функция, которая принимает по крайней мере одну переменную, может быть выражена с точки зрения функций fi. Поскольку каждая булева функция по крайней мере одной переменной может быть выражена в терминах двоичных булевых функций, F функционально полная, если и только если каждая двоичная булевая функция может быть выражена в терминах функций в F. Более естественным условием будет то, что клон, генерируемый F, будет состоять из всех функций f: Bn → B, для всех целых чисел n ≥ 0. Однако приведенные выше примеры не являются функционально полными в этом более сильном смысле, потому что невозможно написать нулевую функцию, т. е. постоянное выражение, с точки зрения F, если сама F не содержит по крайней мере одной нулевой функции. При таком более строгом определении, самые маленькие функционально полные множества будут иметь 2 элемента. Еще одним естественным условием будет то, что клон, генерируемый F вместе с двумя нулевыми постоянными функциями, будет функционально полным или, эквивалентно, функционально полным в строгом смысле предыдущего пункта. Пример булевой функции, данный 1=S(x, y, z) = z, если 1=x = y и 1=S(x, y, z) = x, в противном случае показывает, что это условие строго слабее, чем функциональная полнота.
A more natural condition would be that the clone generated by F consist of all functions f : Bn → B, for all integers n ≥ 0. However, the examples given above are not functionally complete in this stronger sense because it is not possible to write a nullary function, i. e. a constant expression, in terms of F if F itself does not contain at least one nullary function. With this stronger definition, the smallest functionally complete sets would have 2 elements. Another natural condition would be that the clone generated by F together with the two nullary constant functions be functionally complete or, equivalently, functionally complete in the strong sense of the previous paragraph. The example of the Boolean function given by 1=S(x, y, z) = z if 1=x = y and 1=S(x, y, z) = x otherwise shows that this condition is strictly weaker than functional completeness.
В других областях
Помимо логических соединителей (булевых операторов), функциональная полнота может быть введена в других областях. Например, набор обратимых ворот называется функционально полным, если он может выразить каждый обратимый оператор. Входные ворота Фредкина с 3 входами являются функционально полными обратимыми воротами сами по себе единственный достаточный оператор. Существует много других трех входных универсальных логических ворот, таких как Toffoli gate. В квантовых вычислениях ворота Хадамарда и T-ворота являются универсальными, хотя с определением, немного более ограничивающим, чем функциональная полнота.
Теория множеств
Между алгеброй множеств и булевой алгеброй существует изоморфизм, то есть они имеют одну и ту же структуру. Затем, если мы отобразим булевых операторов в операторы множеств, "переведенный" выше текст действителен также для множеств: существует много "минимальных полных множеств операторов теории множеств", которые могут генерировать любые другие отношения множеств. Более популярными являются "Минимальные полные множества операторов" и Если универсальное множество запрещено, операторы множества ограничены сохранением ложности (Ø), и не могут быть эквивалентными функционально полной булевой алгебре.