第一编集合论

《第一编集合论》由会员分享，可在线阅读，更多相关《第一编集合论（81页珍藏版）》请在金锄头文库上搜索。

1、第一编 集合论第一章 集合1 Peking University1.1 预备知识（prerequisites）命题逻辑和谓词逻辑是数理逻辑中最基本的内容。命题逻辑和谓词逻辑是数理逻辑中最基本的内容。l十九世纪中后期，德国数学家莱布尼兹、英国数学家十九世纪中后期，德国数学家莱布尼兹、英国数学家布尔和逻辑学家怀海特、罗素为数理逻辑的产生和发布尔和逻辑学家怀海特、罗素为数理逻辑的产生和发展有突出贡献。展有突出贡献。l从二十世纪从二十世纪4040年代起，数理逻辑成为计算机科学的重年代起，数理逻辑成为计算机科学的重要基础理论之一。如布尔代数在计算机硬件设计中发要基础理论之一。如布尔代数在计算机硬件设计中

2、发挥了重大作用；形式语言的研究为建立计算机语言提挥了重大作用；形式语言的研究为建立计算机语言提供了基础。供了基础。2 Peking University命题和命题联结词命题公式和真值表命题等值式命题推理定律命题逻辑3 Peking University命题是客观上能判明真假的陈述句。当命题为真时，称命题的真值为“真”；否则，说命题的真值为“假”。用T或1表示“真”，用F或0表示“假”。 （ Proposition: a statement that is either true or false,but not both.）所有这些命题，都应具有确定的真值。4 Peking Universit

3、y判断下列语句是不是命题:(1) 天气多好啊!(2) 你去哪里？(3) X3。(4) 别的星球有生物。(5) 我正在说慌。解：(1)(1)是感叹句；是感叹句；(2)(2)是疑问句；它们都不是命题。是疑问句；它们都不是命题。 (3) (3) 真假要视的值而定，因此这个语句无确定真假要视的值而定，因此这个语句无确定真值。它不是命题。真值。它不是命题。 (4) (4)的真实性目前还无法判明，但在客观上，是真的真实性目前还无法判明，但在客观上，是真是假，二者必居其一。因此它是命题。是假，二者必居其一。因此它是命题。 (5)(5)同同样样不不能能判判明明真真假假。如如说说该该命命题题为为真真，但但原原语

4、语句句却却说说“本本命命题题为为假假”；如如果果说说它它为为假假，却却又又肯肯定定了了它它( (本本命命题题) )是是真真的的，这这样样造造成成了了自自相相矛矛盾盾的的结结果果！这这是所谓悖论。是所谓悖论。5 Peking University无法继续分解的简单陈述句，称为简单命题或无法继续分解的简单陈述句，称为简单命题或原子命题原子命题。(不包含任何不包含任何“与、或、非与、或、非”等联等联结词的命题结词的命题)由一个或几个简单命题通过由一个或几个简单命题通过联结词联结词复合而成的复合而成的命题，称为命题，称为复合命题复合命题。(1)期中考试，张三没有考及格期中考试，张三没有考及格(2)期中

5、考试，张三和李四都考及格了期中考试，张三和李四都考及格了(3)期中考试，张三和李四有人考期中考试，张三和李四有人考90分分(4)如果张三考如果张三考90分，李四也能考分，李四也能考90分分(5)张三能考张三能考90分当且仅当李四也考分当且仅当李四也考90分分6 Peking University否定联结词合取联结词析取联结词蕴涵联结词等价联结词 命题联结词7 Peking University定义1 否定联结词设设为为命命题题，复复合合命命题题非非，叫叫的的否否定定式式，记记作作 。记记号号 叫叫否否定定联联结结词词。 为真当且仅当为假。为真当且仅当为假。 例如，设：今天是星期二。 则：今天不

6、是星期二。8 Peking University定义2 合取联结词设设，表表示示两两个个命命题题，复复合合命命题题“且且”叫叫命命题题与与的的合合取取，记记作作。记记号号叫叫合合取取联联结结词词。为为真真，当当且且仅仅当当，同时为真。同时为真。 例如，设: 2是素数。 : 2是偶数。R： 2是奇数。 则：2既是素数又是偶数。(真值为真) R：2既是素数又是奇数。(真值为假)9 Peking University定义3 析取联结词设设，为为二二命命题题，复复合合命命题题“或或”称称作作与与的的析析取取，记记作作，叫叫析析取取联联结结词词。为为真真，当当且且仅仅当当，之之中至少有一为真。中至少有一

7、为真。 例如，设：2是素数。：2是偶数。 R： 2是奇数。 则：2是素数或2是偶数。(真值为真) R：2是素数或2是奇数。(真值为真)10 Peking University2-30或今天天气很好。 他今天骑车或走路来上课。 从理科1号楼到图书馆要2分钟或4分钟。 意思：意思：意思：意思：大约大约大约大约2 2分钟到分钟到分钟到分钟到4 4分钟分钟分钟分钟pq一个人不可能同时一个人不可能同时骑车又走路骑车又走路11 Peking University注：“或”有两种标准用法，张三或李四考了90分（相容“或”）第一节课上数学或者上英语12 Peking University定义4 蕴涵联结词设设

8、，是是二二命命题题，复复合合命命题题“如如，则则”称称为为与与的的蕴蕴涵涵式式，记记作作, 其其中中叫叫前前件件或或前前题题，叫叫后后件件或或结结论论。为真当且仅当真和假不同时成立为真当且仅当真和假不同时成立。 例如，如果明天天晴就开运动会。 设：明天天晴。:明天开运动会。 则原命题表示为：。 13 Peking University 蕴涵式、蕴涵联结词pq就就则则只要只要仅当仅当才才只有只有pq 蕴涵符号pqp q001011100111如果如果如果明天下雨，我们就放假 明天不下雨 我们不放假 明天不下雨我们放假 明天下雨我们不放假 明天下雨我们放假 14 Peking University

9、定义5 等价联结词设设,为为二二命命题题，复复合合命命题题“当当且且仅仅当当”称称为为与与的的等等价价式式，记记作作。叫叫等等价价联联结结词词，也也记记作作iff。为为真真当当且且仅仅当当,真真值值相同相同。 例如，2+24当且仅当雪是白的。 设： 2+24 。：雪是白的。 则原命题表示为：。15 Peking University命题一般用大写英文字母表示。表示命题的符号叫命题一般用大写英文字母表示。表示命题的符号叫命命题标识符题标识符。 例如，用表示“雪是黑的”，记作“：雪是黑的”。如如果果一一个个命命题题标标识识符符表表示示某某个个确确定定的的命命题题，则则称称为为命命题题常常量量。特特

10、别别地地，真真命命题题( (用用T T表表示示) )和和假假命命题题( (用用F F表表示示) )是命题常量。是命题常量。如如果果一一个个命命题题标标识识符符表表示示不不确确定定的的命命题题，则则称称为为命命题题变元变元。命题常量和命题变元命题变元不是命题命题变元不是命题。在命题演算中，对命题变元指定相应。在命题演算中，对命题变元指定相应的真值的真值( (真或假真或假) )，称为对命题变元的，称为对命题变元的真值指派真值指派。 集合集合 T,FT,F是是命题变元的值域命题变元的值域。16 Peking University相应的真值表相应的真值表17 Peking University命题公式

11、设P和Q是任意两个命题，则下列命题都是复合命题设P和Q是命题变元命题变元，则上述公式均称作命题公式命题公式。P和Q称作命题公式的分量。18 Peking University命题公式(1)单个命题变元（或常元）是命题公式；(2)若A是命题公式，则(A)是命题公式；(3)若A,B是命题公式，则（AB），（AB）, (AB), (A B)也是命题公式；(4)只有有限次应用(1)-(3)形成的符号串才是命题公式。注意： 命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个值。19 Peking University真值表(truth table)定义设为一命题公式，P1,

12、P2，, Pn为出现在中的所有命题变元，简记为（P1, P2，, Pn）。给命题变元P1, P2，, Pn指定一组真值，称为对的一个指派或一个赋值。含有个命题变元的命题公式（P1, P2，, Pn）共有n个指派。将命题公式（P1, P2，, Pn）在所有指派之下取值的情况列成表，叫的真值表。20 Peking University真值表命题形式A在其所有可能的赋值下取得的值列成的表； n元真值函数F: 0, 1n 0，1 (n1)。21 Peking University联结词的真值表22 Peking UniversityA的一个赋值赋值: n个命题变元成真赋值成真赋值成假赋值成假赋值重言式

13、重言式（永真式（永真式tautology）P P = 1矛盾式矛盾式（永假式（永假式contradiction）P P = 0可满足式可满足式23 Peking University 公式分类 重言式 矛盾式 可满足式重言式 24 Peking Universityp q pq pp p(pq)p 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 1 赋值 可满足式 矛盾式 重言式 (永假式) (永真式) 25 Peking University等值式（等价公式）给定两个命题公式（给定两个命题公式（P P1 1, P, P2 2，, P, Pn n）和和（P P1 1

14、, P, P2 2，, P, Pn n），），若对若对P P1 1, P, P2 2，, , P Pn n的任一的任一组真值指派，与的真值都相同，则称与组真值指派，与的真值都相同，则称与等价或逻辑相等。记作等价或逻辑相等。记作。例4 构造命题公式构造命题公式 （PQ）和和 P Q的真值表的真值表。对于、的任一种真值指派，对于、的任一种真值指派， （PQ）与与 P Q都有相同的真值，都有相同的真值，所以这所以这两个命题公式是等价的两个命题公式是等价的。26 Peking University 为书写方便而省略括号 公式最外层的括号可以省略 联结词运算优先级别 同一个联结词连续多次出现且无括号，则

15、从左到右运算 、 、 、27 Peking University例题：层次法构造真值表(p (pq) (pq) (p (pq) (pq) (p (pq) (pq) (p (pq) (pq) p q pq pq p(pq) (pq) 公式公式 0 00 11 01 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 028 Peking University等值式等值式(logical equivalences)29 Peking University AAA, AAA A(BC) (AB)(AC) A(BC) (AB)(AC) ABBA, ABBA(AB)C A(B

16、C) (AB)C A(BC)30 Peking University (AB) A B (AB) A BA (AB) AA (AB) A31 Peking UniversityA1 1, A0 0 A0 A, A1 A AA 1 AA 0 (对偶原理: -互换, 0-1互换)32 Peking UniversityA A AB AB AB (AB)(BA) 33 Peking UniversityAB AB AB BA (AB)(AB) A34 Peking University 设是合式公式中的一个部分，且也是一个合设是合式公式中的一个部分，且也是一个合式公式，则称是的式公式，则称是的子公式

17、子公式。 例例如，设：如，设： ( (PQ)PQ)（Q(RQ(R S)S)），），则则PQPQ、 RR S S、 S S、 Q(R Q(R S)S)都是的子公式。都是的子公式。置换规则定理（置换规则）： 设X是合式公式中的子公式，若是一个合式公式，且 ，用置换中的，得到新的合式公式，则。证明：证明：与除替换部分外均相同，又由于替换部分与除替换部分外均相同，又由于替换部分，即是说对任一指派，与真值相同，那么与对，即是说对任一指派，与真值相同，那么与对任一真值指派也应有相同的真值。故任一真值指派也应有相同的真值。故。35 Peking University等值演算： 由已知的等值式，应用置换规则推

18、演出新的等值式的过程。等值演算 P (Q R) P ( Q R) P ( Q R) ( P Q) R ( P Q) R ( P Q) R36 Peking University 给定命题公式(P1, P2，, Pn)，如果用某个命题公式Bi取代中的某个变元Pi，并且用Bi取代中出现的所有Pi，这样得到的命题公式称为命题公式的代入实例。 例例如，设：如，设：P(QP)，用用(RS)取代中的命题变取代中的命题变元得：元得：(RS)(Q(RS)，是的代入实例。是的代入实例。代入代入规则规则定理（代入规则）： 一个重言式的代入实例仍然是一个重言式。证明证明： 由于重言式的真值与真值指派无关，故对同一命

19、题由于重言式的真值与真值指派无关，故对同一命题变元变元都用某个都用某个命题公式命题公式代替代替，该重言式的真值仍为。，该重言式的真值仍为。例例 证明证明(PS)R) (PS)R)为重言式为重言式证：证：因因P P T，根据根据代入规则代入规则 (PS)R) (PS)R)T37 Peking University命题逻辑推理1. 推理的形式结构 前提: A1, A2, , Ak结论: B 推理的形式结构: (A1A2Ak)B 38 Peking University推理定律推理定律39 Peking University(1) 附加律 A(AB) 前提: A 结论: AB A(AB)是永真式 4

20、0 Peking University(2) 化简律 (AB)A, (AB)B前提: AB 结论: A (AB)A是永真式41 Peking University(3) 假言推理 (AB)AB 前提: AB A 结论: B (AB)A)B是永真式 42 Peking University(4) 拒取式 (AB) B A 前提: AB B 结论: A (AB) B)( A)是永真式 43 Peking University(5) 析取三段论 (AB)AB (AB)BA 前提: AB A 结论: B (AB)A)B是永真式 44 Peking University(6) 假言三段论 (AB)(BC

21、)(AC) 前提: AB BC 结论: AC (AB)(BC)(AC)是永真式 45 Peking University(7) 等价三段论 (AB)(BC)(AC) 前提: AB BC 结论: AC (AB)(BC)(AC)是永真式 46 Peking University(8) 构造性两难 (AB)(CD)(AC)(BD) 前提: AB CD AC 结论: BD 47 Peking University判断推理正确的方法判断推理正确的方法 例前提: p(qr), p, q 结论: r 方法一方法一: 推理的形式结构 方法二方法二: 从前提推演结论 48 Peking University方法

22、一方法一(形式结构是永真式) (p(qr)pqr (p(qr)pqr （蕴涵等值式）蕴涵等值式） (pp)(qr)p)qr （分配律）分配律） (qr)q)pr （零律，同一律，交换律）零律，同一律，交换律） (qq)(rq)pr （分配律）分配律） (rqp)r (rqp)r （蕴涵等值式）蕴涵等值式） rqpr (rr)qp 1 49 Peking University方法二方法二(从前提从前提推演推演结论结论) (p(qr)pq (p(qr)p)q (qr)q （假言推理）假言推理） r 50 Peking University命题逻辑命题和命题联结词命题公式和真值表命题等值式命题推理定

23、律51 Peking University命命 题题等值演算等值演算推理推理52 Peking University谓词逻辑 在在命命题题逻逻辑辑中中，研研究究命命题题和和命命题题的的演演算算。命命题题演演算算的的基基本本单单位位是是原原子子命命题题。在在命命题题演演算算中中，原原子子命命题题不不再再分分解解。命命题题逻逻辑辑在在推推证证中中有有很很大大的的局局限限性性，有有些些简简单的论断也不能用命题逻辑进行推证。单的论断也不能用命题逻辑进行推证。 例例如如，对对著著名名的的“苏苏格格拉拉底底三三段段论论”就就无无法法判判断断其其正正确确性性：“所所有有的的人人都都是是要要死死的的。苏苏格格

24、拉拉底底是是人人，所所以苏格拉底是要死的。以苏格拉底是要死的。” 为为了了克克服服命命题题逻逻辑辑的的局局限限性性，就就需需要要深深入入分分析析命命题题的的内内部部的的逻逻辑辑结结构构。为为此此，必必须须对对原原子子命命题题作作进进一一步的分解，引入谓词逻辑的概念。步的分解，引入谓词逻辑的概念。53 Peking University谓词逻辑 在在命命题题逻逻辑辑中中，研研究究命命题题和和命命题题的的演演算算。命命题题演演算算的的基基本本单单位位是是原原子子命命题题。在在命命题题演演算算中中，原原子子命命题题不不再再分分解解。命命题题逻逻辑辑在在推推证证中中有有很很大大的的局局限限性性，有有些

25、些简简单的论断也不能用命题逻辑进行推证。单的论断也不能用命题逻辑进行推证。 例例如如，对对著著名名的的“苏苏格格拉拉底底三三段段论论”就就无无法法判判断断其其正正确确性性：“所所有有的的人人都都是是要要死死的的。苏苏格格拉拉底底是是人人，所所以苏格拉底是要死的。以苏格拉底是要死的。” 为为了了克克服服命命题题逻逻辑辑的的局局限限性性，就就需需要要深深入入分分析析命命题题的的内内部部的的逻逻辑辑结结构构。为为此此，必必须须对对原原子子命命题题作作进进一一步的分解，引入谓词逻辑的概念。步的分解，引入谓词逻辑的概念。54 Peking University谓词的概念与量词谓词公式与翻译等价式、蕴含式

26、前束范式谓词逻辑55 Peking University谓词的概念 命题是反映判断的句子。反映判断的句子由主语和命题是反映判断的句子。反映判断的句子由主语和谓语两部分组成。主语一般是客体；用以刻划客体性质谓语两部分组成。主语一般是客体；用以刻划客体性质或关系的部分即是谓语。或关系的部分即是谓语。在命题中作为主语的客体称为个体。而。而用以描述个体性质或几个个体间关系的部分称为谓词。 例如对例如对“张三是大学生张三是大学生”和和“李四是大学生李四是大学生” ” 这两这两个命题，个体分别是个命题，个体分别是“张三张三”和和“李四李四”，谓词谓词都是都是“是大学生是大学生”。在作符号化处理时，用表示。

27、在作符号化处理时，用表示“是大学生是大学生”，用表示，用表示“张三张三”，用表示，用表示“李四李四”。上述两个。上述两个命题可分别表示为命题可分别表示为()和和() ，从而把命题中的主，从而把命题中的主语和谓语分离开来。语和谓语分离开来。56 Peking University谓词的概念(续)用用谓谓词词表表达达命命题题，必必须须包包括括个个体体和和谓谓词词两两部部分分。一一般般地地说说，“是是”类类型型的的命命题题可可用用( () )表表达达。而而表表示示两两个个或或两两个个以以上上客客体体之之间间关关系系的的命命题题，如如“大大于于”，“在在和和之之中中”，可可表表示示成成( (，) )，

28、( (，) )。这这里表示里表示“.“.大于大于.”.”，表示，表示“在在和和之中之中”。表示一个个体的性质的谓词称为一元谓词，如（e）。而表述个个体相互关系的谓词称为元谓词，可表示为(e1，e2， ， en)。 57 Peking University个体域对命题函数而言，客体变元的论述范围叫个体域，将所有个体域的集合(即宇宙间的一切事物)称为全总个体域。客体变元取值的范围对命题函数是否构成命题及命题的真值密切相关。 例例如如, 用用（）表表示示“是是大大学学生生”，如如果果的的取取值值范范围围是是某某大大学学某某班班中中的的全全体体学学生生，则则（）是是永永真真式式；如如果果的的取取值值范

29、范围围是是某某中中学学某某班班中中的的全全体体学学生生，则则（）是是永永假假式式；如如果果的的取取值值范范围围是是某某剧剧场场中中的的观观众众，则则（）的的真真值值可可真真可假，因为观众中可能有大学生，也可能有非大学生可假，因为观众中可能有大学生，也可能有非大学生58 Peking University量词 考考虑虑命命题题“所所有有的的人人都都是是要要死死的的”和和“有有些些人人能能活活百百岁岁以以上上”的的符符号号化化问问题题，除除个个体体变变元元和和谓谓词词之之外外，还还有有对对个个体体在在数数量量上上的的量量化化和约束和约束，如，如“所有的所有的”和和“有些有些”，称这种表示数量的词为

30、，称这种表示数量的词为量词量词。 用符号 表达“对所有的”，“对任一个”，“对每一个”等词，叫做全称量词。 例如，例如， “所有的人都是要死的所有的人都是要死的” 。设。设M(x) : x是人。是人。D(x) : x是要死的是要死的。则命题可符号化为：。则命题可符号化为：( x)(M(x)D(x)。 用符号 表达“至少有一个”，“存在一个”，“对某些”等词，叫做存在量词。 例如，例如， “有些人能活百岁以上有些人能活百岁以上” 。设。设M(x):x是人。是人。L(x): x能活百岁以上能活百岁以上。则命题可符号化为：。则命题可符号化为：( x)(M(x) L(x)。59 Peking Univ

31、ersity(1) 个体域中所有有性质F的个体都有性质G，应符号化为(2) 个体域中存在有性质F同时有性质G的个体，应符号化为60 Peking University一阶谓词基本概念个体（词）个体域全总个体域谓词(Predicate)量词(quantifiers)全称量词(universal quantifier)存在量词(existential quantifier)61 Peking University谓词公式谓词公式定义为定义为（1）n元谓词是一个谓词公式；元谓词是一个谓词公式；（2）若）若A是谓词公式，则（是谓词公式，则（A）也是谓词公式；也是谓词公式；（3）若若A，B是是谓谓词词公

32、公式式，则则（AB）、（AB）、（AB）、（）、（AB）也是谓词公式；也是谓词公式；（4）若）若A是谓词公式且含有未被量化的个体变量是谓词公式且含有未被量化的个体变量x，则则 xA(x)， XA(x)也是谓词公式。也是谓词公式。（5）有限次地使用（）有限次地使用（1）（4）所得到的也是谓词公式。）所得到的也是谓词公式。62 Peking University指导变元： xA(x)， xA(x)中的中的x相应量词的辖域： xA(x)， xA(x)中的中的A约束出现： x， x的辖域中，的辖域中，x的所有出现的所有出现自由出现：A中不是约束出现的变元中不是约束出现的变元例：( ( x)(P(x)Q

33、(xx)(P(x)Q(x，y)y)谓词公式中的基本概念63 Peking University谓词公式的解释谓词公式的解释谓词公式中含有个体变元和谓词变元。给定个体域，谓词公式中含有个体变元和谓词变元。给定个体域，将谓词公式中个体变元由确定的个体来取代，谓词变元由特定的谓词来取代，称为对谓词公式的赋值或解释。对谓词公式作了这样的赋值之后，谓词公式成为命题。对谓词公式作了这样的赋值之后，谓词公式成为命题。例例 求求( ( x)x)（P(x)Q(x)P(x)Q(x)）的的真真值值，其其中中( (x)x)：x x等等于于1 1；( (x)x)：x x等于等于2 2；且个体域；且个体域1,21,2。解

34、解：( ( x)(P(x)Q(x)x)(P(x)Q(x) (P(1)Q(1)(P(2)Q(2)(P(1)Q(1)(P(2)Q(2) ( ()()() ) 64 Peking University可满足公式不可满足公式（永假式）永真式可真可假式（不确定式）谓词公式分类：65 Peking University等价式和蕴含式定义 给定个体域E上的两个谓词公式和，若对和中的变项作同样的赋值，所得命题的真值都相同，则称谓词公式和在上是等价的，记作：。66 Peking University谓词演算中的等价式和蕴含式的来源可分为如下几类：谓词演算中的等价式和蕴含式的来源可分为如下几类：1命题公式的推广2

35、. 在有限个体域中消去量词3. 量词与联结词 之间的关系 4.量词辖域的扩张与收缩5.量词分配的等值式6.量词分配的蕴含式67 Peking University1命题公式的推广 用原子谓词公式取代命题演算等价公式中的各命题变用原子谓词公式取代命题演算等价公式中的各命题变元，命题演算的等价式就转化为谓词演算的等价式。例元，命题演算的等价式就转化为谓词演算的等价式。例如：如： A(x) A(x) ( x)A(x)( x)B(x) ( x)A(x)( x)B(x)68 Peking University2在有限个体域中有限个体域中消去量词 xA(x) A(a1) A(a2) A(an) xA(x)

36、 A(a1) A(a2) A(an)69 Peking University3量词与联结词 之间的关系 ( x)A(x) ( x) A(x)。 ( x)A(x) ( x) A(x)。 例如，设例如，设A(x)表示表示“x今天来校上课今天来校上课”，则，则 A(x)表示表示“x今天没来今天没来校上课校上课”。那麽，。那麽， 对对(1),“不是所有的人今天都来上课不是所有的人今天都来上课 ( x)A(x) ”与与“有有(存在存在)一一些人今天没来上课些人今天没来上课( x) A(x)”在意义上是相同的。在意义上是相同的。 对对(2),“今天没有今天没有(不存在不存在)来上课的人来上课的人 ( x)

37、A(x) ”与与“所有的人所有的人今天都没来上课今天都没来上课( x) A(x)”在意义上是相同的。在意义上是相同的。 和和式称为式称为量词转换律。这里这里约定，出现在量词之前的否定不是否定该量词，而是否定被量化了的整个命题。例如， ( x)A(x) ( x)A(x)。70 Peking University等价式和蕴含式(续)4量词辖域的扩张与收缩 ( x)A(x)B( x)（A(x)B） ( x)A(x)B( x)（A(x)B） ( x)A(x)B( x)（A(x)B） ( x)A(x)B( x)（A(x)B） 当个体域为有限集当个体域为有限集a1, a2,., an时，我们可以验证时，我

38、们可以验证式：式： ( x)A(x)B(A(a1)A(a2).A(an)B (A(a1)B)(A(a2)B).(A(an)B) ( x)(A(x)B)。例例: :证明证明 ( x)(A(x)B) ( x)A(x)B证证：( x)(A(x)B) ( x)( A(x)B) ( x) A(x)B ( x)A(x)B( x)A(x)B)71 Peking University等价式和蕴含式(续)5量词分配的等值式 ( x)(A(x)B(x) ( x)A(x)( x)B(x) ( x)(A(x)B(x) ( x)A(x)( x)B(x) 式式的的左左边边表表示示“对对于于所所有有的的，A(x)和和B(x

39、)都都是是真真的的”；右右边边表表示示“对对于于所所有有的的，A(x)是是真真的的；同同时时对对于于所所有有的的，B(x)也也是是真真的的”。显显然然，这这两两个个命命题题是是等等价价的的。例例如如，“联联欢欢会会上上所所有有的的人人既既唱唱歌歌又又跳跳舞舞”和和“联欢会上所有的人唱歌且所有的人跳舞联欢会上所有的人唱歌且所有的人跳舞”的意义相同。的意义相同。 式式左左边边的的命命题题可可表表述述成成“存存在在一一个个，能能使使()为为真真或或者者能能使使()为为真真”；右右边边的的命命题题可可表表述述成成“存存在在使使()为为真真，或或者者存存在在使使()为为真真”。显显然然，这这两两个个命命

40、题题也也是是等等价价的的。例例如如，“联联欢欢会会上上有有人唱歌或跳舞人唱歌或跳舞”和和“联欢会上有人唱歌，或有人跳舞联欢会上有人唱歌，或有人跳舞”的意义相同。的意义相同。72 Peking University等价式和蕴含式(续)6 6量词分配的蕴含式 ( x)A(x)( x)B(x) ( x)(A(x)B(x) ( x)(A(x)B(x) ( x)A(x)( x)B(x) 例例如如，对对式式，“每每一一个个人人都都唱唱歌歌或或者者每每一一个个人人都都跳跳舞舞”，那那么么可可以以说说“每一个人都唱歌或跳舞每一个人都唱歌或跳舞”。但反之不真。但反之不真。 对对式式，“有有人人既既唱唱歌歌又又跳

41、跳舞舞”永永真真蕴蕴含含“有有人人唱唱歌歌且且有有人人跳跳舞舞”。反之不真。反之不真。注意：全称量词 x x对于析取不服从分配律： ( x)(A(x)B(x) ( x)A(x)( x)B(x) 类似的情况是，类似的情况是，存在量词 对于合取不服从分配律： ( x)(A(x)B(x)( x)A(x)( x)B(x)73 Peking University推理定律74 Peking University一阶谓词逻辑等值式与蕴含式命题公式的推广在有限个体域中消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式量词分配蕴含式75 Peking University前束范式定义定义：一个公

42、式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则称该公式叫做前束范式。前束范式可记为如下形式前束范式可记为如下形式 ( (v v1 1)(v)(v2 2).().(v vn n) )其其中中“”“”表表示示量量词词 或或 ，v v1 1，v v2 2，.，v vn n是是客客体体变变元元，是不带量词的谓词公式。是不带量词的谓词公式。例如，例如，( ( x)(x)( y)(y)( z)z)（Q(x,y)R(z)Q(x,y)R(z)）是前束范式。是前束范式。76 Peking University定理 任意一个谓词公式，均和一个前束范式等价。证证明明：首首先先利利用用量量词词转转

43、化化公公式式可可将将否否定定深深入入到到变变元元和和谓谓词词公公式式的的前前面面。其其次次利利用用量量词词辖辖域域扩扩张张可可将将量量词词移移到到全全式的最前面，这样便得前束范式。式的最前面，这样便得前束范式。77 Peking University换名规则换名规则：将公式A中某量词辖域中出现的某个约束出现的个体变元及相应的指导变元x，都改成公式A中没出现过的y78 Peking University命命 题题等值演算等值演算推理推理基本要素中心谓词与量词谓词与量词等值演算等值演算推理推理数理逻辑框架79 Peking University小结命题逻辑命题和命题联结词命题公式和真值表命题等值式命题推理定律谓词逻辑谓词的概念与量词谓词公式与翻译等价式、蕴含式前束范式80 Peking University作业1.用真值表证明以下等价式和蕴涵式2. 不构造真值表证明1中各式3.把下列命题符号化，并求前束范式“所有运动员都钦佩某些教练”4.证明P7定律(3)x(A(x)B(x) xA(x) xB(x) 81 Peking University