离散数学1.6其他联接词课件

1、1,离散数学(Discrete Mathematics),2,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.1 不可兼析取(排斥或/异或)(exclusive or) 1.6.2 与非联结词(Nand) 1.6.3 或非联结词(Nor) 1.6.4 条件否定联结词(Non-conditional) 1.6.5 最小联结词组(The minimal set of connectives),3,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),在第二节(1

2、.2)中我们定义了五种基本的联结词， ， ，,但在命题逻辑中,这些联结词还不能很广泛 地直接表达命题之间的联系(例如, “P异或Q”只能间接地 表示为(PQ)(PQ),为此本节再给出逻辑设计中 常用的另外四种联结词. 1.6.1 不可兼析取(排斥或/异或)(exclusive or) 定义1.6.1:设P,Q为二命题，复合命题“P,Q之中恰有一个为真” 称为P与Q的不可兼析取，记作P Q，符号“ ” 称为异或联结词. P Q 为真当且仅当P和Q的真值不同.,4,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),联结词“ ”的定义

3、真值表,定义了联结词“ ”后, 命题逻辑中的有些命题就可以符号化为非常简捷的形式. 例: 派小王或小李中的一人去开会。（排斥或） 设P：派小王去开会。Q：派小李去开会。 则上述命题可符号化为：(P Q),5,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明：“ ” 属于二元(binary)运算符. 联结词“ ”的性质: 设P, Q, R为命题公式, 则有 (1) P Q Q P (交换律) (2) (P Q) R P (Q R) (结合律) (3) P(Q R) (PQ ) (PR) (分配律) (4) (P Q) (P

4、Q) ( PQ) (5) (P Q) (PQ) (6) P P F, F P P, T P P,6,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),定理1.6.1:设P, Q, R为命题公式, 如果 P QR,则 P RQ ,Q RP, 且P Q R 为一矛盾式. 证: 由 P QR 得 P RP (P Q)(P P) QF QQ Q RQ (P Q)F PP P Q RR RF,7,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.2 与非联结词(Na

5、nd) 定义1.6.2 设P,Q为二命题，复合命题“P与Q的否定” 称为P与Q的与非式，记作PQ，符号“” 称为与非联结词. PQ 为真当且仅当P和Q不同时为真. 联结词“”的定义真值表,8,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明: (1) 由定义可知, PQ (PQ) (2)“” 属于二元(binary)运算符. 联结词“”的性质: (1) PP ( PP) P (2) (PQ)(PQ) ( PQ)(PQ) (3)(PP)(QQ) P Q(PQ) PQ,9,第一章 命题逻辑（Propositional Logi

6、c） 1.6其它联结词(Other Connectives),1.6.3 或非联结词(Nor) 定义1.6.3 设P,Q为二命题，复合命题“P或Q的否定” 称为P与Q的或非式，记作PQ ，符号“”称为或非联结词. PQ为真当且仅当 P与Q同为假. 联结词“”的定义真值表,10,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明: (1) 由定义可知, PQ (PQ) (2)“” 属于二元(binary)运算符. 联结词“”的性质: (1) PP ( PP) P (2) (PQ)(PQ) (PQ) (PQ) (3)(PP)(Q

7、Q)PQ(PQ)PQ,11,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),1.6.4 条件否定联结词(Non-conditional) 定义1.6.4 设P,Q为二命题，复合命题“P Q” 称为命题P与Q的条件否定式, P Q为真当且仅当P为真且Q为假. 联结词“ ”的定义真值表,12,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),说明: (1) 由定义可知, P Q (P Q) (2)“ ” 属于二元(binary)运算符. 有了联结词 后，合式公式的定

8、义1.3.2可加入这 四个联结词. 1.6.5 最小联结词组(The minimal set of connectives) 至此,我们一共定义了9个联结词,为了直接表达命题之间 的联系,是否还需要定义其它联结词呢? 回答是否定的.即 含n个命题变元的所有 个互不等价的命题公式,均可由这 9个联结词直接表达.下面我们以含两个命题变元P，Q的所 有互等价的命题公式为例，来说明这一问题。,13,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),由两个命题变元P，Q所构成的互不等价的 个命题公式 如下:,第一章 命题逻辑（Propos

9、itional Logic） 1.6其它联结词(Other Connectives),由上表可知, 9个联结词足以直接表达命题之间的各种联系.二元运算中，9个联结词并不都是必要的。,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),定义1.6.5：在一个联结词的集合中,如果一个联结词可 由该集合中的其它联结词定义,则称此联结词为冗余联 结词,否则称为独立联结词. 不含冗余联结词的联结词组 称为最小联结词组. 说明:最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。 对于9个联结词的集合, , , , 由于 (1)

10、 PQ (PQ)(QP) (2) PQPQ (3) PQ(PQ) (4) PQ(PQ),16,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),(5) (P Q) (PQ) (6) PQ (PQ) (7) PQ (PQ) (8) P Q (P Q) 故任意命题公式都可由仅包含,或, 的命题 公式等价代换.即9个联结词的集合中至少有七个冗余联 结词. 又注意到联结词,和, 不再有冗余联结 词, 故,或, 为最小联结词组.但实际中为了使 用方便, 命题公式常常同时包含, .,17,第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives),例1:试证是最小联结词组. 证：P(PP)PP PQ(PQ)(PQ)(PQ)(PQ) PQ(PQ)(PP)(QQ) (PP)(QQ) 例2.试证，是最小联结词组 证：PQ(PQ)(PQ) PQ(P)QPQ 小结:本节主要介绍了四种新的联结词 及最 小联结词组. 作业: 1. P29 (1), (2), (4),18,第一章 命题逻辑（Propositional Logic）