查看“︁函数完备性（逻辑联结词）”︁的源代码

[[分类:命题逻辑]]{{DEFAULTSORT:han2shu4wan2bei4xing4}}
{{#seo:
|keywords=函数完备集, 功能完备集, 完备集
|description=本文介绍逻辑联结词的完备集（也称函数完备集或功能完备集）的定义、性质与例子，包括函数完备集作为可以表达所有真值函数的逻辑联结词集合的概念，以及常见功能完备集。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2025-11-03
}}
{{InfoBox
|name=函数完备集
|eng_name=functionally complete set
|aliases=完备集,功能完备集,完备联结词集
}}
{{InfoBox
|name=函数完备
|eng_name=functionally complete
|aliases=完备,功能完备
}}
{{InfoBox
|name=函数完备性
|eng_name=functional completeness
|aliases=完备性,功能完备性
}}
'''函数完备'''('''functionally complete''')指一个[[逻辑联结词]]的[[集合]]，能够通过组合表达所有可能的[[真值函数]]。

== 定义 ==

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

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

== 性质 ==

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

== 常见函数完备集 ==

=== 常见函数完备集 ===
* [[合取]]、[[析取]]、[[否定]]（基本逻辑联结词）
* 否定、合取
* 否定、析取
* 否定、[[蕴含]]
* [[与非]]（Sheffer 竖）
* [[或非]]（Peirce 箭头）

=== 二元以内全部极小完备集 ===
* 单元素集： <math>\{\uparrow\}</math> 、 <math>\{\downarrow\}</math> 。
* 双元素集： <math>\{\lor,\lnot\}</math> 、 <math>\{\land,\lnot\}</math> 、 <math>\{\rightarrow,\lnot\}</math> 、 <math>\{\leftarrow,\lnot\}</math> 、 <math>\{\rightarrow,\bot\}</math> 、 <math>\{\leftarrow,\bot\}</math> 、 <math>\{\rightarrow,\nleftrightarrow\}</math> 、 <math>\{\leftarrow,\nleftrightarrow\}</math> 、 <math>\{\rightarrow,\nrightarrow\}</math> 、 <math>\{\rightarrow,\nleftarrow\}</math> 、 <math>\{\leftarrow,\nrightarrow\}</math> 、 <math>\{\leftarrow,\nleftarrow\}</math> 、 <math>\{\nrightarrow,\lnot\}</math> 、 <math>\{\nleftarrow,\lnot\}</math> 、 <math>\{\nrightarrow,\top\}</math> 、 <math>\{\nleftarrow,\top\}</math> 、 <math>\{\nrightarrow,\leftrightarrow\}</math> 、 <math>\{\nleftarrow,\leftrightarrow\}</math> 。
* 三元素集： <math>\{\lor,\leftrightarrow,\bot\}</math> 、 <math>\{\lor,\leftrightarrow,\nleftrightarrow\}</math> 、 <math>\{\lor,\nleftrightarrow,\top\}</math> 、 <math>\{\land,\leftrightarrow,\bot\}</math> 、 <math>\{\land,\leftrightarrow,\nleftrightarrow\}</math> 、 <math>\{\land,\nleftrightarrow,\top\}</math> 。

== 证明方法 ==

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

=== Post 格中的刻画 ===

以下五个性质分别确定了任意元逻辑联结词的一个集合。
* 单调性联结词。任意个命题变元的真值从假变为真时，复合命题的真值不会从真变为假。如 <math>\lor,\land,\top,\bot</math> 。
* 仿射性联结词。每个命题变元独自改变时，无论其他命题变元的真值如何，或者总是改变复合命题的真值，或者总是不改变复合命题的真值。如 <math>\lnot,\top,\bot,\leftrightarrow,\nleftrightarrow</math> 。
* 自对偶联结词。是自身的[[对偶（命题逻辑）|对偶]]；无论每个命题变元的真值如何，将全部命题变元的真值改变时，复合命题的真值也改变。如 <math>\lnot</math> 。
* 保持真的联结词。若全部命题变元为真，则复合命题为真。如 <math>\lor,\land,\top,\rightarrow,\leftrightarrow</math> 。
* 保持假的联结词。若全部命题变元为假，则复合命题为假。如 <math>\lor,\land,\bot,\nrightarrow,\nleftrightarrow</math> 。

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


{{命题逻辑}}
{{逻辑联结词}}