离散数学(第1.4)陈瑜

陈瑜Email：chenyu.inbox@g2/2/2023离散数学计算机学院2/2/20231计算机科学与工程学院主要内容掌握3个新的联结词掌握：功能完备集、最小功能完备集等概念2/2/20232计算机科学与工程学院§1.4联结词的完备集前面我们已经介绍了最常见的6种逻辑联结词。他们都和自然语言中使用的关联词紧密相关，易于理解。不同联结词产生的真值表是互不相同的。根据对含两个命题变元的公式的解释方式看，共有2*2=4种不同的选择性，因而公式的真值表相应有24=16种可能结果。对其中每一种真值表都应该存在相应的联结词。下面从真值表取值情况的角度定义几个新的联结词。2/2/20233计算机科学与工程学院§1.4联结词的完备集定义1-4.1：设P和Q是命题公式，分别称P↑Q和P↓Q为“与非”和“或非”命题公式。其相应的真值表如下所示：

PQP↑Q1101010110012/2/20234计算机科学与工程学院§1.4联结词的完备集定义1-4.1：设P和Q是命题公式，分别称P↑Q和P↓Q为“与非”和“或非”命题公式。其相应的真值表如下所示：

PQP↓Q1101000100012/2/20235计算机科学与工程学院§1.4联结词的完备集定义1-4.1：设P和Q是命题公式，分别称P↑Q和P↓Q为“与非”和“或非”命题公式。其相应的真值表如下所示：

PQP↓Q110100010001由真值表可以看出:

P↑Q～（P∧Q）;

P↓Q～（P∨Q）

PQP↑Q1101010110012/2/20236计算机科学与工程学院§1.4联结词的完备集根据联结词↑和↓的定义，不难证明下面的等价式:①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q～（～P∧～Q）

P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q～（～P∨～Q）

P∧Q2/2/20237计算机科学与工程学院§1.4联结词的完备集根据联结词↑和↓的定义，不难证明下面的等价式:①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q～（～P∧～Q）

P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q～（～P∨～Q）

P∧Q这些等价式告诉我们，↑可由∧和～表示出来，↓可由∨和～表示出来，反过来，↑和↓都可以单独表示出所有已知联结词，他们的这一性能使得在逻辑电路设计中只用一种门式电路元件就能实现任何电路功能，当然，元件的数量通常也显得更多。

2/2/20238计算机科学与工程学院§1.4联结词的完备集条件否定:

二元联结词“c”,称为条件否定联结词，可以用下面的真值表定义：

PQPcQ000010101110显然，“c”是条件联结词“→”的否定形式，即：PcQ～(P→Q)2/2/20239计算机科学与工程学院§1.4联结词的完备集至此我们定义了9个联结词，其中1个一元联结词，8个二元联结词。那么，还能不能定义出新的联结词呢？让我们来看看含两个命题变元的所有公式所能取得的情况。2/2/202310计算机科学与工程学院§1.4联结词的完备集PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000包含2个命题变元的所有公式可能的取值情况：永真式矛盾式2/2/202311计算机科学与工程学院§1.4联结词的完备集PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000包含2个命题变元的所有公式可能的取值情况：永真式矛盾式……P∧Q2/2/202312计算机科学与工程学院§1.4联结词的完备集PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000包含2个命题变元的所有公式可能的取值情况：永真式矛盾式……P∧Q可见，已定义的9个联结词就是全部可以定义的联结词。

2/2/202313计算机科学与工程学院§1.4联结词的完备集这9个联结词之间还有着内在的联系。例如:→可用～和∨表达，可用～,∨和∧表示,可用～、∨和∧表达,↑可用∧和～表达,↓可用～和∨表达,c可用～和∧表达。这就是说，全部9个联结词都可以用～，∨和∧这三个联结词表达出来，即{～，∨，∧}构成了逻辑联结词的一个功能完备集。此外，根据↑和↓满足的恒等式来看,↑或↓都能单独表达～,∨和∧,从而{↑}和{↓}也是功能完备集。2/2/202314计算机科学与工程学院§1.4联结词的完备集定义1-4.2设S是由某些联结词构成的集合，如果每个逻辑联结词的功能都能够由S中的联结词实现，则称S是联结词的一个功能完备集；进一步，如果去掉S中的任何一个联结词后，至少有一个联结词的功能不能由S中剩余的联结词实现时，则称S是逻辑联结词的一个最小功能完备集。少一个也不成2/2/202315计算机科学与工程学院§1.4联结词的完备集根据定义,我们知道{↑}、{↓}是最小的功能完备集。那么{～，∨，∧}是不是最小功能完备集？由于P∨Q～(～P∧～Q)，可见∨可由{～，∧}表达；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表达，这说明{～，∨，∧}不是最小功能完备集。对于{～，∨}和{～，∧}，是否还可以去掉其中的联结词？答案是否定的。因为根据“～”的功能,其真值表含2个1和2个0，∨对应的真值表含3个1和1个0，∧对应的真值表含1个1和3个0。所以，既不能代替∧也不能代替∨，同样∧和∨都不能代替～。因此，{～，∧}和{～，∨}都是最小功能完备集。2/2/202316计算机科学与工程学院§1.4联结词的完备集根据定义,我们知道{↑}、{↓}是最小的功能完备集。那么{～，∨，∧}是不是最小功能完备集？由于P∨Q～(～P∧～Q)，可见∨可由{～，∧}表达；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表达，这说明{～，∨，∧}不是最小功能完备集。对于{～，∨}和{～，∧}，是否还可以去掉其中的联结词？答案是否定的。因为根据“～”的功能,其真值表含2个1和2个0，∨对应的真值表含3个1和1个0，∧对应的真值表含1个1和3个0。所以，既不能代替∧也不能代替∨，同样∧和∨都不能代替～。因此，{～，∧}和{～，∨}都是最小功能完备集。

2/2/202317计算机科学与工程学院§1.4联结词的完备集根据定义,我们知道{↑}、{↓}是最小的功能完备集。那么{～，∨，∧}是不是最小功能完备集？由于P∨Q～(～P∧～Q)，可见∨可由{～，∧}表达；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表达，这说明{～，∨，∧}不是最小功能完备集。对于{～，∨}和{～，∧}，是否还可以去掉其中的联结词？

答案是否定的。因为根据“～”的功能,其真值表含2个1和2个0，∨对应的真值表含3个1和1个0，∧对应的真值表含1个1和3个0。所以，既不能代替∧也不能代替∨，同样∧和∨都不能代替～。因此，{～，∧}和{～，∨}都是最小功能完备集。2/2/202318计算机科学与工程学院§1