数理逻辑命题逻辑.ppt

《数理逻辑命题逻辑.ppt》由会员分享，可在线阅读，更多相关《数理逻辑命题逻辑.ppt（84页珍藏版）》请在三一办公上搜索。

1、第一部分 数理逻辑,2,概述:基本概念,逻辑学的分类:辩证逻辑形式逻辑 辩证逻辑以辩证法认识论的世界观为基础的逻辑学 形式逻辑对思维的形式结构和规律进行研究的类似于语法的一门工具的学科,3,概述:基本概念,思维的形式结构 包括概念、判断和推理之间的结构和联系 形式逻辑的侧重点与其说是注重论证本身，不如说注重的是论证形式,形式逻辑的一般格式就是三段论。例：苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。,4,概述:基本概念,传统逻辑和数理逻辑19世纪中叶以前的形式逻辑是传统逻辑19世纪中叶以后发展起来的现代形式逻辑，通常称为数理逻辑,5,什么是数理逻辑,数理逻辑：以数学

2、的方法研究思维规律和推理过程的科学。它首先引进一套符号体系，规定一些规则，导出一些定律，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样，因此数理逻辑又称符号逻辑。数理逻辑是传统逻辑的发展，是现代形式逻辑,6,微积分,力学、机械工程,人类体力劳动自动化,数理逻辑,人工智能、知识工程,脑力劳动自动化,7,数理逻辑,命题逻辑（数理逻辑的基础，以命题为研究对象，研究基于命题的符号逻辑体系及推理规律，也称命题演算）。主要内容：、命题与联结词、命题公式、翻译和真值表、重言式、命题联结词的扩充、范式、命题演算的推理规则和证明方法 谓词逻辑（对命题逻辑的深入研究）。,8,第一章 命

3、题逻辑,1 命题与联结词一、命题1、什么是命题？命题是陈述客观外界发生事情的陈述句。命题或为真或为假的陈述句。特征：陈述句真假必居其一，且只居其一。,1 命题与联结词,9,中国是一个发展中国家。人是由猴进化而来的。早上好！王侯将相，宁有种乎？己所不欲，勿施于人！宇宙是大爆炸形成的。我正在说谎。这道题太难。2、命题的真值。一个命题的真或假称为命题的真值，简称值。由于命题只有真假两个值，所以命题逻辑也称二值逻辑。以T（或1）表示命题的真值为真，F（或0）表示命题的真值为假,1 命题与联结词,EX1：,10,3、命题的分类与表示,分类根据其真值分类：真命题。假命题。根据其复杂程度分类：简单命题或原子

4、命题。复合命题。,1 命题与联结词,11,命题的抽象表示在数理逻辑中，通常用大(小)写字母表示命题，P、Q、R，或用带下标的大写字母Pi、Qi、Ri 或者数字（1）、（2）、。表示命题的符号称为命题标识符，如P、Q、R、Pi、Qi、Ri。EX2：P：4是偶数；Q：煤是白的。P1：离散数学考试，张三和李四都及格了。,1 命题与联结词,12,命题的抽象表示,一个命题标识符如果表示确定的命题，就称为命题常量。如果命题标识符只表示任意命题的位置标志，就称为命题变元。则命题的抽象为：取值为T（或1）或F（或0）的P、Q、R等符号。若P取值T（或1），则表示P为真命题；若P取值F（或0），则表示P为假命题

5、；,1 命题与联结词,13,“复杂命题”,EX3：由简单命题能构造更加复杂的命题期中考试，张三没有考及格。期中考试，张三和李四都及格了。期中考试，张三和李四中有人考90分。如果张三能考90分，那么李四也能考90分。张三能考90分当且仅当李四也能考90分。,1 命题与联结词,14,联结词和复合命题,上述诸如“没有”、“如果那么”等词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题成为简单命题。（命题的分类）复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。,1 命题与联结词,15,1、否定联结词,在 EX3 中

6、，“期中考试，张三没有考及格”。P：“期中考试，张三考试及格了”，设 P 为一个命题，复合命题“非P”称为P的否定式，记为P，“”称为否定联结词。“P”为真当且仅当P为假。,二、命题联结词,1 命题与联结词,16,1、否定联结词,EX4：求“我们班上所有的同学都大于18岁”的否定。P：我们班上所有的同学都大于18岁。P：我们班上所有的同学不都大于18岁。P：我们班上所有的同学都不大于18岁。,1 命题与联结词,17,2、合取联结词,EX4：“期中考试，张三和李四都及格了。”P 代表：“期中考试张三考试及格了”Q 代表：“期中考试李四考试及格了”。设P、Q为两个命题，复合命题“P而且Q”称为P、

7、Q的合取式，记为PQ，“”称为合取联结词。PQ为真当且仅当P 与 Q 为同时为真。,1 命题与联结词,18,3、析取联结词,设P、Q为两个命题，复合命题“P或者Q”称为P、Q的析取式，记为PQ，“”称为析取联结词。PQ为真当且仅当P与Q为中至少有一个为真。,EX4：“期中考试张三或李四中有人考90分。”P 代表：“期中考试张三考了90分”，Q 代表：“期中考试李四考了90分”。,1 命题与联结词,19,“可兼或”与“排斥或”,日常语言中“或”有三种标准用法，EX5：张三或者李四考了90分。第一节课上数学课或者上政治课。去教学楼需要6分钟或8分钟。,差异在于：当构成他们的简单命题都真时，（1）为

8、真，（2）为假。（1）称为“可兼或”，（2）称为“排斥或”，（3）非联结词，表示近似的数。（1）可表示为PQ，（2）却不能。注意：不能见了“或”就表示为PQ。,1 命题与联结词,20,EX6：求“今天下雪且今天下雨”的否定。P：今天下雪。Q：今天下雨。练习：求“今天不下雪且今天不下雨”的否定,1 命题与联结词,21,4、蕴含联结词,EX4：“如果张三能考90分，那么李四也考90分。”P：“张三考90分”。Q：“李四考90分”。设P、Q为两个命题，复合命题“如果P，则Q”称为P对Q的蕴含式，记为PQ，其中又称P为此蕴含式的前件，称Q为此蕴含式的后件，“”称为蕴含联结词。“PQ”为假当且仅当P真而

9、Q假。,1 命题与联结词,22,EX7：如果你今年离散数学考100分，那么就奖励你100元。P：你今年离散数学考100分。Q：奖励你100元。,1 命题与联结词,1,23,pq 的逻辑关系：q 为 p 的必要条件“如果 p，则 q”的不同表述法很多：若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q,才 p 或 除非 q,否则非 p，当 p 为假时，pq 为真常出现的错误：不分充分与必要条件,24,例 设 p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才

10、穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,注意：p q与 q p 等值（真值相同）,pq,pq,pq,pq,qp,qp,qp,qp,25,5、等价联结词,EX4：“张三能考90分当且仅当李四也能考90分。”P：“张三考90分。”Q：“李四考90分。”设P、Q为两个命题，复合命题“P当且仅当Q”称为P、Q的等价式，记为PQ，“”称为等价联结词。PQ为真当且仅当P与Q同时为真或同时为假。,1 命题与联结词,26,“注意”,上述五个联结词来源于日常使用的相应词汇，但并不完全一致，在使用时要注意

11、：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“”。有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间真的假值的关系，而不讨论命题的内容。,1 命题与联结词,27,EX1：铁和氧化合，但铁和氮不化合。如果我下班早，就去商店看看，除非我很累。李四是经管院的学生，他住在312室或313室。,1 命题与联结词,三、复合命题,28,铁和氧化合，但铁和氮不化合。P：“铁和氧化合”Q：“铁和氮化合”则用符号表示:P(Q)如果我下班早，就去商店看看，除非我很累。P：“我很累”Q：“我下班早”

12、R：“我去商店看看”则用符号表示:(P)(QR)或者可以表示为：(P)Q)R),命题公式、翻译和真值表,29,李四是经管院的学生，他住在312室或313室。P：“李四是经管院的学生。”Q：“李四住312室。”R：“李四住313室。”则用符号表示:P(Q(R)(Q)R)或者可以表示为：P(QR)(QR),命题公式、翻译和真值表,30,复合命题,由原子命题经命题联结词可构成各种形式的复合命题，在复合命题中涉及到括号的使用问题，目前均使用圆括号，为减少括号的使用，在此作下列规定：规定5个联结词的结合能力强弱顺序为：“否定”、“合取”、“析取”、“蕴含”、“等价”，即，这五个逻辑运算的优先顺序为、。凡

13、符合此顺序者，括号均可除去。,命题公式、翻译和真值表,31,小结,命题及其符号P、Q、R。构成复合命题的联结词、，以及由联结词构成的复合命题及其真假值。注意：有了命题和命题联结词，为了进一步的研究，今后，将只注重命题的真假值，而并不注意其内容含义，对命题联结词，只承认它由真值表定义，而不理会它的实际含义，这样，就可以在命题与命题联结词的基础上建立起一个形式系统。,32,命题联结词的扩充,不可兼析取（排斥或）“”或“”或“”：设P和Q是两个命题，称P Q为P和Q的不可兼析取。规定：P Q的值为真，当且仅当P、Q的真值不相同时，否则P Q的值为F。其真值表如下：,4命题联结词的扩充,33,不可兼析

14、取,“”有以下性质：P QQ P(P Q)RP(Q R)P(Q R)(PQ)(PR)(P Q)(PQ)(PQ)(P Q)(PQ),4命题联结词的扩充,34,蕴含否定（条件非）,蕴含否定或条件非：设P和Q是两个命题，称P Q为P和Q的蕴含否定或条件非。规定：P Q的值为T，当且仅当P的真值为T，Q的真值为F。其真值表如下：由上表可知：P Q(PQ),4命题联结词的扩充,35,谢佛（与非）,谢佛或与非“”：设P和Q是两个命题，称PQ为P和Q的与非。规定：当且仅当P和Q真值都是T时，PQ为F。其真值表如下：由真值表可得出：PQ(PQ),4命题联结词的扩充,36,与非,“”有以下性质：PP(PP)P(

15、PQ)(PQ)(PQ)PQ(PP)(QQ)PQ(PQ)PQ,4命题联结词的扩充,37,魏泊（或非）,魏泊或称作或非“”：设P和Q是两个命题，称PQ为P和Q的或非 规定：当且仅当P和Q的真值都为F时，PQ的真值为T其真值表如下：由真值表可得出：PQ(PQ),4命题联结词的扩充,38,或非（续）,“”有以下性质：PP(PP)P(PQ)(PQ)(PQ)PQ(PP)(QQ)PQPQ,4命题联结词的扩充,39,是否每个符号串都是命题呢？PQ、PQ什么样的符号串才能表示命题呢？如下命题公式定义的符号串表示的才是命题。,命题公式、翻译和真值表一、命题公式（合式公式或公式）,命题公式、翻译和真值表,40,命题

16、公式的定义,由命题变元经命题联结词可构成命题逻辑公式，亦可叫命题公式或公式。定义1:命题公式是由命题变元和联结词按以下规则组成的符号串原子命题变元本身是一个命题公式；如果P是命题公式，则 P 也是命题公式；如果P、Q是命题公式，则PQ、PQ、PQ和PQ都是命题公式；只有有限次地应用构成的符号串才是命题公式。命题公式是一个按上述法则由命题变元、命题联结词及圆括号组成的符号串或字符串。,命题公式、翻译和真值表,41,下列符号串都是命题公式：,PP(Q)P(P)P(P)P(P)(P(P)(P)(PR),命题公式、翻译和真值表,42,下列符号串是否为命题公式？,PQ PQPQ R,命题公式、翻译和真值

17、表,43,一些注意,定义2是归纳定义，而不是循环定义。（1）是奠基，（2）、（3）是归纳步骤，（4）是界限。如果我们规定联结词运算的优先次序为：、，则，PQR也是命题公式。有了联结词和命题公式概念，我们就可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。,命题公式、翻译和真值表,44,二、命题的翻译,EX1：将下列语句翻译为命题公式他既聪明，又用功。他虽聪明但不用功。张明正在睡觉或游泳。除非他通知我，否则我不参加会议。张明与李强都可以做这件事。,命题公式、翻译和真值表,45,二、命题的翻译,EX2：设P：“李明是男生”；Q：“李明是足球队队员”；R：“李明是班干部”用日常语言叙述下列命题

18、：PQQRPQRPQR,命题公式、翻译和真值表,46,三、指派和真值表,命题公式的真假由其中命题变元的值完全确定。命题公式中所有命题变元的一组确定的取值称为公式的一组真值指派。公式值的确定是按公式中联结词出现的先后次序及括号顺序逐步应用命题联结词的真值表规定而得到的，所有的指派构成的公式的值即组成了此公式的真值表。,命题公式、翻译和真值表,47,EX3：构造(PQ)R的真值表,命题公式、翻译和真值表,48,EX4：构造(PQ)(PQ)的真值表,命题公式、翻译和真值表,49,EX5：构造(PQ)P的真值表,命题公式、翻译和真值表,50,3 等价重言式和蕴含重言式,练习：构造(PQ)(QR)(PR

19、)的真值表,(PQ)(QR)(PR),51,命题公式的类型,定义2：一个公式如果对其所有指派均取值为真，则称此类型公式为永真公式或叫重言式。反之，一个公式如果对其所有指派均取假值，则称此类型公式为永假公式或叫矛盾。定义3：一个公式如果至少存在一个指派使其取值为真，则称此公式为可满足公式。重言式特性重言式的否定是矛盾，矛盾的否定是重言式。两个重言式的合取、析取、蕴含、等价均为重言式。若两个公式的等价是重言式，则此两公式对任何指派必同真假(EX4)。,命题公式、翻译和真值表,52,命题公式的类型,命题公式,可满足公式,永真式（或重言式）,可真可假式,不可满足公式（永假式或矛盾式）,命题公式、翻译和

20、真值表,53,判断下列公式的类型,例 A=(qp)qp,54,例 B=(pq)q,55,例 C=(pq)r,56,3 等价重言式和蕴含重言式,EX1：构造PQ与PQ的真值表,(PQ)(PQ),3 等价重言式和蕴含重言式,57,等价重言式,设A、B为两个命题公式，P1，P2Pn是所有出现于A和B的命题变元，如果对于命题变元P1，P2Pn的任何一组真值指派，公式A和B都相同，即AB是永真式，则称A与B是等价重言式或是等价的（逻辑等价的），记作AB。由上例知：(PQ)(PQ),3 等价重言式和蕴含重言式,58,EX2：证明 PQ(PQ)(QP),两者的真值表相等，故PQ(PQ)(QP)不难验证：P

21、P PP P(PP)Q Q P P QQ,3 等价重言式和蕴含重言式,59,注意：“”，“”的区别和联系：,区别：（1）“”是命题联结词，AB是一个命题公式，该公式取值可以是真，可以是假。（2）“”不是命题联结词，而是公式的等价关系符，AB不代表命题，而表示的是命题A、B有完全相同的真值。联系：AB当且仅当AB是永真式。,3 等价重言式和蕴含重言式,60,等价公式的性质,自反性：即对任意公式A，有AA；对称性：即对任意公式A和B，若AB，则BA；传递性：即对任意公式A和B，C，若AB，BC,则AC。,3 等价重言式和蕴含重言式,61,设P、Q、R是命题变元，下表中列出了24个最基本的等值式:,

22、命题逻辑的基本等式,3 等价重言式和蕴含重言式,62,命题逻辑的基本等式,基本的等值式,3 等价重言式和蕴含重言式,63,命题联结词的归约(完备集),由(PQ)(PQ)(QP)。故可把包含的公式等价变换为包含“”和“”的公式。由PQ PQ，说明包含“”的公式可以变换为包含“”和“”的公式。由PQ(P Q)，PQ(P Q），说明“”和“”可以相互代替、故由“”、“”、“”、“”、“”这五个联结词组成命题公式，必可以由、或、组成的命题公式所代替。故任意命题公式都可由仅包含、或、的命题公式等价代换。,命题联结词的归约,64,定义 在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此

23、联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集,中，由于 pqpq,所以，为冗余的联结词;类似地，也是冗余的联结词.又在,中，由于 pq(pq)，所以，是冗余的联结词.类似地，也是冗余的联结词.,65,定义 设S是一个联结词集合，如果任何n(n1)元命题公式都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.若S1,S2是两个联结词集合，且S1 S2.若S1是完备集，则S2也是完备集.,66,联结词的完备集实例,(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,而,等则不是联结词完备集

24、.,67,等价公式的代入规则与替换规则,代入规则：在等价式中，将某一命题变元(原子)出现的每处用另一个命题公式代入所得到的公式仍是等价式。EX3:求证(PQ)(PQ)为永真式 证：RRT，即RR为永真式现用公式PQ代入上述公式中的命题变元R则得(PQ)(PQ)T故(PQ)(PQ)为永真式。如：在PQ PQ 中，若用公式(SR)代替P，则得到新的等价公式：(SR)Q(SR)Q,3 等价重言式和蕴含重言式,68,替(置)换规则：设A1是命题公式A的子公式，若A1B1，如果将A中的A1用B1来替换得到公式B，则AB。（如果A1是命题公式的一部分，且A1本身也是一个命题公式，则称A1为公式A的子公式）

25、EX4:求证:(PQ)(RQ)(PR)Q证：(PQ)(RQ)(P Q)(RQ)(P Q)(RQ)(PR)Q(PR)Q(PR)Q,3 等价重言式和蕴含重言式,69,“代入规则”和“替换规则”的区别：代入只对永真式适用，而替换可以对任何公式进行；代入必须处处进行，而替换可以处处替换也可以部分替换；代入只针对命题变元进行，而替换则可以针对任何子公式、包括命题变元而进行。,3 等价重言式和蕴含重言式,70,应用举例证明两个公式等值,例 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则

26、）,说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出,71,应用举例证明两个公式不等值,例 证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一 真值表法（自己证）方法二 观察赋值法.容易看出000,010等是左边的成真赋值，是右边的成假赋值.方法三 用等值演算先化简两个公式，再观察.,72,应用举例判断公式类型,例 用等值演算法判断下列公式的类型(1)q(pq)解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0

27、（矛盾律）0（零律）由最后一步可知，该式为矛盾式.,73,例(续),(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？,74,例(续),(3)(pq)(pq)r)解(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些,75,蕴含重言式,设A、B为两个命题公式，当且仅当AB为永真式时

28、，称A永真蕴含B，记作AB。注意：AB与AB的区别:(类似于与的区别)区别：“”是命题联结词。“”是公式的关系符号，表示两个公式之间的关系。“AB”是一个复合命题，它可真可假，而AB表示的命题公式之间的关系，而非命题。联系：AB成立的充要条件是AB为永真式。,3 等价重言式和蕴含重言式,76,蕴含重言式的性质,自反性:即对任意公式A，有AA传递性:即对任意公式A、B和C，若AB，BC，则AC对任意公式A、B和C，若AB，AC，则A(BC)对任意公式A、B和C，若AC，BC，则ABC若AT，AB，则BT,3 等价重言式和蕴含重言式,77,蕴含重言式的定理,定理：设A和B是两个命题公式，AB的充要

29、条件是AB且BA。证明：必要性:若AB，则AB为永真式，因为AB(AB)(BA)故AB和BA必为永真，即AB且BA。充分性：若AB且BA则AB和BA为永真又 AB(AB)(BA)AB为永真式，即AB。,3 等价重言式和蕴含重言式,78,蕴含重言式的证明方法：,真值表法EX6：试证，P(PQ)Q 证明：构造 P(PQ)Q 的真值表故P(PQ)Q永真，所以P(PQ)Q，证毕,3 等价重言式和蕴含重言式,79,蕴含重言式的证明方法：,推导法EX7：P(PQ)Q证明：P(PQ)QP(PQ)Q(PP)(PQ)Q(F(PQ)Q(PQ)Q(PQ)Q(P Q)Q P1 1 P(PQ)Q,3 等价重言式和蕴含重

30、言式,1,80,蕴含重言式的证明方法：,分析法包括两种：前件真推导后真方法假设前件A为T，若能推导出后件也为真。则条件式永真式。后件假推导前件假方法：条件式后件为F，若能推导出前件也为F。则条件式是永真式。,3 等价重言式和蕴含重言式,81,EX8：证明 P(PQ)Q 证明：第一种方法：设P(PQ)为T，则P与(PQ)均为T，由P为T且PQ也为真，知Q必为T。P(PQ)Q 第二种方法：设后件Q为F，此时P有两种可能：若P为T，因设Q为F，则PQ为F，所以P（PQ）为F；若P为F，则P（PQ）为F。故无论P取怎样的值，只要后件Q为F，前件P(PQ)必为F，P(PQ)Q,3 等价重言式和蕴含重言式,82,蕴含式的直观解释:,设P表示“天下雨”，Q表示“马路湿”，则P(PQ)QQ(PQ)P设 P表示“今天下雨”，Q表示“今天刮风”。则 P(PQ)Q,3 等价重言式和蕴含重言式,83,命题逻辑的基本蕴含式,3 等价重言式和蕴含重言式,设P、Q、R是命题变元，下表中列出了16个最基本的蕴含式。,84,基本的蕴含式,命题逻辑的基本蕴含式,3 等价重言式和蕴含重言式,