离散数学(命题逻辑)精讲

理学院命题逻辑离散数学第一章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范式1.5推理理论2§1命题符号化及联结词一、命题与真值二、命题分类：原子命题，复合命题三、命题常项与命题变项及其符号化四、联结词3一、命题与真值命题:具有唯一确定真假意义的陈述句命题的真值:判断的结果真值的取值:真或假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中判断结果不惟一确定的也不是命题4.5真命题假命题疑问句感叹句祈使句不是命题（1）2是素数.（2）雪是黑色的.（3）2+3=5.（4）现在是六点钟.（5）3能被2整除.（6）这朵花多好看呀!（7）明天下午有会吗?（8）请关上门!（9）x+y5.（10）地球外的星球上也有人.真命题假命题在数理逻辑中，不需要纠结在各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句。二、命题分类：简单命题与复合命题简单命题（原子命题）：命题不能分成更简单的句子的命题，又称为命题常项（命题常元）。2是素数.雪是黑色的.2+3=5.明年十月一日是晴天.3能被2整除.6二、命题分类：简单命题与复合命题复合命题：由简单命题用联结词联结而成的命题。3不是偶数;2是素数和偶数;林芳学过英语或日语;如果角A和角B是对顶角，则角A等于角B．7三、命题常项与命题变项及其符号化1.命题变项（命题变元、命题函数）：真值可以变化的陈述句。如：x+y5.命题变项不是命题。2.命题常项（命题常元）：真值唯一确定的陈述句。如：2是偶数.命题常项是命题。83.简单命题、命题变项的符号化简单命题符号化：p:2是素数;--命题常项q:雪是白的;--命题常项命题变项符号化：p:x+y5;--命题变项（不是命题）命题的真值表示：1(T)表示真;0(F)表示假.9四、联结词与复合命题1.否定式与否定联结词“”定义1设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p.符号称作否定联结词p为真当且仅当p为假.例p：3是偶数。┐p：3不是偶数10四、联结词与复合命题(续)2.合取式与合取联结词“∧”定义2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q.∧称作合取联结词p∧q为真当且仅当p与q同时为真合取联结词是逻辑“与”的意思。11例将下列命题符号化.（1）李平既聪明又用功（2）李平虽然聪明,但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功（5）李文和李武是兄弟解：令p：李平用功，q：李平聪明，则（1）p∧q（2）p∧┐q（3）p∧q（4）（┐(┐p)∧┐q）（5）r:李文和李武是兄弟分清简单命题与复合命题不能见到“和”、“与”就用“∧”描述合取式的灵活性与多样性12四、联结词与复合命题(续)定义3设p,q为命题，复合命题“p或q”称作p与q的析取式，记作p∨q.∨称作析取联结词p∨q为假当且仅当p与q同时为假.133.析取式与析取联结词“∨”四、联结词与复合命题(续)14例将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.解令p:2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3)均为相容或.分别符号化为:p∨r,p∨q,r∨s,它们的真值分别为1,1,0.而(4)为排斥或.(4)令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为(t∧u)∨(t∧u).15四、联结词与复合命题(续)定义4设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，pq为假当且仅当p为真q为假.164.蕴涵式与蕴涵联结词“”四、联结词与复合命题(续)pq的逻辑关系：q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q只要p，就q只有q,才p除非q，才p除非q，否则非p17自然语言中p与q具有联系，而数理逻辑中p与q可以没有联系。例如果3＋3＝6，则雪是黑的。如果3+36，则雪是黑的。18例设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(7)如果天不冷，则小王不穿羽绒服.19注意：pq与qp等值（真值相同）pqpqpqqpqpqp四、联结词与复合命题(续)定义5设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.pq为真当且仅当p与q同时为真或同时为假.说明:(1)pq的逻辑关系:p与q互为充分必要条件205.等价式与等价联结词“”例将下列复合命题符号化并求其真值（1）2+2=4当且仅当3是奇数:p↔q1（2）2+2≠4当且仅当3是奇数:┐p↔q0（3）2+2=4当且仅当3不是奇数:p↔┐q0（4）2+2≠4当且仅当3不是奇数:┐p↔┐q121习题小王是游泳冠军或百米赛跑冠军:小王现在在宿舍或在图书馆:(┐p∧q)∨(p∧┐q)或p∨q选小王或小李中的一人当班长:(┐p∧q)∨(p∧┐q)如果我上街，我就去书店看看，除非我很累:┐r→(p→q)王一乐是计算机系的学生，他生于1968年或1969年，他是三好学生:p∧(q∨r)∧s22p∨q联结词运算规则我们所学的5种基本联结词也称为逻辑运算符，其运算顺序为：23┐，∧，∨，→，↔如果出现的基本联结词相同，又无括号时，则按从左到右的运算顺序；如果遇有括号时，不管出现的基本联结词如何，都先进行括号中的运算。真值表ppTFFTpqp∧qTTTTFFFTFFFFpqp∨qTTTTFTFTTFFFpqpqTTTTFFFTTFFT24pqpqTTTTFFFTFFFT第一章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范式1.5推理理论25§2命题公式及分类一、命题（合式）公式二、公式的赋值三、真值表四、命题的分类：重言式矛盾式可满足式26一、命题（合式）公式递归定义：（1）单个命题常项或变项p,q,r,...,pi,qi,ri,...,0,1是合式公式；（2）如果Ａ是合式公式，则┐Ａ是合式公式；（3）如果Ａ,B是合式公式，则(A∧B),(A∨B),(A→B),(A↔B)是合式公式；（4）只有有限次地应用(1)-(3)组成的符号串才是合式公式.27命题（合式）公式：由命题常项、命题变项、联结词、括号等组成的符号串.1.定义28(p∧q)↔r(┐p∧q)↔r(┐pq)↔r┐p∨→rp∧┐q↔rp┐∧q↔r√√××√×二、公式的赋值定义给公式A中的命题变项p1,p2,…,pn指定一组真值称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值29A=(p∧q)→r110：A=0成假赋值111，011，010：A=1成真赋值三、真值表真值表:公式A在所有赋值下的取值情况列成的表例给出公式的真值表A=(qp)qp的真值表30pqqp(qp)q(qp)qp0001101110110001111131例B=(pq)q的真值表pqppq(pq)(pq)q000110111100110100100000实例32例C=(pq)r的真值表pqrpqr(pq)r000001010011100101110111001111111010101011101010四、公式的类型定义设A为一个命题公式(1)若A无成假赋值，则称A为重言式(也称永真式)(2)若A无成真赋值，则称A为矛盾式(也称永假式)(3)若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A=(qp)qp，B=(pq)q，C=(pq)r33第一章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范式1.5推理理论34§3等值演算一、等值式二、基本等值式三、等值演算与置换规则四、应用举例35一、等值式36定义若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式┐(pVq)与┐pV┐q┐(pVq)与┐p∧┐q注:不是逻辑联结词，表示对任意的赋值，A与B的值相同。↔是等价联结词，它与不能混为一谈。真值表法（1）pq┐p┐qpVq┐(pVq)┐pV┐q001101101101011001101110010037┐(pVq)与┐pV┐q不等值真值表法（2）pq┐p┐ppVq┐(pVq)┐p∧┐q001101101101001001100110010038┐(pVq)与┐p∧┐q等值二、基本等值式序号等值式定律1A┐┐A双重否定2AAVA等幂律3AA∧A4AVBBVA交换律5A∧BB∧A6(AVB)VCAV(BVC)结合律7(A∧B)∧CA∧(B∧C)8AV(B∧C)(AVB)∧(AVC)分配律9A∧(BVC)(A∧B)V(A∧C)39基本等值式（2）序号等值式定律10┐(AVB)┐A∧┐B德.摩根律11┐(A∧B)┐AV┐B12AV(A∧B)A吸收律13A∧(AVB)A14AV11零律15A∧0016AV0A同一律17A∧1A18AV┐A1排中律19A∧┐A0矛盾律40基本等值式（3）序号等值式定律20A→B┐AVB蕴涵等值式(真值表)21A↔B(A→B)∧(B→A)等价等值式22A→B┐B→┐A假言易位(逆否命题)23A↔B┐A↔┐B等价否定等值式24(A→B)∧(A→┐B)┐A归缪论41三、等值演算与置换规则等值演算:由已知的等值式推演出新的等值式的过程置换规则：若AB,则(A)(B)等值演算的基础：(1)等值关系的性质：自反、对称、传递(2)基本的等值式(3)置换规则42四、应用举例——验证等值式验证下列等值式:p→(q→r)(p∧q)→r（P10例1.9(1))43p→(q→r)┐p∨(q→r)（蕴涵等值式)┐p∨(┐q∨r)（蕴涵等值式)(┐p∨┐q)∨r（结合律）┐(p∧q)∨r（德摩根律）(p∧q)→r（蕴涵等值式)(p∧q)→r┐(p∧q)∨r(┐p∨┐q)∨r┐p∨(┐q∨r)┐p∨(q→r)p→(q→r)验证等值式（续）验证下列等式:p(p∧q)∨(p∧┐q)（P10例1.9(2))pp∧1（同一律）p∧(q∨┐q)（排中律）(p∧q)∨(p∧┐q)（分配律）44四、应用举例——判断公式类型例3用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，该式为矛盾式.45例3(续)(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.46例3(续)(3)((pq)(pq))r)解((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.47总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些第一章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范式1.5推理理论48一、对偶式和对偶原理定义在仅含有联结词,∧,∨的命题公式A中，将∨换成∧,∧换成∨，若A中