数理逻辑12.ppt

《数理逻辑12.ppt》由会员分享，可在线阅读，更多相关《数理逻辑12.ppt（624页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 数理逻辑Mathematical Logic 自我介绍v杨磊v生物数学教研室v外语学馆411v手机:15244775691vQQ:4064534562v运筹学v最优化方法v网络生物医学资源v生物信息学软件3v数理逻辑：离散数学的分支v离散数学：计算机科学的核心基础课程，它以离散量为研究对象。v数学分析：(微积分)以连续函数为主要研究对象，属于连续型数学。4v计算机软件和硬件都属于离散结构，必然大量使用离散数学，只能处理离散的或离散化了的数量关系v(0,1)v离散数学在计算机领域有着广泛的应用v数据结构v操作系统v编译原理v人工智能v程序设计5离散数学数理逻辑集合论图论代数结构组合数学6数理逻

2、辑 Mathematical Logic v数理：Mathematical 数学理论v逻辑：Logic7什么是逻辑v逻辑通常指人们思考问题，从某些已知条件出发推出合理的结论的规律。v逻辑学：一门研究思维形式及思维规律的科学。v逻辑学主要研究对象：推理形式。8逻辑学现代逻辑古典逻辑传统逻辑数理逻辑9什么是数理逻辑v字面含义：数学理论的逻辑。v广义理解：用数学方法研究演绎规律的学科。v狭义理解：用数学方法研究数学中演绎规律的学科。v研究对象：推理过程的正确性标准。10什么是数理逻辑v更深入的理解：就是采用数学的方法来研究思维形式的逻辑结构及其规律的一门科学。v所谓数学的方法就是用一套符号(即人工符

3、号语言)的方法。11数理逻辑与传统逻辑的区别v1.使用一整套符号语言，从而简化了推理形式。v2.借助人工符号语言，使整个推理形式化。v3.具有系统性。12数理逻辑的历史v数理逻辑的创始人：莱布尼兹 贡献：把数学引入形式逻辑；v布尔 贡献：1847年实现了命题演算；v弗雷格v贡献：1879年建立了第一个谓词演算系统；13v皮尔斯 贡献：在著作中引入了逻辑符号。现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科14课程教材vKenneth H.Rosen著的Discrete Mathematics and Its Applicationsv离散数学领域的经典教材,全世界几乎所有知名的院校都曾

4、使用.v离散数学 左孝凌 刘永才 上海科学技术文献出版社。v国内经典著作中内容最全的一本。1516学习本课程的目的v很多专业课的先修课 离散数学后继课程有：数据结构、人工智能、数据库、操作系统、计算机网络等。v培养学生抽象的思维和逻辑推理能力和创新能力v离散数学可以帮助学生提高数学素质,提高创造力v专业核心课程，考研、计算机等级考试、程序员考试的考试科目17学习本课程的方法v课程特点 内容杂，概念多，定理多，很抽象，给学习带来一定难度v学习方法 强调：逻辑性、抽象性 注重：概念、方法与应用18本课程主要内容v第一章 逻辑、集合和函数v命题逻辑、谓词逻辑、逻辑等价v集合、集合运算v函数、函数增长

5、19v第二章 算法、整数和矩阵v算法、搜索算法v整数和除法(素数、最大公约数、最小公倍数、模运算等)、整数和算法v矩阵v第三章 数学推理v证明方法、数学归纳法、递归算法等v第四章 关系v关系及其性质、n元关系及应用、关系的表示20第一章 逻辑、集合和函数Chapter 1 Logic、set and function21命题逻辑Propositional Logic22命题(Proposition)vDefinition:A declarative sentence that is either true or false,but not bothv定义：命题是一个或真或假的陈述句，但不能既真

6、又假vNote:陈述句 或者真 或者假23命题满足的条件v(1)命题的语句形式：陈述句v(2)非命题语句：疑问句、命令句、感叹句、非命题陈述句(悖论语句)v(3)命题所表述的内容可决定是真还是假，不能不真又不假，也不能又真又假。24命题的真值v命题具有两种可能的取值(又称真值)，为真或为假，并且只能取其一。v命题真值(Truth Values)的表示：v 真：T、1；假：F、0v因为命题只有两种取值，所以这样的命题逻辑称为二值逻辑。25命题语句真值确定的几点说明：v1、时间性v2、区域性v3、标准性v注意：注意：严格地说，含有可变时间、地点、人物的语句不是命题，除非假定了一个确定的时间、地点、

7、人物。26Example(1)The sun is bigger than earth.(太阳比地球大)-Proposition (TRUE)(2)The integer 9 is prime.(整数9是素数)-Proposition (FALSE)(3)This statement is false.(这个陈述是错误的)-Not a proposition27(4)Please open the book.(请打开课本)-Not a proposition(5)What time is it？(现在几点了？)-Not a proposition(6)x+1=2.-Not a proposit

8、ion28下列句子中那些是命题v(1)2 是无理数.v(2)2+5 8.v(3)x+5 3.v(4)你有铅笔吗？v(5)这只兔子跑得真快呀！v(6)请不要讲话！v(7)我正在说谎话.v(3)(7)not a proposition29命题表示法命题常用字母表示。习惯上用来表示命题的字母是p、q、r、s 30命题的分类v简单命题v复合命题31简单命题 简单命题又称原子命题，由最简单的陈述句构成的命题(该句不能再分解成更简单的句子)。例:2是个素数32复合命题复合命题又称分子命题，由若干个原子命题构成的命题。例:ab、bc、ac，是由三个原子命题构成的复合命题。33逻辑运算的概念 命题可以通过逻辑

9、联结词(逻辑运算)构成新的命题-复合命题.复合命题的真值依赖于其中简单命题的真值 逻辑运算符也称为联结词 体现了复合命题中各个原子命题之间的运算关系34逻辑运算符vNegation (NOT)否定vConjunction (AND)合取vDisjunction (OR)析取vExclusive or (XOR)异或vImplication (if then)蕴涵35否定 Negation(NOT)v定义：令p为一命题，则语句“不是p所说的情形。”是另一个命题，称为p的否定。v用p:not p，表示，读作：“非p”v例：p:Today is Tuesday.今天是星期二 p:Today is n

10、ot Tuesday今天不是星期二 不能说今天是星期一、星期三等36v例：找出命题“昨天张三看球赛了”的否定vp：昨天张三看球赛了。vp：并非昨天张三看球赛了。vp：昨天张三没有看球赛。37命题之否定的真值表ppTFFT38合取 Conjunction(AND)v定义：令p和q为命题，用pq表示的命题“p而且q”是这样的一个命题：当p和q均为真时它成真，否则为假。命题pq称为p和q的合取。39vp：小王能唱歌 q：小王能跳舞v合取为：vpq：小王能歌善舞vTrue if and only if both p and q are true.v当且仅当p和q都为真时，pq 才为真40命题合取的真值

11、表pqpqTTTTFFFTFFFF41析取 Disjunction(OR)v定义：令p和q为命题，用pq表示的命题“p或q”是这样的一个命题：它的真值在p和q均为假时为假，否则成真。命题pq称为p和q的析取。v同或 异或42析取的真值表pqpqTTTTFTFTTFFF43v析取中包含两种情况：v同或：两个命题之一成真或两者均成真时，析取成真v异或：两个命题之一成真，析取成真；两者均成真时或两者均假时，析取成假44异或Exclusive or(XOR)v定义：令p和q为命题，p和q的异或，用 表示.vTrue if and only if exactly one of p and q is tr

12、ue.v(当p和q中恰有一个成真时它成真，否则它为假)vp:米卢在西安 q:米卢在北京。v :米卢在西安或者米卢在北京。45v异或表示两个命题不可能同时都成立。v 命题“第一节课上数学或者上英语。”可以解释为：“第一节课上数学而没有上英语或者第一节课上英语而没有上数学。46异或真值表pqTTFTFTFTTFFF47蕴含Implicationv令p和q为命题，蕴含pq是这样一个命题：在p成真而q为假时它为假，否则成真。其中p称为假设(前项、前提)，q称为结论(或后果)48v例：如果缺少水分，植物就会死亡vp：缺少水分vq：植物会死亡vpq：如果缺少水分，植物就会死亡v缺少水分是前提条件vFals

13、e if and only if p is true and q is false.v当且仅当p为真且q为假时，pq为假49蕴含真值表pqpqTTTTFFFTTFFT50蕴含术语v“如果p，那么q”v“p是q的充分条件”v“p蕴含q”“q如果p”v“如果p，q”“q每当p”v“p仅当q”“q是p的必要条件”51vv例：令：P：天气好。Q：我去公园。v1.如果天气好，我就去公园。（充分）v2.只要天气好，我就去公园。（充分）v3.仅当天气好，我才去公园。（必要）v4.只有天气好，我才去公园。（必要）v命题1、2 写成：PQ v命题3、4 写成：QP52逆蕴含Converse of an Impl

14、icationv定义：命题qp称为pq的逆蕴含vFor example:Implication:蕴含If it is raining now,then there are clouds outside.如果现在在下雨，那么外面有很多乌云Converse:逆蕴含If there are clouds outside,then it is raining now.如果外面有很多乌云，那么现在在下雨53逆否命题Contrapositive of an Implication v定义(倒置命题)：pq的逆否命题是命题qpvFor exampleImplication:蕴含If it is rainin

15、g now,then there are clouds outside.如果现在在下雨，那么外面有乌云Contrapositive:逆否If there are not clouds outside,then it is not raining now.如果外面没有乌云，那么现在没下雨vNote:pq 等价于q p54双蕴含Biconditionalv定义：令p和q为命题，双蕴含 是这样一个命题：其真值只有在p和q有同样真值时为真，否则为假。v双蕴含恰在pq和qp均为真时为真。55双蕴含术语v“p当且仅当q”v“p是q的充分必要条件”v“如果p，那么q；反之亦然。”56双蕴含真值表pqTTTT

16、FFFTFFFT57Precedence of Logical Operators逻辑运算符的优先级vPrecedence:v优先级优先级:vFor example:pqr means(pq)r,not p(qr)pqr means(pq)r58v命题是一个或真或假的陈述句，但不能既真又假vNote:陈述句 或者真 或者假v真：T、1；假：F、0v简单命题v复合命题v逻辑运算符v否定：令p为一命题，则语句“不是p所说的情形。”是另一个命题，称为p的否定vp:not p，表示，读作：“非p”59v合取：当p和q均为真时它成真，否则为假。命题pq称为p和q的合取v析取：p和q均为假时为假，否则成真

17、。命题pq称为p和q的析取v异或：当p和q中恰有一个成真时它成真，否则它为假v蕴含：在p成真而q为假时它为假，否则成真。其中p称为假设(前项、前提)，q称为结论(或后果)60v逆蕴含：命题qp称为pq的逆蕴含v逆否命题：pq的逆否命题是命题qpv双蕴含：恰在pq和qp均为真时为真v优先级:61练习题vp:气温在零度以下vq:正在下雪(1)气温在零度以下且正在下雪 pq(2)气温在零度以下但不在下雪 pq62(3)气温不在零度以下，也不在下雪 pq(4)如果气温在零度以下，那么就在下雪 pq(5)气温在零度以下是下雪的充分必要条件 pq63v侦探调查了罪案的四位证人。从证人的话侦探得出的结论是：

18、如果男管家说的是真话，厨师说的也是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都说慌；如果杂役说的是真话，那么厨师说的就是假话。vg：管家说的是真话；c：厨师说的是真话；vy：园丁说的是真话；z：杂役说的是真话；gc (cy)yz zc64命题的符号化v目的：把自然语言的句子翻译成由命题变量和逻辑联结词组成的表达式。v1.首先要明确给定命题的含义。v2.对于复合命题，找联结词，用联结词断句，分解出各个原子命题。v3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。65v说离散数学无用且枯燥无味是不对的。P：离散数学是有用的。Q：离散数学是枯燥无味的。该命题可写

19、成：(PQ)66v人不犯我，我不犯人；人若犯我，我必犯人。P：人犯我 Q：我犯人。该命题可写成：(PQ)(PQ)或写成：PQ67v除非你已满16周岁，否则只要你身高不足4英尺就不能玩过山车vp:你能玩过山车。vr:你身高不足4英尺。vs:你已满16周岁。v(sr)p68必要条件和充分条件v只有 p才 q 必要条件vqpv只要 p 就 q 充分条件vpq69ExamplevYou can access the Internet from campus only if you are a computer science major or you are not a freshman(只有你主修计

20、算机科学或不是新生，才可以从校园内访问因特网)a:you can access the Internet from campus(你可以从校内网访问因特网)c:you are a computer science major(你主修计算机科学)f:you are a freshman(你是个新生)a(cf)70vp:你的车速超过每小时65英里vq:你接到一张超速罚单v1)你的车速没有超过每小时65英里vpv2)你的车速超过每小时65英里，但没接到超速罚单v pq71v3)你的车速若超过每小时65英里，将接到一张超速罚单vpqv4)你的车速不超过每小时65英里，就不会接到超速罚单vpqv5)你车

21、速超过每小时65英里足以接到超速罚单vpq72v6)你接到一张超速罚单，但你的车速没超过每小时65英里vqpv7)只要你接到一张超速罚单，你的车速就超过每小时65英里vqp73将下列命题符号化将下列命题符号化(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.令 p：王晓用功，q：王晓聪明 (1)pq (2)pq (3)qp74(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.令 r:张辉是三好学生，s:王丽是三好学生(4)rs.(5)令 t:张辉与王丽是同学，t 是简单命题.75将下列命题符号化将下列命题符号化v(1)2或4是素数.v(2)2或3是素数.v(

22、3)4或6是素数.vp:2是素数,q:3是素数,r:4是素数,s:6是素数vpr vpqvrs76v小元元只能拿一个苹果或一个梨vp:小元元拿一个苹果，q:小元元拿一个梨v王晓红生于1975年或1976vp:王晓红生于1975年,q:王晓红生于1976年77例例 设 p:天冷，q:小王穿羽绒服 将下列命题符号化 (1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.pqpqpqpqqp qp78例例 求下列复合命题的真值 (1)2+2 4 当且仅当

23、3+3 6.(2)2+2 4 当且仅当 3 是偶数.(3)2+2 4 当且仅当 太阳从东方升起.(4)2+2 4 当且仅当 美国位于非洲.(5)2+2 4 当且仅当3不是奇数.(6)两圆面积相等当且仅当它们的半径相等.它们的真值分别为 1，0，1，0，1,179布尔检索v定义：运用布尔逻辑运算符对检索词进行逻辑组配，表达两个概念之间的逻辑关系的检索。v与(AND)v或(OR)v非(NOT)80v与(AND)：用于匹配包含两个检索项的记录v目的：提高查准率v或(OR)：用于匹配两个检索项之一或两项均匹配的记录v目的：提高查全率v非(NOT)：用于排除某个特定的检索项v目的：提高查准率818283

24、逻辑运算和位运算v计算机用字位表示信息，每个字位有两个可能的值，即0或1。v字位、字节、英文字母、汉字v1byte=8bitsv一个英文字母一个字节，一个汉字两个字节；84vBit意为位或比特，是计算机运算的基础；vByte意为“字节”，是计算机文件大小的基本计算单位；v1字节=8位，1KB=1024字节，MG=1024KB，v1GB=1024MB，1TB=1024GB；85字位运算对应于逻辑联结词vAND：vOR：vXOR：v信息一般用位串来表示，也就是0和1的序列表示。v对位串的运算即可用来处理信息。86字位运算符的真值表xyxyxyx y0000001101101011111087v在长

25、度相同的两个位串上定义按位运算(每个字位分别运算)：vBitwise(按位)ORvBitwise(按位)ANDvBitwise(按位)XOR88求位串01 1011 0110和位串11 0001 1101的按位OR、按位AND和按位XOR。01 1011 011011 0001 110111 1011 1111 按位OR01 0001 0100 按位AND10 1010 1011 按位XOR89模糊逻辑v定义：命题的真值是介于0和1之间的数。v1为真值的命题为真v0为真值的命题为假v“张三是幸福的”真值为0.8；v“李四是幸福的”真值为0.4；v命题的否定：1减去该命题的真值。v“张三不幸福”

26、真值为1-0.8=0.290v命题的合取：两个命题真值的最小值。v“张三和李四都幸福”真值为0.4v命题的析取：两个命题真值的最大值。v“张三或李四幸福”真值为0.891v命题的符号化v目的：把自然语言的句子翻译成由命题变量和逻辑联结词组成的表达式v布尔检索v与(AND)或(OR)非(NOT)v查准率 查全率 查准率v字位运算vAND OR XOR92命题等价 Equivalent propositions 93重言式重言式观察下面真值表PQ(PQ)(PQ)PPFF F TFT F TTF F TTT F Tv可见不论P、Q取值如何，PP 的真值总为真，(PQ)(PQ)的真值总为假。故称PP为

27、重言式(永真式)；称(PQ)(PQ)为矛盾式(永假式)。94 P Q (PQ)P0 0 00 1 01 0 01 1 1公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T可满足公式95v永真(重言)式(Tautology)公式中的命题变量元论怎样指派，公式对应的真值恒为T。v永假(矛盾)式(Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。v可满足公式(Satisfaction)公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。96从上述定义可知三种特殊公式之间的关系：永真式的否定是矛盾式；矛盾式的否定是永真式。永真式一定是可满足式，可满足式

28、不一定是永真式可满足式的否定不一定为矛盾式关系97练习写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。1)G1=()()2)G2=(Q)(Q)(Q)3)G3=(PQ)Q98P Q()()(Q)(Q)(Q)(P Q)Q0 01 0 10 11 0 11 0 1 0 11 11 0 0永真公式永真公式永假公式永假公式可满足公式可满足公式三个公式的真值表如下：99逻辑等价 G1=()()拆分成两个命题，分别令：，是一个永真公式v如果在任意情况下，G与H的真值相同，则称命题G、H是逻辑等价的，记作v命题G和H等价，当且仅当它们真值的两列完全一致100证明等价公式成立的常用方法证明等价公

29、式成立的常用方法v方法1：真值表v方法2：逻辑等价关系101v真值表法对于只含少数变量的命题，可以用手工完成；v涉及n个命题的复合命题的真值表有2n行；n=20，它的真值表就有220，需要计算机编程；vn=1000，它的真值表就有21000行，它是一个超过300位的十进制数，一台计算机在几万亿年之内都不可能完成。v判断两个命题是否等价的另外一个方法是利用逻辑等价关系推导102逻辑等价关系v证明逻辑等价的另外一种方法叫做逻辑等价关系v基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。v基本等价式常叫命题定律。下面是常用的命题定律103设G，H，S是任何的命题，则：基本等价

30、公式1)1:GG G (幂等律幂等律)2:GG G2)3:GH HG (交换律交换律)4:GH HG3)5:G(HS)(GH)S (结合律结合律)6:G(HS)(GH)S4)7:G(GH)G (吸收律吸收律)8:G(GH)G1045)9：G(HS)(GH)(GS)(分配律分配律)10：G(HS)(GH)(GS)6)11：GG(同一律同一律)12：GG 7)13：G(零律零律)14：G8)15：GG1(排中律排中律)9)16：GG0(矛盾律矛盾律)10510)17：(G)G(双重否定律)11)18：(GH)GH (De MoRGan定律)19：(GH)GH。12)20:(GH)(GH)(HG)(

31、等价)13)21：(GH)(GH)(蕴涵)14)E22：GG。(假言易位)15)E23：GG。(等价否定等式)16)E24：(G)(G)G (归谬论)106ABAB A B A B(AB)0011101011001010010101100010107例例.求证吸收律 P(PQ)P证明 P(PQ)(PF)(PQ)(同一律)P(FQ)(分配律)PF (零律)P (同一律)108例例.求证(PQ)(PQ)P证明 (PQ)(PQ)(PQ)(PQ)(蕴含)(PQ)(PQ)(摩根定律)(PQ)(PQ)(对合律)P(QQ)(分配律)PT (排中律)P (同一律)109110例例 证明 p(qr)(pq)r证

32、明 p(qr)p(qr)(蕴涵)(pq)r (结合律)(pq)r (德摩根律)(pq)r (蕴涵)110基本的逻辑等价关系v利用文氏图理解等价关系ABUBUAUAAABAB111v(1)利用文氏图理解等价关系p(pq)=pp(pq)=pv(2)利用自然语言理解等价关系p:张三是学生q:李四是工人(pq):并非张三是学生或李四是工人张三不是学生并且李四不是工人pq112v(3)利用已有的逻辑等价关系，构造其它的等价关系；v复合命题中的一个命题可以用与它逻辑等价的命题替换而不改变复合命题的真值。v逻辑等价的性质自反性 pp对称性 若pq,则qp传递性 若pq,qr,则pr113v由析取的结合律表明

33、pqr是有定义的 因为先析取p和q再和r析取或先析取q和r再和p析取，结果是一样的 同理pqr也是有意义的v推广v p1p2pn p1p2 pn 均有有定义114v德摩根律可以扩展为：(p1p2 pn)(p1p2 pn)115 将P中的联结词换成，换成，若有特殊变元T和F，则将T换成F，F换成T，所得公式称为P的对偶式，记为P*命题公式P的对偶公式116(1)P的对偶 P*=P(2)QR的对偶 (QR)*=QR(3)(PT)Q的对偶 (PT)Q)*=(PF)Q117公式的标准型范式定义(1)命题或命题的否定称为文字(2)有限个文字的析取称为析取式(也称为子句)(3)有限个文字的合取称为合取式(

34、也称为短语)(4)P与P称为互补对。118(1)p、p是文字；(2)pqr是子句，析取式；(3)pqr是短语，合取式。119v一个命题或者其否定既可以是简单的子句，也可以是简单的短语。v因此，不但是文字，也是子句、短语120析取范式与合取范式析取范式与合取范式公式A如果写成如下形式：A1A2.An (n1)其中每个Ai(i=1,2.n)是合取式，称之为A的析取范式。公式A如果写成如下形式：A1A2.An (n1)其中每个Ai(i=1,2.n)是析取式，称之为A的合取范式。121 例 PQ 的析取范式与合取范式：PQ 合取范式 (PQ)(QP)(等价)(PQ)(QP)(蕴涵)PQ 析取范式 (P

35、Q)(PQ)范式定理：对于任意命题公式，都存在与其等价的析取范式和合取范式。122v永真(重言)式v永假(矛盾)式v可满足公式v永真式的否定是矛盾式；矛盾式的否定是永真式v永真式一定是可满足式，可满足式不一定是永真式v可满足式的否定不一定为矛盾式123v如果在任意情况下，G与H的真值相同，则称命题G、H是逻辑等价的，记作v真值表v逻辑等价关系v真值表法对于只含少数变量的命题v基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算v24个基本等价公式124设G，H，S是任何的命题，则：基本等价公式1)1:GG G (幂等律幂等律)2:GG G2)3:GH HG (交换律交换律)

36、4:GH HG3)5:G(HS)(GH)S (结合律结合律)6:G(HS)(GH)S4)7:G(GH)G (吸收律吸收律)8:G(GH)G1255)9：G(HS)(GH)(GS)(分配律分配律)10：G(HS)(GH)(GS)6)11：GG(同一律同一律)12：GG 7)13：G(零律零律)14：G8)15：GG1(排中律排中律)9)16：GG0(矛盾律矛盾律)12610)17：(G)G(双重否定律)11)18：(GH)GH (De MoRGan定律)19：(GH)GH。12)20:(GH)(GH)(HG)(等价)13)21：(GH)(GH)(蕴涵)14)E22：GG。(假言易位)15)E23

37、：GG。(等价否定等式)16)E24：(G)(G)G (归谬论)127v利用文氏图理解等价关系v利用自然语言理解等价关系v利用已有的逻辑等价关系，构造其它的等价关系v逻辑等价的性质v自反性v对称性v传递性128v对偶公式v将P中的换成，换成，T换成F，F换成Tv记为P*v文字:命题或命题的否定v析取式:有限个文字的析取 (也称为子句)v合取式 有限个文字的合取(也称为短语)vP，P不但是文字，也是子句、短语129v析取范式v合取范式130证明(pq)(pq)为永真式 (pq)(pq)(pq)(pq)蕴含(pq)(pq)德摩根定律(p p)(qq)结合律TT 排中律 T131求范式的步骤(1)将

38、公式中的联结词化成由，组成的限定性公式。PQPQ PQ(PQ)(PQ)PQ(PQ)(QP)PQ(PQ)(PQ)132(2)将否定联结词移到命题变量的前面。A(P1,P2,Pn)A*(P1,P2,Pn)(PQ)PQ (PQ)PQ (3)用分配律、幂等律等公式进行整理，使之成为所要求的形式133Examplev求(P(QR)S的合取范式。Solution：(P(QR)S (P(QR)S (P(QR)S P(QR)S (结合律结合律)(PS)(QR)(分配律分配律)(PSQ)(PSR)134 求命题公式求命题公式(pq)p的的合取范式合取范式和和析取范式析取范式。求合取范式求合取范式 (pq)p (

39、pq)p)(p(pq)(消去)(pq)p)(p(pq)(消去)(pq)p)(p(pq)(内移)(pp)(qp)(ppq)(分配律，合取范式)1(qp)(1q)(排中律)1(qp)1 (零律，合取范式)(qp)(同一律，合取范式)135求析取范式 (pq)p (pq)p)(pq)p)(消去)(pq)p)(pq)p)(内移)p(pqp)(吸收律，析取范式)p(ppq)(交换律)p(pq)(幂等律，析取范式)136求(PQ)R的析取范式与合取范式(1)析取范式 (PQ)R(PQ)(QP)R 等价(PQ)(PQ)R 蕴涵 交换律(PQ)(PQ)R 蕴涵(PQ)(PQ)R 德摩根律-析取范式137(2)

40、合取范式 (PQ)R PQ(PQ)(PQ)(PQ)R(PQ)(PQ)R 蕴涵(PQ)(PQ)R 德摩根律(PQR)(PQR)分配律合取范式138v一个命题公式的合取范式或析取范式并不是唯一的。例例 P(QR)是一个析取范式，但它也可以写成 P(QR)(PQ)(PR)(PP)(PR)(QP)(QR)139其它的几个联结词vNAND (与非)p|q(谢菲尔竖)或pqvNOR (或非)pq(皮尔斯箭头)140其它的几个联结词真值表pqp|qpqTTFFTFTFFTTFFFTT141谓词逻辑Predicate Logic142引言v命题逻辑局限性：命题逻辑能够解决的问题是有局限性的。只能进行命题间关系

41、的推理，无法解决与命题的结构和成分有关的推理问题。v例(著名的苏格拉底三段论)v(1)所有的人都是要死的；v(2)苏格拉底是人。v(3)苏格拉底是要死的。143苏格拉底三段论vP：所有的人都是要死的；vQ：苏格拉底是人。vR：所以，苏格拉底是要死的。v 可见，P，Q，R为不同的命题，无法体现三者相互之间的联系。v问题在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间。对此，命题逻辑将无能为力。144vx+1=3是命题吗？v当变量x未知时，不能判断该语句的真值，既不成真也不成假。v本节课将要讲解从这类语句产生命题的方式145v在命题逻辑中，其基本的组

42、成单位是原子命题，并把它看作是不可再分解的；v但是，原子命题实际上还可以做进一步的分析，特别是一些原子命题间常常有一些共同的特征。(谓词逻辑)146v“猫是动物”v“猫”：主词、主语(一般是客体)v“是动物”：谓词(用来描述或判定客体性质、特征或客体之间关系的词项)v“3大于2”v3和2都是客体，而“大于”是谓词。147 x3v语句“x3”由两个部分组成：v第一部分是变量x，即语句的主语，v第二部分为语句的谓词“大于3”，表示主语的一个性质。v可以用P(x)表示语句“x3”。其中P表示谓词“大于3”，x为变量。v一旦给变量x赋值，P(x)就成为命题148Propositional functi

43、on has not a definite truth value.命题函数没有明确的真值Once a value has been assigned to the variable x,P(x)becomes a proposition and has a truth value.当变量x被赋予一个值时，P(x)变为一个有真假值的命题The truth value of P(x)can be determined when x is assigned a value.(The variable x is bound.)当x被指派一个值时，P(x)的真值就能确定了Note149客体vv定义定义

44、：能够独立存在的事物，称为客体，也称为个体。它可以是具体的，也可以是抽象的。通常用小写英文字母a、b、c、.表示。v例，小张、小李、8、a、沈阳、等等都是客体。150客体变元客体变元vv定义定义：用小写英文字母x、y、z.表示任何客体，则称这些字母为客体变元。v注意注意：客体变元本身不是客体。151谓词 定义：谓词用来描述个体的性质或个体间的关系，用大写字母后加括号表示，括号内为客体变元 如果括号内有n个客体变元，称该谓词为n元谓词 用 P(x1,x2,xn)表示n元谓词152Example(1)x is greater than y.P(x,y)(2)x is between y and z

45、.B(x,y,z)例1 涉及两个变量：二元谓词例2 涉及三个变量：三元谓词153 例例：S(x):表示x是大学生。一元谓词 G(x,y)：表示 xy。二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词 注意：S(x)、G(x,y)，B(x,y,z)表示的不是命题，而是命题函数。154命题函数v用 P(x1,x2,xn)表示n元谓词。n元谓词也称简单命题函数v将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。v简单命题函数与复合命题函数统称为命题函数。155例例 给定简单命题函数：A(x)：x身体好 B(x)：x学习好，C(x)：x工作好.则：复合命题函数 A(x

46、)(B(x)C(x)表示如果x身体不好，则x的学习与工作都不会好156论域定义：在命题函数中命题变元的取值范围，称之为论域，也称之为个体域。例：S(x):x是大学生，论域是:人类。论域对命题函数是否成为命题以及命题的真值有很大的影响。例：设Q(x,y)表示“x比y重”，当x，y指人或物时，它是一个命题，但若x，y指实数时，它就不是一个命题。157v例：R(x)表示“x是大学生”，v(1)如果x的论域是在座的全体学生，则R(x)是永真式；v(2)如果x的讨论范围附属中学的学生，那么R(x)是矛盾式；v(3)如果x论域为一个电影院里所有观众，那么对某些观众R(x)为真，对另外一些观众，R(x)为假

47、。158量词vv例：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。v定义：命题中表示对客体数量化的词，称之为量词。159量词的种类v(1)全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。v(2)存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。160全称量词v x P(x)-P(x)is truevfor all values of x in the universe of discourse.v对论域中任意一个x而言，P(x)的真值都为真vFor all x P(x)For every x P(x)

48、v-Universal quantifier 全称量词161v例：“所有的人都是要呼吸的”v用P(x)表示“x是要呼吸的”vxP(x)，其中论域为所有的人。162v例：“本班每个学生都学过微积分”v用P(x)表示“x学过微积分”vxP(x)，其中论域由本班学生组成。v如果论域是所有学生的集合v用S(x)表示“x属于本班”vx(S(x)P(x)163Example:Express the following statement as a universal quantification.All lions are fierce.Solution:Let Q(x)denote the statem

49、ent“x is fierce”.(1)Assuming that the universe of discourse is the set of all lions.(2)Assuming that the universe of discourse is the set of all creatures.Let P(x)denote the statement“x is a lion”.164Solution:Assume that the universe of discourse is .x P(x)=?In general,the universe of discourse is .

50、（当当域域中中的的所所有有元元素素可可以以列列成成 时时，量量化化语语句句 与合取与合取 是等价的）是等价的）165 x P(x)-There exists an element x in the universe of discourse such that P(x)is true.(在论域中存在一个在论域中存在一个x使使P(x)的真值为真的真值为真)For some x P(x);(对某个对某个x,P(x)There is an x such that P(x);(有一个有一个x使得使得P(x)There is at least one x such that P(x);(至少有一个至少有