函数完备性（逻辑联结词）

函数完备集
术语名称	函数完备集
英语名称	functionally complete set
别名	完备集, 功能完备集, 完备联结词集

函数完备
术语名称	函数完备
英语名称	functionally complete
别名	完备, 功能完备

函数完备性
术语名称	函数完备性
英语名称	functional completeness
别名	完备性, 功能完备性

函数完备(functionally complete)指一个逻辑联结词的集合，能够通过组合表达所有可能的真值函数。

定义

对逻辑联结词的集合 [math]\displaystyle{ S }[/math] ，若对任意 [math]\displaystyle{ n }[/math] 元真值函数 [math]\displaystyle{ f: \{0,1\}^n \to \{0,1\} }[/math] ，都存在一个只使用 [math]\displaystyle{ S }[/math] 中联结词的命题公式 [math]\displaystyle{ \phi }[/math] ，使得 [math]\displaystyle{ \phi }[/math] 所表达的真值函数与 [math]\displaystyle{ f }[/math] 相同，则称集合 [math]\displaystyle{ S }[/math] 是函数完备的(functionally complete)，或集合 [math]\displaystyle{ S }[/math] 具有函数完备性(functional completeness)，集合 [math]\displaystyle{ S }[/math] 是一个函数完备集(functionally complete set)。

也简称为完备，也有人译为功能完备。

性质

向函数完备集中添加新的逻辑联结词，得到的新集合也是函数完备的。
存在极小的函数完备集，即去掉其中任何一个联结词后就不再是函数完备的。不特殊说明时，函数完备集经常仅指这样最小的函数完备集。
若联结词集 [math]\displaystyle{ S }[/math] 函数完备，且 [math]\displaystyle{ S }[/math] 中所有联结词可用 [math]\displaystyle{ T }[/math] 中联结词表达，则 [math]\displaystyle{ T }[/math] 也是函数完备集。
不同函数完备集在表达能力上等价。

常见函数完备集

合取、析取、否定（基本逻辑联结词）
否定、合取
否定、析取
否定、蕴含
与非（Sheffer 竖）
或非（Peirce 箭头）

二元以内全部极小完备集

二元联结词及更少元数联结词中只能构成以下完备集^[1]。

单元素集： [math]\displaystyle{ \{\uparrow\} }[/math] 、 [math]\displaystyle{ \{\downarrow\} }[/math] 。
双元素集： [math]\displaystyle{ \{\lor,\lnot\} }[/math] 、 [math]\displaystyle{ \{\land,\lnot\} }[/math] 、 [math]\displaystyle{ \{\rightarrow,\lnot\} }[/math] 、 [math]\displaystyle{ \{\leftarrow,\lnot\} }[/math] 、 [math]\displaystyle{ \{\rightarrow,\bot\} }[/math] 、 [math]\displaystyle{ \{\leftarrow,\bot\} }[/math] 、 [math]\displaystyle{ \{\rightarrow,\nleftrightarrow\} }[/math] 、 [math]\displaystyle{ \{\leftarrow,\nleftrightarrow\} }[/math] 、 [math]\displaystyle{ \{\rightarrow,\nrightarrow\} }[/math] 、 [math]\displaystyle{ \{\rightarrow,\nleftarrow\} }[/math] 、 [math]\displaystyle{ \{\leftarrow,\nrightarrow\} }[/math] 、 [math]\displaystyle{ \{\leftarrow,\nleftarrow\} }[/math] 、 [math]\displaystyle{ \{\nrightarrow,\lnot\} }[/math] 、 [math]\displaystyle{ \{\nleftarrow,\lnot\} }[/math] 、 [math]\displaystyle{ \{\nrightarrow,\top\} }[/math] 、 [math]\displaystyle{ \{\nleftarrow,\top\} }[/math] 、 [math]\displaystyle{ \{\nrightarrow,\leftrightarrow\} }[/math] 、 [math]\displaystyle{ \{\nleftarrow,\leftrightarrow\} }[/math] 。
三元素集： [math]\displaystyle{ \{\lor,\leftrightarrow,\bot\} }[/math] 、 [math]\displaystyle{ \{\lor,\leftrightarrow,\nleftrightarrow\} }[/math] 、 [math]\displaystyle{ \{\lor,\nleftrightarrow,\top\} }[/math] 、 [math]\displaystyle{ \{\land,\leftrightarrow,\bot\} }[/math] 、 [math]\displaystyle{ \{\land,\leftrightarrow,\nleftrightarrow\} }[/math] 、 [math]\displaystyle{ \{\land,\nleftrightarrow,\top\} }[/math] 。

证明方法

以下方法均可证明一个联结词集合 [math]\displaystyle{ S }[/math] 是函数完备的。

通过具体构造展示 [math]\displaystyle{ S }[/math] 可以定义已知另一个函数完备集中的所有联结词。
分析 [math]\displaystyle{ S }[/math] 中联结词的真值表特性，证明它们能够表达所有可能的真值模式。
对真值函数的元数 [math]\displaystyle{ n }[/math] 进行归纳，证明对于任意 [math]\displaystyle{ n }[/math] ，集合 [math]\displaystyle{ S }[/math] 都能表达所有 [math]\displaystyle{ n }[/math] 元真值函数。

Post 格中的刻画

以下五个性质分别确定了任意元逻辑联结词的一个集合。

单调性联结词。任意个命题变元的真值从假变为真时，复合命题的真值不会从真变为假。如 [math]\displaystyle{ \lor,\land,\top,\bot }[/math] 。
仿射性联结词。每个命题变元独自改变时，无论其他命题变元的真值如何，或者总是改变复合命题的真值，或者总是不改变复合命题的真值。如 [math]\displaystyle{ \lnot,\top,\bot,\leftrightarrow,\nleftrightarrow }[/math] 。
自对偶联结词。是自身的对偶；无论每个命题变元的真值如何，将全部命题变元的真值改变时，复合命题的真值也改变。如 [math]\displaystyle{ \lnot }[/math] 。
保持真的联结词。若全部命题变元为真，则复合命题为真。如 [math]\displaystyle{ \lor,\land,\top,\rightarrow,\leftrightarrow }[/math] 。
保持假的联结词。若全部命题变元为假，则复合命题为假。如 [math]\displaystyle{ \lor,\land,\bot,\nrightarrow,\nleftrightarrow }[/math] 。

一个联结词集合具有函数完备性，当且仅当这个集合不是这五个集合中任意一个的子集。

命题逻辑/零阶逻辑
基本概念	命题	命题、命题变元、命题常量
基本概念	真值	真 [math]\displaystyle{ \mathrm{T} }[/math]/[math]\displaystyle{ 1 }[/math]/[math]\displaystyle{ \top }[/math] 、假 [math]\displaystyle{ \mathrm{F} }[/math]/[math]\displaystyle{ 0 }[/math]/[math]\displaystyle{ \bot }[/math]
命题结构	命题结构	原子命题、复合命题
	逻辑联结词	否定（非） [math]\displaystyle{ \lnot }[/math] 、合取（且/与） [math]\displaystyle{ \land }[/math] 、析取（或） [math]\displaystyle{ \lor }[/math]
	逻辑联结词	蕴含（推出） [math]\displaystyle{ \rightarrow }[/math] 、等价（当且仅当） [math]\displaystyle{ \leftrightarrow }[/math]
命题公式	语义	真值表、指派、解释、满足
	分类	重言式/永真式、偶然式/仅可满足式/可真可假式、矛盾式/永假式/不可满足式
	范式	析取范式、合取范式（主析取范式、主合取范式）
语义关系	等值	等值/等价 [math]\displaystyle{ = }[/math]/[math]\displaystyle{ \Leftrightarrow }[/math] 、置换
语义关系	重言蕴含	重言蕴含 [math]\displaystyle{ \Rightarrow }[/math]

逻辑联结词
零元
真值表			[math]\displaystyle{ \bot }[/math]								[math]\displaystyle{ \top }[/math]
真值表			T								F
名称			真 [math]\displaystyle{ \top }[/math]								假 [math]\displaystyle{ \bot }[/math]
二进制			0								1
一元
真值表	[math]\displaystyle{ p }[/math]		[math]\displaystyle{ \bot }[/math]				[math]\displaystyle{ \lnot p }[/math]				[math]\displaystyle{ p }[/math]				[math]\displaystyle{ \top }[/math]
	T		F								T
	F		F				T				F				T
名称			假 [math]\displaystyle{ \bot }[/math]				否定（非） [math]\displaystyle{ \lnot }[/math]				（恒等映射 [math]\displaystyle{ \mathrm{id} }[/math]）				真 [math]\displaystyle{ \top }[/math]
缩写			-				NOT				-				-
二进制			0				1				2				3
二元
真值表	[math]\displaystyle{ p }[/math]	[math]\displaystyle{ q }[/math]	[math]\displaystyle{ \bot }[/math]	[math]\displaystyle{ p \bar{\vee} q }[/math] [math]\displaystyle{ p \downarrow q }[/math]	[math]\displaystyle{ p \nleftarrow q }[/math]	[math]\displaystyle{ \lnot p }[/math]	[math]\displaystyle{ p \nrightarrow q }[/math]	[math]\displaystyle{ \lnot q }[/math]	[math]\displaystyle{ p \oplus q }[/math] [math]\displaystyle{ p \nleftrightarrow q }[/math]	[math]\displaystyle{ p \barwedge q }[/math] [math]\displaystyle{ p \uparrow q }[/math]	[math]\displaystyle{ p \land q }[/math]	[math]\displaystyle{ p \leftrightarrow q }[/math]	[math]\displaystyle{ q }[/math]	[math]\displaystyle{ p \rightarrow q }[/math]	[math]\displaystyle{ p }[/math]	[math]\displaystyle{ p \leftarrow q }[/math]	[math]\displaystyle{ p \lor q }[/math]	[math]\displaystyle{ \top }[/math]
	T	T	F								T
	T	F	F				T				F				T
	F	T	F		T		F		T		F		T		F		T
	F	F	F	T	F	T	F	T	F	T	F	T	F	T	F	T	F	T
名称			假 [math]\displaystyle{ \bot }[/math]	或非 [math]\displaystyle{ \downarrow }[/math]/[math]\displaystyle{ \bar{\vee} }[/math]	-	否定非 [math]\displaystyle{ \lnot }[/math]	-	否定非 [math]\displaystyle{ \lnot }[/math]	互斥析取异或 [math]\displaystyle{ \oplus }[/math]/[math]\displaystyle{ \nleftrightarrow }[/math]/[math]\displaystyle{ \veebar }[/math]	与非 [math]\displaystyle{ \uparrow }[/math]/[math]\displaystyle{ \barwedge }[/math]	合取且/与 [math]\displaystyle{ \land }[/math]	等价当且仅当 [math]\displaystyle{ \leftrightarrow }[/math]	投影映射 [math]\displaystyle{ \mathrm{proj}_2 }[/math]	蕴含推出 [math]\displaystyle{ \rightarrow }[/math]	投影映射 [math]\displaystyle{ \mathrm{proj}_1 }[/math]	-	析取或 [math]\displaystyle{ \lor }[/math]	真 [math]\displaystyle{ \top }[/math]
缩写			-	NOR	-	NOT	NIMPLY	NOT	XOR	NAND	AND	XNOR EQV	-	IMPLY	-	-	OR	-
二进制			0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

↑ https://en.wikipedia.org/wiki/Logical_connective#Redundancy

[1] ttps://en.wikipedia.org/wiki/Logical_connective#Redundancy

[1]