1、2018/9/25,1,上海电力学院,离散数学教程,2018/9/25,2,前言,一、为什么要学习离散数学?,2、离散数学:是许多数学分支的总称.主要括： 数理逻辑,集合论,代数系统,图论.,1、专业的需要:,2、对本身素质的训练,二、连续数学与离散数学,1、连续数学:微积分,微分方程,复变函数等.,三.教学方法1)引路 2)预习 3)作业 4)章后总结,2018/9/25,3,前言,四、参考书,五、作业,1)离散数学耿素云等编著，高教出版社,2)离散数学何自强等编著，科学出版社,如何使用参考书？,每章每节后看参考书，然后总结，压缩即：薄厚薄,2018/9/25,4,前言,离散数学是现代数学的
2、一个重要分支，是学习计算机科学与术的重要,第一篇集合论（集合基本概念、关系、无限集）,第二篇代数结构（代数系统、群、环、域、格）,第三篇图论（图的基本概念以及不同类型的图）,第四篇数理逻辑（命题逻辑和谓词逻辑）,基础课之一。本课程以集合论、代数结构、数理逻辑、图论的,四大部分为主干教学内容,并辅以组合论、数论基础、形式语言与,自动机初步等内容。本教案选取课程的主干内容进行组织,包括：,2018/9/25,5,第1章命题逻辑,数理逻辑是计算机科学的基础理论之一。可分为五大部分：,第一篇数理逻辑第一章命题逻辑,逻辑演算、集合论、证明论、模型论、递归论。数理逻辑既是,数学又是逻辑学：它研究数学中的逻
3、辑问题，用数学方法研究,形式逻辑。计算机的硬件，软件，算法及语言都具有数理逻辑的性质。,我们在此仅讲授数理逻辑的基础部分逻辑演算部分。它包,括命题演算和（一阶）谓词演算两部分。,2018/9/25,6,第1章命题逻辑,第一篇数理逻辑第一章命题逻辑,1.2 联结词,1.3 命题公式与翻译,1.41.5 命题逻辑的等值演算,1.6 其它联结词及联结词完备集,1.1命题及表示法,1.7 对偶与析取范式和合取范式(范式),1.8 命题逻辑推理理论,2018/9/25,7,第2章谓词逻辑,2.1谓词的概念与表示,第一篇数理逻辑第二章谓词逻辑,2.2命题函数与量词,2.32. 4一阶谓词公式,2.5一阶谓
4、词演算的等价式与蕴含式,2.6 一阶谓词前束范式,2.7一阶逻辑的推理理论,2018/9/25,8,1.1命题及表示法,命题逻辑研究的中心问题是推理，即研究推理中的前题和结论之,第一篇数理逻辑第一章命题逻辑,定义1：命题是能判断真假的陈述句。,定义2：真值是陈述句为真或假的这种性质。,间的形式关系，而不涉及前题和结论的具体内容。推理的基本单,位为命题。,注1：上命题必须是陈述句。而疑问句、祈使句和感叹句等不是命题。,注2：命题的真值是唯一的，但与我们是否知道它的真值无关。,假命题：凡与事实不相符的命题，其真值为假。符号化：用“0”或“F”表示。,真命题：凡与事实相符的命题，其真值为真。符号化：
5、用“1”或“T”表示。,2018/9/25,9,1.1命题及表示法,（1）三角形的三个内角和为180度。,第一篇数理逻辑第一章命题逻辑,（2）4为素数。,例：判断下列语句是否为命题,（3）1+101=110,（4）你喜欢离散数学吗？,（5）这朵花真美啊！,（6）xy,（7）我正在说谎。,2018/9/25,10,1.1命题及表示,第一篇数理逻辑第一章命题逻辑,例：(1)P：“雪是黑的”,命题符号化：一般用大写字母A，B，P，Q，或带下标的大,命题常元与命题变元,写字母或数字表示。,(2)Q2：“上海是个美丽的城市”,(3)：“X+28”,命题常元：表示具体确定内容的命题。,命题变元：表示任意的
6、，没有赋予具体内容的抽象命题。,注1：命题变元与命题常元的区别,注2：命题变元与命题常元在逻辑演算中处理原则相同。,2018/9/25,11,1.2命题联结词,第一篇数理逻辑第一章命题逻辑,若干个简单命题通过命题联结词而构成的新命题。,定义：简单命题（原子命题）不能再分解为更简单的命题。,1、否定词“”,注： “”为一元运算，否定全部而非部分。,2、合取词“”,定义：复合命题,定义：设P为一个命题，利用“”与P组成复合命题称为P的否命题，,记为“ P”。读作“非P”，其真值表见表1-1,定义：设P和Q为两个命题，由P与Q用二元联结词 “”,成复合命题，记为“PQ”。读作“P且Q”,2018/9
7、/25,12,1.2命题联结词,第一篇数理逻辑第一章命题逻辑,PQ：,例1：P：“李军聪明”，Q：“李军用功”,注：内容上无联系的两个命题也可以组成具有确定真值的命题。,3：析取词“”,定义：设P和Q为两个命题，由P与Q用二元联结词 “”组成,例1：P：“开关坏了”，Q：“灯炮坏了”：PQ：,注： “”表示可兼或。不可兼或不能用“”表示。,PQ：“李军聪明且用功”,复合命题，记为“PQ”。读作“P或Q”,例2：P：“1+11=100”，Q：“熊猫为稀有动物”,2018/9/25,13,1.2命题联结词,第一篇数理逻辑第一章命题逻辑,4、条件“”,例2：小李下午去打蓝球或在宿舍玩电脑。,定义：设
8、P和Q为两个命题，由P与Q用二元联结词 “”组成复合命,例1：有位父亲对儿子说：“如果我去书店，我一给你买光盘。”,解：P：父亲去书店，Q：给儿子买光盘,题，记为“P Q”。读作“如果P，则Q”，其中P为前件，Q为后件。,只有当前件为真，后件为假时， PQ为假。,试问：在何种情况下，这位父亲算失信？,1) P=1，Q=1,3) P=0，Q=1,2) P=1，Q=0,4) P=0，Q=0,注：善意的推论。,2018/9/25,14,1.2命题联结词,第一篇数理逻辑第一章命题逻辑,5、等价词（双条件）“”,例2：雪是黑的，仅当太阳从西方出来。 等价于,定义：设P和Q为两个命题，由P与Q用二元联结词
9、 “”组成复合命,例：将下列命题符号化，并讨论它们的真值,1) if：3+3=6，则雪是白的。,如果雪是黑的，则太阳从西方出来。,题，称为等价复合命题记为“PQ”。读作“P当且仅当Q”，当且仅,P和Q的真值相同时，PQ为真。否则为假。,2) if：3+3不等于6，则雪是白的。,3) if：3+3=6，则雪不是白的。,4) if：3+3不等于6，则雪不是白的。,5) 3为有理数当且仅当美国在亚洲。,2018/9/25,15,1.2命题联结词,第一篇数理逻辑第一章命题逻辑,解：P：3+3=6，Q：雪是白的,1)逻辑词的优先级别分别为：，,二、语句形式化,1) PQ，真值为1(P(1)Q(1),2)
10、 PQ，真值为1(P(0)Q(1),3) PQ，真值为0(P(1)Q(0),5) PQ，真值为0(P(1)Q(0),4) PQ，真值为1(P(1)Q(1) P：3为有理数，Q：美国在亚洲,推理问题：自然语言描述逻辑语言逻辑演算规律推理运算,在命题形式化时，若命题包含多个联结词时，应注意联结词的,运算规律。,括号中的运算为最优先级。,2018/9/25,16,1.2命题联结词,第一篇数理逻辑第一章命题逻辑,2)同级联结词，按从左到右的次序运算。,例2：如果你和他不都是傻子，那么你们不会去自讨没趣。,例1：狗急跳墙,例3：如果你走路看书，那么你一定会成为近视眼。,例4：如果明天天气好，我们去郊游；
11、否则不去郊游。,2018/9/25,17,1.3命题公式及其赋值,第一篇数理逻辑第一章命题逻辑,一、命题公式(合式公式)：由命题常元、命题变元、命题联结词及,定义：命题公式的递归定义（简称公式）,是否任何字符串都是命题呢？AB，A，B,(RP)，P(R)，(P(R）,定义：设A为含有命题变元P1，P2，Pn的命题公式，给P1，,圆括号等组成的字符串。,1)单个命题变元为命题公式。,2) if：P，Q为命题公式，则P，PQ，PQ，PQ，PQ也为命题公式。,3)仅有有限次地利用上述1)、2)产生的字符串才是命题公式。,例：PQ(QR)，(PQ)R(QR)Q),P2，Pn一组确定的真值，称为对A的一
12、个赋值或解释或真值指派。,2018/9/25,18,1.3命题公式及其赋值,第一篇数理逻辑第一章命题逻辑,成真赋值：若指定的一组值使A的真值为1，则这组值为成真赋值。,规定：1)若A中出现命题变项为P1，P2，Pn，给定A的赋值为1，,成假赋值：若指定的一组值使A的真值为0，则这组值为成假赋值。,2)若A中出现命题变项为P，Q，R，给定A的赋值为1，2，,二、定义：真值表,2，n，则指P1=1， P2=2，Pn=n,n，则指P=1， Q= 2，最后字母赋值n。,上述的i，取值为0或1。,将命题公式A在所有赋值情况列表，称为A的真值表。,2018/9/25,19,1.3命题公式及其赋值,第一篇数
13、理逻辑第一章命题逻辑,命题公式真值表构造步骤如下：,2)按从低到高的顺序写出公式的各个层次。,1)找出命题公式中的所有命题变元，按下标或字母次序排列，按二,3)计算各个层次的真值，直到最后计算出公式的真值。,注：两个公式有相同的真值表或不同的真值表是指真值表的最后,例：求下列公式的真值表，并求成真赋值和成假赋值。,1) (PP)(QQ),三、命题公式的类型,进制依次写出赋值。,一列是否相同。,2) (QP)R,2018/9/25,20,1.3命题公式及其赋值,第一篇数理逻辑第一章命题逻辑,定义：重言式或永真式,定义：矛盾式或永假式,定义：可满足式,1)、3)同，2)、4)同。,例：下列各公式中
14、均含有两个变元P，Q，它们中哪些有相同的真值表？,1) PQ，2) PQ，3) (PQ)4) (PQ)(QP)，5) PQ,一个命题公式，如果对它含的命题变元的任一组赋值，取值恒为真。,一个命题公式，如果对它含的命题变元的一组赋值，取值恒为假。,一个命题公式，如果对它含的命题变元的至少有一组赋值，取值为真。,2018/9/25,21,1.41.5 命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,一、等值式(等价公式),定义：命题公式的等价关系,注1： A与B为等价公式可定义为AB为重言式。,例2：判断下列公式是否等价？,注2： AB 不表示公式（命题），仅代表A与B之间逻辑等价公式。,例1：
15、证明,设A与B为两个命题公式，若A与B有相同的真值表时称公式A与B为等,价公式。记为：AB,AB表示命题公式（命题）。,(PQ)(QP),(QP)PQ,1) P(QR)与(PQ)R,2) (PQ)R与(PQ)R,2018/9/25,22,1.41.5 命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,“ ”公式之间等价关系满足：,2)幂等律：AAA，AAA,等价式的基本定律：,1)双重否定定律：AA,3)交换律：ABBA，ABBA,4)结合律：(AB)CA(BC) (AB)CA(BC),5)分配律： A(BC)(AB)(AC)A(BC)(AB)(AC),1)自反性：A，AA,2)对称性：A，B
16、，if：AB，则B A,3)可传递性：A，B，R，if：AB，BR，则： AR,2018/9/25,23,1.41.5 命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,8)零律：A11，A00,6)德摩根律：(AB)BA(AB)BA,7)吸收律：A(AB)A A(AB)A,9)同一律：A0A，A1A,10)排中律：AA1,11)矛盾律：AA0,12)条件等价式：ABAB,13)双等价等值式：(AB)(AB)(BA),2018/9/25,24,1.41.5 命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,定义:等值演算,16)归谬论:(AB)(AB)A,14)假言易位：ABBA,15)等价否
17、定等价式：ABAB,二、等值演算,置换规律则,设F(A)为包含公式A的命题公式，F(B)是用公式B置换了F(A)中所,由一些等值式推算另一些等值式的过程。,有A后得到的命题公式，若BA，则F(B)F(A),2018/9/25,25,1.41.5 命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,1)解：(PQ)R(PQ)R,例2：用等值演算证明等值式,例1：(PQ)R(PQ)R,1) (PQ)R(PR)(QR),2) (PQ)(PQ)(QP),例3：用等值演算判断下列公式的类型,(PQ)R,(PQ)R,(RP)(RQ),(PQ)R(PR)(QR),(PR)(QR),3) P(PQ)PQ,201
18、8/9/25,26,1.4 1.5命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,三、蕴含式,2)解：(P(PQ)R(P(PQ)R,1) (PQ)(PQ),定义：当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ。,对于PQ来说，除P的真值取T，Q的真值取F这样一种指派时，PQ,2) (P(PQ)R,(PPQ)R(TQ)R,TRF,证明PQ，即是证明PQ是重言式。,的真值为F外，其余情况，PQ的真值为T。故要证PQ，只需对条,件命题PQ的前件P，指定真值为T，若由此推出Q的真值亦为T，,则PQ是重言式，即PQ成立；同理，如对条件命题PQ中，假定,后件Q的真值取F，若由此推出P的真值亦
19、为F，即推证了QP,故PQ成立。,2018/9/25,27,1.4 1.5命题逻辑的等值演算,第一篇数理逻辑第一章命题逻辑,例：推证Q(PQ)P,对PQ来说，QP称作它的逆换式；P Q称作它的反换式；,定义：逆换式、反换式、逆反式,证法1：,证法2：假定P为F，则P为T。,QP称作它的逆反式。,假定Q(PQ)为T，则Q为T。且(PQ) 为T。由Q为F，PQ为T，,则必须P为F，,故P为T。,(a)：若Q为F，则PQ为F，Q(PQ)为F。,(b)：若Q为T，则Q为F，Q(PQ)为F。,所以Q(PQ)P成立。,常用的蕴含式如表1-5.2。,2018/9/25,28,1.6 其它联结词及联结词完备集
20、,第一篇数理逻辑第一章命题逻辑,1：不可兼析取“ ”,一、其它联结词,2： 条件否定“ ”,二、联结词完备集（最小联结词组）,合命题，记为P Q。当且仅当P和Q有不同的真值时， P不可,定义：设P和Q为两个命题，由 P与Q用二元联结词 “ ”组成复,析取Q为1；否则为零。其真值表见表,定义：设P和Q为两个命题，由 P与Q用二元联结词 “ ”组成复,合命题，记为P Q。当且仅当P为真，Q为假时，其真值为1。,2018/9/25,29,1.6 其它联结词及联结词完备集,第一篇数理逻辑第一章命题逻辑,定义：设P和Q为两个命题，由 P与Q用二元联结词 “”组成,3：与非“”,4：或非“”,题，记为PQ
21、。当且仅当P与Q同时为假时, PQ为1；否则为0。,定义：n元真值函数,复合命题，记为“PQ”。当且仅当P与Q同时为真时, pq为,零,否则为1。其真值表见表1-6.3(左图,定义：设P和Q为两个命题，由 P与Q用二元联结词 “”组成复合命,真值表见表1-6.4(右图)。,称F：0，1n0，1为n元真值函数。,F：自变量为n个命题变元0，1组成的长度为n的符号串。,值域：0，1,2018/9/25,30,1.6 其它联结词及联结词完备集,第一篇数理逻辑第一章命题逻辑,n=1时， 1元真值函数为22个,n个命题变元共构成2的2n次幂个不同的真值函数。,定义：（联结词完备集）,设S是一个联结词完备
22、集合，如果任何n(n1)元真值函数都可以仅,定理：S=，是联结词完备集。,推论：下列联结词集都是完备集,n=2时， 1元真值函数为24个,由S中的联结词构成的公式表示。,2018/9/25,31,1.6 其它联结词及联结词完备集,第一篇数理逻辑第一章命题逻辑,1）S1= ，,4）S4= ，,5）S5= ，,6）S6= ,2）S2= ，,3）S3= ，,7）S7= ,例1：仅用，表示（p q） p。,例2：用表示p 。,定理：S=，或S=，是最小联结词完备集。,2018/9/25,32,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,在给定的命题公式中，将联结词“”换成“”
23、，将联结词“”换成,注：A也为A*的对偶式。,例：写出下列各式的对偶式,一、对偶式,定义：A的对偶式,定理：设A与A*是对偶式, P1,P2，,Pn是出现在A与A*中的原子,A(P1,P2,Pn)A*(P1,P2,Pn),定理：设P1,P2,Pn是出现在A与B中的原子变元，如果A B，则A* B*。,“” ，若有特殊元“0”或“1”亦相互取代，所得公式A*称为A的对偶式。,(PQ)R，(PQ)1，PQ，PQ,则:,A(P1,P2,Pn)A*(P1,P2,Pn),2018/9/25,33,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,简单析取式：仅由有限个文字构成的析取式
24、。,简单合取式：仅由有限个文字构成的合取式。,二、析取范式和合取范式,定义：,例：P，PQ，PQQ 为简单析取式,注：单个文字既可为简单析取式又为简单合取式。,定理：,文字：命题变元或命题变元的否定。,P，PQ，PQQ 为简单合取式,1）一个简单析取式为重言式的充要条件是它同时含有命题变元和命,题变元的否定。,2018/9/25,34,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,析取范式：由有限个简单合取式构成的析取式。,合取范式：由有限个简单析取式构成的合取式。,2）一个简单合取式为矛盾式的充要条件是它同时含有命题变元和,定义：,注1：析取范式与合取范式仅含有，,注
25、2：单个文字，简单析取范式与简单合取范式既为析取范式又是合取范式。,定理：,2)一个合取范式为重言式的充要条件是它的每个简单析取式都是重言式。,命题变元的否定。,1)一个析取范式为矛盾式的充要条件是它的每个简单合取式都是矛盾式。,2018/9/25,35,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,求给定公式范式的步骤：,1)消去联结词“”，“”,定理（范式存在定理）,对任意公式A，都存在等价于它的析取范式和合取范式。,PQPQ,(PQ)(PQ)(PQ)(求合取范式),2)消去否定号“”,3)利用分配律和结合律,例1：求公式(PQ)R的合取范式,(PQ)(PQ)(PQ
26、)(求析取范式),解：(PQ)R(PQ)R,2018/9/25,36,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,3)全体小项的析取式为永真。,三命题变元P，Q和R，其极小项为：,一般n个命题变元有2n个极小项。一个极小项对一组赋值使其真值,m7=PQR，m6=PQR，m5=PQR，m4=PQR, m3=PQR,极小项有下列性质：,1)每个小项当其真值指派与编码相同时，其真值为1，其余的指派为0。,2)任意两个不同小项的合取式为永假。,定义：布尔析取或极大项,n个变元的析取式，称作布尔析取或极大项，其中每个变元,为1，此时所对应的二进制数为i，引入记号mi表示。,m2
27、=PQR, m1=PQR，m0=PQR,它的否定不能同时存在，但两者必须出现且仅出现一次。,2018/9/25,37,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,1)每个大项当其真值指派与编码相同时，其真值为0，其余的指派为1。,例：两命题变元P和Q，其极大项为：,三命题变元P，Q和R，其极大项为：,一般说，n个命题变元共有2n个极大项。一个极大项对一组赋值使,极大项有下列性质：,2)任意两个不同大项的析取式为永真。,3)全体大项的合取式为永假。,M0 =PQ, M1=PQ, M2=PQ, M3=PQ,M0=PQR，M1=PQR，M2=PQR，,M4=PQR, M3=
28、PQR, M6=PQ R,M5=PQR，M7=PQR,其真值为0，此时所对应的二进制数为i，引入记号Mi表示。,2018/9/25,38,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,定理：在真值表中，一个公式的真值为0的指派所对应的大项的合,定义：主析取范式、主合取范式,对于一个给定的命题公式，如果有一个等价公式，它仅由小项组,对于一个给定的命题公式，如果有一个等价公式，它仅由大项组,定理：在真值表中，一个公式的真值为1的指派所对应的小项的,求主范式的方法：,方法1：已知公式的真值表求。,例：求PQ，PQ，PQ的主析取范式和主合取范式。,成析取范式，则该等价公式称为原
29、式的主析取范式。,成合取范式，则该等价公式称为原式的主合取范式。,析取，即为此公式的主析取范式。,取，即为此公式的主合取范式。,2018/9/25,39,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,求主析取范式步骤：,PQ的主析取范式为：m3m1m0,(4)对合取项补入没有出现的命题变元，即添加(PP)，再用分配律展开。,方法2：用求范式的方法来求,(1)化归为析取范式。,(2)除去析取范式中所有永假的析取项。,(3)将析取式中重复出现的合取项和相同的变元合并。,PQ的主合取范式为：M2,PQ的主析取范式为：m3m2m1,PQ的主合取范式为：M0,PQ的主析取范式为：
30、m1,PQ的主合取范式为：M3M2M0,2018/9/25,40,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,求主合取范式步骤：,例：求下列公式的主析取范式,(4)对合取项补入没有出现的命题变元,即添加(PP),再用分配律展开.,1) (PQ)(PR)(QR),(1)化归为合取范式,(2)除去合取范式中所有永真的合取项。,(3)将合取式中重复出现的析取项和相同的变元合并。,例：求(PQ)R的主合取范式.,2) P(PQ)(QP),2018/9/25,41,1.7对偶与析取范式和合取范式(范式),第一篇数理逻辑第一章命题逻辑,A：有三个变元，if：A m1m2m3 ，则
31、,方法3：由主析取范式求主合取范式,A：有两个变元，if：Am1m2，,则AM0 M3,AM0M4M5M6M7,2018/9/25,42,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,一、推理的形式结构,推理是由已知命题得到新命题的思维过程。,前题：已知命题,定义：设A1,A2,An，B都是命题公式，如果A1A2AnB,注：由前提推出的结论是否正确与诸前题的排列次序无关。,判断一个推理是否正确的方法有四种：,(1)真值表演算 (2)直接证明 (3)间接证明,推理=前提+结论,结论：新命题,为重言式，则称从前提A1,A2,An推出B。A1A2AnB，,称A1,A2,An为前提集合。,20
32、18/9/25,43,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,1)真值表演算,判断A1A2AnB是否为重言式。,if：B亦有真值1 ，则推理正确。Or看真值为0的行，if：在每,2)直接演算法,判断下列推理是否正确？,例1：若a能被4整除，则a能被2整除。 a能被4整除，故a能被2整除。,在真值表中找出所有A1,A2,An的真值为的行，对这样的行，,一个这样的行中，A1,A2,An的为真值中至少有一个 为0，则,推理正确。,看书p41例1,2018/9/25,44,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,解：P：a能被4整除，Q：a能被2整除,判断A1A2AnB是否
33、为重言式。,前提：PQ，P，结论：Q,推理形式： (PQ)PQ,例2：下午马芳或者去看电影，或去游泳。她没去看电影，所以她去游泳了。,解：P：马芳去看电影，Q：马芳去游泳,前提：PQ，P 结论：Q,推理形式：(PQ)PQ,2018/9/25,45,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,例3：若下午温度超过30度，则王小燕必去游泳；若她去游泳，她,解：P：下午温度超过30度,Q：王小燕必去游泳，R：王小燕去看电影,前提：PQ，QR,定义：自然推理系统由三部份组成,1)字母表2)合式公式3)推理规则,其中字母表为：a)命题变元符号：P,Q,R,不去看电影。所以若王小燕去看电影，下午
34、气温必不超过30度。,结论：RP,2018/9/25,46,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,b)联结词符号:, c)括号与逗号:( ) ,推理规则:,1o：前提引入规则,2o：结论引入规则,3o：置换规则,4o：假言推理规则：AB,AB,5o：化简规则：ABB,6o：附加规则：AAB,7o：拒取式规则：AB,BA,9o：析取三段论规则：AB, BA,8o：假言三段论规则：AB, BCAC,10o：构造性二难规则：AB,CD,ACBD,2018/9/25,47,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,在自然推理系统中构造下列推理证明,例4：前提：PQ，QR，P
35、S，S 结论：R(PQ),证明PS 前提引入,S 前提引入,P 拒取式,PQ 前提引入,Q析取三段论,QR 前提引入,R 假言推理规则,R(PQ),2018/9/25,48,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,例5：前提：PQ，PR，QS 结论：SR,证明PR 前提引入,PQRQ 附加规则,QS 前提引入,RQRS 附加规则,PQRS 假言三段论,PQ 前提引入,RS,2018/9/25,49,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,二、运算和推理,1、A蕴含B,证明AB为重言式，可用前件或后件方法,2、A、B两公式的等价,(1)比较真值表；(2)AB为重言式,
36、4、推理,3、求主析(合)取范式,(1)真值表；(2)步骤法；(3)互换法,(1)真值表；(2)直接法；(3)间接法,2018/9/25,50,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,PC规则：if:证明A1,A2,An BC，可引入附加前提 B，去推出C。,例：证明A(BC)，DA，B DC,证明D 附加前提引入,DA 前提引入,A 析取三段论,B 前提引入,A(BC) 前提引入,BC 假言推理,C 假言推理,D C,则推理正确。,2018/9/25,51,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,3)间接证明(归谬法),A1,A2,AnB，若B可推出矛盾，如AA则
37、说明推理正确。,例1： PQ，(PQ)P,证明PQ 前提引入,Q 假言推理规则,P 附加前提,(PQ) 前提引入,PQ 徳摩根律,Q,QQ (矛盾),否则错误。,2018/9/25,52,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,例2：证明CB，AB AC,证明(AC)附加前提引入,A I7 C I8,AB 前提引入,CB 前提引入,B析取三段论,B 假言推理,BB 矛盾,例3：设有下列情况，结论是否有效？,2018/9/25,53,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,(1）或者天晴，或者下雨。,（2）如果是晴天，我去看电影。,（3）如果我去看电影，我就不看书。,
38、结论：如果我在看书则天在下雨。,2018/9/25,54,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,第一章：小结,一、基本概念和术语,命题，原子命题，复合命题，命题常元，命题变元，公合式公式,否定词、析取词、合取词、条件词，双条件，优先顺序,对偶式，简单析取式，简单合取式，析取范式，合取范式，,真值表，重言式，矛盾式，可满足式，蕴含式，等价式，逆反式,小项，大项，主析取范式，主合取范式,2018/9/25,55,1.8命题逻辑推理理论,第一篇数理逻辑第一章命题逻辑,二、运算和推理,1、A蕴含B,证明AB为重言式，可用前件或后件方法,2、A、B两公式的等价,(1)比较真值表；(2)A
39、B为重言式,3、求主析(合)取范式,(1)真值表；(2)步骤法；(3)互换法,4、推理(1)真值表；(2)直接法；(3)间接法,2018/9/25,56,2.1谓词的概念与表示,第一篇数理逻辑第二章谓词逻辑,在命题演算中，把简单命题作为基本研究单位而不在进行分解，,例1：所有人总是要死的。,P：所有人总是要死的,PQR,显然此不是命题逻辑的重言式。,这使得命题逻辑有很大的局限性。有些很简单的推理形式，如典,型逻辑三段论，用命题演算的推理理论无法论证。,苏格拉底是人。,所以苏格拉底是要死的。,Q：苏格拉底是人,R：苏格拉底是要死的,2018/9/25,57,2.1谓词的概念与表示,第一篇数理逻辑
40、第二章谓词逻辑,造成上述的原因在于我们没有对简单命题自身内部特征作进一,例2：熊猫是动物。,P：熊猫是动物,P和Q不能揭示这两个命题的共性,对简单命题的成份、结构和简单命题间的共性等作进一步的,步的分析，无法揭示前提和结论在形式结构方面的联系，所以,不能认识到这种推理的形式和规律。,狗是动物。,Q：狗是动物,分析，这正是一阶逻辑所要研究的问题。一阶逻辑又称一,谓词逻辑或谓词逻辑。,2018/9/25,58,2.1谓词的概念与表示,第一篇数理逻辑第二章谓词逻辑,一、个体词和个体域,定义：,个体常元：表示具体、特指的个体词。常用小写字a，b，c等表示。,个体变元：表示抽象的、泛指的或一定范围个体词
41、。常用小写字,个体域：个体变元的取值范围。常用D表示。,注1：个体域可以是有限的或无限的。,个体：可以独立存在的事物。,母x，y，z等表示。,注2：全总个体域：最大的个体域包含整个宇宙全体事物。,注3：如果无特别声明个体域均为全总个体域。,2018/9/25,59,2.1谓词的概念与表示,第一篇数理逻辑第二章谓词逻辑,一般句子是有主语和谓语两部份组成。,个体通常是主语，可以是抽象的或具体的。,如：小张，小王，熊猫，计算机等。,谓词：用来刻划一个个体的性质或多个个体之间的关系的词。,元数：谓词中包含个体的数目。,谓词常元：表示有具体意义的性质或关系的谓词。,谓词变元：表示有抽象的或泛指的性质或关
42、系的谓词。,从数学角度来讲：谓词是一个以D为定义域，以0，1为值域的函数。,0元谓词：将不带个体变元的谓词。,2018/9/25,60,2.1谓词的概念与表示,第一篇数理逻辑第二章谓词逻辑,一元谓词：表示一个个体的性质。,二元谓词：表示两个个体之间关系。,n元谓词：表示n个个体之间关系。,用谓词表达式写出下列命题,元数：谓词中包含个体的数目。,例1：只有2为素数，4才是素数。,解：一元谓词F(x):x为素数,a=2，b=4 F(a)F(b),例2：如果5大于4，则4大于6,解：二元谓词G(x,y)：xy,2018/9/25,61,2.2命题函数与量词,第一篇数理逻辑第二章谓词逻辑,定义：简单命
43、题函数：由一个谓词，一些个体变元组成的表达式。,复合命题函数：由一个或n个简单命题函数以及逻辑联结词组成的表达式。,仅在命题中分析出个体或谓词后，还不足以表达逻辑三段论和日,定义:量词：表示数量的词。分为全称量词和存在量词。,全称量词：表示“所有的”，“任意的”，“每一个”，“凡”等的词。记为：,x A(x) or (x) A(x)：表示个体域中的所有个体都有性质A。,存在量词：表示“存在着”，“有某些”，“至少存在一个”等的词。记,常生活中的各种问题。因为还缺少表示个体常元与变元之间的数,量关系。,“”， x表示个体域中的所有个体，x称为全称变元。,为：“”，x表示存在个体域中的个体，x为存
44、在性变元。,2018/9/25,62,2.2命题函数与量词,第一篇数理逻辑第二章谓词逻辑,x A(x) or (x) A(x)：表示存在个体域中的某个体都具有性质A。,量词也称为对个体所附加的约束词。,例1：设F(x)：表示x会飞，D为鸟集合,例2：设G(x)：x为白的，D：为菊花集合,注：带有量词的命题函数必须确定其个体域；否则无法准确表达命题含义。,x A(x) or (x) A(x)：表示个体域中的所有个体都有性质A。,定义：特定谓词,x F(x)：x F(x)：,x G(x)：x G(x)：,If：所有命题函数的个体域为全总个体域，对每个个体的性质要特,别指明。为了讨论个体域中某部分个
45、体的性质，引入刻划这部分个,体的谓词。,2018/9/25,63,2.2命题函数与量词,第一篇数理逻辑第二章谓词逻辑,一般对全称量词，此特性谓词常作蕴涵前件。,如x A(x)可写成x (M(x)A(x)，M(x)为 A(x)的特性谓词。,一般对存在量词，此特性谓词常作合取项。,如x H(x)可写成x (M(x)H(x)，M(x)限制H(x)的变化。,三、一阶逻辑命题中的符号化问题,1、一元谓词符号化,例1：凡人都有呼吸。,解：F(x)：x为人，H(x)：x呼吸x (F(x)H(x),例2：有人用左手写字。,2018/9/25,64,2.2命题函数与量词,第一篇数理逻辑第二章谓词逻辑,解：F(x
46、)：x为人，G(x)：x用左手写字 x (F(x)G(x),例3：小李是大学生和运动员。,解：L(x)：x是大学生，P(x)：x是运动员 a：小李,L(a)P(a),注：在命题符号化时，如果没有特别指明个体域，则采用全总体域。,将下列命题符号化，并指明其真值。,例1：所有人都长黑头发。,解：M(x)：x为人，F(x)：x长黑头发,例2：每个学生都要参加考试。,x (M(x)F(x),2018/9/25,65,2.2命题函数与量词,第一篇数理逻辑第二章谓词逻辑,解：M(x)：x为学生，F(x)：x要参加考试 x (M(x)F(x),例3：任何整数或是正的或是负的。,解：P(x)：x为整数，Q(x)：x是正数 R(x)：x是负数,x (P(x)(Q(x)R(x),例4：在美国留学的学生未必是亚州人。,
