1命题逻辑基本概念.ppt

《1命题逻辑基本概念.ppt》由会员分享，可在线阅读，更多相关《1命题逻辑基本概念.ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 11.21.2 命题公式及其赋值命题公式及其赋值1.11.1 命题与联结词命题与联结词第一章第一章 命题逻辑的基本概念命题逻辑的基本概念2 21 1、命题及其真值、命题及其真值q数理逻辑研究的中心问题是推理。数理逻辑研究的中心问题是推理。q推理的前提和结论都是表达判断的陈述句。这样，表达判推理的前提和结论都是表达判断的陈述句。这样，表达判断的陈述句构成了推理的基本单位。断的陈述句构成了推理的基本单位。q命题是客观上能判明真假的陈述句。命题是客观上能判明真假的陈述句。作为命题的陈述句所作为命题的陈述句所表达得的判断结果称为命题的真值。当命题为真时，称表达得的判断结果称为命题的真值。当命题为真

2、时，称命命题的真值题的真值为为“真真”；否则，说命题的真值为；否则，说命题的真值为“假假”。用。用T T或或1 1表示表示“真真”，用，用F F或或0 0表示表示“假假”。1.1 1.1 命题命题与与联结词联结词3 3(1)(1)深圳市是广东省省会。深圳市是广东省省会。(2)(2)(3)(3)x x大于大于y y。(4)(4)外星人曾来过地球。外星人曾来过地球。(5)(5)今天是星期二。今天是星期二。(6)(6)(7)(7)请不要吸烟！请不要吸烟！(8)(8)这朵花真美丽啊！这朵花真美丽啊！(9)(9)本命题为假。本命题为假。例例例例 判断下列句子是否为命题。判断下列句子是否为命题。判断下列句

3、子是否为命题。判断下列句子是否为命题。(1)(1)是，假命题是，假命题(2)(2)是，真命题是，真命题(3)(3)不是，无确定的真值不是，无确定的真值(4)(4)是，真值客观存在是，真值客观存在(5)(5)是，真值根据具体情况而定是，真值根据具体情况而定(6)(6)不是，疑问句不是，疑问句(7)(7)不是，祈使句不是，祈使句(8)(8)不是，感叹句不是，感叹句(9)(9)不是，悖论不是，悖论4 42 2、原子命题与复合命题、原子命题与复合命题q无法继续分解的简单陈述句，称为简单命题或无法继续分解的简单陈述句，称为简单命题或原子命原子命题题。q由一个或几个简单命题通过联结词复合而成的命题，由一个

4、或几个简单命题通过联结词复合而成的命题，称为称为复合命题复合命题。q命题一般用大写英文字母表示。表示命题的符号叫命题一般用大写英文字母表示。表示命题的符号叫命命题标识符题标识符。q 例如，用表示例如，用表示“是奇数是奇数”，记作，记作 “：是奇数：是奇数”。5 5q否定联结词q合取联结词q析取联结词q条件联结词q双条件联结词 3 3 3 3、命题联结词、命题联结词、命题联结词、命题联结词6 6定义定义1 1 否定联结词否定联结词q设设为为命命题题，复复合合命命题题非非，叫叫的的否否定式，记作定式，记作。q记号记号 叫叫否定联结词否定联结词。q 为真当且仅当为假。为真当且仅当为假。pp1001q

5、例如，设例如，设：今今天是星期一。天是星期一。q 则则：今今天不是星期一。天不是星期一。q练习，设练习，设：韶关是一个大城市。韶关是一个大城市。q 则则：韶关不是一个大城市。韶关不是一个大城市。7 7 设设，表表示示两两个个命命题题，复复合合命命题题“且且”叫叫命命题题与与的的合合取取，记作记作。记号记号叫叫合取联结词合取联结词。为为真真，当当且且仅仅当当，同同时时为真。为真。定义定义2 2 合取联结词合取联结词pqpq1 11 11 11 10 00 00 01 10 00 000 0使用合取联结词时要注意的两点使用合取联结词时要注意的两点：1、描述合取式的灵活性、描述合取式的灵活性与多样性

6、。自然语言中的与多样性。自然语言中的“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一面一面一面一面”等联结词都可以符号化等联结词都可以符号化为为。2、分清简单命题与复合命题。、分清简单命题与复合命题。8 8例例例例2 2 2 2 将下列命题符号化。将下列命题符号化。将下列命题符号化。将下列命题符号化。(1)(1)吴颖既用功又聪明。吴颖既用功又聪明。(2)(2)吴颖不仅用功而且聪明。吴颖不仅用功而且聪明。(3)(3)吴颖虽然聪明但不用功。吴颖虽然聪明但不用功。(4)(4)张辉与王丽都是三好学生。张辉与王丽都是三好学生。(5)(5)张辉与王丽是同学。张辉与王丽是同学。设设p:p:吴颖

7、用功。吴颖用功。q:q:吴颖聪明。吴颖聪明。r:r:张辉是三好学生。张辉是三好学生。s:s:王丽是三好学生。王丽是三好学生。t:t:张辉与王丽是同学。张辉与王丽是同学。(1)pq(1)pq(2)pq(2)pq(3)qp(3)qp(4)rs(4)rs(5)t(5)t解题要点：解题要点：正确理解命题含义。正确理解命题含义。找出原子命题并符号化。找出原子命题并符号化。选择恰当的联结词。选择恰当的联结词。9 9 设，为二命题，复合命题设，为二命题，复合命题 “或或”称与的析取，称与的析取，记作记作,叫叫析取联结词析取联结词.为为假假，当当且且仅仅当当，均均为为假假。定义定义3 3 析取联结词析取联结词

8、p pq qp pq q1 1 1 11 11 10 01 10 01 11 10 00 00 0 自然语言中的自然语言中的“或或”具有二义性，用它联结的命题有时具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或或和排斥或(排异或排异或)。1010解：解：(1)(1)设设 :小王是跳远冠军小王是跳远冠军.:小王是百米赛跑冠军。小王是百米赛跑冠军。符号化为符号化为:。（相容或）。（相容或）(2)(2)设设 ：小王在宿舍。：小王在图书馆：小王在宿舍。：小王在图书馆。符号化为符号化为:（）（）。（排斥或）。

9、（排斥或）(3)(3)设设：小王是计算机系的学生小王是计算机系的学生。：小王小王是广东人。是广东人。：小王：小王是是湖南人。：小王是三好学生。湖南人。：小王是三好学生。符号化为符号化为:（）（）。例例3 3 将下列命题符号化：将下列命题符号化：(1)(1)小王是跳远冠军或百米赛跑冠军。小王是跳远冠军或百米赛跑冠军。(2)(2)小王在宿舍或在图书馆。小王在宿舍或在图书馆。(3)(3)小王是计算机系的学生。小王是计算机系的学生。他他是广东人或湖南人是广东人或湖南人，是三好是三好学生学生。1111 设设,是是二二命命题题，复复合合命命题题“若若,则则”称称为为与与的的条条件件命命题题，记记作作。其其

10、中中叫叫前前件件或或前前题题，叫叫后件或结论。后件或结论。为为假当且仅当为真和为假假当且仅当为真和为假。定义定义4 4 条件联结词条件联结词pqp q1 11 11 11 10 00 00 01 11 10 001 1qp pq q的逻辑关系表示的逻辑关系表示q q是是p p的必要条件。的必要条件。qq q是是p p的必要条件有许多不同的叙述方式的必要条件有许多不同的叙述方式 只要只要p p，就，就q q ；因为因为p p，所以所以q q ；p p仅当仅当q q；只有只有q q才才p p ；除非除非q q才才p p；除非除非q q，否则非否则非p p。1212解：设：天下雨，：我骑车上班。解：

11、设：天下雨，：我骑车上班。(1)(1)。天不下雨是骑车上班的充分条件。天不下雨是骑车上班的充分条件。(2)(2)或或 。如如果果骑骑车车上上班班，一一定定是是天天不不下下雨雨。但但天天不不下下雨雨也也可可能不骑车上班。能不骑车上班。(3)(3)设设X X：2+22+24 4。Y Y：太阳从西太阳从西边边出来出来。则则原原命题表示为：命题表示为：XYXY。其。其真值为真值为1 1例例4 4 将下列命题符号化：将下列命题符号化：(1)(1)只要天不下雨，我就骑自行车上班。只要天不下雨，我就骑自行车上班。(2)(2)只有天不下雨，我才骑自行车上班。只有天不下雨，我才骑自行车上班。(3)(3)如果如果

12、2+242+24，则太阳从西，则太阳从西边出来边出来。1313设设,为为二二命命题题，复复合合命命题题“当当且且仅仅当当”称称为为与与的的双双条条件件命命题题，记作记作。叫双条件联结词叫双条件联结词。为真当且仅当为真当且仅当,真值相同。真值相同。定义定义5 5 双条件联结词双条件联结词pqp q1 11 11 11 10 00 00 01 10 00 001 1qq也称等价联结词。也称等价联结词。也称等价联结词。也称等价联结词。qp pq q的逻辑关系为的逻辑关系为p p与与q q互为充分必要条件。互为充分必要条件。q(pq)(qppq)(qp)与与p pq q的逻辑关系完全一致。的逻辑关系完

13、全一致。说说明明1414例例5 5、将下列命题符号化，并讨论它们的真值。、将下列命题符号化，并讨论它们的真值。q是无理数当且仅当加拿大位于亚洲。是无理数当且仅当加拿大位于亚洲。q2+32+35 5的充要条件是的充要条件是是无理数。是无理数。q当王小红心情愉快时，她就唱歌；反之，当她唱歌时，当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。一定心情愉快。(1)(1)解：设解：设 p p：是无理数是无理数，q q：加拿大位于亚洲加拿大位于亚洲。符号化为符号化为 p pq q，真值为真值为0 0。(2)(2)解：设解：设 p p：2+32+35 5，q q：是无理数是无理数。符号化为符号

14、化为 p pq q，真值为真值为1 1。(3)(3)解：设解：设 p p：王小红心情愉快王小红心情愉快，q q：王小红唱歌王小红唱歌。符号化为符号化为 p pq q，真值由具体情况而定。真值由具体情况而定。15154 4、关于基本联结词的说明、关于基本联结词的说明q,，称为一个联结词集。，称为一个联结词集。q由联结词集由联结词集,中的一个联结词联结一个或中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以两个原子命题组成的复合命题是最简单的复合命题，可以称它们为称它们为基本的复合命题基本的复合命题。q基本复合命题的真值见下表：基本复合命题的真值见下表：1616q多次使用联

15、结词集中的联结词，可以组成更为复杂的复多次使用联结词集中的联结词，可以组成更为复杂的复合命题。合命题。q求复杂复合命题的真值时，除依据上表外，还要规定联求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。结词的优先顺序，将括号也算在内。q本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：()()，对于同一优先级的联结词，先出现者先运算。，对于同一优先级的联结词，先出现者先运算。1717 例例6 6 令令 p p：北京比天津人口多。北京比天津人口多。q:2+2=4q:2+2=4。r r：乌鸦是白色的。乌鸦是白色的。求下列复合命题的真值：求下列复合命题的真值：(1

16、)(pq)(pq)r(1)(pq)(pq)r(2)(qr)(pr)(2)(qr)(pr)(3)(pr)(3)(pr)(pr)(pr)解：解：p p、q q、r r的真值分别为的真值分别为1 1、1 1、0 0 (1)1(1)1(2)1(2)1(3)0(3)0我们关心的是复合命题中命题之间的真值关系，而不关我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。心命题的内容。说说明明18181.1.2 2 命题命题公式及其赋值公式及其赋值1 1 1 1、命题常量和命题变元、命题常量和命题变元、命题常量和命题变元、命题常量和命题变元q简单命题是真值唯一确定的命题逻辑中最基本的研究单简单命题是

17、真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为位，所以也称简单命题为命题常项命题常项或或命题常元命题常元。q称真值可以变化的陈述句为称真值可以变化的陈述句为命题变项命题变项或或命题变元命题变元。也用也用p,q,rp,q,r,表示命题变项。表示命题变项。q当当p,q,rp,q,r,表示命题变项时，它们就成了取值表示命题变项时，它们就成了取值0 0或或1 1的变的变项，因而项，因而命题变项已不是命题命题变项已不是命题。q这样一来，这样一来，p,q,rp,q,r,既可以表示命题常项，也可以表示既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是命题变项。在使用

18、中，需要由上下文确定它们表示的是常项还是变项。常项还是变项。19192 2 2 2、命题公式、命题公式、命题公式、命题公式定义定义 命题演算的合式公式规定为命题演算的合式公式规定为：(1)(1)任意一个命题变元是合式公式；任意一个命题变元是合式公式；(2)(2)如果如果是是合式公式合式公式，则，则 是合式公式；是合式公式；(3)(3)如果、是合式公式，则如果、是合式公式，则，是合式公式；是合式公式；(4)(4)当当且且仅仅当当有有限限次次的的应应用用(1)(1)、(2)(2)、(3)(3)生生成成的的式式子子是是合式公式。合式公式。合式公式亦称为命题公式，也叫命题表达式合式公式亦称为命题公式，

19、也叫命题表达式。设设A A为合式公式，为合式公式，B B为为A A中一部分，若中一部分，若B B也是合式公式，也是合式公式，则称则称B B为为A A的的子公式子公式。2020q(A)(A)、(AB)(AB)等公式单独出现时，外层括号可以等公式单独出现时，外层括号可以省去，写成省去，写成A A、ABAB等。等。q公式中不影响运算次序的括号可以省去，公式中不影响运算次序的括号可以省去，如公式如公式(pq)(rpq)(r)可以写成可以写成pqrpqr。q合式公式的例子：合式公式的例子：(pq)(qpq)(q r)r)(pq)rpq)rp(qrp(qr)q不是合式公式的例子不是合式公式的例子pqrpq

20、r(p(rqp(rq)21213 3 3 3、公式的层次、公式的层次、公式的层次、公式的层次定义定义2:(1)2:(1)若公式若公式A A是单个的命题变项，则称是单个的命题变项，则称A A为为0 0层合式层合式。(2)(2)称称A A是是n+1(n0)n+1(n0)层公式层公式是指下面情况之一：是指下面情况之一：(a)A(a)AB B，B B是是n n层公式；层公式；(b)A(b)ABCBC，其中其中B,CB,C分别为分别为i i层和层和j j层公式，且层公式，且 n=max(i,j)；(c)A(c)ABCBC，其中其中B,CB,C的层次及的层次及n n同同(b)(b)；(d)A(d)ABCB

21、C，其中其中B,CB,C的层次及的层次及n n同同(b)(b)；(e)A(e)AB BC C，其中其中B,CB,C的层次及的层次及n n同同(b)(b)。(3)(3)若公式若公式A A的层次为的层次为k k，则称则称A A是是k k层公式层公式。例如：例如：(pq)rpq)r，(pq)(rs)pq)(rs)pp)分别为分别为3 3层和层和4 4层公式层公式 22224 4 4 4、公式的赋值或解释、公式的赋值或解释、公式的赋值或解释、公式的赋值或解释q 设设p p1 1,p,p2,2,p pn n是出现在公式是出现在公式A A中的全部命题变项，给中的全部命题变项，给p p1 1,p,p2,2,

22、p pn n各指定一个真值，称为对各指定一个真值，称为对A A的一个的一个赋值赋值或或解释解释。若。若指定的一组值使指定的一组值使A A的真值为的真值为1 1，则称这组值为，则称这组值为A A的的成真赋值成真赋值；若；若使使A A的真值为的真值为0 0，则称这组值为，则称这组值为A A的的成假赋值成假赋值。q 对含对含n n个命题变项的公式个命题变项的公式A A的赋值情况做如下规定：的赋值情况做如下规定：(1)(1)若若A A中出现的命题符号为中出现的命题符号为p p1 1,p,p2,2,p pn n，给定给定A A的赋值的赋值1,1,2,2,n n 是指是指p p1 11 1，p p2 22

23、 2,，p pn nn n。(2)(2)若若A A中出现的命题符号为中出现的命题符号为p p，q q，r.,r.,给定给定A A的赋值的赋值1,1,2,2,n n是指是指p p1 1，q q2 2,，最后一个字母赋值最后一个字母赋值n n。上述上述i i取值为取值为0 0或或1 1，i i1,2,1,2,n,n。2323q在公式在公式(p(p1 1pp2 2pp3 3)(p)(p1 1pp2 2)中，中，000(p000(p1 10 0，p p2 20 0，p p3 30)0)，110(p110(p1 11 1，p p2 21 1，p p3 30)0)都是成真赋值，都是成真赋值，001(p00

24、1(p1 10 0，p p2 20 0，p p3 31)1)，011(p011(p1 10 0，p p2 21 1，p p3 31)1)都是成假赋值。都是成假赋值。q在在(pq)rpq)r中，中，011(p011(p1 10 0，p p2 21 1，p p3 31)1)为成真赋值，为成真赋值，100(p100(p1 11 1，p p2 20 0，p p3 30)0)为成假赋值。为成假赋值。q重要结论：重要结论：含含n(n1)n(n1)个命题变项的公式共有个命题变项的公式共有2 2n n个不同的赋值。个不同的赋值。赋值举例赋值举例24245 5 5 5、真值表、真值表、真值表、真值表q将命题公式

25、将命题公式A A在所有赋值下取值情况列成表，称作在所有赋值下取值情况列成表，称作A A的的真值表真值表。q构造真值表的具体步骤如下：构造真值表的具体步骤如下：(1)(1)找出公式中所含的全体命题变项找出公式中所含的全体命题变项p p1 1,p,p2 2,p pn n(若无下角标就若无下角标就按字典顺序排列按字典顺序排列)，列出，列出2 2n n个赋值。本书规定，赋值从个赋值。本书规定，赋值从00000 0开始，然后按二进制加法依次写出各赋值，直到开始，然后按二进制加法依次写出各赋值，直到11111 1为止。为止。(2)(2)按从低到高的顺序写出公式的各个层次。按从低到高的顺序写出公式的各个层次

26、。(3)(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。真值。公式公式A与与B具有相同的或不同的真值表，是指真值表的最具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。后一列是否相同，而不考虑构造真值表的中间过程。说说明明2525例例1 1、求下列公式的真值表，并求成真赋值和成假赋值。、求下列公式的真值表，并求成真赋值和成假赋值。(1)(pq)r(1)(pq)r(2)(pp)(2)(pp)(qq)(qq)(3)(pq)qr (3)(pq)qr 2626例例例例2 2 2 2、求命题公式求命题

27、公式求命题公式求命题公式(p(qr)p(qr)p(qr)p(qr)的真值表的真值表的真值表的真值表。p pq qr r0 00 00 00 00 01 10 01 10 00 01 11 11 10 00 01 10 01 11 11 10 01 11 11 1qrqr0 00 00 01 10 00 00 01 1p(qrp(qr)1 11 11 11 10 00 00 01 1(p(qrp(qr)0 00 00 00 01 11 11 10 027276 6 6 6、重言式、永真式、可满足式、重言式、永真式、可满足式、重言式、永真式、可满足式、重言式、永真式、可满足式定义定义3 3、设、设

28、A A为任一命题公式为任一命题公式 (1)(1)若若A A在它的各种赋值下取值均为真在它的各种赋值下取值均为真,则称则称A A是是重言式重言式或或永真式永真式。(2)(2)若若A A在它的各种赋值下取值均为假在它的各种赋值下取值均为假,则称则称A A是是矛盾式矛盾式或或永假式永假式。(3)(3)若若A A不是矛盾式不是矛盾式,则称则称A A是是可满足式可满足式。q真值表可用来判断公式的类型真值表可用来判断公式的类型:若真值表最后一列全为若真值表最后一列全为1 1，则公式为重言式。，则公式为重言式。若真值表最后一列全为若真值表最后一列全为0 0，则公式为矛盾式。，则公式为矛盾式。若真值表最后一列

29、中至少有一个若真值表最后一列中至少有一个1 1，则公式为可满足式。，则公式为可满足式。2828例例3 3、下列各公式均含两个命题变项下列各公式均含两个命题变项p p与与q q，它们中哪些具有相它们中哪些具有相同的真值表同的真值表?(1)(1)pqpq(4)(4)(pq)(qppq)(qp)(2)(2)p pq q(5)(5)qpqp(3)(3)(pqpq)2929q设公式设公式A,BA,B中共含有命题变项中共含有命题变项p p1 1,p,p2 2,p pn n，而而A A或或B B不全不全含有这些命题变项，比如含有这些命题变项，比如A A中不含中不含p pi i,p,pi+1i+1,p pn

30、n ,称这些称这些命题变项为命题变项为A A的的哑元哑元，A A的取值与哑元的变化无关，因而的取值与哑元的变化无关，因而在讨论在讨论A A与与B B是否有相等的真值表时，将是否有相等的真值表时，将A,BA,B都看成都看成p p1 1,p,p2,2,p pn n的命题公式。的命题公式。7 7 7 7、哑元、哑元、哑元、哑元3030q命题与真值（或真假值）。命题与真值（或真假值）。q简单命题与复合命题。简单命题与复合命题。q联结词：联结词：，。q命题公式（简称公式）。命题公式（简称公式）。q命题公式的层次和公式的赋值。命题公式的层次和公式的赋值。q真值表。真值表。q公式的类型：重言式（永真式），矛

31、盾式（永假式），公式的类型：重言式（永真式），矛盾式（永假式），可满足式。可满足式。q本章典型习题：本章典型习题：求命题符号化；复合命题的真值与命求命题符号化；复合命题的真值与命题公式的赋值；判断公式的类型。题公式的赋值；判断公式的类型。8 8 8 8、小结、小结、小结、小结3131例例例例4 4 4 4、将、将、将、将下列下列下列下列命题符号化。命题符号化。命题符号化。命题符号化。(1)(1)我和他既是兄弟又是同学我和他既是兄弟又是同学 p p：我和他是兄弟，：我和他是兄弟，q q：我和他是同学。：我和他是同学。故命题可符号化为：故命题可符号化为：pqpq。(2)(2)鱼和熊掌不可兼得。鱼和

32、熊掌不可兼得。p p：鱼可得。：鱼可得。q q：熊掌可得。：熊掌可得。故命题可符号化为：故命题可符号化为：（pqpq）。）。(3)(3)仅当我有时间且天不下雨，我将去镇上。仅当我有时间且天不下雨，我将去镇上。对于对于“仅当仅当”，实质上是，实质上是“当当”的逆命题。的逆命题。“当当A A则则B B”是是ABAB，而，而“仅当仅当A A则则B B”是是BABA。p p：我有时间。：我有时间。q q：天不下雨。：天不下雨。r r：我将去镇上。：我将去镇上。故命题可符号化为：故命题可符号化为：r(pqr(pq)。3232例例例例5 5 5 5、求下列命题公式的真值表求下列命题公式的真值表求下列命题公式的真值表求下列命题公式的真值表：PPPP（QQQQ R R R R）解：解：3333同学们学习愉快！同学们学习愉快！下次课再见！下次课再见！