16.3 联结词的完备集
本章目录 · 1 节
本章导读
【16.3 联结词的完备集】本节讨论能否仅用指定联结词表达所有真值函数,而不是讨论某几个公式写起来是否方便。
【定义16.3.1】n元真值函数是F:{0,1}ⁿ→{0,1},n≥1。定义域有2ⁿ个输入,陪域为{0,1};实际像可以只有{0}或{1},所以原文“值域为{0,1}”应理解为陪域,不能排除常值函数。全部n元函数有 个。
表中按pq=00,01,10,11将输出当成四位二进制数,由0000到1111编号。例如F₀恒0,F₁=p∧q,F₂=p∧¬q,F₃=p,F₇=p∨q,F₈=¬p∧¬q,F₁₄=¬(p∧q),F₁₅恒1。一元同理,F₀恒0、F₁=p、F₂=¬p、F₃恒1;三元共有256个函数。一个函数有唯一规范主范式,却有无穷多个等值的语法公式。
【定义16.3.2】联结词集S若能用仅含S中联结词和命题变项的公式表达任意n≥1元真值函数,称函数完备集。不额外免费提供0、1常量;若允许额外常量,须另行说明,因为会改变某些完备性结论。
【定理16.3.1及推论16.3.1】{¬,∧,∨}完备,由主DNF存在定理得到。包含它的{¬,∧,∨,→}、{¬,∧,∨,→,↔}也完备。以下更小集合仍完备:
(1){¬,∧},因为p∨q⇔¬(¬p∧¬q)。
(2){¬,∨},因为p∧q⇔¬(¬p∨¬q)。
(3){¬,→},因为p∨q⇔¬p→q,p∧q⇔¬(p→¬q)。
仅用∧、∨、→、↔而没有否定、没有额外常量0时不完备:所有这些运算都保持全1输入为1,由结构归纳,所有构造公式也保持1,不能表达恒0函数。因此它们的任意子集均不完备。若添加0,则p→0可以表达¬p,不能再沿用上述同一论证。
【定义16.3.3 与非及或非】p↑q⇔¬(p∧q),称NAND或与非;p↓q⇔¬(p∨q),称NOR或或非。↑仅同真时为0,↓仅同假时为1。箭头向上、向下不是蕴涵箭头。
【定理16.3.2】{↑}单独完备,因为
同理{↓}单独完备,因为
先表达¬、∧、∨,再逐层替换任意公式中的联结词,便能生成全部函数。NAND、NOR虽交换但不结合,构造中括号必须保留;“一个联结词足够”不代表只能用一次门。
