(北大)数理逻辑

1、1,离散数学,2,数理逻辑部分,命题逻辑,3,第1章命题逻辑,1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4对偶与范式1.5推理理论,4,1.1命题符号化及联结词,命题与真值原子命题复合命题命题常项命题变项联结词,5,命题与真值,命题:能判断真假的陈述句命题的真值:判断的结果真值的取值:真与假真命题:真值为真的命题假命题:真值为假的命题注意:1.感叹句、祈使句、疑问句都不是命题；2.陈述句中的悖论不是命题；3.判断结果不惟一确定的不是命题,6,例：下列句子中哪些是命题？(1)是无理数.(2)2+58.(3)x+53.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话

2、！(7)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,7,例：下列句子中那些是命题？(8)明年10月1日是晴天.(9)地球外的星球上也有人.（10）111100.,（8）、（9）的真值虽然现在还不知道，但它的真值是唯一的，因而是命题。（10）在二进制中为真，在十进制中为假，需根据上下文才能确定其真值，因而不是命题。,8,命题的分类,1.简单命题(原子命题)简单构成的命题(不能分解成更简单的陈述句)简单命题的真值是确定的，又称为命题常项或命题常元2.复合命题由简单命题与联结词按一定规则复合而成的命题3.命题变项（命题变元）真值不确定的陈述句，如

3、:x+35注意：命题变元不是命题！,9,简单命题符号化,用小写英文字母p,q,r,pi,qi,ri(i1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p的真值为0,q：2+5=7，则q的真值为1,命题变项：也用小写英文字母p,q,r,pi,qi,ri(i1）表示,10,联结词与复合命题,1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词p为真当且仅当p为假2.合取式与合取联结词“”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq，称作合取联结词，并规定pq为真当且仅当

4、p与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题,11,例将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解:令p：王晓用功，q：王晓聪明，则(1)pq(2)pq(3)qp.,12,例(续),令r:张辉是三好学生，s:王丽是三好学生(4)rs.(5)令t:张辉与王丽是同学，t是简单命题.,说明:(1)(4)说明描述合取式的灵活性与多样性.(5)中“与”不是联结词的含义，因而(5)中句子是简单命题.又如：李文与李武是兄弟。,13,联结词与复合命题(续),定义设p,q为二命

5、题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假.,例将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.,3.析取式与析取联结词“”,14,解令p:2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3)均为相容或（允许同时为真）.分别符号化为:pr,pq,rs,它们的真值分别为1,1,0.而(4),(5)为排斥或（不相容或）.令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为(tu)(tu).令v:王晓红生

6、于1975年,w:王晓红生于1976年,则(5)既可符号化为(vw)(vw),又可符号化为vw,为什么?,15,例（6）选小王或小李中的一人当班长.解令t:小王当班长，u:小李当班长则(6)符号化为(tu)(tu).例（7）小王现在在宿舍或图书馆里.令v:小王在宿舍,w:小王在图书馆则(7)符号化为vw,16,联结词与复合命题(续),定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.注意：1.p与q不一定有内在联系2.前件p为假时，pq为真,4.蕴涵式与蕴涵联结词“”,17,

7、pq的逻辑关系：p为q的充分条件，q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q,否则非p，常出现的错误：不分充分与必要条件,联结词与复合命题(续),18,例设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,注意：pq与qp等值（真值相同）,pq,pq,pq,pq,q

8、p,qp,qp,qp,19,联结词与复合命题(续),定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并pq规为真当且仅当p与q同时为真或同时为假.说明:(1)pq的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假(3)pq与(pq)(qp)等值,5.等价式与等价联结词“”,20,例求下列复合命题的真值(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+24当且仅当美国位于非洲.(5)2+24当且仅当3不是奇数.（6）两圆面积相等当且仅当它们的半径相等.它们的真值分别为1

9、，0，1，0，1,1,21,复合命题符号化：第一步：分析出各简单命题，并将它们符号化第二步：使用合适的连接词，把简单命题逐个联结起来例1.小王是游泳冠军或百米赛跑冠军2.小王现在在宿舍或在图书馆里3.选小王或小李中的一人当班长4.如果我上街，我就去书店看看，除非我很累r（pq）或（rp)q5.小王是计算机系学生，他生于1985年或1986年，他是三好学生,22,联结词与复合命题(续),以上给出了5个联结词：,，组成一个联结词集合,，联结词的优先顺序为：,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算.注意:今后使用的括号全为圆括号.,23,1.

10、2命题公式及分类,命题变项与合式公式公式的赋值真值表命题公式的分类重言式矛盾式可满足式,24,命题变项与合式公式,命题常项：简单命题,真值确定的陈述句命题变项：真值不确定的陈述句定义合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项p,q,r,pi,qi,ri,0,1是合式公式(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)只有有限次地应用(1)(3)形成的符号串才是合式公式,25,合式公式的层次,定义(1)若公式A是单个的命题变项或命题常项（包括0，1）,则称A为0层公式.(2)称A是n+1(n0)层

11、公式是指下面情况之一：(a)A=B,B是n层公式；(b)A=BC,其中B,C分别为i层和j层公式，且n=max(i,j)；(c)A=BC,其中B,C的层次及n同(b)；(d)A=BC,其中B,C的层次及n同(b)；(e)A=BC,其中B,C的层次及n同(b).,26,合式公式的层次(续),例如公式p0层p1层pq2层(pq)r3层(pq)r)(rs)4层,27,公式的赋值,定义给公式A中的命题变项p1,p2,pn，给p1,p2,pn各指定一个真值（0或1），称为对A的一个赋值或解释成真赋值:使公式为真的赋值成假赋值:使公式为假的赋值说明：赋值=12n之间不加标点符号，i=0或1.A中仅出现p1,p2,pn，给A赋值12n是指p1=1,p2=2,pn=nA中仅出现p,q,r,给A赋值123是指p=1,q=2,r=3含n个变项的公式有2n个赋值.,28,真值表,真值表:公式A在所有赋值下的取值情况列成的表（1）列出所有命题变项，列出所有可能赋值（2）按从低到高的顺序写出各层次；（3）对应每个赋值，计算命题公式各层次的值，直到命题公式的值例给出公式的真值表A=(qp)qp的真值表,29,例B=(pq)q的真值表,实例,3