离散数学(命题逻辑)精讲课件.ppt

1、理学院理学院离散数学离散数学1.1 命题符号化及联结词1.2 命题公式及分类1.3 等值演算1.4 对偶与范式1.5 推理理论2一、命题与真值二、命题分类：原子命题，复合命题三、命题常项与命题变项及其符号化四、联结词 3命题:具有唯一确定真假意义的陈述句命题的真值:判断的结果真值的取值:真或假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中判断结果不惟一确定的也不是命题 4.5真命题真命题假命题假命题疑问句疑问句感叹句感叹句祈使句祈使句不是命题不是命题（1）2是素数是素数.（2）雪是黑色的）雪是黑色的.（3）2+3=5.（4）现在是六点钟）现在是六点钟

2、.（5）3能被能被2整除整除.（6）这朵花多好看呀）这朵花多好看呀!（7）明天下午有会吗）明天下午有会吗?（8）请关上门）请关上门!（9）x+y5.（10）地球外的星球上也有人）地球外的星球上也有人.真命题真命题假命题假命题在数理逻辑中，不需要纠结在各种具体命题的真假问题，而是将命题当成在数理逻辑中，不需要纠结在各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句。陈述句。简单命题（原子命题）：命题不能分成更简单的句子的命题，又称为命题常项（命题常元）。2是素数.雪是黑色

3、的.2+3=5.明年十月一日是晴天.3能被2整除.6复合命题：由简单命题用联结词联结而成的命题。3不是偶数;2是素数和偶数;林芳学过英语或日语;如果角A和角B是对顶角，则角A等于角B71.命题变项（命题变元、命题函数）：真值可以变化的陈述句。如：x+y5.命题变项不是命题。2.命题常项（命题常元）：真值唯一确定的陈述句。如：2是偶数.命题常项是命题。8简单命题符号化：p:2是素数;-命题常项q:雪是白的;-命题常项命题变项符号化：p:x+y5;-命题变项（不是命题）命题的真值表示：1(T)表示真;0(F)表示假.91.否定式与否定联结词“”定义1 设p为命题，复合命题“非p”（或“p的否定”）

4、称 为p的否定式，记作p.符号称作否定联结词 p 为真当且仅当p为假.例 p：3是偶数。p：3不是偶数102.合取式与合取联结词“”定义2 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq.称作合取联结词pq为真当且仅当p与q同时为真合取联结词是逻辑“与”的意思。11 例 将下列命题符号化.（1）李平既聪明又用功（2）李平虽然聪明,但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功（5）李文和李武是兄弟解：令 p：李平用功，q：李平聪明，则（1）p q （2）p q（3）p q （4）（(p)q）（5）r:李文和李武是兄弟分清简单命题与复合命

5、题不能见到“和”、“与”就用“”描述合取式的灵活性与多样性 12 定义3 设 p,q为命题，复合命题“p或q”称作p与q 的析取式，记作pq.称作析取联结词 pq为假当且仅当p与q同时为假.133.3.析取式与析取联结词析取式与析取联结词“”14例例 将下列命题符号化将下列命题符号化 (1)2或或4是素数是素数.(2)2或或3是素数是素数.(3)4或或6是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.解 令 p:2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3)均为相容或.分别符号化为:pr,pq,rs,它们的真值分别为 1,1,0.而(

6、4)为排斥或.(4)令 t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为 (tu)(tu).15 定义4 设 p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，pq为假当且仅当 p 为真 q 为假.164.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”pq 的逻辑关系：q 为 p 的必要条件“如果 p，则 q”的不同表述法很多：若 p，就 q 只要 p，就 q 只有 q,才 p 除非 q，才 p 除非 q，否则非 p17自然语言中p与q具有联系，而数理逻辑中p与q可以没有联系。例如果如果3 33 36 6，则雪是黑

7、的。，则雪是黑的。如果如果3+33+3 6 6，则雪是黑的。，则雪是黑的。18例 设 p:天冷，q:小王穿羽绒服，将下列命题符号化 (1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(7)如果天不冷，则小王不穿羽绒服.19注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpqpqqp qpqp定义5 设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.pq为真当且仅当p与q同时为真或同时为假.说明:(1)pq 的逻辑关系:p与q互

8、为充分必要条件 205.等价式与等价联结词等价式与等价联结词“”例 将下列复合命题符号化并求其真值 （1）2+2=4当且仅当3是奇数:pq 1（2）2+24当且仅当3是奇数:p q 0（3）2+2=4当且仅当3不是奇数:p q 0（4）2+24当且仅当3不是奇数:p q 121小王是游泳冠军或百米赛跑冠军:小王现在在宿舍或在图书馆:(p q)(p q)或 p q选小王或小李中的一人当班长:(p q)(p q)如果我上街，我就去书店看看，除非我很累:r(p q)王一乐是计算机系的学生，他生于1968年或1969年，他是三好学生:p(q r)s22p q我们所学的5种基本联结词也称为逻辑运算符，其

9、运算顺序为：23，v如果出现的如果出现的基本联结词基本联结词相同，又相同，又无括号无括号时，则按时，则按从左到右从左到右的的运算顺序运算顺序；v如果遇有如果遇有括号括号时，不管出现的时，不管出现的基本联结基本联结词词如何，都先进行如何，都先进行括号中括号中的的运算运算。p p T F F T p q pq T T T T F F F T F F F F p q p q T T T T F T F T T F F F p q p q T T T T F F F T T F F T24 p q p q T T T T F F F T F F F T1.1 命题符号化及联结词1.2 命题公式及分类1

10、.3 等值演算1.4 对偶与范式1.5 推理理论25一、命题（合式）公式二、公式的赋值三、真值表四、命题的分类：重言式 矛盾式 可满足式26递归定义：（1 1）单个命题常项或变项）单个命题常项或变项p,q,r,.,pi,qi,ri,.,0,1是是合合式公式式公式；（2 2）如果）如果是合式公式，则是合式公式，则是是合式公式合式公式；（3 3）如果）如果,B是合式公式，则是合式公式，则(A B),(A B),(A B),(A B)是是合式公式合式公式；（4 4）只有有限次地应用）只有有限次地应用(1)-(3)(1)-(3)组成的符号串才组成的符号串才是是合式公式合式公式.27命题（合式）公式：命

11、题（合式）公式：由命题常项、命题变项、联结词、由命题常项、命题变项、联结词、括号等组成的符号串括号等组成的符号串.1.1.定义定义28(p q)r(p q)r(p q)rp r p q rp q r 定义 给公式A中的命题变项 p1,p2,pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值29 A=(pq)r 1 1 0：A=0 成假赋值成假赋值 1 1 1，0 1 1，0 1 0：A=1 成真赋值成真赋值 真值表:公式A在所有赋值下的取值情况列成的表 例 给出公式的真值表 A=(qp)qp 的真值表30 p q qp (qp)q (qp)qp 0 0

12、0 11 01 1 1011 0001 111131例例 B B=(p p q q)q q 的真值表的真值表 p q ppq(pq)(pq)q0 00 11 01 1 1100110100100000实例实例32例例 C C=(=(p p q q)r r 的真值表的真值表 p q r pq r (pq)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010定义 设A为一个命题公式 (1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称

13、A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式 A=(qp)qp，B=(pq)q，C=(pq)r331.1 命题符号化及联结词1.2 命题公式及分类1.3 等值演算1.4 对偶与范式1.5 推理理论34一、等值式二、基本等值式三、等值演算与置换规则四、应用举例3536定义定义 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称，并称AB是是等值式等值式(pVq)与与 pV q(pVq)与与 pq注注:不是逻辑联结词，表示对任意的赋值，不是逻辑联结词，表示对任意的赋值，A与与B的值相同。的值相同。是等价联结词，它与是等

14、价联结词，它与不能混为一谈。不能混为一谈。p qpqpVq(pVq)pV q0 0110110 1101011 0011011 10010037(pVq)与与 pV q 不等值不等值p qpppVq(pVq)pq0 0110110 1101001 0011001 10010038(pVq)与与pq 等值等值序号序号等值式等值式定律定律1A A双重否定双重否定2A AVA等幂律等幂律3A AA4AVB BVA交换律交换律5ABBA6(AVB)VC AV(BVC)结合律结合律7(AB)C A(BC)8AV(BC)(AVB)(AVC)分配律分配律9A(BVC)(AB)V(AC)39序号序号等值式等值

15、式定律定律10(AVB)AB德德.摩根律摩根律11(AB)AV B12AV(AB)A吸收律吸收律13A(AVB)A14A V1 1零律零律15A0 016AV 0 A同一律同一律17A1 A18AV A 1排中律排中律19AA 0矛盾律矛盾律40序号序号等值式等值式定律定律20AB AVB蕴涵等值式蕴涵等值式(真值表真值表)21A B(AB)(BA)等价等值式等价等值式22AB B A假言易位假言易位(逆否命题逆否命题)23A B A B等价否定等值式等价否定等值式24(AB)(AB)A归缪论归缪论41等值演算:由已知的等值式推演出新的等值式的过程置换规则：若AB,则(A)(B)等值演算的基础

16、：(1)等值关系的性质：自反、对称、传递 (2)基本的等值式 (3)置换规则 42验证下列等值式:p(q r)(p q)r（P10例1.9(1)43 p(qr)p(qr)（蕴涵等值式)p(qr)（蕴涵等值式)(pq)r（结合律）(pq)r （德摩根律）(pq)r（蕴涵等值式)(pq)r (pq)r (pq)r p(qr)p(qr)p(qr)验证下列等式:p(p q)(p q)（P10例1.9(2)pp1（同一律）p(q q)（排中律）(pq)(p q)（分配律）44例3 用等值演算法判断下列公式的类型(1)q(pq)解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律

17、，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.45(2)(pq)(qp)解 (pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.46(3)(pq)(pq)r)解 (pq)(pq)r)(p(qq)r （分配律）p1r （排中律）pr （同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.47总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些1.1 命题符号化

18、及联结词1.2 命题公式及分类1.3 等值演算1.4 对偶与范式1.5 推理理论48定义 在仅含有联结词,的命题公式A中，将换成,换成，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.pq 与 pVq是对偶式；(pq)与(pVq)是对偶式。49定理 设A和A*互为对偶式，p1,p2,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则(1)A(p1,p2,pn)A*(p1,p2,pn)(2)A(p1,p2,pn)A*(p1,p2,pn)50例如例如:A(p,q,r)=p(qVr)A(p,q,r)=(p(qVr)pV(qr)A*(p,q,r)=pV

19、(qr)A*(p,q,r)=pV(qr)A*(p,q,r)=(pV(qr)p(qV r)A(p,q,r)=p(qV r)设A,B为两命题公式,若AB,则A*B*,其中A*,B*分别为A,B的对偶式.例如:(pq)V(pV(pVq)pVq(pq)V(pV(pVq)(pq)v(pvq)(pv(pvq)(qv(pvq)1(pvq)pVq对偶式(pvq)(p(pq)pq(pvq)(p(pq)(pvq)(pq)(p(pq)v(q(pq)0v(p q)pq51简单析取式:有限个命题变项及其否定构成的析取式52如 p,q,pq,pqr,简单合取式简单合取式:有限个命题变项及其否定构成的合取式有限个命题变项及

20、其否定构成的合取式如 p,q,pq,pqr,析取范式析取范式:由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式A A1 1 A A2 2ArAr,其中其中A A1 1,A A2 2,ArAr是简单合取式是简单合取式合取范式合取范式:由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,Ar是简单析取式53范式范式:析取范式与合取范式的总称析取范式与合取范式的总称 公式公式A的析取范式的析取范式:与与A等值的析取范式等值的析取范式公式公式A A的合取范式的合取范式:与与A A等值的合取范式等值的合取范式说明：单个文字既是简单析取式，又是简单合取式

21、p pq q r r,p p q qr r 既是析取范式，又是合取范式既是析取范式，又是合取范式 定理 任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）(2)否定联结词的内移或消去 (3)使用分配律 对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一54例 求下列公式的析取范式与合取范式(1)A=(pq)r55解 (pq)r (pq)r （消去）pqr （结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）解 (pq)r (pq)r （消去第一个）(pq)r （消去第二个）(p

22、q)r （否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r (pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）56(2)B=(pq)r推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法 57推理举例:(1)正项级数收敛当且仅当部分和有上界.(2)若ACBD，则AB且CD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.58定义 若对于每组赋值，或者A1A2 Ak 均为假，或者当A1A2Ak为真时,B也为真,则称由A1,A2,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,Ak 推B”的推理正

23、确 当且仅当 A1A2AkB为重言式.推理的形式结构:A1A2AkB 或 前提：A1,A2,Ak 结论：B 若推理正确，则记作：A1A2AkB.59真值表法等值演算法 判断推理是否正确主析取范式法构造证明法 证明推理正确 说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1A2AkB”.而在构造证明时，采用“前提:A1,A2,Ak,结论:B”.60重要的推理定律 A (AB)附加律 (AB)A 化简律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段论 (AB)(BC)(AC)假言三段论 (AB)(BC)(AC)等价三段论 (AB)(CD)(AC)(

24、BD)构造性二难 61例 构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天没备课.所以，明天不是星期一和星期三.解 设 p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为 前提：(pq)r,rs,s 结论：pq 62前提：(pq)r,rs,s 结论：pq 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq)拒取式 pq 置换 63欲证明 前提：A1,A2,Ak 结论：CB等价地证明 前提：A1,A2,Ak,C 结论：B 理由：(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B (A1A2AkC)

25、B64 65222例例 构造下面推理的证明构造下面推理的证明:2是素数或合数是素数或合数.若若2是素数，则是素数，则 是无理数是无理数.若若 是无理数，则是无理数，则4不是素数不是素数.所以，如果所以，如果4是是 素数，则素数，则2是合数是合数.用附加前提证明法构造证明用附加前提证明法构造证明解解 设设 p：2是素数，是素数，q：2是合数，是合数，r：是无理数，是无理数，s：4是素数是素数推理的形式结构推理的形式结构 前提：前提：p q,pr,rs 结论：结论：sq222证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论66前提：前提：p q,pr,rs 结论：结论：sq欲证明 前提：A1,A2,Ak 结论：B将B加入前提，若推出矛盾，则得证推理正确.理由:A1A2AkB (A1A2Ak)B (A1A2AkB)括号内部为矛盾式当且仅当(A1A2AkB)为重言式 67例 构造下面推理的证明 前提：(pq)r,rs,s,p 结论：q证明（用归缪法）q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式68 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq)析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取由得出了矛盾，根据归谬法说明推理正确。69