离散数学总复习

1、12主要内容主要内容l 命题逻辑基本概念命题逻辑基本概念l 命题逻辑等值演算命题逻辑等值演算l 命题逻辑推理理论命题逻辑推理理论l 一阶逻辑基本概念一阶逻辑基本概念第一部分第一部分 数理逻辑数理逻辑3第一章第一章 命题逻辑的基本概念命题逻辑的基本概念主要内容主要内容l 命题与联结词命题与联结词 命题及其分类命题及其分类 联结词与复合命题联结词与复合命题l 命题公式及其赋值命题公式及其赋值4命题与真值命题与真值 命题命题：判断结果惟一的陈述句：判断结果惟一的陈述句 命题的真值命题的真值：判断的结果：判断的结果 真值的取值真值的取值：真与假：真与假 真命题与假命题真命题与假命题注意：注意：感叹句、

2、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的陈述句中的悖论悖论，判断结果不惟一确定的不是命题，判断结果不惟一确定的不是命题（我正在说假话）（我正在说假话） 1.1 命题与联结词命题与联结词5否定、合取联结词否定、合取联结词定义定义1.1 设设 p为命题，复合命题为命题，复合命题“非非p”(或或“p的否定的否定”)称称为为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联结词否定联结词. 规定规定 p 为真当且仅当为真当且仅当p为假为假. 是有理数是不对的是有理数是不对的2p p : : 是有理数是有理数2 符号化为符号化为 p p 6例例2 将下列命题符号化将

3、下列命题符号化. (1) 吴颖既用功又聪明吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生张辉与王丽都是三好生. (5) 张辉与张辉与王丽是同学王丽是同学.合取联结词的实例合取联结词的实例定义定义1.2 设设p,q为两个命题，复合命题为两个命题，复合命题“p并且并且q”(或或“p与与 q”)称为称为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词. 规定规定pq为真当且仅当为真当且仅当p与与q同时为真同时为真.7定义定义1.3 设设p, q为两个命题，复合命题为两个

4、命题，复合命题“p或或q”称作称作p与与q的的析取式析取式，记作，记作pq，称作称作析取联结词析取联结词. 规定规定pq为假当为假当且仅当且仅当p与与q同时为假同时为假.析取联结词析取联结词例例3 将下列命题符号化将下列命题符号化(1) 2 或或 4 是素数是素数.(2) 2 或或 3 是素数是素数.(3) 4 或或 6 是素数是素数.(4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5) 王小红生于王小红生于 1975 年或年或 1976 年年.8定义定义1.4 设设p, q为两个命题，复合命题为两个命题，复合命题“如果如果p, 则则q”称作称作p与与q的的蕴涵式蕴涵式，记

5、作，记作pq，并称，并称p是蕴涵式的是蕴涵式的前件前件，q为蕴涵式的为蕴涵式的后后件件，称作称作蕴涵联结词蕴涵联结词. 规定：规定：pq为假当且仅当为假当且仅当p为真为真q为假为假.蕴涵联结词蕴涵联结词(1) pq 的逻辑关系：的逻辑关系：q为为 p 的必要条件的必要条件(2) “如果如果 p, 则则 q” 有很多不同的表述方法：有很多不同的表述方法： 若若p，就，就q 只要只要p，就，就q p仅当仅当q 只有只有q 才才p 除非除非q, 才才p 或或 除非除非q，否则非，否则非p， (3) 当当 p 为假时，为假时，pq恒为真，称为空证明恒为真，称为空证明 (4) 常出现的错误：不分充分与必

6、要条件常出现的错误：不分充分与必要条件9例例4 设设 p：天冷，：天冷，q：小王穿羽绒服：小王穿羽绒服，将下列命题符号化，将下列命题符号化(1) 只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5) 除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7) 如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8) 小王穿羽绒服仅当天冷的时

7、候小王穿羽绒服仅当天冷的时候.蕴涵联结词的实例蕴涵联结词的实例pq注意：注意： pq 与与 qp 等值（真值相同）等值（真值相同）pqpqqpqppqqpqp10定义定义1.5 设设 p, q为两个命题，复合命题为两个命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结词等价联结词. 规定规定pq为真为真当且仅当当且仅当p与与q同时为真或同时为假同时为真或同时为假.pq 的逻辑关系：的逻辑关系：p与与q互为充分必要条件互为充分必要条件等价联结词等价联结词例例5 5 求下列复合命题的真值求下列复合命题的真值(1) 2 + 2 4 当且仅当当且仅

8、当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数.(3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5) 函数函数 f (x) 在在 x0 可导的充要条件是可导的充要条件是 它在它在 x0 连续连续. 1001111l 联结词集为联结词集为 , , , , ， p, p q, p q, pq, pq为为基本复合命题基本复合命题. 其中要特别注意理解其中要特别注意理解pq的涵义的涵义. 反复使用反复使用 , , , , 中的联结词组成更为复杂的复合命题中的联结词组成更为复杂

9、的复合命题.小结小结l 联结词的优先顺序：联结词的优先顺序： , , , , , 同级按先出现者先运算同级按先出现者先运算.121.2 命题公式及其赋值命题公式及其赋值命题变项与合式公式命题变项与合式公式l 命题变项命题变项l 合式公式合式公式l 合式公式的层次合式公式的层次公式的赋值公式的赋值l 公式赋值公式赋值l 公式类型公式类型l 真值表真值表13命题变项与合式公式命题变项与合式公式 命题常项：命题常项：真值确定的简单命题真值确定的简单命题 命题变项（命题变元）：命题变项（命题变元）：取值取值1或或0的变元，表示真值可以变化的变元，表示真值可以变化的陈述句的陈述句 常项与变项均用常项与变

10、项均用 p, q, r, , pi, qi, ri, , 等表示等表示. 定义定义1.6 合式公式合式公式（简称公式）的递归定义：（简称公式）的递归定义： (1) 单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式公式, 称作称作原子命题公式原子命题公式 (2) 若若A是合式公式，则是合式公式，则 ( A)也是也是 (3) 若若A, B是合式公式，则是合式公式，则(A B), (A B), (AB), (AB)也是也是 (4) 只有有限次地应用只有有限次地应用(1)(3) 形成的符号串才是合式公式形成的符号串才是合式公式几点说明：几点说明：归纳或递归定义归纳或递归定义, 元语言与对象

11、语言元语言与对象语言, 外层括号可以省去外层括号可以省去14定义定义1.8 设设p1, p2, , pn是出现在公式是出现在公式A中的全部命题变项中的全部命题变项, 给给p1, p2, , pn各指定一个真值各指定一个真值, 称为对称为对A的一个的一个赋值赋值或或解释解释. 若使若使A为为1, 则称这组值为则称这组值为A的的成真赋值成真赋值; 若使若使A为为0, 则称这组则称这组值为值为A的的成假赋值成假赋值.公式赋值公式赋值15定义定义1.9 将命题公式将命题公式A在所有赋值下取值的情况列成表在所有赋值下取值的情况列成表, 称作称作A的的真值表真值表.真值表真值表16(1) A = (p q

12、) r成真赋值成真赋值:000,001,010,100,110; 成假赋值成假赋值:011,101,111 p q rp q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表117公式的类型公式的类型定义定义1.10 (1) 若若A在它的任何赋值下均为真在它的任何赋值下均为真, 则称则称A为为重言式重言式或或永真式永真式;(2) 若若A在它的任何赋值下均为假在它的任何赋值下均为假, 则称则称A为为矛盾式矛盾式或或永假式永假式;(3) 若若A不是矛盾式不是矛盾式, 则称则称A是是可

13、满足式可满足式.18第一章第一章 习题课习题课主要内容主要内容l 命题、真值、简单命题与复合命题、命题符号化命题、真值、简单命题与复合命题、命题符号化l 联结词联结词 , , , , 及复合命题符号化及复合命题符号化l 命题公式及层次命题公式及层次l 公式的类型公式的类型l 真值表及应用真值表及应用基本要求基本要求l 深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系, 熟练地将命题符号化熟练地将命题符号化l 会求复合命题的真值会求复合命题的真值l 深刻理解合式公式及重言式、矛盾式、可满足式等概念深刻理解合式公式及重言式、矛盾式、可满足式等概念l 熟练地求公式的真值表，并用它求公式的成真赋值

14、与成假熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型赋值及判断公式类型19主要内容主要内容l 等值式与基本的等值式等值式与基本的等值式l 等值演算与置换规则等值演算与置换规则l 析取范式与合取范式，主析取范式与主合取范式析取范式与合取范式，主析取范式与主合取范式l 联结词完备集联结词完备集l 可满足性问题与消解法可满足性问题与消解法第二章第二章 命题逻辑等值演算命题逻辑等值演算202.1 等值式等值式定义定义2.1 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作，记作AB，并称，并称AB是是等值式等值式21基本等值式基本等值式双重否定律双重否定律

15、AA幂等律幂等律 A AA, A AA交换律交换律 A BB A, A BB A结合律结合律 (A B) CA (B C), (A B) CA (B C)分配律分配律 A (B C)(A B) (A C), A (B C)(A B) (A C)德摩根律德摩根律 (A B)AB (A B)AB吸收律吸收律 A (A B)A, A (A B)A22基本等值式基本等值式零律零律 A 11, A 00同一律同一律 A 0A. A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位 ABBA等价否定等值式等价否定等值式

16、 ABAB归谬论归谬论 (AB) (AB) A特别提示：必须牢记这特别提示：必须牢记这16组等值式，这是继续学习的基础组等值式，这是继续学习的基础23等值演算与置换规则等值演算与置换规则1. 等值演算等值演算由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程2. 等值演算的基础：等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式基本的等值式 (3) 置换规则（见置换规则（见3）3. 置换规则置换规则 设设 (A) 是含公式是含公式 A 的命题公式，的命题公式， (B) 是用公式是用公式 B 置换置换

17、 (A) 中所有的中所有的 A 后得到的命题公式后得到的命题公式 若若 BA，则，则 (B)(A)242.2 析取范式与合取范式析取范式与合取范式基本概念基本概念(1) 文字文字命题变项及其否定的总称命题变项及其否定的总称 p, q(2) 简单析取式简单析取式有限个文字构成的析取式有限个文字构成的析取式 p, q, pq, p q r, (3) 简单合取式简单合取式有限个文字构成的合取式有限个文字构成的合取式 p, q, pq, p q r, (4) 析取范式析取范式由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 p, p q, pq, (pq) ( p qr) (q r)(5)

18、 合取范式合取范式由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 p, pq, p q, (p q ) p (p q r)(6) 范式范式析取范式与合取范式的总称析取范式与合取范式的总称25极小项与极大项极小项与极大项定义定义2.4 在含有在含有n个命题变项的个命题变项的简单合取式简单合取式（简单析取式简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第一次，而且第i个文字出现在左起第个文字出现在左起第i位上（位上（1 i n），称这），称这样的样的简单合取式简单合取式（简单析取式简单析取式）为）为极小项极小

19、项（极大项极大项）.几点说明：几点说明：l n个命题变项有个命题变项有2n个极小项和个极小项和2n个极大项个极大项l 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值l 用用mi表示第表示第i个极小项，其中个极小项，其中i是该是该极小项成真赋值极小项成真赋值的十进的十进制表示制表示. 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该是该极大项成假赋值极大项成假赋值的十进制表示的十进制表示. mi（Mi）称为极小项（极大项）的名称）称为极小项（极大项）的名称. 26实例实例由两个命题变项由两个命题变项 p, q 形成的极小项与极大项形成的极小项与极大项极小项极小项极大项极大项

20、公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 pq p qpqp q 0 0 0 1 1 0 1 1 m0m1m2m3 p q pq p q pq 0 0 0 1 1 0 1 1M0M1M2M327实例实例极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r

21、 p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7由三个命题变项由三个命题变项 p, q, r 形成的极小项与极大项形成的极小项与极大项. mi与与Mi的关系：的关系： mi Mi, Mi mi 28主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为 p, q, r 时，时， ( pq r) ( p q r) m1 m3 主析取范式主析取范式 (p qr)

22、( pqr) M1 M7主合取范式主合取范式公式公式A的主析取的主析取(合取合取)范式范式与与A 等值的主析取等值的主析取(合取合取)范式范式 定理定理2.5 (主范式的存在惟一定理主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主合取范式任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的并且是惟一的292.3 联结词的完备集联结词的完备集定义定义2.6 称称F:0,1n 0,1 为为n元真值函数元真值函数. 0,1n=000, 001, , 111，包含，包含 个长为个长为n的的0,1符号串符号串. 共有共有 个个n元真值函数元真值函数. n221元真值函数元真

23、值函数 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFFn230公式与真值函数公式与真值函数)2(13F任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应惟一的一个都对应惟一的一个n元元真值函数真值函数 F , F 恰好为恰好为A的真值表的真值表. 等值的公式对应的真值函数相同等值的公式对应的真值函数相同. 例如：例如：pq, p q 都对应都对应每个真值函数与唯一的一个主析取范式（主合取范式）等值。每个真值函数与唯一的一个主析取范式（主合取范式）等值。例如：例如：3)2(120)(0mqpF,F)(31联结词完备集联结词完备集定义定义2

24、.7 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1) 元真值函元真值函数都可以由仅含数都可以由仅含S中的联结词构成的公式表示，则称中的联结词构成的公式表示，则称S是是联结联结词完备集词完备集若若S是联结词完备集是联结词完备集, 则任何命题公式都可由则任何命题公式都可由S中的联结词表示中的联结词表示定理定理2.6 S = , , 是联结词完备集是联结词完备集证明证明 由范式存在定理可证由范式存在定理可证32复合联结词复合联结词定义定义2.8 设设 p, q 为两个命题为两个命题, (p q)称作称作p与与q的的与非式与非式, 记作记作p q, 即即 p q (p q),

25、称为称为与非联结词与非联结词 (p q) 称作称作 p 与与 q 的的或非式或非式, 记作记作 p q, 即即 p q (p q), 称为称为或非联结词或非联结词定理定理2.7 与与 为联结词完备集为联结词完备集. 证明证明 , , 为完备集为完备集 p pp (p p) p p p q ( pq) pq (p p) (q q) p q (p q) (p q) (p q) (p q) 得证得证 为联结词完备集为联结词完备集. 对对 类似可证类似可证33主要内容主要内容推理的形式结构推理的形式结构l 推理的正确与错误推理的正确与错误l 推理的形式结构推理的形式结构l 判断推理正确的方法判断推理正

26、确的方法l 推理定律推理定律自然推理系统自然推理系统Pl 形式系统的定义与分类形式系统的定义与分类l 自然推理系统自然推理系统Pl 在在P中构造证明中构造证明:直接证明法、附加前提证明法、归谬法直接证明法、附加前提证明法、归谬法第三章第三章 命题逻辑的推理理论命题逻辑的推理理论343.1 推理的形式结构推理的形式结构定义定义3.1 设设A1, A2, , Ak, B为命题公式为命题公式. 若对于每组赋值，若对于每组赋值，A1 A2 Ak 为假，或当为假，或当A1 A2 Ak为真时，为真时，B也为真，也为真，则称由则称由前提前提A1, A2, , Ak推出推出结论结论B的的推理推理是是有效的有效

27、的或或正确正确的的, 并称并称B是是有效结论有效结论.定理定理3.1 由命题公式由命题公式A1, A2, , Ak 推推B的推理正确当且仅当的推理正确当且仅当A1 A2 AkB为重言式为重言式注意注意: 推理正确不能保证结论一定正确推理正确不能保证结论一定正确所谓推理是指从前提出发推出结论的思维过程。所谓推理是指从前提出发推出结论的思维过程。35推理的形式结构推理的形式结构2. A1 A2 AkB 若推理正确若推理正确, 记为记为A1 A2 Ak B3. 前提：前提： A1, A2, , Ak 结论：结论： B判断推理是否正确的方法判断推理是否正确的方法: 真值表法（见例子真值表法（见例子3.

28、1） 等值演算法（见例子等值演算法（见例子3.2） 主析取范式法（见例子主析取范式法（见例子3.2）由由A1, A2, , Ak推推B的的推理有以下的形式结构：推理有以下的形式结构：1. A1, A2, , Ak B 若推理正确若推理正确, 记为记为A1,A2,An B36推理定律推理定律重言蕴涵式重言蕴涵式1. A (A B) 附加律附加律 2. (A B) A 化简律化简律3. (AB) A B 假言推理假言推理4. (AB)B A 拒取式拒取式 5. (A B)B A 析取三段论析取三段论6. (AB) (BC) (AC) 假言三段论假言三段论7. (AB) (BC) (AC) 等价三段

29、论等价三段论8. (AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) B 构造性二难构造性二难(特殊形式特殊形式)9. (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如, 由由AA可产生可产生 AA 和和 AA37自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1. 字母表字母表 (1) 命题变项符号：命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：联结词符号： , , , , (3) 括号与逗号：括号与逗号：

30、(, ), ，2. 合式公式（同定义合式公式（同定义1.6）3. 推理规则推理规则 (1) 前提引入规则：前提引入规则：在证明的任何步骤都可引入前提在证明的任何步骤都可引入前提 (2) 结论引入规则：结论引入规则：在证明的任何步骤得到的结论都可以做在证明的任何步骤得到的结论都可以做 为后续证明的前提为后续证明的前提 (3) 置换规则：置换规则：在证明的任何步骤，命题公式中的子公式都在证明的任何步骤，命题公式中的子公式都 可用等值的公式置换，得到公式序列中又可用等值的公式置换，得到公式序列中又 一个公式一个公式38推理规则推理规则(4) 假言推理规则假言推理规则 (6) 化简规则化简规则 (8)

31、 假言三段论规则假言三段论规则 AB AB AA B A B A(5) 附加规则附加规则 (7) 拒取式规则拒取式规则 (9) 析取三段论规则析取三段论规则 AB B A AB BCACA B BA39推理规则推理规则(10) 构造性二难推理规则构造性二难推理规则 (11) 破坏性二难推理规则破坏性二难推理规则 (12) 合取引入规则合取引入规则 AB CD A C B D AB CD BD A C A BA C40附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：CB等价地证明等价地证明

32、前提：前提：A1, A2, , Ak, C 结论：结论：B理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B41附加前提证明法实例附加前提证明法实例 (3) 证明证明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段论假言三段论 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论42归谬法（反证法）归谬法（反证法）归谬法归谬法 (反证法反证法)欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，

33、推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB) (A1 A2 AkB) 0 A1 A2 AkB043归谬法实例归谬法实例例例4 前提：前提： (p q) r, rs, s, p 结论：结论： q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q) r 前提引入前提引入 (p q) 析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取44主要内容主要内容l 一阶逻辑命题符号化一阶逻辑命题符号化 个体词、谓词、量词个体

34、词、谓词、量词 一阶逻辑命题符号化一阶逻辑命题符号化第四章第四章 一阶逻辑基本概念一阶逻辑基本概念454.1 一阶逻辑命题符号化一阶逻辑命题符号化 凡是人都离不开水。我是人。所以我离不开水。凡是人都离不开水。我是人。所以我离不开水。命题符号化：命题符号化：个体词个体词所研究对象中可以独立存在的具体或抽象的客体所研究对象中可以独立存在的具体或抽象的客体例如张三、李四、中国、例如张三、李四、中国、9、 x等等 个体常项个体常项：具体的事务，用：具体的事务，用a, b, c表示表示 个体变项个体变项：抽象的事物，用：抽象的事物，用x, y, z表示表示 个体域个体域(论域论域)个体变项的取值范围个体

35、变项的取值范围 有限个体域，如有限个体域，如 a, b, c, 1, 2 无限个体域，如无限个体域，如 N, Z, R, 全总个体域全总个体域由宇宙间一切事物组成由宇宙间一切事物组成rqp )(46谓词谓词谓词谓词表示个体词性质或相互之间关系的词，常用表示个体词性质或相互之间关系的词，常用F,G,H,表示表示 谓词常项谓词常项 表示具体性质或关系表示具体性质或关系 如如, F(a)：a是人是人 谓词变项谓词变项 表示抽象或泛指的性质或关系表示抽象或泛指的性质或关系 如如, F(x)：x具有性质具有性质F n（n 1）元谓词）元谓词 含含n个个体变项的谓词个个体变项的谓词 一元谓词一元谓词(n=

36、1)表示性质表示性质 多元谓词多元谓词(n 2)表示事物之间的关系表示事物之间的关系 如如, L(x,y)：x与与 y 有关系有关系 L，G(x,y)：x y， 0元谓词元谓词不含个体变项的谓词不含个体变项的谓词, 即命题常项即命题常项 或命题变项（见例子或命题变项（见例子4.1）47量词量词量词量词表示数量的词表示数量的词 全称量词全称量词 : 表示所有的表示所有的. x : 对个体域中所有的对个体域中所有的x 如如, xF(x)表示个体域中所有的表示个体域中所有的x具有性质具有性质F x yG(x,y)表示个体域中所有的表示个体域中所有的x和和y有关系有关系G 存在量词存在量词 : 表示存

37、在表示存在, 有一个有一个. x : 个体域中有一个个体域中有一个x 如如, xF(x)表示个体域中有一个表示个体域中有一个x具有性质具有性质F x yG(x,y)表示个体域中存在表示个体域中存在x和和y有关系有关系G x yG(x,y)表示对个体域中每一个表示对个体域中每一个x都存在一个都存在一个y使得使得 x和和y有关系有关系G x yG(x,y)表示个体域中存在一个表示个体域中存在一个x使得对每一个使得对每一个y, x和和y有关系有关系G48实例实例2例例 2 在一阶逻辑中将下面命题符号化（另见例子在一阶逻辑中将下面命题符号化（另见例子4.3） (1) 人都爱美人都爱美 (2) 有人用左

38、手写字有人用左手写字个体域分别为个体域分别为 (a) D为人类集合为人类集合 (b) D为全总个体域为全总个体域解解 (a) (1) xG(x), G(x)：x爱美爱美(2) xG(x), G(x)：x用左手写字用左手写字 (b) F(x)：x为人，为人，G(x)：x爱美爱美 (1) x(F(x)G(x) (2) x(F(x) G(x)1. 引入特性谓词引入特性谓词F(x) 2. (1),(2)是一阶逻辑中两个是一阶逻辑中两个“基本基本”公式公式 3.注意注意和和 的使用的使用49主要内容主要内容l 集合的基本概念集合的基本概念 属于、包含属于、包含 幂集、空集幂集、空集 文氏图等文氏图等l

39、集合的基本运算集合的基本运算 并、交、补、差等并、交、补、差等l 集合恒等式集合恒等式 集合运算的算律、恒等式的证明方法集合运算的算律、恒等式的证明方法 第二部分第二部分 集合论集合论第六章第六章 集合代数集合代数506.2 集合的运算集合的运算初级运算初级运算集合的基本运算有集合的基本运算有定义定义6.7 并并 A B = x | x A x B 交交 A B = x | x A x B 相对补相对补 A B = x | x A x B定义定义6.8 对称差对称差 A B = (A B) (B A) 定义定义6.9 绝对补绝对补 A = E A E是全集是全集51广义运算广义运算1. 集合的

40、广义并集合的广义并(集合的元素的元素构成的集合集合的元素的元素构成的集合)与广义交与广义交 (非非空空集合的所有元素的公共元素构成的集合集合的所有元素的公共元素构成的集合)定义定义6.10 广义并广义并 A = x | z ( z A x z ) 广义交广义交 A= x | z ( z A x z ) 实例实例 1, 1,2, 1,2,3=1,2,3 1, 1,2, 1,2,3=1 a=a， a=a a=a， a=a526.4 集合恒等式集合恒等式集合算律集合算律1只涉及一个运算的算律：只涉及一个运算的算律： 交换律交换律、结合律结合律、幂等律幂等律 交换交换A B=B AA B=B AA B

41、=B A结合结合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B C)幂等幂等A A=AA A=A53集合算律集合算律 2涉及两个不同运算的算律：涉及两个不同运算的算律： 分配律、吸收律分配律、吸收律 与与 与与 分配分配A (B C)=(A B) (A C)A (B C)=(A B) (A C)A (B C)=(A B) (A C)吸收吸收A (A B)=AA (A B)=A54集合算律集合算律3涉及补运算的算律：涉及补运算的算律： DM律律，双重否定律双重否定律 D.M律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B

42、 C)= BC (B C)= BC双重否定双重否定A=A55集合算律集合算律4涉及全集和空集的算律：涉及全集和空集的算律： 补元律补元律、零律零律、同一律同一律、否定律否定律E补元律补元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=56集合证明题集合证明题证明方法：命题演算法、等式置换法证明方法：命题演算法、等式置换法命题演算证明法的书写规范命题演算证明法的书写规范 (以下的以下的X和和Y代表集合公式代表集合公式)(1) 证证X Y 任取任取x， x X x Y (2) 证证X=Y 方法一方法一 分别证明分别证明 X Y 和和 Y X 方法二方法二 任取任

43、取x，x X x Y注意：在使用方法二的格式时，必须保证每步推理都是充注意：在使用方法二的格式时，必须保证每步推理都是充分必要的分必要的57主要内容主要内容l 有序对与笛卡儿积有序对与笛卡儿积l 二元关系的定义与表示法二元关系的定义与表示法l 关系的运算关系的运算l 关系的性质关系的性质l 关系的闭包关系的闭包l 等价关系与划分等价关系与划分l 偏序关系偏序关系第七章第七章 二元关系二元关系587.1 有序对与笛卡儿积有序对与笛卡儿积定义定义7.1 由两个元素由两个元素 x 和和 y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为称为有序对有序对或或序偶序偶，记作，记作.定义定义7

44、.2 设设A,B为集合，为集合，A与与B的的笛卡儿积笛卡儿积记作记作A B，且，且 A B = | x A y B.597.2 二元关系二元关系定义定义7.3 如果一个集合满足以下如果一个集合满足以下条件之一条件之一：(1) 集合非空集合非空, 且它的元素都是有序对且它的元素都是有序对(2) 集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系, 简称为关系，记作简称为关系，记作R.如果如果R, 可记作可记作xRy；如果；如果 R, 则记作则记作x R y实例：实例：R=, S=,a,b. R是二元关系是二元关系, 当当a, b不是有序对时，不是有序对时，S不是二元关系不是二元

45、关系根据上面的记法，可以写根据上面的记法，可以写1R2, aRb, a S c等等. 60A到到B的关系与的关系与A上的关系上的关系定义定义7.4设设A,B为集合为集合, AB的的任何子集任何子集所定义的二元关系叫做所定义的二元关系叫做从从A到到B的二元关系的二元关系, 当当A=B时则叫做时则叫做A上的二元关系上的二元关系.定义定义7.5 设设 A 为集合为集合, (1) 是是A上的关系，称为上的关系，称为空关系空关系(2) 全域关系全域关系 EA = | xAyA = AA 恒等关系恒等关系 IA = | xA 小于等于关系小于等于关系 LA = | x,yAxy, A为实数子集为实数子集

46、整除关系整除关系 DB = | x,yBx整除整除y, B为非为非0整数子集整数子集 包含关系包含关系 R = | x,yAx y, A是集合族是集合族.61关系的表示关系的表示1. 关系矩阵关系矩阵 若若A=x1, x2, , xm，B=y1, y2, , yn，R是从是从A到到B的的 关系，关系，R的关系矩阵是布尔矩阵的关系矩阵是布尔矩阵MR = rij m n, 其中其中 rij = 1 R. 2. 关系图关系图 若若A= x1, x2, , xm，R是是A上的关系，上的关系，R的关系图是的关系图是GR=, 其中其中A为结点集，为结点集，R为边集为边集. 如果如果属于属于 关系关系R，在

47、图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边. 注意：注意：l 关系矩阵适合表示从关系矩阵适合表示从A到到B的关系或的关系或A上的关系（上的关系（A,B为有为有穷集）穷集）l 关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系 62实例实例例例4 A=1,2,3,4, R=, R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下： 0010000011000011RM637.3 关系的运算关系的运算关系的基本运算关系的基本运算定义定义7.6 关系的关系的定义域定义域、值域值域与与域域分别定义为分别定义为 domR = x | y ( R) ranR = y

48、| x ( R) fldR = domR ranR 例例5 R=, 则则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 64关系运算关系运算(逆与合成逆与合成)定义定义7.7 关系的关系的逆运逆运算算 R 1 = | R 定义定义7.8 关系的关系的合成合成运算运算 R S = | y ( R S) 例例6 R = , , , S = , , , , R 1 = , , , R S = , , S R = , , , 65关系运算关系运算(限制与像限制与像)定义定义7.9 设设R为二元关系为二元关系, A是集合是集合 (1) R在在A上的上的限制限制记作记

49、作 R A, 其中其中 R A = | xRyxA (2) A在在R下的下的像像记作记作RA, 其中其中 RA=ran(R A) 66关系的幂运算关系的幂运算定义定义7.10设设 R 为为 A 上的关系上的关系, n为自然数为自然数, 则则 R 的的 n 次幂次幂定义为：定义为：(1) R0 = | xA = IA(2) Rn+1 = Rn R注意：注意：l对于对于A上的任何关系上的任何关系 R1 和和 R2 都有都有 R10 = R20 = IA l对于对于A上的任何关系上的任何关系 R 都有都有 R1 = R67R3和和R4的矩阵是：的矩阵是：因此因此M4=M2, 即即R4=R2. 因此可

50、以得到因此可以得到 R2=R4=R6=， R3=R5=R7=R0的关系矩阵是的关系矩阵是 0000000010100101,000000000101101043MM 10000100001000010M幂的求法幂的求法687.4 关系的性质关系的性质定义定义7.11 设设 R 为为A上的关系上的关系, (1) 若若 x(xA R), 则称则称 R 在在 A 上是上是自反自反的的.(2) 若若 x(xA R), 则称则称 R 在在 A 上是上是反自反反自反的的. 实例：实例：自反：全域关系自反：全域关系EA, 恒等关系恒等关系IA, 小于等于关系小于等于关系LA, 整除关系整除关系DA反自反：实

51、数集上的小于关系、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系. A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R2 自反自反 ，R3 反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.69对称性与反对称性对称性与反对称性定义定义7.12 设设 R 为为 A上的关系上的关系, (1) 若若 x y( x,yARR), 则称则称 R 为为 A上上对对称称的关系的关系.(2) 若若 x y( x,yARRx=y), 则称则称 R 为为A上的上的反对称反对称关系关系.实例：对称关系：实例：对称关系：A上的全域

52、关系上的全域关系EA, 恒等关系恒等关系IA和空关系和空关系反对称关系：反对称关系：恒等关系恒等关系IA和空关系和空关系也是也是A上的反对称关系上的反对称关系. 设设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1,，R2, R3,，R4, R1：对称和反对称；：对称和反对称； R2：只有对称；：只有对称；R3：只有反对称；：只有反对称； R4：不对称、不反对称：不对称、不反对称70传递性传递性定义定义7.13 设设R为为A上的关系上的关系, 若若 x y z(x,y,zARRR),则称则称 R 是是A上的上的传递传递关系关系.实例：实例： A上的全域关

53、系上的全域关系 EA,恒等关系恒等关系 IA和空关系和空关系 ，小于等小于等于和小于关系，整除关系，包含与真包含关系于和小于关系，整除关系，包含与真包含关系设设 A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R1和和R3是是A上的传递关系上的传递关系, R2不是不是A上的传递关系上的传递关系. 71关系性质成立的充要条件关系性质成立的充要条件定理定理7.9 设设R为为A上的关系上的关系, 则则(1) R 在在A上自反当且仅当上自反当且仅当 IA R(2) R 在在A上反自反当且仅当上反自反当且仅当 RIA = (3) R 在在A上对称当且仅当上对称

54、当且仅当 R=R 1(4) R 在在A上反对称当且仅当上反对称当且仅当 RR 1 IA(5) R 在在A上传递当且仅当上传递当且仅当 R R R 727.5 关系的闭包关系的闭包 主要内容主要内容l 闭包定义闭包定义l 闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示l 闭包的性质闭包的性质 73闭包定义闭包定义定义定义7.14 设设R是非空集合是非空集合A上的关系上的关系, R的的自反自反(对称对称或或传递传递)闭闭包包是是A上的关系上的关系R , 使得使得R 满足以下条件：满足以下条件：(1) R 是自反的是自反的(对称的或传递的对称的或传递的) (2) R

55、R (3) 对对A上任何包含上任何包含R的自反的自反(对称或传递对称或传递)关系关系R 有有RR R的自反闭包记作的自反闭包记作r(R), 对称闭包记作对称闭包记作s(R), 传递闭包记作传递闭包记作t(R). 定理定理7.10 设设R为为A上的关系上的关系, 则有则有(1) r(R)=RR0(2) s(R)=RR 1(3) t(R)=RR2R3说明：对有穷集说明：对有穷集A(|A|=n)上的关系上的关系, (3)中的并最多不超过中的并最多不超过Rn747.6 等价关系与划分等价关系与划分 主要内容主要内容l 等价关系的定义与实例等价关系的定义与实例l 等价类及其性质等价类及其性质l 商集与集

56、合的划分商集与集合的划分l 等价关系与划分的一一对应等价关系与划分的一一对应 75等价关系的定义与实例等价关系的定义与实例定义定义7.15 设设R为非空集合上的关系为非空集合上的关系. 如果如果R是自反的、对称的和是自反的、对称的和传递的传递的, 则称则称R为为A上的上的等价关系等价关系. 设设 R 是一个等价关系是一个等价关系, 若若R, 称称 x等价于等价于y, 记做记做xy. 实例实例 设设 A=1,2,8, 如下定义如下定义A上的关系上的关系R： R=| x,yAx y(mod 3)其中其中x y(mod 3)叫做叫做 x与与 y 模模3相等相等, 即即x除以除以3的余数与的余数与y除

57、以除以3的余数相等的余数相等. 不难验证不难验证 R 为为A上的等价关系上的等价关系, 因为因为(1) xA, 有有 x x (mod 3)(2) x,yA, 若若x y(mod 3), 则有则有y x(mod 3) (3) x,y,zA, 若若x y(mod 3), y z(mod 3), 则有则有x z(mod 3)76模模 3 等价关系的关系图等价关系的关系图等价关系的实例等价关系的实例77等价类定义等价类定义 定义定义7.16 设设R为非空集合为非空集合A上的等价关系上的等价关系, xA，令，令 xR = y | yAxRy称称xR 为为x关于关于R的等价类的等价类, 简称为简称为x的

58、的等价类等价类, 简记为简记为x或或 实例实例 A=1, 2, , 8上模上模3等价关系的等价类：等价关系的等价类： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6x78商集与划分商集与划分定义定义7.17 设设 R 为非空集合为非空集合A上的等价关系上的等价关系, 以以 R 的所有等价的所有等价类作为元素的集合称为类作为元素的集合称为A关于关于R的的商集商集, 记做记做A/R, A/R = xR | xA实例实例 设设 A=1,2,8，A关于模关于模3等价关系等价关系R的商集为的商集为 A/R = 1,4,7, 2,5,8, 3,6A

59、关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为： A/IA = 1, 2, , 8， A/EA = 1,2,8定义定义7.18 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A)满足满足:(1) (2) x y(x,y xyxy=)(3) = A则称则称是是A的一个的一个划分划分, 称称中的元素为中的元素为A的的划分块划分块.商集就是一个划分，不同的商集对应不同的划分商集就是一个划分，不同的商集对应不同的划分797.7 偏序关系偏序关系 主要内容主要内容l 偏序关系偏序关系 偏序关系的定义偏序关系的定义 偏序关系的实例偏序关系的实例l 偏序集与哈斯图偏序集与哈斯图

60、l 偏序集中的特殊元素及其性质偏序集中的特殊元素及其性质 极大元、极小元、最大元、最小元极大元、极小元、最大元、最小元 上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界80定义与实例定义与实例定义定义7.19 偏序关系偏序关系：非空集合：非空集合A上的自反、反对称和传递的关系，上的自反、反对称和传递的关系，记作记作 . 设设 为偏序关系为偏序关系, 如果如果 , 则记作则记作 x y, 读读作作x“小于或等于小于或等于”y. 实例实例集合集合A上的恒等关系上的恒等关系 IA是是 A上的偏序关系上的偏序关系. 小于或等于关系小于或等于关系, 整除关系和包含关系也是相应集合上的偏整除关