数理逻辑-第一章-逻辑、集合和函数-集合、集合运算

1、数理逻辑Mathematical Logic 第一章 逻辑、集合和函数Chapter 1 Logic、set and function复习绑定变量当量词作用于变量x或给这一变量赋值时，我们说此变量的这一次出现为绑定的。量词所约束的范围称为量词的辖域。x (P(x) yQ(x,y)绑定变量除非所有量词均为全称量词或均为存在量词，否则量词的顺序非常重要。P(x,y)= xy =0P(x,y)= x+y =0复习复习语句何时为真何时为假xy P(x,y) 对每一对x,y，P(x,y)均为真 有一对x,y， 使P(x,y)均为假yx P(x,y)xy P(x,y) 对每个x，都有y使得 P(x,y)为

2、真 有一个x，使P(x,y) 对每个y总是假xy P(x,y) 有一个x，使P(x,y)对所有y均为真 对每个x都有y使得 P(x,y)为假xy P(x,y) 有一对x,y使P(x,y)为真 对每一对x,y，P(x,y) 均为假yx P(x,y)复习 (x) A(x) (x) A(x) (x) A(x) (x) A(x) (x)(A(x) B(x) (x) A(x) (x)B(x) (x) (A(x) B(x) xA(x)xB(x) ( x) (A(x) B) xA(x) B ( x) (A(x) B) xA(x) B ( x) (A(x) B) xA(x) B ( x) (A(x) B) x

3、A(x) B1.4 集合Set一、概念和表示法集合是构造所有其他离散结构的基础（关系、组合、图等）集合是一个不能精确定义的基本概念直观地说，把具有共同性质的一些事物，汇集成一个整体，就形成一个集合，而这些事物就是这个集合的元素或成员。26个英文字母的集合教室内的桌椅通常用大写字母表示集合N：全体自然数组成集合Z：全体整数组成的集合Q：全体有理数组成的集合R：全体实数组成的集合C：全体复数组成的集合小写字母表示集合中的元素一、概念和表示法集合的表示方法枚举法描述法文氏图枚举法在可能的情况下列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。A=a，b，c，z一、概念和表示法枚举法小于

4、10的正奇数集合O可以表示为：O=1,3,5,7,9有时也并不列出它的所有元素。先列出集合中的某些元素，然后当元素的一般形式很明显时就用省略号（）表示。小于100的正整数集合可以表示为 1,2,3,99一、概念和表示法描述法用谓词来概括集合中元素的属性用x|P(x)表示集合，其中P(x)表示任何谓词N=x|x是自然数O=x|x是小于10的正奇数一、概念和表示法文氏图我们所考虑的所有对象的集合U，称为全集（相当于论域）；全集用长方形表示；圆或其它集合图形用于表示集合；点表示集合中特定的元素；文氏图常用于表示集合之间的关系。一、概念和表示法文氏图例：表示英语中的元音字母V的文氏图，全集U为26个英

5、文字母的集合VU. a. e. i. o. u一、概念和表示法集合相等两个集合相等当且仅当它们有相同的元素，记作A=B，不相等记作AB。集合的元素还可以允许是一个集合S=a,1,2,p,q集合中的各个元素在该集合中无次序的集合中的各个元素是可以相互分开的，重复出现就算一个一、概念和表示法集合相等1,2,4 1,2,2,41,2,4 1,4,21,2,4 1,2,41,3,5,7, x|x是正奇数=一、概念和表示法元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作。Aa，b，c，d，d aA，b，cA，dA，dA，但b A，d A； b和d是A的元素的元素。一、概念和表示法一、

6、概念和表示法子集：集合A是集合B的子集，当且仅当A的每个元素也是B的元素。记作： AB，或BA。A包含在B内，或B包含A。A B x (xA xB ) 一、概念和表示法子集：例：A=1,2,3, B=1,3, C=3B A, C A, C B例：a a,b a,b a,b,a一、概念和表示法子集：两个集合相等的充分必要条件是它们互为子集，即A=B ABB A。证明：A=B x(xA xB) x(xAxB)(xBxA) x(xAxB)x(xBxA) ABB A证明集合相等的一种有用的方式。一、概念和表示法子集：A A 自反性(A B) (B C) A C 传递性ABB A A = B 反对称性

7、一、概念和表示法真子集：如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集，记作：AB。AB (x)(xAxB)(x)(xBxA) AB AB AB一、概念和表示法真子集：AB用文氏图表示UAB一、概念和表示法空集：不包含任何元素的集合是空集，记作。空集可以符号化表示为：。 对于任意一个集合A，A。空集是唯一的。一、概念和表示法空集：与是不同的。是以为元素的集合，而没有任何元素。 ；。一、概念和表示法基数：令S为集合，若S中恰有n个不同的元素，n是非负整数，就说S是有限集合，而n是S的基数。表示为|S|。例：令A为小于10的正奇数集合，则|A|=5；例：由于空

8、集没有元素，所以|=0。一、概念和表示法二、幂集合给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集合，记作：P(A)。例：A=a,b，求其幂集合P(A)。P(A)=,a,b,a,b。例：求和的幂集合。P()=；P()=,。如果一个集合有n个元素，那么它的幂集合有2n个元素。二、幂集合Aa1 a1a2a3ana1,a3 二、幂集合有序n元组(a1,a2,an)是以a1为第1个元素，a2为第2个元素，an为第n个元素的有序组。只有在两个有序n元组每一对对应的元素都相等时，它们才相等。2元组特称为有序偶。三、笛卡尔积有序偶(a,b)和(c,d)相等，当且仅当a=c和b=d。可以表示为

9、： (a,b)=(b,a) a=b b=a(a,b)和(b,a)不相等，除非a=b。三、笛卡尔积例：已知(x+2,4)=(5,2x+y)，求x和y。由有序对相等的充要条件有 x+2=5 2x+y=4 解得x=3,y=-2。三、笛卡尔积令A和B为集合。A和B的笛卡尔积用AB表示，是所有有序偶(a,b)的集合，其中aA，而bB。AB=(a,b)| aA bB例：设A=a,b, B=0,1,2，则AB=(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)BA=(0,a),(0,b),(1,a),(1,b),(2,a),(2,b) 三、笛卡尔积ABBA；若A=或B=，则AB=。集合A

10、1,A2,An的笛卡尔积用A1A2An表示，这是有序n元组(a1,a2,an)的集合，其中对于i=1,2,n, aiAi。P44 例16三、笛卡尔积四、集合运算并集：设任意两个集合A和B，所有属于A或属于B的元素组成的集合S，称为A和B的并集，记作：AB。S= AB=x|(xA)(xB)BUA交集：设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作：AB。S= AB=x|(xA)(xB)ABU四、集合运算不相交：如果两个集合的交集为空集（AB=），就说它们不相交。包含排斥原理：求集合并集的基数|AB|=|A|+|B|-|AB|BUA四、集合运算差集：设任意两个

11、集合A和B，所有属于A而不属于B的元素组成的集合S，称为A和B的差集，或B对于A的补集，记作：AB。S= AB=x|(xA)(xB) =x|(xA)(xB)ABU四、集合运算补集令U为全集，集合A的补集用A表示，这是A对于U的补集，记作：UA。S= UA=x|(xU)(xA)UA四、集合运算对称差：设任意两个集合A和B，A和B的对称差为S，其元素或属于A，或属于B，但不能既属于A又属于B。记作：AB。S= AB =(A-B)(B-A) =x|(xA)(xB)ABU四、集合运算集合等式集合等式可以直接用对应的逻辑等价关系证明；三种证明方法：两个集合中的任何一个都是另一个的子集描述法和逻辑等价成员

12、表法四、集合运算等式名称AA恒等律AU=AAUU支配律A=AAA 幂等律AA=A(A)补集律A(AB)=A吸收律A(AB)=A等式名称ABBA交换律ABBAA(BC)= (AB)C结合律A(BC)= (AB)CA(BC)=(AB)(BC) 分配律A(BC)=(AB)(BC)ABAB德摩根定律ABAB集合等式两个集合互为子集P49 例10描述法和逻辑等价P50 例11成员表法（类似于真值表）P50 例12四、集合运算集合等式令A, B, C为集合。证明A(BC)=(CB)A解： A(BC)= A(BC) = A(BC) = (BC)A = (CB)A四、集合运算扩展的并集和交集由于集合的并集和交

13、集满足结合律，所以只要A,B,C为集合，ABC和ABC都有定义。BUACBUAC四、集合运算扩展的并集和交集一组集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合。记作： 表示集合A1,A2,An的并集。四、集合运算扩展的并集和交集一组集合的交集是包含那些属于这组集合中所有成员集合的元素的集合。记作： 表示集合A1,A2,An的并集。四、集合运算集合的计算机表示把集合的元素无序地存储起来。但是在做集合的并集、交集或差集等运算时会浪费时间，因为这些运算将需要大量的元素检索；假定全集U是有限的。首先为U的元素任意规定一个顺序，例如a1,a2, ,an。于是可以用长度为n的位串表示U的子集A：如果ai属于A，则位串中第i位为1；如果ai不属于A，则位串中的第i位是0。四、集合运算集合的计算机表示 P52 例16用位串表示集合便于