数理逻辑课件(离散数学)

1、第一部分数理逻辑,1,数理逻辑部分主要内容：,命题逻辑,1.1命题符号化及联结词1.2命题公式及分类2.1等值演算2.2范式2.3联结词的完备集3.1-3.2推理理论,一阶逻辑（谓词逻辑）,4.1一阶逻辑命题符号化4.2一阶逻辑公式及解释5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论,2,第一章命题逻辑基本概念,3,1.1命题与联结词,命题与真值原子命题的符号化复合命题联结词,4,例1：下列句子中哪些是命题？并判断真值(1)清华大学是一所全国重点大学.(2)2+58.(3)你有铅笔吗？(4)这只兔子跑得真快呀！(5)请不要讲话！,真命题,假命题,疑问句,感叹句,祈

2、使句,一、命题与真值（例题）,5,一、命题与真值,命题:判断结果惟一的陈述句命题的真值:判断的结果真值的取值:真、假真命题:真值为真的命题假命题:真值为假的命题,6,一、命题与真值（例题）,例2：判断下列语句是否是命题明年我将去欧洲下个月十五号是晴天xy2,是命题,不是命题,不确定真值,不知道真值,7,一、命题与真值（例题）,例3：“我正在说假话”，这句话是命题吗？,如果这句话是“真”的,如果这句话是“假”的,根据这句话的意义推得这句话是“假”的,这句话是“真”的,该陈述句为悖论,该陈述句不是命题,8,一、命题与真值（小结）,感叹句、祈使句、疑问句属于非陈述句，所以都不是命题；如果陈述句的判断

3、结果不惟一确定，那么该陈述句也不是命题；陈述句中的悖论也不是命题。,9,二、命题符号化,“是有理数”，是命题，且真值为0或F；2+5=7，是命题，且真值为1或T；,上述命题不能再分解为更简单的命题。,定义：一个命题不能再分解为更简单的命题，则称该命题为原子命题，也称简单命题。,命题逻辑中研究的最基本单位,10,二、命题符号化,用小写英文字母p，q，r，pi，qi，ri(i1）等表示简单命题（原子命题）。例：令p:2+5=7用“1”或“T”表示真，用“0”或“F”表示假。,11,二、命题符号化,令t：我来自西安，s：我是一名教师。,问题：如何表示“我是一名教师，并且我来自西安”？,复合命题,定义

4、：由简单命题与联结词按一定规则复合而成的命题。,12,三、复合命题及联结词,1.否定式与否定联结词“”,定义：设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词。,p真值表,13,三、复合命题及联结词,例如：p:上海是一个城市。p:上海不是一个城市。,规则：(p)等价于p,p:上海是一个大城市。p:上海是一个小城市。,p:上海不是一个大城市。,14,三、复合命题及联结词,“p与q”记作pq称为p、q的合取式为合取联结词,2.合取式与合取联结词“”,15,三、复合命题及联结词（例题）,例4：将下列命题符号化。(1)王晓既用功又聪明。(2)王晓不仅聪明，而且用

5、功。(3)王晓虽然聪明，但不用功。(4)张辉与王丽都是三好生。(5)张辉与王丽是同学。,简单命题,pq,pq,p(q),rs,令p：王晓用功；q：王晓聪明；r:张辉是三好学生s:王丽是三好学生,16,三、复合命题及联结词,ppp1p0p(p),等价于,p,等价于,p,等价于,0,等价于,0,关于“合取”的相关规则,例5：计算下列命题的真值,(10),1(p0),(p0)1,0,0,1,17,三、复合命题及联结词,合取满足交换律。,pq等价于qp,合取满足结合律。,p(qr)等价于(pq)r,18,三、复合命题及联结词,“p或q”记作pq称作p与q的析取式称作析取联结词,3.析取式与析取联结词,

6、19,三、复合命题及联结词（例题）,例6：将命题“2或4”是素数符号化,pq,令p:2是素数;q:4是素数；,例7：将下列命题符号化小元元只能拿一个苹果或一个梨。王晓红生于1975年或1976年。,t:小元元拿一个苹果;u:小元元拿一个梨；v:王晓红生于1975年;w:王晓红生于1976年。,20,三、复合命题及联结词（例题续）,分析：在例6中，构成复合命题的两个原子命题之间没有排斥性，即两个原子命题有同时为真的可能性。例7中，构成复合命题的两个原子命题之间存在排斥性。,相容或,排斥或,21,三、复合命题及联结词（例题续）,“排斥或”的复合命题该如何符号化呢？,小元元只能拿一个苹果或一个梨。符

7、号化为(tu)(tu)王晓红生于1975年或1976年。符号化为(vw)(vw)也可以表示成：vw,可以用异或来表示,22,三、复合命题及联结词,小结：自然语言中的“或”是多义的，主要有以下两种情况：可兼或（相容或）：二者至少有一个发生，不排斥二者都发生的情况。同析取联结词的含义完全相同。排斥或：非此即彼，二者不可兼得。,23,三、复合命题及联结词,ppp1p0p(p),等价于,p,等价于,1,等价于,p,等价于,1,关于“析取”的相关规则,析取也满足交换律合结合律。,24,三、复合命题及联结词,例8：假设e表示“Alice高兴”，r表示“Tom高兴”，那么将下列自然语言的陈述转换成逻辑命题。

8、,如果Alice高兴，那么Tom高兴；除非Alice高兴，Tom才高兴；,25,三、复合命题及联结词,4.蕴涵式与蕴涵联结词“”“如果p,则q”称作p、q的蕴涵式记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件。称作蕴涵联结词，或条件联结词。,26,三、复合命题及联结词,pq真值表,善意的推定,27,三、复合命题及联结词,pq的逻辑关系：p是q的充分条件；q为p的必要条件。“如果则”的不同表述法有：“只要就”，“仅当”，“除非才”等。,28,三、复合命题及联结词（例题）,例9：将下列命题符号化（1）只有努力才能取得成功（2）只要努力过就不后悔,设：p:努力q:成功s：努力过t：不后悔,qp,s

9、t,29,三、复合命题及联结词（例题）,例10：设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服。(2)因为天冷，所以小王穿羽绒服。(3)若小王不穿羽绒服，则天不冷。(4)只有天冷，小王才穿羽绒服。,pq,pq,qp,qp,30,三、复合命题及联结词（例题续）,(5)除非天冷，小王才穿羽绒服。(6)除非小王穿羽绒服，否则天不冷。(7)如果天不冷，则小王不穿羽绒服。(8)小王穿羽绒服仅当天冷的时候。,pq,qp,pq,qp,31,三、复合命题及联结词,小结：只有才、除非才、仅当表达的是必要条件；只要就、如果就（则）表达的是充分条件；,课堂练习：习题8,32,三、复合命

10、题及联结词,5.等价式与等价联结词“”“p当且仅当q”记作pq称作p、q的等价式也称作双条件式称作等价联结词。,33,三、复合命题及联结词,需要注意以下两点：等价联结词即通常的“充分必要条件”;pq为真当且仅当p与q同真或同假，也称“同或”。,34,三、复合命题及联结词（例题）,例11：求下列复合命题的真值(1)2+24当且仅当3+36。(2)2+24当且仅当3是偶数。(3)2+24当且仅当太阳从东方升起。(4)2+24当且仅当美国位于非洲。,1,0,1,0,复合命题的真值取决于构成它的各原子命题的真值，而与它们的内容、含义无关。,35,三、复合命题及联结词,等价联结词具有以下性质：满足结合律

11、(pq)r等价于p(qr)满足交换律pq等价于qppp的真值永远为“真”pp的真值永远为“假”,36,三、复合命题及联结词,有关联结词优先级如下：联结词的优先顺序为：,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;有括号时，应该先进行括号中的运算。,37,三、复合命题及联结词,（1）与含义相同（2）与含义相同（3）与含义相同,由联结词的优先级可得：,38,例题,例12：利用联结词，将下述语句符号化：“如果你走路时看书，那么你一定会成为近视眼”。,解：令p：你走路；q：你看书；r：你是近视眼。则上述语句可以符号化为：(pq)r,39,例题,例13：将下列命题符号化（1）他努力而且聪

12、明，这不是真的。,令p:他努力；q:他聪明,（2）虽然天气很冷，老王还是来了。,令p:天气很冷；q:老王来了,40,例题,（3）不经一事，不长一智,令p:经一事；q:长一智,（4）若两个圆面积相等，那么它们的半径相等；反之亦然。,令p:两个圆面积相等；q:两个圆半径相等,41,例题,例14：符号化下列两个命题如果你和他都不固执己见的话，那么不愉快的事也不会发生了。如果你和他不都固执己见的话，那么不愉快的事也不会发生了。,42,例题,例15：将下列命题符号化，并讨论各命题的真值。若今天是星期一，则明天是星期二若今天是星期一，则明天是星期三,43,作业,习题一：14，15,44,1.2命题公式及其

13、赋值,命题常项和命题变项合式公式公式的赋值真值表公式的分类,45,一、命题常项和命题变项,命题常项：一个确定的具体的简单命题称作命题常项。也称命题常元。命题变项：当p所代表的只是一个抽象的命题，它可以表示任意的命题，称p为命题变项。也称命题变元。命题变项不是命题。,p:天气很冷,46,一、命题常项和命题变项,当用一个特定的命题取代命题变元时，才能确定其真值：真或假。这种取代称作对该命题变元指派真值。,p:,太阳从东边升起,p:太阳从东边升起,47,二、合式公式,合式公式的一般化定义：将命题变项用联结词和括号按一定逻辑关系联结起来的符号串称作合式公式，也称命题公式，简称公式。,公式通常用字母A、

14、B、C等表示。,例：(pq)r)(rs),48,二、合式公式,合式公式的递归定义：(1)单个命题常项或变项p,q,r,是合式公式；(2)若A是合式公式，则(A)也是合式公式；(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)(3)形成的包含命题变元、联结词和括号的符号串才是合式公式。,此处的A、B等称作元语言符号，代表抽象的公式,49,二、合式公式,子公式定义：若A为合式公式，B为A的一部分，且B也是合式公式，则称B为A的子公式。,例：(pq)r是合式公式A，pq是合式公式B，B是A的一部分。称B是A的子公式。,50,三、公式的赋值,p

15、q是一个合式公式，但是真值是多少呢？,若令p:2是偶数，q：2是素数，则pq真值为真；,若令p:3是偶数，q：3是素数，则pq真值为假；,定义：给公式A中的命题变项p1,p2,pn给予一定的解释，使其获得一组确定的真值，这个过程称为对A的一个赋值或解释。,51,三、公式的赋值,例1：公式B=(pq)q的真值表,52,例2：C=(pq)r的真值表,含n个变项的公式有2n个赋值。,成假赋值,53,四、公式的层次,公式(pq)r)(rs)p0层p1层pq2层(pq)r3层(pq)r)(rs)4层,54,四、公式的层次,合式公式的层次定义(1)若公式A是单个的命题变项,则称A为0层公式.(2)称A是n+1层公式是指下面情况之一：(a)A=B，B是n层公式；(b)A=BC；(c)A=BC；(d)A=BC；(e)A=BC.其中B、C分别为i层和j层公式，且n0，n=max(i,j)；,55,五、公式的分类,定义：设A为一个命题公式若A无成假赋值，则称A为重言式(或永真式)若A无成真赋值，则称A为矛盾式(或永假式)若A不是矛盾式，则称A为可满足式。,注意：重言式是可满足式，