离散数学：第1章 命题逻辑基本概念

《离散数学：第1章 命题逻辑基本概念》由会员分享，可在线阅读，更多相关《离散数学：第1章 命题逻辑基本概念（54页珍藏版）》请在金锄头文库上搜索。

1、 1第第1章章命题逻辑基本概念命题逻辑基本概念离散数学离散数学 2本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容命题、联结词、复合命题命题、联结词、复合命题命题公式、赋值、命题公式的分类命题公式、赋值、命题公式的分类q本章与后续各章的关系本章与后续各章的关系本章是后续各章的准备或前提本章是后续各章的准备或前提 31.1 命题与联结词q数理逻辑研究的数理逻辑研究的中心问题中心问题是是推理推理.q推理的推理的前提前提和和结论结论都是都是表达判断表达判断的的陈述句陈述句.q表达判断的陈述句构成了推理的表达判断的陈述句构成了推理的基本单位基本单位. 41.1 1.1 命题与联结词命题与

2、联结词q称能判断真假而不是可真可假的陈述句为称能判断真假而不是可真可假的陈述句为命题命题（proposition）. q作为命题的陈述句所表达得的判断结果称为命题的作为命题的陈述句所表达得的判断结果称为命题的真值真值. q真值只取两个：真值只取两个：真与假真与假. q真值为真的命题称为真值为真的命题称为真命题真命题. q真值为假的命题称为真值为假的命题称为假命题假命题. q感叹句、疑问句、祈使句都不能称为命题感叹句、疑问句、祈使句都不能称为命题. . q判断结果不唯一确定的陈述句不是命题判断结果不唯一确定的陈述句不是命题. . q陈述句中的悖论不是命题陈述句中的悖论不是命题. . 说说明明 5

3、(1)4是素数是素数.(2)21/2是无理数是无理数.(3)x大于大于y.(4)充分大的偶数等于两个素充分大的偶数等于两个素数之和数之和.(5)今天是星期二今天是星期二.(6) 大于大于21/2吗？吗？(7)请不要吸烟！请不要吸烟！(8)这朵花真美丽啊！这朵花真美丽啊！(9)我正在说假话我正在说假话.例例1.1 1.1 判断下列句子是否为命题判断下列句子是否为命题. . (1)(1)是是, , 假命题假命题(2)(2)是是, , 真命题真命题(3)(3)不是不是, , 无确定的真值无确定的真值(4)(4)是是, , 真值客观存在真值客观存在(5)(5)是是, , 真值根据具体情况真值根据具体情

4、况而定而定. . (6)(6)不是不是, , 疑问句疑问句(7)(7)不是不是, , 祈使句祈使句(8)(8)不是不是, , 感叹句感叹句(9)(9)不是不是, , 悖论悖论 6命题和真值的符号化命题和真值的符号化q用小写英文字母p, q, r, pi , qi , ri 表示命题q用“1”表示真, 用“0”表示假p:4是素数是素数.r:充分大的偶数等于两个素数之和充分大的偶数等于两个素数之和q:21/2是无理数是无理数.s:今天是星期二今天是星期二.q不能被分解成更简单的陈述句不能被分解成更简单的陈述句, , 称这样的命称这样的命题为题为简单命题简单命题或或原子命题原子命题. . q由简单陈

5、述句通过联结词而成的陈述句由简单陈述句通过联结词而成的陈述句, , 称称这样的命题为这样的命题为复合命题复合命题. . 7例例1.2将下面这段陈述中所出现的原子命题符号化将下面这段陈述中所出现的原子命题符号化, , 并指出它并指出它们的真值们的真值, , 然后再写出这段陈述然后再写出这段陈述. . 2 21/21/2是是有有理理数数是是不不对对的的；2 2是是偶偶素素数数；2 2或或4 4是是素素数数；如如果果2 2是素数是素数, , 则则3 3也是素数；也是素数；2 2是素数当且仅当是素数当且仅当3 3也是素数也是素数. . p：2 21/21/2是有理数是有理数q：2 2是素数；是素数；r

6、：2 2是偶数是偶数s s：3 3是素数；是素数；t：4 4是素数是素数0111 10非非p；q并且并且(与与)r；q或或t t；如果如果q, , 则则s；q当且仅当当且仅当s. 8例例例例1.21.2的讨论的讨论的讨论的讨论q半形式化形式半形式化形式q数理逻辑研究方法的主要特征是将论述或推数理逻辑研究方法的主要特征是将论述或推理中的理中的各种要素都符号化各种要素都符号化.即构造各种符号语即构造各种符号语言来代替自然语言言来代替自然语言.q形式化语言形式化语言：完全由符号所构成的语言完全由符号所构成的语言.q将联结词（将联结词（connective）符号化）符号化,消除其二义消除其二义性性,对

7、其进行严格定义对其进行严格定义.q例如：例如： 他是他是100米或米或400米赛跑的冠军米赛跑的冠军.鱼香肉丝或锅包肉鱼香肉丝或锅包肉,加一碗汤加一碗汤. 9定义1.1 否定否定(negation)q设设p为命题为命题,复合命题复合命题“非非p”(或或“p的的否定否定”)称为称为p的否定式的否定式,记作记作 p,符符号号 称作称作否定联结词否定联结词,并规定并规定 p为真为真当且仅当当且仅当p为假为假.例如例如：p： 哈尔滨哈尔滨是一个大城市是一个大城市. . p：哈尔滨是一个不大城市哈尔滨是一个不大城市. p：哈尔滨不是一个大城市哈尔滨不是一个大城市.p p1001 10定义定义1.21.2

8、 合取合取合取合取( (conjunctionconjunction) )q设设p,q为二命题为二命题,复合命题复合命题“p并且并且q”(或或“p与与q”)称为称为p与与q的的合取式合取式,记作记作p q, 称作称作合合取联结词取联结词,并规定并规定p q为真当为真当且仅当且仅当p与与q同时为真同时为真.使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1)1)描述合取式的灵活性与多样性描述合取式的灵活性与多样性. . 自然语言中的自然语言中的“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一面一面一面一面”等联结词都等联结词都可以符号化为可以符号化为 . . 2)2)分

9、清简单命题与复合命题分清简单命题与复合命题. . 不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词 . . pqp q1 11 11 11 10 00 00 01 10 00 000 0 11例1.3将下列命题符号化将下列命题符号化(1)吴颖既用功又聪明吴颖既用功又聪明.(2)吴颖不仅用功而且聪明吴颖不仅用功而且聪明.(3)吴颖虽然聪明吴颖虽然聪明,但不用功但不用功.(4)张辉与王丽都是三好学生张辉与王丽都是三好学生.(5)张辉与王丽是同学张辉与王丽是同学.p: p: 吴颖用功吴颖用功. . q: q: 吴颖聪明吴颖聪明. . r: r: 张辉是三好学生张辉是三好学生. . s:

10、s: 王丽是三好学生王丽是三好学生. . t: t: 张辉与王丽是同学张辉与王丽是同学. . (1)p(1)p q q(2)p(2)p q q(3)q(3)q p p(4)r(4)r s s (5)t(5)t解题要点：解题要点：正确理解命题含义正确理解命题含义. . 找出原子命题并符号化找出原子命题并符号化. . 选择恰当的联结词选择恰当的联结词. . 12合取举例合取举例qp：我们去看电影我们去看电影.q：房间里有十张桌子房间里有十张桌子.p q：我们去看电影并且房间里有十张桌子我们去看电影并且房间里有十张桌子.在数理逻辑中在数理逻辑中, , 关心的只是复合命题与构成复合关心的只是复合命题与

11、构成复合命题的各原子命题之间的真值关系命题的各原子命题之间的真值关系, , 即抽象的逻即抽象的逻辑关系辑关系, , 并不关心各语句的具体内容并不关心各语句的具体内容. . 说说明明 13定义1.3 析取析取(disjunction)q设设p,q为二命题为二命题,复合命题复合命题“p或或q”称作称作p与与q的的析取式析取式,记作记作p q, 称作称作析取联结词析取联结词,并规定并规定p q为假当且仅当为假当且仅当p与与q同时为假同时为假.自然语言中的自然语言中的“或或”具有二义性具有二义性, , 用它联结的命用它联结的命题有时具有相容性题有时具有相容性, , 有时具有排斥性有时具有排斥性, ,

12、对应的联对应的联结词分别称为相容或结词分别称为相容或和排斥或排斥或( (排异或排异或) ). . 说说明明pqp q1 11 11 11 10 01 10 01 11 10 000 0 14例例1.4将下列命题符号化将下列命题符号化(1)张晓静爱唱歌或爱听音乐张晓静爱唱歌或爱听音乐.(2)张晓静只能挑选张晓静只能挑选202或或203房间房间.(3)张晓静是江西人或安徽人张晓静是江西人或安徽人.(4)他昨天做了二十或三十道习题他昨天做了二十或三十道习题.(1)(1)设设 p p：张晓静爱唱歌张晓静爱唱歌, , q q：张晓静爱听音乐张晓静爱听音乐. . 相容或相容或, , 符号化为符号化为 p

13、p q q(2)(2)设设t t：张晓静挑选张晓静挑选202202房间房间, , u u：张晓静挑选张晓静挑选203203房间房间. . 排斥或排斥或, , 符号化为：符号化为：( (t tu u) ) ( ( t t u u) )(3)(3)设设r r：张晓静是江西人张晓静是江西人, , s s：张晓静是安徽人张晓静是安徽人. . 排斥或排斥或, , 符号化为：符号化为：r r s s. . ( (排斥或排斥或联结的两个命题事实上不可能同时为真联结的两个命题事实上不可能同时为真) )或符号化为：或符号化为：( (r rs)s) ( ( r r s)s)(4)(4)原子命题原子命题, , 因为

14、因为“或或”只表示了习题的只表示了习题的近似数目近似数目. . 15定义定义1.41.4 蕴涵蕴涵蕴涵蕴涵( (implicationimplication) )q设设p,q为二命题为二命题,复合命题复合命题“如果如果p,则则q”称作称作p与与q的的蕴涵式蕴涵式,记作记作pq,并称并称p是蕴涵式的是蕴涵式的前件前件,q为蕴涵式的为蕴涵式的后件后件,称作称作蕴涵联结词蕴涵联结词,并规定并规定pq为假当且为假当且仅当仅当p为真为真q为假为假.说说明明qpq的的逻辑关系表示关系表示q是是p的必要条件的必要条件. . qq是是p的必要条件有的必要条件有许多不同的叙述方式多不同的叙述方式只要只要p, ,

15、 就就q因因为p, , 所以所以qp仅当当q只有只有q才才p除非除非q才才p除非除非q, , 否否则非非ppqp q1 11 11 11 10 00 00 01 11 10 001 1 16例例例例1.51.5将下列命题符号化将下列命题符号化将下列命题符号化将下列命题符号化, ,并指出其真值并指出其真值并指出其真值并指出其真值 (1)如果如果3+36,则雪是白的则雪是白的.(2)如果如果3+36,则雪是白的则雪是白的.(3)如果如果3+36,则雪不是白的则雪不是白的.(4)如果如果3+36,则雪不是白的则雪不是白的.解：令解：令p p：3+33+36, 6, p p的真值为的真值为1 1. .

16、 q q：雪是白色的雪是白色的, , q q的真值也为的真值也为1 1. . (1)pq (2)(2) pq (3) pq (4)(4) pq1101 17说明说明:q(1)pq的逻辑关系的逻辑关系:q为为p的必要条件的必要条件q(2)“如果如果p,则则q的不同表述法很多的不同表述法很多:若若p,就就q只要只要p,就就qp仅当仅当q只有只有q才才p除非除非q,才才p或除非或除非q,否则非否则非p,q(3)当当p为假时为假时,pq为真为真,可称为空证明可称为空证明q(4)常出现的错误常出现的错误:不分充分与必要条件不分充分与必要条件 18例例例例1.51.5将下列命题符号化将下列命题符号化将下列

17、命题符号化将下列命题符号化, ,并指出其真值并指出其真值并指出其真值并指出其真值 以下命题中出现的以下命题中出现的a是一个给定的正整数：是一个给定的正整数：(5)只要只要a能被能被4整除整除,则则a一定能被一定能被2整除整除.(6)a能被能被4整除整除,仅当仅当a能被能被2整除整除.(7)除非除非a能被能被2整除整除,a才能被才能被4整除整除.(8)除非除非a能被能被2整除整除,否则否则a不能被不能被4整除整除.(9)只有只有a能被能被2整除整除,a才能被才能被4整除整除.(10)只有只有a能被能被4整除整除,a才能被才能被2整除整除.解：解：令令r r： a a能被能被4 4整除整除 s s

18、： a a能被能被2 2整除整除 (5)(5)至至(9)(9)五个命题均叙述的是五个命题均叙述的是a a能被能被2 2整除是整除是a a能被能被4 4整除的必要整除的必要条件条件, , 因而都符号化为因而都符号化为r rs s. . 其真值为其真值为1 1在在(10)(10)中中, , 将将a a能被能被4 4整除看成了整除看成了a a能被能被2 2整除的必要条件整除的必要条件, , 因而因而应符号化为应符号化为s sr r. . a a值不定时值不定时, , 真值未知真值未知. . 19例例设设p:天冷天冷,q:小王穿羽绒服小王穿羽绒服,将下列命题符号化将下列命题符号化q(1)只要天冷只要天

19、冷,小王就穿羽绒服小王就穿羽绒服.q(2)因为天冷因为天冷,所以小王穿羽绒服所以小王穿羽绒服.q(3)若小王不穿羽绒服若小王不穿羽绒服,则天不冷则天不冷.q(4)只有天冷只有天冷,小王才穿羽绒服小王才穿羽绒服.q(5)除非天冷除非天冷,小王才穿羽绒服小王才穿羽绒服.q(6)除非小王穿羽绒服除非小王穿羽绒服,否则天不冷否则天不冷.q(7)如果天不冷如果天不冷,则小王不穿羽绒服则小王不穿羽绒服.q(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.q注意注意:pq与与 qp等值等值(真值相同真值相同)q(1),(2),(3),(6)符号化为符号化为pqq其余的符号化为其余的符号化为qp 2

20、0关于蕴含的进一步说明关于蕴含的进一步说明q作为一种规定作为一种规定,当当p为假时为假时,无论无论q是真是假是真是假,pq均为真均为真.也也就是说就是说,只有只有p为真为真q为假这一种情况使得复合命题为假这一种情况使得复合命题pq为为假假.称为称为实质蕴含实质蕴含.q例：如果例：如果x5,则则x2.(1)x=6如果如果65,则62.(2)x=3如果如果35,则32.(3)x=1如果如果15,则12.q例：如果我有车例：如果我有车,那么我去接你那么我去接你q常出现的错误常出现的错误,没有分清充分条件与必要条件没有分清充分条件与必要条件. 21定义定义1.51.5 等价等价等价等价( (two-w

21、ay-implicationtwo-way-implication) )q设设p,q为二命题为二命题,复合命题复合命题“p当当且仅当且仅当q”称作称作p与与q的的等价式等价式,记记作作pq,称作称作等价联结词等价联结词,并规并规定定pq为真当且仅当为真当且仅当p与与q同时同时为真或同时为假为真或同时为假.说说明明q“当且仅当当且仅当”（if and only if）qp pq q的逻辑关系为的逻辑关系为p p与与q q互为充分必要条件互为充分必要条件. . q( (p pq)q) (q(qp)p)与与p pq q的逻辑关系完全一致的逻辑关系完全一致. . pqp q1 11 11 11 10

22、00 00 01 10 00 001 1 22例例例例1.61.6将下列命题符号化将下列命题符号化将下列命题符号化将下列命题符号化, ,并讨论它们的真值并讨论它们的真值并讨论它们的真值并讨论它们的真值 (1)是无理数当且仅当加拿大位于亚洲是无理数当且仅当加拿大位于亚洲.(2)2+35的充要条件是的充要条件是是无理数是无理数.(3)若两圆若两圆A,B的面积相等的面积相等,则它们的半径相等；反之亦然则它们的半径相等；反之亦然.(4)当王小红心情愉快时当王小红心情愉快时,她就唱歌；反之她就唱歌；反之,当她唱歌时当她唱歌时,一定心情愉快一定心情愉快.(1)(1)设设 p p：是无理数是无理数, , q

23、 q：加拿大位于亚洲加拿大位于亚洲. . 符号化为符号化为 p pq q, , 真值为真值为0 0. . (2)(2)设设 p p：2+32+35 5, , q q：是无理数是无理数. . 符号化为符号化为 p pq q, , 真值为真值为1 1. . (3)(3)设设 p p：两圆两圆A, BA, B的面积相等的面积相等, , q q：两圆两圆A, BA, B的半径相等的半径相等. . 符号化为符号化为 p pq q, , 真值为真值为1 1. . (4)(4)设设 p p：王小红心情愉快王小红心情愉快, , q q：王小红唱歌王小红唱歌. . 符号化为符号化为 p pq q, , 真值由具

24、体情况而定真值由具体情况而定. . 23关于基本联结词的说明关于基本联结词的说明q , , ,称为一个联结词集称为一个联结词集.q由联结词集由联结词集 , , ,中的一个联结词联结一个或两中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题个原子命题组成的复合命题是最简单的复合命题,可以称可以称它们为它们为基本的复合命题基本的复合命题.q基本复合命题的真值见下表：基本复合命题的真值见下表： 24关于基本联结词的说明关于基本联结词的说明q多次使用联结词集中的联结词多次使用联结词集中的联结词,可以组成更为复杂的复合可以组成更为复杂的复合命题命题.q求复杂复合命题的真值时求复杂复合命

25、题的真值时,除依据上表外除依据上表外,还要规定联结词还要规定联结词的优先顺序的优先顺序,将括号也算在内将括号也算在内.q本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：(), , , ,对于对于同一优先级的联结词同一优先级的联结词,先出现者先运算先出现者先运算. 25例例1.7令令p：北京比天津人口多北京比天津人口多.q：2+24.r：乌鸦是白色的乌鸦是白色的.求下列复合命题的真值：求下列复合命题的真值：(1)( p q) (pq)r(2)(q r)(pr)(3)( p r)(pr)解：解：p p、q q、r r的真值分别为的真值分别为 1 1、1 1、0 0 (1) 1(1) 1(2

26、) 1(2) 1(3) 0(3) 0我们关心的是复合命题中命题之间的真值关系我们关心的是复合命题中命题之间的真值关系, , 而不关心命题的内容而不关心命题的内容. . 说说明明 261.2命题公式及其赋值命题公式及其赋值q简单命题是真值唯一确定的命题逻辑中最基本的研究单位简单命题是真值唯一确定的命题逻辑中最基本的研究单位,所所以也称简单命题为以也称简单命题为命题常项命题常项或或命题常元命题常元.(proposition constant)q称真值可以变化的陈述句为称真值可以变化的陈述句为命题变项命题变项或或命题变元命题变元(proposition variable).也用也用p,q,r,表示命

27、题变项表示命题变项.q当当p,q,r,表示命题变项时表示命题变项时,它们就成了取值它们就成了取值0或或1的变项的变项,因因而而命题变项已不是命题命题变项已不是命题.q这样一来这样一来,p,q,r,既可以表示命题常项既可以表示命题常项,也可以表示命题变也可以表示命题变项项.在使用中在使用中,需要由上下文确定它们表示的是常项还是变项需要由上下文确定它们表示的是常项还是变项.q将命题变项用联结词和圆括号按一定的逻辑关系联结起来的将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为符号串称为合式公式合式公式或或命题公式命题公式. 27定义定义1.6合式公式合式公式(wff )(1)单个命题变

28、项是合式公式单个命题变项是合式公式,并称为并称为原子命题公式原子命题公式.(2)若若A是合式公式是合式公式,则则( A)也是合式公式也是合式公式.(3)若若A,B是合式公式是合式公式,则则(A B),(A B),(AB),(AB)也是合式公式也是合式公式.(4)只有有限次地应用只有有限次地应用(1)(3)形式的符号串才是合式公形式的符号串才是合式公式式.合式公式也称为合式公式也称为命题公式命题公式或或命题形式命题形式,并简称为并简称为公式公式.设设A为合式公式为合式公式,B为为A中一部分中一部分,若若B也是合式公式也是合式公式,则称则称B为为A的的子公式子公式.合式公式：合式公式：Well F

29、ormed Formula 28关于合式公式的说明关于合式公式的说明q定义定义1.6给出的合式公式的定义方式称为给出的合式公式的定义方式称为归纳定义归纳定义或或递归定义递归定义方方式式.q定义中引进了定义中引进了A,B等符号等符号,用它们表示任意的合式公式用它们表示任意的合式公式,而不是而不是某个具体的公式某个具体的公式,这与这与p,p q,(p q)r等具体的公式是有所等具体的公式是有所不同的不同的.qA,B等符号被称作等符号被称作元语言元语言符号符号.p,q等被称作等被称作对象语言对象语言符号符号.q所谓所谓对象语言对象语言是指用来描述研究对象的语言是指用来描述研究对象的语言,而而元语言元

30、语言是指用来是指用来描述对象的语言描述对象的语言,这两种语言是不同层次的语言这两种语言是不同层次的语言.q例如中国人学习英语时例如中国人学习英语时,英语为对象语言英语为对象语言,而用来学习英语的汉而用来学习英语的汉语则是元语言语则是元语言. 29关于合式公式的说明关于合式公式的说明q( A)、(A B)等公式单独出现时等公式单独出现时,外层括号可以省去外层括号可以省去,写成写成 A、A B等等.q公式中不影响运算次序的括号可以省去公式中不影响运算次序的括号可以省去,如公式如公式(p q) ( r)可以写成可以写成p qr.q合式公式的例子：合式公式的例子：(pq) (qr)(p q)rp (q

31、r)q不是合式公式的例子不是合式公式的例子pqr(p(rq) 30定义定义1.7公式层次公式层次(1)若公式若公式A是单个的命题变项是单个的命题变项,则称则称A为为0层公式层公式.(2)称称A是是n+1(n0)层公式层公式是指下面情况之一：是指下面情况之一：(a)A B,B是是n层公式；层公式；(b)AB C,其中其中B,C分别为分别为i层和层和j层公式层公式,且且n=max(i,j)；(c)AB C,其中其中B,C的层次及的层次及n同同(b)；(d)ABC,其中其中B,C的层次及的层次及n同同(b)；(e)ABC,其中其中B,C的层次及的层次及n同同(b).(3)若公式若公式A的层次为的层次

32、为k,则称则称A是是k层公式层公式.例如：例如：( p q)r,( (pq) (r s) p)分别为分别为3层和层和4层公式层公式 31公式的解释公式的解释q在命题公式中在命题公式中,由于有命题符号的出现由于有命题符号的出现,因而真值是不确定的因而真值是不确定的.当将公式中出现的全部命题符号都解释成具体的命题之后当将公式中出现的全部命题符号都解释成具体的命题之后,公公式就成了真值确定的命题了式就成了真值确定的命题了.q(p q)rq若若p：2是素数是素数,q：3是偶数是偶数,r：是无理数是无理数,则则p与与r被解释成被解释成真命题真命题,q被解释成假命题被解释成假命题,此时公式此时公式(p q

33、)r解释成：若解释成：若2是是素数或素数或3是偶数是偶数,则则是无理数是无理数.（真命题真命题）qr被解释为：被解释为：是有理数是有理数,则则(p q)r被解释成：若被解释成：若2是素数或是素数或3是偶数是偶数,则则是有理数是有理数.（假命题假命题）q将命题变项将命题变项p解释成真命题解释成真命题,相当于指定相当于指定p的真值为的真值为1,解释成解释成假命题假命题,相当于指定相当于指定p的真值为的真值为0. 32定义定义1.8赋值或解释赋值或解释q设设p1,p2,pn是出现在公式是出现在公式A中的全部命题变项中的全部命题变项,给给p1,p2,pn各指定一个真值各指定一个真值,称为对称为对A的一

34、个的一个赋值赋值或或解释解释.若若指定的一组值使指定的一组值使A的真值为的真值为1,则称这组值为则称这组值为A的的成真赋成真赋值值；若使；若使A的真值为的真值为0,则称这组值为则称这组值为A的的成假赋值成假赋值.q对含对含n个命题变项的公式个命题变项的公式A的赋值情况做如下规定：的赋值情况做如下规定：(1)若若A中出现的命题符号为中出现的命题符号为p1,p2,pn,给定给定A的赋值的赋值1,2,n是指是指p11,p22,pnn.(2)若若A中出现的命题符号为中出现的命题符号为p,q,r.,给定给定A的赋值的赋值1,2,n是指是指p1,q2,最后一个字母赋值最后一个字母赋值n.上述上述i取值为取

35、值为0或或1,i1,2,n. 33赋值举例赋值举例q在公式在公式( p1p2p3) (p1 p2)中中,000(p10,p20,p30),110(p11,p21,p30)都是成真赋值都是成真赋值,001(p10,p20,p31),011(p10,p21,p31)都是成假赋值都是成假赋值.q在在(pq)r中中,011(p10,p21,p31)为成真赋值为成真赋值,100(p11,p20,p30)为成假赋值为成假赋值.q重要结论：重要结论：含含n(n1)个命题变项的公式共有个命题变项的公式共有2n个不同的赋值个不同的赋值. 34定义定义1.9真值表真值表q将命题公式将命题公式A在所有赋值下取值情况

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

37、各个层次. . (3)(3)对应各个赋值计算出各层次的真值对应各个赋值计算出各层次的真值, , 直到最后计算出公式的直到最后计算出公式的真值真值. . 公式公式A A与与B B具有相同的或不同的真值表具有相同的或不同的真值表, , 是指真值表的最是指真值表的最后一列是否相同后一列是否相同, , 而不考虑构造真值表的中间过程而不考虑构造真值表的中间过程. . 说说明明 35例例1.8求下列公式的真值表求下列公式的真值表,并求成真赋值和成假赋值并求成真赋值和成假赋值.(1)( p q)r(2)(pp)(qq)(3) (pq) q r 36定义定义1.10重言式、永真式、可满足式重言式、永真式、可满

38、足式设设A为任一命题公式为任一命题公式(1)若若A在它的各种赋值下取值均为真在它的各种赋值下取值均为真,则称则称A是是重言式重言式(tautology)或或永真式永真式.(2)若若A在它的各种赋值下取值均为假在它的各种赋值下取值均为假,则称则称A是是矛盾式矛盾式(contradiction)或或永假式永假式.(3)若若A不是矛盾式不是矛盾式,则称则称A是是可满足式（可满足式（satisfactable formula）. 37定义定义1.10的进一步说明的进一步说明qA是可满足式的等价定义是：是可满足式的等价定义是：A至少存在一个成真赋值至少存在一个成真赋值.q重言式一定是可满足式重言式一定是

39、可满足式,但反之不真但反之不真.因而因而,若公式若公式A是可满足是可满足式式,且它至少存在一个成假赋值且它至少存在一个成假赋值,则称则称A为非重言式的可满足为非重言式的可满足式式.q真值表可用来判断公式的类型真值表可用来判断公式的类型:若真值表最后一列全为若真值表最后一列全为1,则公式为重言式则公式为重言式.若真值表最后一列全为若真值表最后一列全为0,则公式为矛盾式则公式为矛盾式.若真值表最后一列中至少有一个若真值表最后一列中至少有一个1,则公式为可满足式则公式为可满足式.说说明明qn n个命题变项共产生个命题变项共产生2 2n n个不同赋值个不同赋值q含含n n个命题变项的公式的真值表只有个

40、命题变项的公式的真值表只有 种不同情况种不同情况 38例题例题例题例题1.9下列各公式均含两个命题变项下列各公式均含两个命题变项p与与q,它们中哪它们中哪些具有相同的真值表些具有相同的真值表?(1)pq(4)(pq) (qp)(2)pq(5) q p(3) (pq) 39哑元哑元q设公式A, B中共含有命题变项p1,p2,pn,而而A或或B不全含有这些命题变项不全含有这些命题变项,比如比如A中不含中不含pi,pi+1,pn,称这些命题变项为称这些命题变项为A的的哑元哑元,A的取值与的取值与哑元的变化无关哑元的变化无关,因而在讨论因而在讨论A与与B是否有相等的是否有相等的真值表时真值表时,将将A

41、,B都看成都看成p1,p2,pn的命题公式的命题公式. 40例题例题例例1.10下列公式中下列公式中,哪些具有相同的真值表哪些具有相同的真值表?(1)pq(2) q r(3)( p q) (p r)p)(4)(qr) (pp) 41本章主本章主要内容要内容q命题与真值（或真假值）命题与真值（或真假值）. . q简单命题与复合命题简单命题与复合命题. . q联结词：联结词： , , , , , , , , . . q命题公式（简称公式）命题公式（简称公式）. . q命题公式的层次和公式的赋值命题公式的层次和公式的赋值. . q真值表真值表. . q公式的类型：重言式（永真式）公式的类型：重言式（

42、永真式）, , 矛盾式（永假式）矛盾式（永假式）, , 可满足式可满足式. . 42本章学习要求本章学习要求q在在5种联结词中种联结词中,要特别注意蕴涵联结的应用要特别注意蕴涵联结的应用,要弄清要弄清三个问题：三个问题：pq的逻辑关系的逻辑关系pq的真值的真值pq的灵活的叙述方法的灵活的叙述方法q写真值表要特别仔细认真写真值表要特别仔细认真,否则会出错误否则会出错误.q深刻理解各联结词的逻辑含义深刻理解各联结词的逻辑含义.q熟练地将复合命题符号化熟练地将复合命题符号化.q会用真值表求公式的成真赋值和成假赋值会用真值表求公式的成真赋值和成假赋值. 43本章典型习题本章典型习题q命题符号化命题符号

43、化q求复合命题的真值与命题公式的赋值求复合命题的真值与命题公式的赋值q判断公式的类型判断公式的类型 44例题：命题符号化例题：命题符号化(1)我和他既是兄弟又是同学我和他既是兄弟又是同学p：我和他是兄弟我和他是兄弟,q：我和他是同学我和他是同学.故命题可符号化为：故命题可符号化为：p q.(2)张三或李四都可以做这件事张三或李四都可以做这件事.p：张三可以做这件事张三可以做这件事.q：李四可以做这件事李四可以做这件事.故命题可符号化为：故命题可符号化为：p q.(3)仅当我有时间且天不下雨仅当我有时间且天不下雨,我将去镇上我将去镇上.对于对于“仅当仅当”,实质上是实质上是“当当”的逆命题的逆命

44、题.“当当A则则B”是是AB,而而“仅当仅当A则则B”是是BA.p：我有时间我有时间.q：天不下雨天不下雨.r：我将去镇上我将去镇上.故命题可符号化为：故命题可符号化为：r(p q). 45例题：命题符号化例题：命题符号化例题：命题符号化例题：命题符号化(4)张刚总是在图书馆看书张刚总是在图书馆看书,除非图书馆不开门或张刚生病除非图书馆不开门或张刚生病.对于对于“除非除非”,只要记住只要记住,“除非除非”是条件是条件.p：张刚在图书馆看书张刚在图书馆看书,q：图书馆不开门图书馆不开门,r：张刚生病张刚生病.故命题可符号化为：故命题可符号化为：(q r)p.(5)风雨无阻风雨无阻,我去上学我去上

45、学.可理解为可理解为“不管是否刮风、是否下雨不管是否刮风、是否下雨,我都去上学我都去上学”.p：天刮风天刮风,q：天下雨天下雨,r：我去上学我去上学.故命题可符号化为：故命题可符号化为：(p qr) (p qr) ( p qr) ( p qr)或或(p q r) (p q r) ( p q r) ( p q r)理解为理解为“四种情况必居其一四种情况必居其一,而每种情况下我都去上学而每种情况下我都去上学” 46命题符号化的要点命题符号化的要点q要准确确定原子命题要准确确定原子命题,并将其符号化并将其符号化.q要要选选用用恰恰当当的的联联结结词词,尤尤其其要要善善于于识识别别自自然然语语言言中中

46、的联结词（有时它们被省略）的联结词（有时它们被省略）.q否定词的位置要放准确否定词的位置要放准确.q需需要要的的括括号号不不能能省省略略,而而可可以以省省略略的的括括号号,在在需需要要提提高公式可读性时亦可不省略高公式可读性时亦可不省略.q要注意的是要注意的是,语句的符号化未必是唯一的语句的符号化未必是唯一的. 47例题：求公式例题：求公式 (p(q r)的真值表的真值表.pqr000001010011100101110111q r00010001p(q r)11110001 (p(q r)00001110 48q设设p:2是素数是素数qq:北京比天津人口多北京比天津人口多qr:美国的首都是旧

47、金山美国的首都是旧金山q求下面命题的真值求下面命题的真值(p q)r(q r)(pr)(qr)(pr)(qp)(pr)( rq) 49q提示提示:qp,q为真命题为真命题,r是假命题是假命题q反复用基本复合命题的真值求解反复用基本复合命题的真值求解(心算即可心算即可)q答案答案:真值分别为真值分别为0,1,0,0 50q用真值表判断下面公式的类型用真值表判断下面公式的类型1.p r(qp)2.(pq)( qp) r3.(pq)(pr)q提示提示:按层次写真值表按层次写真值表,由最后一列判类型由最后一列判类型 51(1)p r(qp) 矛盾式矛盾式p q rqp (qp)p r(qp)000001010011100101110111110011110011000000000000 52(2)(pq)( qp) r 永真式永真式p q rpq qp(pq)( qp) r000001010011100101110111111100111111001111111111 53(3)(pq)(pr)非永真式的可非永真式的可满足式足式p q rpqpr(pq)(pr)000001010011100101110111111100111111010111111001 54本章作业本章作业习题一习题一书上：书上：1,2,4作业本上：作业本上：9(1-4),14(1-5),18,19(1-2)