离散数学(第1.4)陈瑜

1、2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院1 1陈瑜陈瑜Email：2022-4-292022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院2 2主要内容主要内容n 掌握掌握3 3个新的联结词个新的联结词n 掌握：功能完备集、最小功能完备集等概念掌握：功能完备集、最小功能完备集等概念2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院3 31.4 1.4 联结词的完备集联结词的完备集n 前面我们已经介绍了最常见的前面我们已经介绍了最常见的6 6种逻辑联结词。种逻辑联结词。他们都和自然语言中使用的关联词紧密相关，他们

2、都和自然语言中使用的关联词紧密相关，易于理解。易于理解。n 不同联结词产生的真值表是互不相同的。不同联结词产生的真值表是互不相同的。根据根据对含两个命题变元的公式的解释方式看，共有对含两个命题变元的公式的解释方式看，共有2 2* *2=42=4种不同的选择性，因而公式的真值表相应种不同的选择性，因而公式的真值表相应有有2 24 4=16=16种可能结果种可能结果。对其中每一种真值表都应。对其中每一种真值表都应该存在相应的联结词。该存在相应的联结词。n 下面从真值表取值情况的角度定义几个新的联下面从真值表取值情况的角度定义几个新的联结词。结词。 2022-4-292022-4-29计算机科学与工

3、程学院计算机科学与工程学院4 41.4 1.4 联结词的完备集联结词的完备集n 定义定义 1-4.1：设设P P和和Q Q是命题公式，分别称是命题公式，分别称PQPQ和和PQPQ为为“与非与非”和和“或非或非”命题公式。命题公式。其其相应的真值表如下所示：相应的真值表如下所示： P Q PQ 1 1 0 1 0 1 0 1 1 0 0 12022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院5 51.4 1.4 联结词的完备集联结词的完备集n 定义定义 1-4.1：设设P P和和Q Q是命题公式，分别称是命题公式，分别称PQPQ和和PQPQ为为“与非与非”和和“或非或非”

4、命题公式。命题公式。其其相应的真值表如下所示：相应的真值表如下所示： P Q PQ 1 1 0 1 0 0 0 1 0 0 0 12022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院6 61.4 1.4 联结词的完备集联结词的完备集n 定义定义 1-4.1：设设P P和和Q Q是命题公式，分别称是命题公式，分别称PQPQ和和PQPQ为为“与非与非”和和“或非或非”命题公式。命题公式。其其相应的真值表如下所示：相应的真值表如下所示： P Q PQ 1 1 0 1 0 0 0 1 0 0 0 1由真值表可以看出由真值表可以看出: : PQ （PQ）; ; PQ （PQ） P

5、 Q PQ 1 1 0 1 0 1 0 1 1 0 0 12022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院7 71.4 1.4 联结词的完备集联结词的完备集 根据联结词根据联结词和和的定义，不难证明下面的等的定义，不难证明下面的等价式价式: PP（PP）P ( PQ)( PQ) ( PQ) PQ ( PP)(QQ) PQ（PQ） PQ PP（PP）P ( PQ) ( PQ) ( PQ) PQ ( PP) (QQ) PQ（PQ） PQ2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院8 81.4 1.4 联结词的完备集联结词的完备集 根据联结

6、词根据联结词和和的定义，不难证明下面的等的定义，不难证明下面的等价式价式: PP（PP）P ( PQ)( PQ) ( PQ) PQ ( PP)(QQ) PQ（PQ） PQ PP（PP）P ( PQ) ( PQ) ( PQ) PQ ( PP) (QQ) PQ（PQ） PQ 这些等价式告诉我们，这些等价式告诉我们，可由可由和表示和表示出来，出来，可由可由和表示出来，反过来，和表示出来，反过来，和和都可以单独表示出所有已知联结词，他们的都可以单独表示出所有已知联结词，他们的这一性能使得在逻辑电路设计中只用一种门式这一性能使得在逻辑电路设计中只用一种门式电路元件就能实现任何电路功能，当然，元件电路元件

7、就能实现任何电路功能，当然，元件的数量通常也显得更多。的数量通常也显得更多。 2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院9 91.4 1.4 联结词的完备集联结词的完备集 条件否定条件否定: : 二元联结词二元联结词“ “ c c ”, ”,称为称为条件否定条件否定联结词联结词，可以用下面的真值表定义：可以用下面的真值表定义： P Q P c Q 0 0 0 0 1 0 1 0 1 1 1 0显然，显然， “ “ c ” c ” 是条件联结词是条件联结词“”的的否定形式，否定形式，即：即：P c QP c Q(PQ) (PQ) 2022-4-292022-4-

8、29计算机科学与工程学院计算机科学与工程学院10101.4 1.4 联结词的完备集联结词的完备集 至此我们定义了至此我们定义了9 9个联结词，其中个联结词，其中1 1个一元联结词，个一元联结词，8 8个二元联结词。那么，还能不能定义出新的联结词呢？个二元联结词。那么，还能不能定义出新的联结词呢？ 让我们来看看含两个命题变元的所有公式所能取得的让我们来看看含两个命题变元的所有公式所能取得的情况。情况。2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院11111.4 1.4 联结词的完备集联结词的完备集P QP Q1 2 3 4 5 6 7 8 9 10 11 12 13

9、 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 11 11 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 01 0 0

10、1 1 1 0 0 1 0 1 1 1 0 0 0包含包含2 2个命题变元的所有公式可能的取值情况：个命题变元的所有公式可能的取值情况：永永真真式式矛矛盾盾式式2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院12121.4 1.4 联结词的完备集联结词的完备集P QP Q1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 11 11 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 1 0 1

11、 1 1 0 0 0 0 0 0 11 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0包含包含2 2个命题变元的所有公式可能的取值情况：个命题变元的所有公式可能的取值情况：永永真真式式矛矛盾盾式式PQ2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院1

12、3131.4 1.4 联结词的完备集联结词的完备集P QP Q1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 11 11 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 1 0 1 1 1 0 0 0 0 0 0 11 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 1 0 1 1 0 0 1 1 0 0 0 1 01 0 1 0 1 1 0 1 0 1 0 1 0 1 0 01 0 1 0

13、1 1 0 1 0 1 0 1 0 1 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 01 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0包含包含2 2个命题变元的所有公式可能的取值情况：个命题变元的所有公式可能的取值情况：永永真真式式矛矛盾盾式式PQ可见，已定义的可见，已定义的9个联结词就是全部可以定义的联个联结词就是全部可以定义的联结词。结词。 2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院14141.4 1.4 联结词的完备集联结词的完备集 这这9 9个联结词之间还有着内在的联系。个联结词之间还有着内在的联系。 例如例如: :

14、 可用和可用和表达，表达，可用可用, , 和和表示表示, , 可用、可用、和和表达表达,可用可用和表达和表达, , 可用可用和和表达表达, c , c 可用和可用和表达。表达。 这就是说，这就是说，全部全部9 9个联结词都可以用，个联结词都可以用，和和这三这三个联结词表达出来，即个联结词表达出来，即 ，构成了逻辑联结构成了逻辑联结词的一个功能完备集。词的一个功能完备集。 此外，此外，根据根据和和满足的恒等式来看满足的恒等式来看, , 或或都能单都能单独表达独表达,和和,从而从而和和 也是功能完备集。也是功能完备集。2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院15

15、151.4 1.4 联结词的完备集联结词的完备集 定义定义 1-4.21-4.2 设设S S 是由某些联结词构成的集合，是由某些联结词构成的集合，如果每个逻辑联结词的功能都能够由如果每个逻辑联结词的功能都能够由S S中的联中的联结词实现，则称结词实现，则称S S是联结词的一个是联结词的一个功能完备集功能完备集； 进一步，如果去掉进一步，如果去掉S S中的任何一个联结词中的任何一个联结词后，至少有一个联结词的功能不能由后，至少有一个联结词的功能不能由S S中剩余中剩余的联结词实现时，则称的联结词实现时，则称S S是逻辑联结词的一个是逻辑联结词的一个最小功能完备集最小功能完备集。少一个也不少一个也

16、不成成2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院16161.4 1.4 联结词的完备集联结词的完备集n 根据定义根据定义, ,我们知道我们知道、是最小的功能完备集。是最小的功能完备集。n 那么那么 ， 是不是最小功能完备集？是不是最小功能完备集？ 由于由于PQPQ( (PPQ)Q)，可见，可见可由可由 ， 表表达；达； 同理同理, PQ, PQ( (PPQ) ,Q) ,因而因而可由可由 ， 表达，这说明表达，这说明 ， 不是最小功能完备集。不是最小功能完备集。n 对于对于 ， 和和 ， ，是否还可以去掉其中的联，是否还可以去掉其中的联结词？结词？ 答案是否定的

17、。因为根据答案是否定的。因为根据“”的功能的功能, ,其真值表其真值表含含2 2个个1 1和和2 2个个0 0 ， 对应的真值表含对应的真值表含3 3个个1 1和和1 1个个0 0，对应的真值表含对应的真值表含1 1个个1 1和和3 3个个0 0。所以，。所以， 既不能代替既不能代替也也不能代替不能代替，同样，同样和和都不能代替。因此，都不能代替。因此， ， 和和 ， 都是最小功能完备集。都是最小功能完备集。 2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院17171.4 1.4 联结词的完备集联结词的完备集n 根据定义根据定义, ,我们知道我们知道、是最小的功能完

18、备集。是最小的功能完备集。n 那么那么 ， 是不是最小功能完备集？是不是最小功能完备集？ 由于由于PQPQ( (PPQ)Q)，可见，可见可由可由 ， 表表达；达； 同理同理, PQ, PQ( (PPQ) ,Q) ,因而因而可由可由 ， 表达，这说明表达，这说明 ， 不是最小功能完备集。不是最小功能完备集。n 对于对于 ， 和和 ， ，是否还可以去掉其中的联，是否还可以去掉其中的联结词？结词？ 答案是否定的。因为根据答案是否定的。因为根据“”的功能的功能, ,其真值表其真值表含含2 2个个1 1和和2 2个个0 0 ， 对应的真值表含对应的真值表含3 3个个1 1和和1 1个个0 0，对应的真值

19、表含对应的真值表含1 1个个1 1和和3 3个个0 0。所以，。所以， 既不能代替既不能代替也也不能代替不能代替，同样，同样和和都不能代替。因此，都不能代替。因此， ， 和和 ， 都是最小功能完备集。都是最小功能完备集。 2022-4-292022-4-29计算机科学与工程学院计算机科学与工程学院18181.4 1.4 联结词的完备集联结词的完备集n 根据定义根据定义, ,我们知道我们知道、是最小的功能完备集。是最小的功能完备集。n 那么那么 ， 是不是最小功能完备集？是不是最小功能完备集？ 由于由于PQPQ( (PPQ)Q)，可见，可见可由可由 ， 表表达；达； 同理同理, PQ, PQ( (PPQ) ,Q) ,因而因而可由可由 ， 表达，这说明表达，这说明 ， 不是最小功能完备集。不是最小功能完备集。n 对于对于 ， 和和 ， ，是否还可以去掉其中的联，是否还可以去掉其中的联结