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

1、数理逻辑Mathematical Logic 第一章 逻辑、集合和函数Chapter 1 Logic、set and function复习集合的表示法空集基数幂集合如果一个集合有n个元素，那么它的幂集合有2n个元素。复习笛卡尔积和有序偶集合运算 AB集合等式集合相等的证明方法集合的计算机表示位串等式名称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复习证明(AB)(A

2、B)=A证明： (AB)(AB) = A(BB) = AU = A复习求 的基数和幂集合。解：基数3， 幂集为： 1.6 函数Function一、引言在许多情况下，我们都会为一个集合的每个元素指派另一个集合的一个特定元素。例如：假定为学习数理逻辑课的每个学生从A,B,C,D中选择一个字母作为他的得分。再假定张三的得分为A，李四的得分为C，王五的得分为A，赵六的得分为D。这种打分就是一个函数。一、引言令A和B为集合。从A到B的函数f是对元素的一种指派，对A的每个元素恰好指派B的一个元素。如果f指派给A中元素a的唯一的B的元素是b，就写成f(a)b。如果f是从A到B的函数，就写成 f: AB。一、

3、引言如果f是从A到B的函数，就说A是f的定义域，而B是f的伴域。如果f(a)=b，就说b是a的像，而a是b的原像。A中元素的所有像元素的集合称为f的值域。若f是从A到B的函数，有时也说成f是把A映射到B。一、引言从函数的定义，我们可以知道：函数的定义域是A，而不能是A的某个真子集；一个aA，只能对应于唯一的一个b。即，如果f (a)=b且f (a)=c，那么b=c。一、引言A：定义域/domain of f domf =AB：伴域/codomain of f ranf B a ： b 的原象/pre-imageb ： a的象/imagef (A)：值域/range of f张三李四王五赵六AB

4、CDab=f (a)fABf一、引言设函数f : XY，g: TW，如果X=T，Y=W，且对于所有xX和xT有f (x) = g(x)，则称函数f 和g相等，记作: f = g。例：设X=a,b,c，Y=0,1，XY=(a,0)，(b,0)，(c,0)，(a,1)，(b,1)，(c,1)，XY有26个子集，但只有23个子集定义为从X到Y的函数。一、引言f0=(a, 0)，(b, 0)，(c, 0)f1=(a, 0)，(b, 0)，(c, 1)f2=(a, 0)，(b, 1)，(c, 0)f3=(a, 0)，(b, 1)，(c, 1)f4=(a, 1)，(b, 0)，(c, 0)f5=(a, 1

5、)，(b, 0)，(c, 1)f6=(a, 1)，(b, 1)，(c, 0)f7=(a, 1)，(b, 1)，(c, 1)一、引言例： 设X和Y都为有限集，且|X|=m，|Y|=n，问X到Y可以定义多少种不同的函数？因为从X到Y的每一个函数的定义域都是X，在这些函数中，每一个恰有m个有序偶。另外，对于任何xX，可以有Y中的n个元素中的任何一个作为它的像，所以共有nm个不同的函数。一、引言具有相同定义域的两个实数值函数可以相加和相乘。令f1和f2是从A到R的函数，那么f1f2和f1f2也是从A到R的函数，其定义为： (f1f2)(x)= f1(x)+f2(x) f1f2(x)= f1(x)f2(

6、x)一、引言令f为从集合A到集合B的函数，S为A的一个子集。S的像是由S中元素的像组成的B的子集。我们用f (S)表示S的像，于是：f (S) = f(s) | sS例：令A=a,b,c,d,e而B=1,2,3,4，且f(a)=2, f(b)=1, f(c)=4, f(d)=1及f(e)=1。子集S=b,c,d的像是集合f(S)=1,4。二、一对一函数和映上函数函数f称为一对一的或单射的，当且仅当f的定义域中的所有x和y， f(x)=f(y)蕴含着xy。一对一的函数称为单射。函数f是一对一的，当且仅当只要xy，就有f(x)f(y)P59 例6 - 例8二、一对一函数和映上函数定义域和伴域都是实

7、数集合子集的函数f称为严格递增的，如果对f定义域中的x和y，只要xy就有f(x)f(y)。f称为严格递减的，如果对f定义域中的x和y，只要xf(y)。只要函数是严格递增的或严格递减的，它必定是一对一的。二、一对一函数和映上函数从A到B的函数f称为映上的，当且仅当对每个bB，有元素aA使得f(a)b。如果函数是映上的，就说它是满射函数。若函数f既是一对一的，又是映上的，就说它是一一对应或双射的。假定f是从集合A到它自己函数。如果A是有限的，那么f是一对一的当且仅当它是映上的。二、一对一函数和映上函数例：A=1,2,3,4，B=a,b,c，如果f : AB为f(1)=a，f(2)=c，f(3)=b

8、，f(4)=c， 则f是满射。例：A=1,2,3，B=a,b,c,d，如果f : AB为f(1)=a，f(2)=c，f(3)=b， 则f是单射。 例：A=1,2,3，B=a,b,c，如果f : AB为f(1)=a，f(2)=c，f(3)=b，则f既是单射又是满射，所以是双射函数。二、一对一函数和映上函数例：判定下列函数是单射、满射函数，还是双射函数?设A是正整数集合，B是正偶数集合，f是A到B的函数，且对于任意的正整数n有f(n)=2n。 单射 满射 双射设Z是整数集合，N是自然数集合，f是Z到N的函数，对于任意的整数x，f (x)=x2。 单射 满射 双射二、一对一函数和映上函数设X是工人的

9、集合，Y表示工作的集合；从X到Y的满射：每项工作至少分配有一个工人从X到Y的单射：没有两个工人做同一项工作从X到Y的双射：每一项工作都分配有工人，而且没有两个工人分配相同的工作abcd12345一对一函数abcd123映上函数123123二、一对一函数和映上函数例：P61 图112。令A为集合。A上的恒等函数是函数A：AA，其中A(a)=a，或者写成 IA ：AA 。三、反函数和函数组合令f 为从集合A到集合B的一一对应，f的反函数：它指派给B中元素b的是A中使得f (a)=b唯一元素a。f的反函数用f1表示f (a)=b时，f1(b)=a。三、反函数和函数组合如果函数f 不是一一对应，就无法

10、定义反函数。若f 不是一对一的，则伴域中的某元素b是定义域中多个元素的像；若f 不是映上的，那么伴域中某个元素b不是定义域中任何元素的像。三、反函数和函数组合一一对应关系称为可逆的，否则，就说它是不可逆的。P61 例1416。令g为从集合A到集合B的函数，f是从集合B到集合C的函数，函数f和g的组合用f g表示，定义为：(f g)(a)=f ( g (a) )三、反函数和函数组合如果g的值域不是f 的定义域的子集，就无法定义f g。P62 例1718。对函数组合而言交换律不成立。三、反函数和函数组合令gf 是一个复合函数若f 和g都是满射的，则gf是满射的；若f 和g都是单射的，则gf是单射的

11、；若f 和g都是双射的，则gf是双射的；三、反函数和函数组合证明：设f :XY, g: Y Z，令z为Z的任一元素，因g是满射，故必有某个元素yY使得g(y)=z，又因为f是满射，故必有某个元素xX，使得f(x)=y，故(gf )(x)=g (f (x)=g (y)=z。令x1,x2为X的元素，假定x1x2，因为f是单射的，故f (x1)f (x2)。又因g是单射的且f(x1)f(x2)，故g(f (x1)g(f (x2)，于是x1x2(gf )(x1) (gf )(x2)。因为g 和f 是双射，故根据上面的证明， gf为满射和单射的，即gf是双射的。三、反函数和函数组合函数和它的反函数组合，

12、不论以什么次序组合，得到的都是恒等函数。(f1f )(a)= f1(f (a)= f1(b)=a(ff1 )(b)= f (f1(b)= f1(a)=b(f1)1 =f三、反函数和函数组合若f: XY, g: Y Z均为一一对应函数，则(gf )-1=f -1g -1。证明：因f: XY, g: Y Z均为一一对应函数，故f -1和g -1均存在，且f -1: YX， g-1: ZY，所以f -1g -1: ZX。因为f 和g 都是双射的，所以gf: XZ是双射的，故(gf )-1存在且(gf )-1: ZX。有 dom(f -1g -1)=dom(gf )-1=Z三、反函数和函数组合对任意z

13、Z存在唯一yY，使得g(y)=z存在唯一xX，使得f (x)=y，故(f -1g -1)(z)= f -1(g -1(z)=f -1 (y)=x 同时：(gf )(x)=g(f (x)=g(y)=z 故: (gf )-1(z)=x 因此，对任一zZ有 (gf )-1(z) = (f -1g -1)(z)综上，(gf )-1=f -1g -1四、函数的图像令f 为从集合A到集合B的函数，函数f的图像是有序偶集合(a,b)|aAf (a)=b。P63 例19、例20五、几个重要函数底函数指派给实数x的是小于或等于x的最大整数，记作： x。顶函数指派给实数x的是大于或等于x的最小的整数，记作：五、几

14、个重要函数P64 例21-23底函数和顶函数的有用性质表1-191.7 序列和求和Sequence and Summation一、序列用于表示有序表的离散结构。序列是从整数集合的一个子集到某个集合S的函数。我们用an表示整数n的像，并称an为该序列的一个项。记作：an一、序列计算机科学中常用的序列格式是：a1,a2,an这种有限的序列也称为串。串S的长度是串中项的个数。空串是不包含任何项的串。空串长度为0。二、特殊的整数序列找出构造序列项的公式和通用规则。已知解题序列的几个项，目标是找出整个序列。例：如果序列的头10项是1,2,2, 3,3,3,4,4,4,4，求产生序列项的规则。整数n恰出现

15、n次二、特殊的整数序列是否是同一个值的反复出现？能否在前项上加一常量，或加一与项在序列中位置有关的量，就得到后项？能否将前项乘以某个特定的量得到后项？能否以某种方式组合前面的项以得到后项？将问题中的序列项与熟知的某个整数序列的项比较。P72-表1-20给出了若干常用的序列。二、特殊的整数序列例：5,11,17,23,29,35,41,47,53 an=an-1+6, a1=5;例：1,7,25,79,241,727,2185,6559 an=3n-2;二、特殊的整数序列例：1, 5, 11, 27, 65, 157, 379, 915例：0,2,10,30,68,130,222The On-Line Encyclopedia of Integer Sequenceshttp:/njas/sequences二、特殊的整数序列算术序列a,a+d,a+2d,a+3d,a+nd几何序列a,ar,ar2,ar3,arn三、求和序列an的项am,am-1,an之和可以用符号表示为：我们可以用任何字母表示求和下标：三、求和求和符号中的下标移位： 想让下标从0到4，可令k=j-1 三、求和几何序列的求和称为几何级数。例：求 若r=1S=(n+1)a三、求和双重求和：三、求和函数值f (s)对S中所有元素s求和：求几个有用的求和公式（表1-21）小结函数定义域、伴域、值