(1.2.6)--ch1-第四讲离散数学离散数学.pdf
Discrete MathematicsDiscrete Mathematics 离散数学离散数学 1-6 其它联结词其它联结词(Other Connectives)1.不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)定义定义1-6.1 设设P,Q 为两个命题为两个命题,复合命题复合命题 PQ 称为称为P与与Q的的不可兼析取不可兼析取.PQ 的真值为的真值为T,当且仅当当且仅当P 与与Q 的取值不相同时的取值不相同时.称为称为异或异或联结词联结词.符号符号 第第一一章章 命命题题逻逻辑辑 P Q 0 0 1 1 0 1 0 1 0 1 1 0 PQ 相同为假相同为假,相异为真相异为真.(P Q)(PQ)1.不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)第第一一章章 命命题题逻逻辑辑 设设 P:派小王去开会派小王去开会;可以符号化为非常简捷的形式可以符号化为非常简捷的形式.例例:派小王或小李中的一人去开会派小王或小李中的一人去开会.(排斥或排斥或)则上述命题可符号化为则上述命题可符号化为:Q:派小李去开会派小李去开会.PQ 定义了联结词定义了联结词“”后后,命题逻辑中的有些命题就命题逻辑中的有些命题就 说明说明:“”属于二元属于二元(binary)运算符运算符.1.不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)第第一一章章 命命题题逻逻辑辑 联结词联结词“”的性质的性质:设设P,Q,R为命题公式为命题公式,则有则有(1)P Q Q P (交换律交换律)(2)(P Q)R P (Q R)(结合律结合律)(3)P(Q R)(PQ)(PR)(分配律分配律)(4)(P Q)(PQ)(PQ)(5)(P Q)(PQ)(6)P P F,F P P,T P P 第第一一章章 命命题题逻逻辑辑 设设P,Q,R为命题公式为命题公式.如果如果 定理定理1-6.1 P QR,则则 P RQ,Q RP,且且P Q R 为一矛盾式为一矛盾式.证证:由由 P QR 得得 P R P (P Q)(P P)Q F Q Q Q R Q (P Q)(Q Q)P F P P P Q R R R F 1.不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)第第一一章章 命命题题逻逻辑辑 2.条件否定联结词条件否定联结词(Non-conditional)定义定义1-6.2 设设P,Q为两个公式为两个公式,复合命题复合命题 c P Q 称为命题称为命题P与与Q的的条件否定式条件否定式.c P Q 的真值为的真值为T,当且仅当当且仅当P为真且为真且Q为假为假.第第一一章章 命命题题逻逻辑辑 P Q 0 0 1 1 0 1 0 1 0 0 1 0 前真后假为真前真后假为真,其余为假其余为假.c P Q (P Q)c P Q 2.条件否定联结词条件否定联结词(Non-conditional)第第一一章章 命命题题逻逻辑辑 3.与非联结词与非联结词(Nand)定义定义1-6.3 设设 P,Q 为两个命题为两个命题,复合命题复合命题 P Q 称为称为 命题命题 P与与Q 的的与非式与非式.PQ 为真当且仅当为真当且仅当P 和和 Q不同时为真不同时为真.符号“符号“”称为称为与非与非联结词联结词.第第一一章章 命命题题逻逻辑辑 P Q PQ 0 0 1 1 0 1 0 1 1 1 1 0 全真为假全真为假,见假为真见假为真.PQ (PQ)3.与非联结词与非联结词(Nand)第第一一章章 命命题题逻逻辑辑 联结词“联结词“”的性质”的性质:(1)PP (PP)P(2)(PQ)(PQ)(PQ)(PQ)(3)(PP)(QQ)P Q (P Q)P Q 第第一一章章 命命题题逻逻辑辑 4.或非联结词或非联结词(Nor)定义定义1-6.4.设设 P,Q为两个命题为两个命题,复合命题复合命题 PQ 称作称作 命题命题 P 与与Q 的的或非式或非式.PQ 为真当且仅当为真当且仅当 P 和和 Q 同为假同为假.符号“符号“”称为”称为或非或非联结词联结词.第第一一章章 命命题题逻逻辑辑 P Q PQ 0 0 1 1 0 1 0 1 1 0 0 0 全假为真全假为真,见真为假见真为假.PQ (PQ)4.或非联结词或非联结词(Nor)第第一一章章 命命题题逻逻辑辑 联结词“联结词“”的性质”的性质:(1)PP (PP)P(2)(PQ)(PQ)(PQ)(PQ)(3)(PP)(QQ)P QPQ 说明说明:有了联结词有了联结词 后后,合式公式的定义合式公式的定义1.3.1,c 可加入这四个联结词可加入这四个联结词.第第一一章章 命命题题逻逻辑辑 最小联结词组最小联结词组(The minimal set of connectives)至此至此,我们一共定义了我们一共定义了9个联结词个联结词,为了直接表达为了直接表达命题之间的联系命题之间的联系,是否还需要定义其它联结词呢是否还需要定义其它联结词呢?回回答是否定的答是否定的.即含即含n个命题变元的所有个命题变元的所有22n个互不等价个互不等价的命题公式的命题公式,均可由这均可由这 9个联结词直接表达个联结词直接表达.下面我们下面我们以含两个命题变元以含两个命题变元 P,Q 的所构成的互不等价的所构成的互不等价24个命个命题公式为例题公式为例,来说明这一问题来说明这一问题.第第一一章章 命命题题逻逻辑辑 最小联结词组最小联结词组(The minimal set of connectives)P Q F PQ P Q PQ 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 c P Q c Q P PQ 第第一一章章 命命题题逻逻辑辑 P Q T PQ PQ P QP Q PQ PQ 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 由上表知由上表知,9个联结词足以直接表达命题之间的各种联系个联结词足以直接表达命题之间的各种联系.最小联结词组最小联结词组(The minimal set of connectives)第第一一章章 命命题题逻逻辑辑 定义定义(补补):在一个联结词的集合中在一个联结词的集合中,如果一个联结词如果一个联结词可由该集合中的其它联结词定义可由该集合中的其它联结词定义,则称此联结词为则称此联结词为冗余联冗余联结词结词,否则称为否则称为独立联结词独立联结词.不含冗余联结词的联结词组不含冗余联结词的联结词组称为称为最小联结词组最小联结词组.说明说明:最小联结词组中的联结词构成的式子足以把最小联结词组中的联结词构成的式子足以把 一切命题公式等价的表达出来一切命题公式等价的表达出来.最小联结词组最小联结词组(The minimal set of connectives)第第一一章章 命命题题逻逻辑辑 第第一一章章 命命题题逻逻辑辑 对于对于9个联结词的集合个联结词的集合,c 由于由于(1)PQ(PQ)(QP)(2)PQ PQ (3)PQ (P Q)(4)PQ (P Q)(5)(P Q)(P Q)(PQ)(P Q)c P Q P Q (8)(7)PQ (PQ)(6)PQ (PQ)第第一一章章 命命题题逻逻辑辑 故任意命题公式都可由仅包含故任意命题公式都可由仅包含,或或,的命的命 题公式等价代换题公式等价代换.即即9个联结词的集合中至少有七个冗个联结词的集合中至少有七个冗 余联结词余联结词.又注意到联结词又注意到联结词,和和,不再有冗余不再有冗余 联结词联结词,故故,或或,为最小联结词组为最小联结词组.但实际中为了使用方便但实际中为了使用方便,命题公式常常同时包含命题公式常常同时包含,.第第一一章章 命命题题逻逻辑辑 例例1:试证试证是最小联结词组是最小联结词组.证证:P (P P)PP P Q (PQ)(PQ)(PQ)P Q (P Q)(PP)(QQ)(P P)(Q Q)第第一一章章 命命题题逻逻辑辑 例例2.试证试证 ,是最小联结词组是最小联结词组 证证:P Q (P Q)(P Q)P Q (P)Q PQ
