离散数学基础 (5)

(7). P(c) ? ?Q(c) // 全称量词消除规则，使用(2)中个体c (8). P(c) // 析取三段论，(3)和(7) (9). P(c) ? S(c) // 合取的引入，(4)和(8) (10). ?x(S(x) ? P(x)) // 存在量词引入规则 [3]. 同样因为每个句子都是对数作了限制，引入我们不需要使用全总域，而使用的个体域为所有的数。这样要引入的谓词包括： Q(x): x 是有理数；R(x): x是实数；N(x): x是无理数；C(x): x是虚数 前提可符号化为：?x(Q(x)?R(x))、?x(N(x)?R(x))、?x(C(x)? ?R(x)) 结论可符号化为：?x(C(x)? (?Q(x) ? ?N(x))，验证该结论的公式序列如下： (1). ?x(Q(x)?R(x)) // 前提 (2). Q(x)?R(x) // 全称量词消除规则 (3). ?x(N(x)?R(x)) // 前提 (4). N(x)?R(x) // 全称量词消除规则 (5). ?x(C(x)? ?R(x)) // 前提 (6). C(x)? ?R(x) // 全称量词消除规则 (7). C(x) // 附加前提 (8). ?R(x) // 分离规则，(6)和(7) (9). ?Q(x) // 拒取式，(8)和(2) (10). ?N(x) // 拒取式，(8)和(4) (11). ?Q(x) ? ?N(x) // 合取的引入 (12). C(x)?(?Q(x) ? ?N(x) // 附加前提规则，(7)和(11) (13). ?x(C(x)? (?Q(x) ? ?N(x)) // 全称量词引入规则 [4]. 通过分析发现，我们不能使用个体域为所有的旅客，只能使用全总域，而引入下列谓词：P(x): x是旅客；Q(x): x坐头等舱；R(x): x坐二等舱；S(x): x是富裕的。 前提可符号化为：

?x(P(x)?(Q(x)?R(x)))、?x(P(x)?(Q(x)?S(x)))、?x(P(x)?S(x))、?(?x(P(x)?S(x)))

结论可符号化为：?x(P(x)?R(x))，验证该结论的公式序列如下： (1). ?(?x(P(x)?S(x))) // 前提 (2). ?x(P(x)??S(x)) // 等值替换规则 (3). P(c)??S(c) // 存在量词消除规则 (4). P(c) // 合取的消除 (5). ?S(c) // 合取的消除，(3)

(6). ?x(P(x)?(Q(x)?R(x))) // 前提 (7). P(c)?(Q(c)?R(c)) // 全称量词消除规则，使用(3)中个体c

(8). Q(c)?R(c) // 分离规则，(4)和(7) (9). ?x(P(x)?(Q(x)?S(x))) // 前提 (10). P(c)?(Q(c)?S(c)) // 全称量词消除规则，使用(3)中个体c (11). Q(c)?S(c) // 分离规则，(4)和(11) (12). Q(c)?S(c) // 合取的消除 (13). ?Q(c) // 拒取式，(12)和(5) (14). R(c) // 析取三段论，(13)和(8) (15). P(c) ? R(c) // 合取的引入，(4)和(14) (16). ?x(P(x)?R(x)) // 存在量词的引入 作业：教材p104~105的11、12、13、16，选作14、15

46

第三讲 集合论

一、集合的基本概念和运算

1. 集合的基本概念

·集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象称为该集合的一个元素(member或element)。

·用大写字母A, B, C等表示集合，用小写字母a, b, c等表示集合的元素 ·a?A表示：a是集合A的元素，或说a属于集合A

·a?A表示：a不是集合A的元素，或说a不属于集合A

·集合中的元素是无序的，不重复的。通常使用两种方法来给出一个集合： ·列元素法：列出某集合的所有元素，如：

·A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于10的自然数所构成的集合 ·B = {a, b, …, z} 表示所有小写英文字母所构成的集合

·性质概括法：使用某个性质来概括集合中的元素，如： ·A = { n | n 是小于10的自然数} ·C = { n | n 是质数} 表示所有质数所构成的集合 ·集合由它的元素所决定，换句话说，两个集合A和B相等，记为A = B，如果A和B具有相同的元素，即a属于集合A当且仅当a属于集合B。 ·子集(subset)：说集合A是集合B的子集，记为A?B，如果a属于集合A则a也属于集合B。因此A=B当且仅当A?B且B?A。说集合A是集合B的真子集(proper subset)，如果A?B且A不等于B(A ? B)。 ·空集(empty set)：约定存在一个没有任何元素的集合，称为空集，记为?，有时也用{}来表示。按子集的定义，空集是任何集合的子集(为什么？)。 ·幂集(power set)：集合A的幂集，记为P(A)，是A的所有子集所构成的集合，即： ·P(A) = { B | B ? A } ·例如，A = {0, 1}，则P(A) = { {}, {0}, {1}, {0, 1} } ·显然，对任意集合A，有?? P(A)和A?P(A) ·补集(complement set)：集合A的补集，记为A，是那些不属于集合A的元素所构成的集合，即A = {x | x?A}。通常来说，是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。

2. 集合的基本运算

·集合的并(union)：集合A和B的并A?B定义为：A?B = {x | x?A ? x?B}，集合的并可推广到多个集合，设A1, A2, …, An都是集合，它们的并定义为：

A1?A2…?An = {x | ?i(x?Ai)} ·集合的交(intersection)：集合A和B的并A?B定义为：A?B = {x | x?A ? x?B}，集合的交也可推广到多个集合，设A1, A2, …, An都是集合，它们的交定义为： A1?A2…?An = {x | ?i(x?Ai)} ·集合的相对补：集合B对A的相对补集A?B定义为：A?B = {x | x?A ? x?B}。集合B对全集U的相对补集记为~B，称为B的绝对补集。

47

·集合的对称差：集合A和B的对称差A?B定义为：A?B = (A?B)?(B?A)，对称差的一个等价定义是：A?B = (A?B) ? (A?B) ·集合的运算可使用文氏图形象地表示。 ·集合的运算中，~优先于并、交、相对补及对称差，后面四种运算的顺序由括号决定。

作业：教材p132的3、4、6

3. 集合恒等式

·集合的基本恒等式包括幂等律、结合律、交换律、分配律、同一律、零律、排中律、矛盾律、吸收律、德·摩尔根律、双重否定律，其中最重要的恒等式有： 吸收律： A?(A?B) = A A?(A?B) = A 德·摩尔根律： A?(B?C) = (A?B)?(A?C) A?(B?C) = (A?B)?(A?C) ·例3.2、例3.3表明证明集合恒等式的一个重要方法是，如果要证明集合 A = B，即可证明对任意的x?A有x?B，且对任意的x?B有x?A。 ·其它的一些有关集合运算的性质：

(A?B)?A (A?B)?B A?(A?B) B?(A?B) (A?B)?A A?B ? (A?B) = B ? (A?B) = A ? (A?B) = ? (A?B) = (A? ~B) A?B = B?A A?(B?C) = (A?B)?C A?? = A A?A = ? A?B = A?C ? B = C

·例3.5、例3.6、例3.7运用上述性质来证明集合的恒等式。

4. 有穷集合的计数

·含有有限个元素的集合称为有穷集合（有限集合，finite set），有限集合A的元素个数通常记为|A|。 ·A的幂集P(A)的元素个数有如下等式：| P(A)| = 2|A|。 ·使用文氏图再加上列方程组，求解方程组的办法可解决许多有关集合计数的问题，例3.8、例3.9采用了这种方法。 ·集合计数中一个很重要的定理称为容斥原理，其简单形式如下：

|A?B| = |A| + |B| ? |A?B|

|A?B?C| = |A| + |B| + |C| ? |A?B| ? |B?C| ? |A?C| + |A?B?C| 设U为全集，|~A| = |U| ? |A| ·使用容斥原理求解例3.9：

设：A = 会打排球的人、B = 会打网球的人、C = 会打篮球的人，即按题意有： |A| = 12, |B| = 6, |C| = 14, |A?C| = 6, |B?C| = 5, |A?B?C| = 2

根据容斥定理有：|A?B?C| = |A| + |B| + |C| ? |A?B| ? |B?C| ? |A?C| + |A?B?C|，即： |A?B?C| = 14 + 12 + 6 - |A?B| - 5 - 6 + 2,

即|A?B?C| = 23 - |A?B|，而且根据题意有：|B?(A?C)| = 6，即：

|(B?A)?(C?B)| = |(B?A)| + |(C?B)| - |A?B?C| = 5 + |(A?B)| - 2 = 6，

即|(A?B)| = 3，所以|A?B?C| = 20，所以不会打这三种球的人为25 - 20 = 5人。

5. 例题分析

作业：教材p133~135的8、9、11、13

48

49

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究离散数学基础 (5)全文阅读和word下载服务。