命题逻辑基本概念.ppt

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

1、第一部分 数理逻辑,传统逻辑与数理逻辑：逻辑一词源于希腊文，意思指：词、思想、理性、规律等。逻辑学研究的是：判别一个推理过程是否正确的标准。数理逻辑也叫符号逻辑，即用人工符号来书写逻辑法则，它是一门涉及数学、逻辑学、哲学等几门学科的横向交叉学科。,传统逻辑用以表示命题形式和推理形式的是自然语言的某些词语，而自然语言是多义的，不适于用以精确地表示各种命题形式和推理形式。数理逻辑克服了这方面的局限性，以其特有的人工符号来书写逻辑法则，突出体现了方便、精确的优势。,数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题

2、逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。,一、主要内容,命题逻辑基本概念命题逻辑等值演算命题逻辑推理理论一阶逻辑基本概念一阶逻辑等值演算与推理理论,二、学习要求,深刻理解命题、联结词、复合命题、命题公式、等值式、等值演算、推理及证明等概念熟练进行等值演算与构造证明,第一章 命题逻辑基本概念,本章的主要内容：命题、联结词、复合命题命题公式、赋值、命题公式的分类本章与后续各章的关系本章是后续各章的准备或前提,1.1 命题与联结词,一、命题及其分类1命题与真值,命题：能判断真假的陈述句。,感叹句、疑

3、问句、祁使句都不是命题,真值：用真值来描述命题是“真”还是“假”。分别用“1”和“0”或“T”和“F”表示。,模糊的陈述句不是命题 例如：他很高 自相矛盾的句子不是命题 例如：我正在说谎（悖论）,命题是陈述句，但陈述句不一定都是命题,悖论就是自相矛盾的句子，如果承认它是正确的，则可以推出它是错误的。而如果承认它是错误的，又能推出它是正确的。,关于悖论,如果理发师的头由别人给他理,也就是说理发师自己不替自己理发,那么按照规定,这位理发师应该给自己理发。另一方面,如果理发师的头由自己理,那么按照规定,理发师不能给自己理发。,例：一个村上，有一个理发师公开宣布他给而且只给村子中所有自己不替自己理发的

4、人理发。现在要问：谁给这个理发师理发？,这就是由19世纪数学家希尔伯特提出的著名的“理发师悖论”。这一悖论的提出，指出康托尔集合论的理论基础的不足之处，促进了集合论的发展。所以悖论的提出并不可怕，它只是表明数学理论的基础缺乏完备性。只要完善理论基础，就可以避免悖论的产生。,(1）是有理数.（2）2+5 7.（3）x+5 3.（4）你去教室吗？（5）这个苹果真大呀！（6）请不要讲话！（7）明年元旦下雪.,解：（1）是假命题，（2）是真命题.（7）是命题，它的真值现在不知道，到明年元旦就知道了。可见命题的真值是客观存在的，不以我们是否知道而改变。,例：下列句子中哪些是命题？,（1）判断一个语句是否

5、为命题，首先看是否为陈述句，再看其真值是否唯一。（2）“能判断真假”并不同于“已知真假”。,注意：,2.命题的分类,（1）简单命题（也称原子命题）由简单句形成的命题。（2）复合命题：由一个或几个简单命题通过联结词的联接而构成的命题。,例：李明既是三好学生又是足球队员。张平或者正在钓鱼或者正在睡觉。如果明天天气晴朗，那么我们举行运动会。,3.简单命题符号化（1）用小写英文字母p，q，r，pi，qi，ri（i1）表示简单命题。（2）用“1”表示真，用“0”表示假,例如：令 p：是有理数，则p的真值为0。q：2+5=7，则q的真值为1。,二、联结词与复合命题,1否定式与否定联结词“”定义1.1：设p

6、为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p 为真当且仅当p为假。,2合取式与合取联结词“”,定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作pq，称作合取联结词，并规定pq为真当且仅当p与q同时为真。,例 将下列命题符号化：（1）吴颖既用功又聪明。（2）吴颖不仅用功而且聪明。（3）吴颖虽然聪明，但不用功。（4）张辉与王丽都是三好生。（5）张辉与王丽是同学。,（1）-（3）说明描述合取式的灵活性与多样性（4）-（5）要求分清联结词“与”联结的复合命题与简单命题,3.析取式与析取联结词“”,定义1.3：设

7、p,q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假。,例：将命题“他可能是100米或400米赛跑的冠军。”符号化。,解：令 p：他可能是100米赛跑冠军；q：他可能是400米赛跑冠军。,则命题可表示为pq。,设p、q是两个命题，p排斥或（不可兼或）q是一个复合命题，记作pq。,令p：今天晚上我在家看电视。q：今天晚上我去剧场看戏。命题可表示为p q，或者表示为（pq(pq)。,例：今天晚上我在家看电视或去剧场看戏。,例 将下列命题符号化：（1）2或4是素数。（2）2或3是素数。（3）4或6是素数。（4）小元元只能拿一个苹果或一个

8、梨。（5）王小红生于1975年或1976年。,（1）-（3）为相容或（4）-（5）为排斥或,4.蕴涵式与蕴涵联结词“”,定义1.4：设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假。,（1）pq的逻辑关系：p为q的充分条件，q为p的必要条件（2）“如果p,则q的不同表述法很多：若p，则q；只要p，就q；p仅当q；只有q 才p；除非q,才p;除非q，否则非p；,说明：,下例有助于理解蕴涵式真值表：,例：一位父亲对儿子说：“如果我去书店，就一定给你买本儿童画报。”问：什么情况下父亲食

9、言？,解：可能情况有四种：(1)父亲去了书店，给儿子买了儿童画报。(2)父亲去了书店，却没给儿子买儿童画报。(3)父亲没去书店，却给儿子买了儿童画报。(4)父亲没去书店，也没给儿子买儿童画报。显然，(1)、(4)父亲没有食言，(3)与父亲的许诺没有抵触，当然也没有食言，只有(2)算食言，而这种情况正好对应蕴涵式为假的“前件真后件假”的条件。,例：用符号形式表示下列命题。(1)如果明天早上下雨或下雪,那么我不去学校。(2)如果明天早上不下雨且不下雪,那么我去学校。(3)如果明天早上不是下雨又下雪，那么我去学校。(4)只有当明天早上不下雨且不下雪时,我才去学校。,解:令 p：明天早上下雨；q：明天

10、早上下雪；r：我去学校。(1)（pq）r；(2)（p q）r；(3)(pq）r；(4)r（p q）,练习：令p,q,r,s代表以下命题：p：我在午饭前写完了计算机程序；q：我要在下午打网球；r：阳光明媚；s：湿度很低。给出以下句子的符号化形式：(a)如果阳光明媚，那么我要在下午打网球；(b)在午饭前写完了计算机程序是我在下午打网球的必要条件；(c)湿度很低和阳光明媚是我在下午打网球的充分条件。,例：设p：天冷，q：小王穿羽绒服，将下列命题符号化：（1）只要天冷，小王就穿羽绒服。（2）因为天冷，所以小王穿羽绒服。（3）若小王不穿羽绒服，则天不冷。（4）只有天冷，小王才穿羽绒服。（5）除非天冷，小

11、王才穿羽绒服。（6）除非小王穿羽绒服，否则天不冷。（7）如果天不冷，则小王不穿羽绒服。（8）小王穿羽绒服仅当天冷的时候。,解：（1）,（2）,（3）,（6）符号化为pq 其余的符号化为qp。,5.等价式与等价联结词,定义1.5：设p,q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词，并规定，pq为真当且仅当p与q同时为真或同时为假.,说明：p q的逻辑关系为p与q互为充分必要条件。,例：非本仓库工作人员，一律不得入内。,解：令 p：某人是仓库工作人员；q：某人可以进入仓库。则上述命题可表示为pq。,6.逻辑联结词与自然语言中联结词的关系：,否定：不是，没有，非，

12、不。合取：并且，同时，和，既又，不但而且，虽然但是。析取：或者，或许，可能。蕴涵：若则，假如那么，既然那就，倘若就，只要就，只有才，。等价：当且仅当，充分必要，相同，一样，。,同级按先出现者先运算。若有括号时，先进行括号内运算。,7.联结词的运算顺序：,例：(qp)q p p,8.复合命题符号化,（1）从语句中分析出各简单命题，将它们符号化；（2）使用合适的命题联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。,例：将下列命题符号化：（1）派小王或小李出差。（2）我们不能既划船又跑步。（3）如果你来了，那么他唱不唱歌将看你是否伴奏而定。（4）如果李明是体育爱好者，但不是文艺爱好者，那么

13、李明不是文体爱好者。（5）假如上午不下雨，我去看电影，否则就在家里看书。,解（1）令p：派小王出差；q：派小李出差。命题符号化为pq。,（2）令p：我们划船；q：我们跑步。则命题可表示为(pq）。,（3）令p：你来了；q：他唱歌；r：你伴奏。则命题可表示为 p（qr）,（4）令p：李明是体育爱好者；q：李明是文艺爱好者。则命题可表示为（p q）（p q）,（5）令p：上午下雨；q：我去看电影；r：我在家看书。则命题可表示为（p q）（pr）。,练习 1.判断下列语句哪些是命题，若是命题，则指出其真值。（1）只有小孩才爱哭。（2）X+6=Y（3）银是白的。（4）起来吧，我的朋友。,(是 假),(

14、不是),(是 真),(不是),2 将下列命题符号化（1）我看见的既不是小张也不是老李。,解 令p：我看见的是小张；q：我看见的是老李。,则该命题可表示为pq,（2）如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。,解 令 p：他晚上做完了作业；q：他晚上有其它的事；r：他看电视；s：他听音乐。则该命题可表示为（pq）（rs）,1.2 命题公式及其赋值,一、命题变项与合式公式1命题变项（或命题变元）（1）命题常项 真值惟一确定的简单命题（2）命题变项 真值可以变化的陈述句（3）常项与变项均用p,q,r,pi,qi,ri,等表示.,2合式公式（简称公式）,定义1.6 合式公式的递归定义：

15、（1）原子合式公式（单个命题变项）（2）若A是合式公式，则(A)也是合式公式（3）若A,B是合式，则(AB),(AB),(AB),(AB)也是合式公式（4）只有有限次地应用（1）-（3）形成的符号串才是合式公式,例：下列符号串是否为命题公式。（1）p(qpr）；（2）（pq）（qr）,解：（1）不是命题公式。（2）是命题公式。,合式公式的层次,定义1.7（1）若公式A是单个的命题变项，则称A为0层合式.（2）称A是n+1(n0)层公式是指下面情况之一：(a)A=B,B是n层公式；(b)A=BC,其中B,C分别为i层和j层公式，且n=max(i,j)；(c)A=BC,其中B,C的层次及n同(b)

16、；(d)A=BC,其中B,C的层次及n同(b)；(e)A=BC,其中B,C的层次及n同(b).（3）若公式A的层次为k,则称A为k层公式.,例如：公式A=p,B=p,C=pq,D=(pq)r,E=(pq)r)(rs),分别为0层，1层，2层，3层，4层公式.,二、公式的赋值（或解释）与真值表,1.公式的赋值定义1.8（1）赋值（解释）设 p1,p2,pn是出现在公式A中的全部的命题变项，给p1,p2,pn各指定一个真值，称为对A的一个赋值或解释。,（2）成真赋值 若指定的一组值使A的真值为1，则称这组值为A的成真赋值。（3）成假赋值若使A的真值为0，则称这组值为A的成假赋值。,例如，000,0

17、10,101,110是(pq)r的成真赋值，而001,011,100,111是成假赋值.,2.公式的类型,定义1.9：（1）重言式（也称永真式）在各种赋值下取值均为真。（2）矛盾式（也称为永假式）在各种赋值下取值均为假。（3）可满足式（不是矛盾式的公式）。,判断(pp)q,(pp)q,pq的类型？,问：（1）如何判断公式的类型？（2）如何求出公式A的全部成真与成假赋值？,答案：重言式、矛盾式、可满足式.,3真值表,定义1.10：A的真值表 A的取值情况列成的表。,例：写出下列公式的真值表A=(pq)rB=(qp)qpC=(pq)q,A的真值表,从上表看出A的成真与成假赋值及它的类型,B的真值表

18、,从表看出B是哪种类型公式？,C的真值表,C是哪种类型?,第一章 小结,1主要内容命题、真值、命题的分类、命题符号化联结词,及复合命题符号化命题公式及层次公式的类型真值表及应用,深刻理解各联结词的逻辑关系会求复合命题的真值熟练地将复合命题符号化准确地求公式的真值表，并用它求公式成真与成假赋值及判断公式类型,2要求,练习：1将下列命题符号化（1）豆沙包是由面粉和红小豆做成的.（2）苹果树和梨树都是落叶乔木.（3）王小红或李大明是物理组成员.（4）王小红或李大明中的一人是物理组成员.（5）由于交通阻塞，他迟到了.（6）如果交通不阻塞，他就不会迟到.（7）他没迟到，所以交通没阻塞.（8）除非交通阻塞

19、，否则他不会迟到.（9）他迟到当且仅当交通阻塞.,提示：(1)分清复合命题与简单命题；(2)分清相容或与排斥或；(3)分清充分与必要条件及充分必要条件。,答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）排斥或设p:交通阻塞，q:他迟到（5）pq,（6）pq或qp（7）qp 或pq,（8）qp或pq（9）pq 或pq可见（5）与（7），（6）与（8）等值,2p:2是素数；q:北京比天津人口多；r:美国的首都是旧金山。求下面命题的真值（1）(pq)r（2）(qr)(pr)（3）(qr)(pr)（4）(qp)(pr)(rq),答案：真值分别为0，1，0，0,3用真值表判断下面公式的类型（1）pr(qp)（2）(pq)(qp)r（3）(pq)(pr),提示：按层次写真值表，由最后一列判类型。,答案：（1）为矛盾式，（2）为重言式，（3）为可满足式,作 业：,习题一1，4，8，11，12，14，15，19（1，2，3，6），20（1，3）21（2），24，25,