命题逻辑基本概念PPT课件.ppt

第第1 1章章 命题逻辑基本概念命题逻辑基本概念离离 散散 数数 学学本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容–命题、联结词、复合命题命题、联结词、复合命题–命题公式、赋值、命题公式的分类命题公式、赋值、命题公式的分类q本章与后续各章的关系本章与后续各章的关系–本章是后续各章的准备或前提本章是后续各章的准备或前提2021/7/232数理逻辑概述数理逻辑概述Ø数理逻辑是用数学的方法研究思维规律的一门学科由于它使用了一套符号，简洁的表达出各种推理的逻辑关系，因此数理逻辑一般又称为符号逻辑Ø数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础2021/7/233数理逻辑的发展前期前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论初创时期——逻辑代数时期（17世纪末） (1)资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用 (2)人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算2021/7/234数理逻辑的发展前期 (3)莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。

使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开使得演算从很大程度上取决与符号 的组合规律，而与其含义无关2021/7/235数理逻辑的发展前期 (4)布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算2021/7/236数理逻辑的奠基时期弗雷格(G.Frege,1848~1925)：《概念语言—一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分—命题演算和谓词演算的正式建立皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统2021/7/237数理逻辑的奠基时期罗素(Bertrand Russell,1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义类和关系的概念，建立了抽象的类演算和关系演算由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。

2021/7/238数理逻辑的奠基时期逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴含怪论和严格蕴含、相干逻辑等，卢卡西维茨的多值逻辑等2021/7/239第1章 命题逻辑 命题逻辑研究的是以原子命题为基本单位的推理演算，其特征在于，研究和考查逻辑形式时，我们把一个命题只分析到其中所含的原子命题成分为止通过这样的分析可以显示出一些重要的逻辑形式，这种形式和有关的逻辑规律就属于命题逻辑2021/7/23101.1 命题与联结词q数理逻辑研究的数理逻辑研究的中心问题中心问题是是推理推理q推理的推理的前提前提和和结论结论都是都是表达判断表达判断的的陈述句陈述句q表达判断的陈述句构成了推理的表达判断的陈述句构成了推理的基本单位基本单位2021/7/23111.1 1.1 命题与联结词命题与联结词q称能判断真假而不是可真可假的陈述句为称能判断真假而不是可真可假的陈述句为命题命题（（proposition））。

q作为命题的陈述句所表达得的判断结果称为命题的作为命题的陈述句所表达得的判断结果称为命题的真值真值q真值只取两个：真值只取两个：真与假真与假q真值为真的命题称为真值为真的命题称为真命题真命题q真值为假的命题称为真值为假的命题称为假命题假命题q感叹句、疑问句、祈使句都不能称为命题感叹句、疑问句、祈使句都不能称为命题q判断结果不唯一确定的陈述句不是命题判断结果不唯一确定的陈述句不是命题q陈述句中的悖论不是命题陈述句中的悖论不是命题说明说明2021/7/2312(1)(1)4 4是素数2)(2) (3)(3)x x大于大于y y4)(4)充分大的偶数等于两个素充分大的偶数等于两个素数之和5)(5)今天是星期二今天是星期二6)(6) (7)(7)请不要吸烟！请不要吸烟！(8)(8)这朵花真美丽啊！这朵花真美丽啊！(9)(9)我正在说假话我正在说假话例例1.11.1 判断下列句子是否为命题判断下列句子是否为命题 (1)(1)是，假命题是，假命题(2)(2)是，真命题是，真命题(3)(3)不是，无确定的真值不是，无确定的真值(4)(4)是，真值客观存在是，真值客观存在(5)(5)是，真值根据具体情况是，真值根据具体情况而定。

而定6)(6)不是，疑问句不是，疑问句(7)(7)不是，祈使句不是，祈使句(8)(8)不是，感叹句不是，感叹句(9)(9)不是，悖论不是，悖论2021/7/2313q一个陈述句一个陈述句能否分辨真假能否分辨真假和我们是否知道它的真假是和我们是否知道它的真假是两回事！两回事！例：小李去过长城例：小李去过长城q判断结果不唯一确定的陈述句不是命题判断结果不唯一确定的陈述句不是命题q陈述句中的悖论不是命题陈述句中的悖论不是命题即：要把即：要把““自指谓的自指谓的陈述陈述句句””排除命题之外排除命题之外例：本页这一行的这句话是假例：本页这一行的这句话是假说明说明2021/7/2314命题和真值的符号化命题和真值的符号化q用小写英文字母p,q,r…,pi ,qi ,ri …表示命题q用“1”表示真，用“0”表示假 r：：充分大的偶数等于两充分大的偶数等于两个素数之和个素数之和s：：今天是星期二今天是星期二p：：4 4是素数q：：q不能被分解成更简单的陈述句，称这样的命不能被分解成更简单的陈述句，称这样的命题为题为简单命题简单命题或或原子命题原子命题q由简单陈述句通过联结词而成的陈述句，称由简单陈述句通过联结词而成的陈述句，称这样的命题为这样的命题为复合命题复合命题。

2021/7/2315例例1.21.2将下面这段陈述中所出现的原子命题符号化，并指出它将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述们的真值，然后再写出这段陈述 是是有有理理数数是是不不对对的的；；2 2是是偶偶素素数数；；2 2或或4 4是是素素数数；；如如果果2 2是素数，则是素数，则3 3也是素数；也是素数；2 2是素数当且仅当是素数当且仅当3 3也是素数也是素数 p：： 是有理数是有理数q：：2 2是素数；是素数；r：：2 2是偶数是偶数s s：：3 3是素数；是素数；t：：4 4是素数是素数0111 10非非p；；q并且并且(与与)r；；q或或t t；；如果如果q，，则则s；；q当且仅当当且仅当s2021/7/2316例例例例1.21.21.21.2的讨论的讨论的讨论的讨论q半形式化形式半形式化形式q数理逻辑研究方法的主要特征是将论述或推数理逻辑研究方法的主要特征是将论述或推理中的理中的各种要素都符号化各种要素都符号化即构造各种符号即构造各种符号语言来代替自然语言语言来代替自然语言q形式化语言形式化语言：：完全由符号所构成的语言。

完全由符号所构成的语言q将联结词（将联结词（connective）符号化，消除其二义）符号化，消除其二义性，对其进行严格定义性，对其进行严格定义q例如：例如： 他他是是100100米或米或400400米赛跑的冠军米赛跑的冠军 鱼香肉丝或锅包肉，加一碗汤鱼香肉丝或锅包肉，加一碗汤2021/7/2317定义1.1 否定否定( (negation) )q设设p为命题，复合命题为命题，复合命题““非非p”(”(或或““p的否定的否定”)”)称为称为p的否定式的否定式, ,记作记作┐┐p，，符号符号┐┐称作称作否定联结词否定联结词，并规定，并规定┐┐p为真当且仅当为真当且仅当p为假为假 例如例如：：p：： 哈尔滨哈尔滨是一个大城市是一个大城市  ┐┐p：：哈尔滨是一个不大城市哈尔滨是一个不大城市 ┐┐p：：哈尔滨不是一个大城市哈尔滨不是一个大城市p┐┐p10012021/7/2318定义定义1.21.2 合取合取合取合取( ( ( (conjunctionconjunction) ) ) )q设设p,qp,q为二命题，复合命题为二命题，复合命题““p p并且并且q”(q”(或或““p p与与q”)q”)称为称为p p与与q q的的合取式合取式，记作，记作p∧qp∧q，，∧∧称称作作合取联结词合取联结词，并规定，并规定p∧qp∧q为为真当且仅当真当且仅当p p与与q q同时为真同时为真。

使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1)1)描述合取式的灵活性与多样性描述合取式的灵活性与多样性自然语言中的自然语言中的““既既…………又又……”……”、、““不但不但…………而且而且……”……”、、““虽然虽然…………但是但是……”……”、、““一面一面…………一面一面……”……”等联结词都等联结词都可以符号化为可以符号化为∧∧2)2)分清简单命题与复合命题分清简单命题与复合命题不要见到不要见到““与与””或或““和和””就使用联结词就使用联结词∧∧ pqp∧∧q1 1 1 11 11 10 00 00 01 10 00 000 02021/7/2319例1.3 将下列命题符号化将下列命题符号化(1)(1)吴颖既用功又聪明吴颖既用功又聪明2)(2)吴颖不仅用功而且聪明吴颖不仅用功而且聪明3)(3)吴颖虽然聪明，但不用功吴颖虽然聪明，但不用功4)(4)张辉与王丽都是三好学生张辉与王丽都是三好学生5)(5)张辉与王丽是同学张辉与王丽是同学 p: p: 吴颖用功吴颖用功q: q: 吴颖聪明吴颖聪明r: r: 张辉是三好学生张辉是三好学生s: s: 王丽是三好学生。

王丽是三好学生t: t: 张辉与王丽是同学张辉与王丽是同学 (1)p∧q(1)p∧q(2)p∧q(2)p∧q(3)q∧┐p(3)q∧┐p(4)r∧s (4)r∧s (5)t(5)t解题要点：解题要点：正确理解命题含义正确理解命题含义找出原子命题并符号化找出原子命题并符号化选择恰当的联结词选择恰当的联结词 2021/7/2320合取举例合取举例qp：：我们去看电影我们去看电影q：：房间里有十张桌子房间里有十张桌子 p∧∧q：：我们去看电影并且房间里有十张桌子我们去看电影并且房间里有十张桌子 在数理逻辑中，关心的只是复合命题与构成复合在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容辑关系，并不关心各语句的具体内容说明说明2021/7/2321定义1.3 析取析取( (disjunction) )q设设p p，，q q为二命题，复合命题为二命题，复合命题““p p或或q q””称作称作p p与与q q的的析取式析取式，记作，记作p p∨∨q q，，∨∨称作称作析取联结词析取联结词，并，并规定规定p p∨∨q q为假当且仅当为假当且仅当p p与与q q同同时为假时为假。

自然语言中的自然语言中的““或或””具有二义性，用它联结的命具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或结词分别称为相容或和排斥或排斥或( (排异或排异或) ) 说明说明pqp∨∨q1 1 1 11 11 10 01 10 01 11 10 000 02021/7/2322例例1.4 1.4 将下列命题符号化将下列命题符号化 (1)(1)张晓静爱唱歌或爱听音乐张晓静爱唱歌或爱听音乐2)(2)张晓静只能挑选张晓静只能挑选202202或或203203房间3)(3)张晓静是江西人或安徽人张晓静是江西人或安徽人4)(4)他昨天做了二十或三十道习题他昨天做了二十或三十道习题1)(1)设设 p p：：张晓静爱唱歌，张晓静爱唱歌，q q：：张晓静爱听音乐张晓静爱听音乐相容或，符号化为相容或，符号化为 p p∨∨q q(2)(2)设设t t：：张晓静挑选张晓静挑选202202房间，房间， u u：：张晓静挑选张晓静挑选203203房间排斥或，符号化为：排斥或，符号化为：( (t t∧┐∧┐u u)∨(┐)∨(┐t t∧∧u u) )(3)(3)设设r r：：张晓静是江西人，张晓静是江西人， s s：：张晓静是安徽人。

张晓静是安徽人排斥或，符号化为：排斥或，符号化为：r r∨∨s s (排斥或排斥或联结的两个命题事实上不可能同时为真联结的两个命题事实上不可能同时为真) )或符号化为：或符号化为：( (r∧┐s)∨(┐r∧s)r∧┐s)∨(┐r∧s)(4)(4)原子命题，因为原子命题，因为““或或””只表示了习题的近似数目只表示了习题的近似数目2021/7/2323定义定义1.41.4 蕴涵蕴涵蕴涵蕴涵( (implicationimplication) )q设设p p，，q q为二命题，复合命题为二命题，复合命题““如果如果p p，，则则q q””称作称作p p与与q q的的蕴涵式蕴涵式，记作，记作p p→→q q，，并称并称p p是蕴涵式的是蕴涵式的前件前件，，q q为蕴涵式的为蕴涵式的后件后件，，→→称作称作蕴涵联结词蕴涵联结词, ,并规定并规定p p→→q q为假当且仅当为假当且仅当p p为真为真q q为假为假 说明说明qp→→q的逻辑关系表示的逻辑关系表示q是是p的必要条件的必要条件 是是p的必要条件有许多不同的叙述方式的必要条件有许多不同的叙述方式 –只要只要p，，就就q –因为因为p，，所以所以q–p仅当仅当q–只有只有q才才p–除非除非q才才p–除非除非q，，否则非否则非p pqp →→q1 1 1 11 11 10 00 00 01 11 10 001 12021/7/2324例例例例1.5 1.5 1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 (1)(1)如果如果3+33+3＝＝6 6，则雪是白的。

则雪是白的2)(2)如果如果3+3≠63+3≠6，则雪是白的则雪是白的3)(3)如果如果3+33+3＝＝6 6，则雪不是白的则雪不是白的4)(4)如果如果3+3≠63+3≠6，则雪不是白的则雪不是白的解：令解：令p p：：3+33+3＝＝6 6，，p p的真值为的真值为1 1    q q：：雪是白色的，雪是白色的，q q的真值也为的真值也为1 1 (1)p→→q (2)(2)┐┐p→→q (3) p→┐→┐q (4)(4) ┐ ┐p→┐→┐q11012021/7/2325例例例例1.5 1.5 1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 以下命题中出现的以下命题中出现的a a是一个给定的正整数：是一个给定的正整数： (5) (5) 只要只要a a能被能被4 4整除，则整除，则a a一定能被一定能被2 2整除 (6) (6) a a能被能被4 4整除，仅当整除，仅当a a能被能被2 2整除 (7) (7) 除非除非a a能被能被2 2整除，整除， a a才能被才能被4 4整除。

整除8) (8) 除非除非a a能被能被2 2整除，否则整除，否则a a不能被不能被4 4整除9)(9) 只有只有a a能被能被2 2整除，整除， a a才能被才能被4 4整除10)(10)只有只有a a能被能被4 4整除，整除， a a才能被才能被2 2整除 解：解：令令r r：： a a能被能被4 4整除整除   s s：： a a能被能被2 2整除整除 (5)(5)至至(9)(9)五个命题均叙述的是五个命题均叙述的是a a能被能被2 2整除是整除是a a能被能被4 4整除的必要整除的必要条件条件，因而都符号化为，因而都符号化为r r→→s s其真值为其真值为1 1在在(10)(10)中，中，将将a a能被能被4 4整除看成了整除看成了a a能被能被2 2整除的必要条件整除的必要条件，因而，因而应符号化为应符号化为s s→→r r a a值不定时，真值未知值不定时，真值未知2021/7/2326关于蕴含的进一步说明关于蕴含的进一步说明q作为一种规定，当作为一种规定，当p p为假时，无论为假时，无论q q是真是假，是真是假，p p→→q q均为真也就是说，只有也就是说，只有p p为真为真q q为假这一种情况使得复合命题为假这一种情况使得复合命题p p→→q q为假。

称为为假称为实质蕴含实质蕴含q例：如果例：如果x>5x>5，，则则x>2x>21) (1) x=6x=6如果如果6>56>5，则，则6>26>22) (2) x=3 x=3 如果如果3>53>5，则，则3>23>23) (3) x=1 x=1 如果如果1>51>5，则，则1>21>2 q例：如果我有车，那么我去接你例：如果我有车，那么我去接你 q常出现的错误，没有分清充分条件与必要条件常出现的错误，没有分清充分条件与必要条件2021/7/2327定义定义1.51.5 等价等价等价等价( (two-way-implicationtwo-way-implication) )q设设p p，，q q为二命题，复合命题为二命题，复合命题““p p当且仅当当且仅当q q””称作称作p p与与q q的的等价式等价式，，记作记作p pq q，，称作称作等价联结词等价联结词，并，并规定规定p pq q为真当且仅当为真当且仅当p p与与q q同时同时为真或同时为假为真或同时为假说明说明q“当且仅当当且仅当”（（if and only if））qp pq q的逻辑关系为的逻辑关系为p p与与q q互为充分必要条件。

互为充分必要条件 q( (p→q)∧(q→pp→q)∧(q→p) )与与p pq q的逻辑关系完全一致的逻辑关系完全一致pqp q1 1 1 11 11 10 00 00 01 10 00 001 12021/7/2328例例例例1.6 1.6 1.6 1.6 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值 (1)(1)ππ是无理数当且仅当加拿大位于亚洲是无理数当且仅当加拿大位于亚洲2)(2)2+32+3＝＝5 5的充要条件是的充要条件是ππ是无理数是无理数3)(3)若两圆若两圆A A，，B B的面积相等，则它们的半径相等；反之亦的面积相等，则它们的半径相等；反之亦然4)(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快一定心情愉快1)(1)设设 p p：：ππ是无理数是无理数，，q q：：加拿大位于亚洲加拿大位于亚洲符号化为符号化为 p pq q，，真值为真值为0 02)(2)设设 p p：：2+32+3＝＝5 5，， q q：：ππ是无理数是无理数。

符号化为符号化为 p pq q，，真值为真值为1 12021/7/2329例例例例1.6 1.6 1.6 1.6 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值 (1)(1)ππ是无理数当且仅当加拿大位于亚洲是无理数当且仅当加拿大位于亚洲2)(2)2+32+3＝＝5 5的充要条件是的充要条件是ππ是无理数是无理数3)(3)若两圆若两圆A A，，B B的面积相等，则它们的半径相等；反之亦然的面积相等，则它们的半径相等；反之亦然4)(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快心情愉快1)(1)设设 p p：：两圆两圆A A，，B B的面积相等的面积相等，， q q：：两圆两圆A A，，B B的半径相等的半径相等符号化为符号化为 p pq q，，真值为真值为1 12)(2)设设 p p：：王小红心情愉快王小红心情愉快，， q q：：王小红唱歌王小红唱歌符号化为符号化为 p pq q，，真值由具体情况而定。

真值由具体情况而定2021/7/2330关于基本联结词的说明关于基本联结词的说明q{┐,∧,∨,→,{┐,∧,∨,→,} }，称为一个联结词集称为一个联结词集q由联结词集由联结词集{┐,∧,∨,→,{┐,∧,∨,→,} }中的一个联结词联结一个或中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以两个原子命题组成的复合命题是最简单的复合命题，可以称它们为称它们为基本的复合命题基本的复合命题 q基本复合命题的真值见下表：基本复合命题的真值见下表： 2021/7/2331关于基本联结词的说明关于基本联结词的说明q多次使用联结词集中的联结词，可以组成更为复杂的复合多次使用联结词集中的联结词，可以组成更为复杂的复合命题 q求复杂复合命题的真值时，除依据上表外，还要规定联结求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内词的优先顺序，将括号也算在内q本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：( )( )，，┐┐，，∧∧，，∨∨，，→→，， ，对于同一优先级的联结词，先出现者先运算对于同一优先级的联结词，先出现者先运算。

2021/7/2332例例1.71.7令令 p p：：北京比天津人口多北京比天津人口多q q：：2+22+2＝＝4. 4.        r r：：乌鸦是白色的乌鸦是白色的 求下列复合命题的真值：求下列复合命题的真值： (1)((┐(1)((┐p∧q)∨(p∧┐q))→r p∧q)∨(p∧┐q))→r  (2)(q∨r)→(p→┐r) (2)(q∨r)→(p→┐r)  (3)(┐p∨r)(3)(┐p∨r)(p∧┐r) (p∧┐r) 解：解：p p、、q q、、r r的真值分别为的真值分别为1 1、、1 1、、0 0     (1) 1(1) 1(2) 1(2) 1(3) 0(3) 0我们关心的是复合命题中命题之间的真值关系，我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容而不关心命题的内容 说明说明2021/7/23331.2 1.2 命题公式及其赋值命题公式及其赋值q简单命题是真值唯一确定的命题逻辑中最基本的研究单位，简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为所以也称简单命题为命题常项命题常项或或命题常元命题常元 (proposition constant) )q称真值可以变化的陈述句为称真值可以变化的陈述句为命题变项命题变项或或命题变元命题变元 ( (proposition variable) )。

也用也用p,q,r,…p,q,r,…表示命题变项表示命题变项q当当p,q,r,…p,q,r,…表示命题变项时，它们就成了取值表示命题变项时，它们就成了取值0 0或或1 1的变项，的变项，因而因而命题变项已不是命题命题变项已不是命题q这样一来，这样一来，p,q,r,…p,q,r,…既可以表示命题常项，也可以表示命题既可以表示命题常项，也可以表示命题变项在使用中，需要由上下文确定它们表示的是常项还是变项在使用中，需要由上下文确定它们表示的是常项还是变项q将命题变项用联结词和圆括号按一定的逻辑关系联结起来的将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为符号串称为合式公式合式公式或或命题公式命题公式2021/7/2334定义定义1.1.3 3 合式公式合式公式( ( wff ) )(1)(1)单个命题变项是合式公式，并称为单个命题变项是合式公式，并称为原子命题公式原子命题公式2)(2)若若A A是合式公式，则是合式公式，则(┐(┐A)A)也是合式公式也是合式公式 (3)(3)若若A A，，B B是合式公式，则是合式公式，则( (A∧B)A∧B)，，(A∨B)(A∨B)，，(A→B)(A→B)，，(A(AB)B)也是合式公式。

也是合式公式4)(4)只有有限次地应用只有有限次地应用(1)(1)～～(3)(3)形式的符号串才是合式公形式的符号串才是合式公式合式公式也称为合式公式也称为命题公式命题公式或或命题形式命题形式，并简称为，并简称为公式公式设设A A为合式公式，为合式公式，B B为为A A中一部分，若中一部分，若B B也是合式公式，则称也是合式公式，则称B B为为A A的的子公式子公式 合式公式：合式公式：Well Formed Formula 2021/7/2335关于合式公式的说明关于合式公式的说明q定义定义1.1.3 3给出的合式公式的定义方式称为给出的合式公式的定义方式称为归纳定义归纳定义或或递归定义递归定义方方式q定义中引进了定义中引进了A,BA,B等符号，用它们表示任意的合式公式，而不是等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与某个具体的公式，这与p, p∧q, (p∧q)→rp, p∧q, (p∧q)→r等具体的公式是有等具体的公式是有所不同的所不同的 qA,BA,B等符号被称作元语言符号等符号被称作元语言符号p,qp,q等被称作对象语言符号等被称作对象语言符号。

q所谓所谓对象语言对象语言是指用来描述研究对象的语言，而是指用来描述研究对象的语言，而元语言元语言是指用是指用来描述对象的语言，这两种语言是不同层次的语言来描述对象的语言，这两种语言是不同层次的语言q例如中国人学习英语时，英语为对象语言，而用来学习英语的例如中国人学习英语时，英语为对象语言，而用来学习英语的汉语则是元语言汉语则是元语言2021/7/2336关于合式公式的说明关于合式公式的说明q(┐(┐A)A)、、(A∧B)(A∧B)等公式单独出现时，外层括号可以省去，写成等公式单独出现时，外层括号可以省去，写成┐┐A A、、A∧BA∧B等q公式中不影响运算次序的括号可以省去，公式中不影响运算次序的括号可以省去，如公式如公式( (p∨q)∨(┐r)p∨q)∨(┐r)可以写成可以写成p∨q∨┐rp∨q∨┐r q合式公式的例子：合式公式的例子：( (p→q)∧(q p→q)∧(q  r) r)(p∧q)∧┐r(p∧q)∧┐rp∧(q∧┐r)p∧(q∧┐r)q不是合式公式的例子不是合式公式的例子pq→rpq→r(p→(r→q) (p→(r→q) 2021/7/2337定义定义1.7 1.7 公式层次公式层次(1)(1)若公式若公式A A是单个的命题变项，则称是单个的命题变项，则称A A为为0 0层合式层合式。

2)(2)称称A A是是n+1(n≥0)n+1(n≥0)层公式层公式是指下面情况之一：是指下面情况之一： (a) A(a) A＝＝┐B┐B，，B B是是n n层公式；层公式；(b) A(b) A＝＝B∧CB∧C，，其中其中B,CB,C分别为分别为i i层和层和j j层公式，且层公式，且n=max(i,j)n=max(i,j)；；(c) A(c) A＝＝B∨CB∨C，，其中其中B,CB,C的层次及的层次及n n同同( (b)b)；； (d) A(d) A＝＝B→CB→C，，其中其中B,CB,C的层次及的层次及n n同同( (b)b)；； (e) A(e) A＝＝B BC C，，其中其中B,CB,C的层次及的层次及n n同同( (b)b) (3)(3)若公式若公式A A的层次为的层次为k k，，则称则称A A是是k k层公式层公式 例如：例如：(┐p∧q)→r(┐p∧q)→r，，(┐(p→┐q))∧((r∨s)(┐(p→┐q))∧((r∨s)┐p)┐p)分别为分别为3 3层和层和4 4层公式层公式 2021/7/2338公式的解释公式的解释q在命题公式中，由于有命题符号的出现，因而真值是不确定在命题公式中，由于有命题符号的出现，因而真值是不确定的。

当将公式中出现的全部命题符号都解释成具体的命题之的当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了后，公式就成了真值确定的命题了q( (p∨q)→rp∨q)→rq若若p p：：2 2是素数，是素数，q q：：3 3是偶数，是偶数，r r：：ππ是无理数，则是无理数，则p p与与r r被解释被解释成真命题，成真命题，q q被解释成假命题，此时公式被解释成假命题，此时公式( (p∨q)→rp∨q)→r被解释成：被解释成：若若2 2是素数或是素数或3 3是偶数，则是偶数，则ππ是无理数真命题）是无理数真命题）qr r被解释为：被解释为：ππ是有理数，则是有理数，则( (p∨q)→rp∨q)→r被解释成：若被解释成：若2 2是素数是素数或或3 3是偶数，则是偶数，则ππ是有理数假命题）是有理数假命题）q将命题变项将命题变项p p解释成真命题，相当于指定解释成真命题，相当于指定p p的真值为的真值为1 1，解释成，解释成假命题，相当于指定假命题，相当于指定p p的真值为的真值为0 0 2021/7/2339定义定义1.8 1.8 赋值或解释赋值或解释q设设p p1 1,p,p2,2,…,p…,pn n是出现在公式是出现在公式A A中的全部命题变项，给中的全部命题变项，给p p1 1,p,p2,2,…,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 1＝＝αα1 1，，p p2 2＝＝αα2 2,…,…，，p pn n＝＝ααn n (2)(2)若若A A中出现的命题符号为中出现的命题符号为p p，，q q，，r...,r...,给定给定A A的赋值的赋值αα1,1,αα2,2,…,α…,αn n是指是指p p＝＝αα1 1，，q q＝＝αα2 2,…,…，，最后一个字母赋最后一个字母赋值值ααn n 上述上述ααi i取值为取值为0 0或或1 1，，i i＝＝1,2,…,n1,2,…,n 2021/7/2340赋值举例赋值举例q在公式在公式(┐(┐p p1 1∧┐p∧┐p2 2∧┐p∧┐p3 3)∨(p)∨(p1 1∧p∧p2 2) )中，中，000(000(p p1 1＝＝0 0，，p p2 2＝＝0 0，，p p3 3＝＝0)0)，，110(p110(p1 1＝＝1 1，，p p2 2＝＝1 1，，p p3 3＝＝0)0)都是成真赋值，都是成真赋值，001(001(p p1 1＝＝0 0，，p p2 2＝＝0 0，，p p3 3＝＝1)1)，，011(p011(p1 1＝＝0 0，，p p2 2＝＝1 1，，p p3 3＝＝1)1)都是成假赋值。

都是成假赋值q在在( (p∧┐q)→rp∧┐q)→r中，中，011(011(p p1 1＝＝0 0，，p p2 2＝＝1 1，，p p3 3＝＝1)1)为成真赋值，为成真赋值，100(100(p p1 1＝＝1 1，，p p2 2＝＝0 0，，p p3 3＝＝0)0)为成假赋值为成假赋值 q重要结论：重要结论：含含n(n≥1)n(n≥1)个命题变项的公式共有个命题变项的公式共有2 2n n个不同的赋值个不同的赋值 2021/7/2341定义定义1.9 1.9 真值表真值表q将命题公式将命题公式A A在所有赋值下取值情况列成表，称作在所有赋值下取值情况列成表，称作A A的的真值表真值表 q构造真值表的具体步骤如下：构造真值表的具体步骤如下： (1)(1)找出公式中所含的全体命题变项找出公式中所含的全体命题变项p p1 1,p,p2 2,…,,…,p pn n ( (若无下角标就若无下角标就按字典顺序排列按字典顺序排列) )，列出，列出2 2n n个赋值本书规定，赋值从个赋值本书规定，赋值从00…000…0开始，然后按二进制加法依次写出各赋值，直到开始，然后按二进制加法依次写出各赋值，直到11…111…1为止。

为止 (2)(2)按从低到高的顺序写出公式的各个层次按从低到高的顺序写出公式的各个层次 (3)(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的对应各个赋值计算出各层次的真值，直到最后计算出公式的真值 公式公式A A与与B B具有相同的或不同的真值表，是指真值表的最具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程后一列是否相同，而不考虑构造真值表的中间过程 说明说明2021/7/2342例例1.8 1.8 求下列公式的真值表，并求成真赋值和成假赋值求下列公式的真值表，并求成真赋值和成假赋值1)(┐(1)(┐p∧q)→┐r p∧q)→┐r (2)((2)(p∧┐p)p∧┐p)(q∧┐q) (q∧┐q) (3)┐((3)┐(p→q)∧q∧rp→q)∧q∧r 2021/7/2343定义定义1.7 1.7 重言式、永真式、可满足式重言式、永真式、可满足式设设A A为任一命题公式为任一命题公式 (1)(1)若若A A在它的各种赋值下取值均为真在它的各种赋值下取值均为真, ,则称则称A A是是重言式重言式( (tautology) )或或永真式永真式。

(2)(2)若若A A在它的各种赋值下取值均为假在它的各种赋值下取值均为假, ,则称则称A A是是矛盾式矛盾式( (contradiction) )或或永假式永假式 (3)(3)若若A A不是矛盾式不是矛盾式, ,则称则称A A是是可满足式（可满足式（satisfactable formula）） 2021/7/2344定义定义1.71.7的进一步说明的进一步说明qA A是可满足式的等价定义是：是可满足式的等价定义是：A A至少存在一个成真赋值至少存在一个成真赋值q重言式一定是可满足式，但反之不真因而，若公式重言式一定是可满足式，但反之不真因而，若公式A A是可满是可满足式，且它至少存在一个成假赋值，则称足式，且它至少存在一个成假赋值，则称A A为非重言式的可满为非重言式的可满足式q真值表可用来判断公式的类型真值表可用来判断公式的类型: :–若真值表最后一列全为若真值表最后一列全为1 1，则公式为重言式则公式为重言式 –若真值表最后一列全为若真值表最后一列全为0 0，则公式为矛盾式则公式为矛盾式–若真值表最后一列中至少有一个若真值表最后一列中至少有一个1 1，则公式为可满足式。

则公式为可满足式 说明说明qn n个命题变项共产生个命题变项共产生2 2n n个不同赋值个不同赋值q含含n n个命题变项的公式的真值表只有个命题变项的公式的真值表只有 种不同情况种不同情况 2021/7/2345例题例题例题例题1.91.9 下列各公式均含两个命题变项下列各公式均含两个命题变项p p与与q q，，它们中它们中哪些具有相同的真值表哪些具有相同的真值表? ? (1) p→q(1) p→q(4) (4) ( (p→q)∧(q→p)p→q)∧(q→p)(2) p(2) pq q(5) (5) ┐┐q∨pq∨p(3) ┐((3) ┐(p∧┐q) p∧┐q) 2021/7/2346哑元哑元q设公式A,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 n , ,称这些命题变项为称这些命题变项为A A的的哑元哑元，，A A的的取值与哑元的变化无关，因而在讨论取值与哑元的变化无关，因而在讨论A A与与B B是否有是否有相等的真值表时，将相等的真值表时，将A,BA,B都看成都看成p p1 1,p,p2,2,…,p…,pn n的命的命题公式。

题公式 2021/7/2347例题例题 例例1.101.10 下列公式中下列公式中, ,哪些具有相同的真值表哪些具有相同的真值表? ?(1)p→q (1)p→q (2)┐(2)┐q∨r q∨r (3)(┐(3)(┐p∨q)∧((p∧r)→p) p∨q)∧((p∧r)→p) (4)((4)(q→r)∧(p→p) q→r)∧(p→p) 2021/7/2348本章主本章主要内容要内容q命题与真值（或真假值）命题与真值（或真假值）q简单命题与复合命题简单命题与复合命题q联结词：联结词：┐┐，，∧∧，，∨∨，，→→，，q命题公式（简称公式）命题公式（简称公式）q命题公式的层次和公式的赋值命题公式的层次和公式的赋值 q真值表 q公式的类型：重言式（永真式），矛盾式（永假式），公式的类型：重言式（永真式），矛盾式（永假式），可满足式可满足式 2021/7/2349本章学习要求本章学习要求q在在5 5种联结词中，要特别注意蕴涵联结的应用，要弄种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：清三个问题： –p→q p→q 的逻辑关系的逻辑关系 –p→q p→q 的真值的真值 –p→q p→q 的灵活的叙述方法的灵活的叙述方法q写真值表要特别仔细认真，否则会出错误。

写真值表要特别仔细认真，否则会出错误 q深刻理解各联结词的逻辑含义深刻理解各联结词的逻辑含义 q熟练地将复合命题符号化熟练地将复合命题符号化 q会用真值表求公式的成真赋值和成假赋值会用真值表求公式的成真赋值和成假赋值 2021/7/2350本章典型习题本章典型习题q命题符号化命题符号化q求复合命题的真值与命题公式的赋值求复合命题的真值与命题公式的赋值q判断公式的类型判断公式的类型2021/7/2351例题：命题符号化例题：命题符号化(1)(1)我和他既是兄弟又是同学我和他既是兄弟又是同学 p p：：我和他是兄弟，我和他是兄弟，q q：：我和他是同学我和他是同学故命题可符号化为：故命题可符号化为： p∧qp∧q2)(2)张三或李四都可以做这件事张三或李四都可以做这件事 p p：：张三可以做这件事张三可以做这件事 q q：：李四可以做这件事李四可以做这件事故命题可符号化为：故命题可符号化为：p∨qp∨q (3)(3)仅当我有时间且天不下雨，我将去镇上仅当我有时间且天不下雨，我将去镇上对于对于““仅当仅当””，实质上是，实质上是““当当””的逆命题的逆命题当当A A则则B”B”是是A→BA→B，，而而““仅当仅当A A则则B”B”是是B→AB→A。

p p：：我有时间我有时间 q q：：天不下雨天不下雨 r r：：我将去镇上我将去镇上故命题可符号化为：故命题可符号化为：r→(p∧q)r→(p∧q) 2021/7/2352例题：命题符号化例题：命题符号化例题：命题符号化例题：命题符号化(4)(4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病张刚总是在图书馆看书，除非图书馆不开门或张刚生病 对于对于““除非除非””，只要记住，，只要记住，““除非除非””是条件p p：：张刚在图书馆看书，张刚在图书馆看书，q q：：图书馆不开门，图书馆不开门，r r：：张刚生病张刚生病 故命题可符号化为：故命题可符号化为：﹁﹁(q∨r)→p(q∨r)→p (5)(5)风雨无阻，我去上学风雨无阻，我去上学可理解为可理解为““不管是否刮风、是否下雨，我都去上学不管是否刮风、是否下雨，我都去上学”” p p：：天刮风，天刮风，q q：：天下雨，天下雨，r r：：我去上学我去上学故命题可符号化为：故命题可符号化为：( (p∧q→r) ∨(p∧┐q→r) ∨(┐p∧q→r) ∨(┐p∧┐q→r)p∧q→r) ∨(p∧┐q→r) ∨(┐p∧q→r) ∨(┐p∧┐q→r)或或( (p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r)p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r) 理解为理解为““四种情况必居其一四种情况必居其一, ,而每种情况下我都去上学而每种情况下我都去上学”” 2021/7/2353命题符号化的要点命题符号化的要点q要准确确定原子命题，并将其形式化要准确确定原子命题，并将其形式化。

q要要选选用用恰恰当当的的联联结结词词，，尤尤其其要要善善于于识识别别自自然然语语言言中中的联结词（有时它们被省略）的联结词（有时它们被省略）q否定词的位置要放准确否定词的位置要放准确q需需要要的的括括号号不不能能省省略略，，而而可可以以省省略略的的括括号号，，在在需需要要提高公式可读性时亦可不省略提高公式可读性时亦可不省略q要注意的是要注意的是, ,语句的形式化未必是唯一的语句的形式化未必是唯一的2021/7/2354例题：求公式例题：求公式┐(p→(q∧r))┐(p→(q∧r))的真值表的真值表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 1q∧rq∧r0 00 00 01 10 00 00 01 1p→(qp→(q∧r)∧r)1 11 11 11 10 00 00 01 1┐(┐(p→(q∧r))p→(q∧r))0 00 00 00 01 11 11 10 02021/7/2355本章作业本章作业习题一习题一1 1、、9 9、、1414、、1515、、1818、、19192021/7/2356个人观点供参考，欢迎讨论。