功能完备性
目录
功能完备性
在逻辑学中，一个功能完备的逻辑连接词或布尔运算符集是指通过将该集的成员组合成一个布尔表达式，可以用来表达所有可能的真值表。一个著名的完整连接词集是{AND,NOT}。每个单子集{NAND}和{NOR}在功能上都是完整的。一个在功能上完整的门或门集也可以被称为通用门/门。一套功能完整的门可以利用或产生”垃圾位”作为其计算的一部分，这些垃圾位既不是输入的一部分，也不是系统输出的一部分。在命题逻辑的背景下，功能完整的连接词集也被称为（表达上的）充分。从数字电子学的角度来看，功能完备性意味着每一个可能的逻辑门都可以实现为集合所规定的类型的门的网络。特别是，所有的逻辑门都可以由二进制NAND门或二进制NOR门组合而成。
功能完备性的引言
现代的逻辑学文献通常把一些连接词的子集作为基本的连接词：连词({displaystyle{leftrightarrow}）；以及可能的双条件（{displaystyle{leftrightarrow}）。).如果需要的话，可以通过在这些基元中定义进一步的连接词。例如，NOR（有时表示为)，可以用disjunction和negation来定义。事实证明，每一个二元连接词都可以用以下术语来定义{¬,∧,∨,→,↔}{displaystyle{neg,and,lor,to,leftrightarrow}}，所以这个集合是函数完整的。因此，这个集合在功能上是完整的。然而，它仍然包含一些冗余：这个集合不是一个最小的功能完整的集合，因为条件和双条件可以用其他连接词来定义为
正式定义
给定布尔域B={0,1}，如果基本函数ƒi在B上生成的克隆包含所有函数ƒ，则一组布尔函数F：Bni→B是函数完整的。Bn→B，对于所有严格的正整数n≥1。换句话说，如果每个至少取一个变量的布尔函数都可以用函数ƒi来表示，那么这个集合就是函数完整的。由于每个至少有一个变量的布尔函数都可以用二元布尔函数来表达，所以当且仅当每个二元布尔函数都可以用F中的函数来表达时，F在功能上是完整的。一个更自然的条件是，F所产生的克隆由所有函数ƒ组成。然而，上面给出的例子在这个更强的意义上并不是函数完整的，因为如果F本身不包含至少一个空函数，就不可能用F来写一个空函数，也就是一个常数表达。
有了这个更强的定义，最小的函数完全集将有两个元素。另一个自然条件是，由F和两个空常数函数一起生成的克隆是函数完全的，或者说，在上一段的强意义上是函数完全的。由S(x,y,z)=z（如果x=y）和S(x,y,z)=x（否则）给出的布尔函数的例子表明，这个条件严格来说弱于函数完备性。功能完备性的特征EmilPost证明，当且仅当一组逻辑连接词不是一个子集的时候，它就是功能完备的。