數(shù)理邏輯-第一章-邏輯、集合和函數(shù)-函數(shù)

1、數(shù)理邏輯Mathematical Logic 第一章 邏輯、集合和函數(shù)Chapter 1 Logic、set and function復(fù)習(xí)集合的表示法空集基數(shù)冪集合如果一個(gè)集合有n個(gè)元素，那么它的冪集合有2n個(gè)元素。復(fù)習(xí)笛卡爾積和有序偶集合運(yùn)算 AB集合等式集合相等的證明方法集合的計(jì)算機(jī)表示位串等式名稱(chēng)AA恒等律AU=AAUU支配律A=AAA 冪等律AA=A(A)補(bǔ)集律A(AB)=A吸收律A(AB)=A等式名稱(chēng)ABBA交換律ABBAA(BC)= (AB)C結(jié)合律A(BC)= (AB)CA(BC)=(AB)(BC) 分配律A(BC)=(AB)(BC)ABAB德摩根定律ABAB復(fù)習(xí)證明(AB)(A

2、B)=A證明： (AB)(AB) = A(BB) = AU = A復(fù)習(xí)求 的基數(shù)和冪集合。解：基數(shù)3， 冪集為： 1.6 函數(shù)Function一、引言在許多情況下，我們都會(huì)為一個(gè)集合的每個(gè)元素指派另一個(gè)集合的一個(gè)特定元素。例如：假定為學(xué)習(xí)數(shù)理邏輯課的每個(gè)學(xué)生從A,B,C,D中選擇一個(gè)字母作為他的得分。再假定張三的得分為A，李四的得分為C，王五的得分為A，趙六的得分為D。這種打分就是一個(gè)函數(shù)。一、引言令A(yù)和B為集合。從A到B的函數(shù)f是對(duì)元素的一種指派，對(duì)A的每個(gè)元素恰好指派B的一個(gè)元素。如果f指派給A中元素a的唯一的B的元素是b，就寫(xiě)成f(a)b。如果f是從A到B的函數(shù)，就寫(xiě)成 f: AB。一、

3、引言如果f是從A到B的函數(shù)，就說(shuō)A是f的定義域，而B(niǎo)是f的伴域。如果f(a)=b，就說(shuō)b是a的像，而a是b的原像。A中元素的所有像元素的集合稱(chēng)為f的值域。若f是從A到B的函數(shù)，有時(shí)也說(shuō)成f是把A映射到B。一、引言從函數(shù)的定義，我們可以知道：函數(shù)的定義域是A，而不能是A的某個(gè)真子集；一個(gè)aA，只能對(duì)應(yīng)于唯一的一個(gè)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一、引言設(shè)函數(shù)f : XY，g: TW，如果X=T，Y=W，且對(duì)于所有xX和xT有f (x) = g(x)，則稱(chēng)函數(shù)f 和g相等，記作: f = g。例：設(shè)X=a,b,c，Y=0,1，XY=(a,0)，(b,0)，(c,0)，(a,1)，(b,1)，(c,1)，XY有26個(gè)子集，但只有23個(gè)子集定義為從X到Y(jié)的函數(shù)。一、引言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)一、引言例： 設(shè)X和Y都為有限集，且|X|=m，|Y|=n，問(wèn)X到Y(jié)可以定義多少種不同的函數(shù)？因?yàn)閺腦到Y(jié)的每一個(gè)函數(shù)的定義域都是X，在這些函數(shù)中，每一個(gè)恰有m個(gè)有序偶。另外，對(duì)于任何xX，可以有Y中的n個(gè)元素中的任何一個(gè)作為它的像，所以共有nm個(gè)不同的函數(shù)。一、引言具有相同定義域的兩個(gè)實(shí)數(shù)值函數(shù)可以相加和相乘。令f1和f2是從A到R的函數(shù)，那么f1f2和f1f2也是從A到R的函數(shù)，其定義為： (f1f2)(x)= f1(x)+f2(x) f1f2(x)= f1(x)f2(

6、x)一、引言令f為從集合A到集合B的函數(shù)，S為A的一個(gè)子集。S的像是由S中元素的像組成的B的子集。我們用f (S)表示S的像，于是：f (S) = f(s) | sS例：令A(yù)=a,b,c,d,e而B(niǎo)=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。二、一對(duì)一函數(shù)和映上函數(shù)函數(shù)f稱(chēng)為一對(duì)一的或單射的，當(dāng)且僅當(dāng)f的定義域中的所有x和y， f(x)=f(y)蘊(yùn)含著xy。一對(duì)一的函數(shù)稱(chēng)為單射。函數(shù)f是一對(duì)一的，當(dāng)且僅當(dāng)只要xy，就有f(x)f(y)P59 例6 - 例8二、一對(duì)一函數(shù)和映上函數(shù)定義域和伴域都是實(shí)

7、數(shù)集合子集的函數(shù)f稱(chēng)為嚴(yán)格遞增的，如果對(duì)f定義域中的x和y，只要xy就有f(x)f(y)。f稱(chēng)為嚴(yán)格遞減的，如果對(duì)f定義域中的x和y，只要xf(y)。只要函數(shù)是嚴(yán)格遞增的或嚴(yán)格遞減的，它必定是一對(duì)一的。二、一對(duì)一函數(shù)和映上函數(shù)從A到B的函數(shù)f稱(chēng)為映上的，當(dāng)且僅當(dāng)對(duì)每個(gè)bB，有元素aA使得f(a)b。如果函數(shù)是映上的，就說(shuō)它是滿(mǎn)射函數(shù)。若函數(shù)f既是一對(duì)一的，又是映上的，就說(shuō)它是一一對(duì)應(yīng)或雙射的。假定f是從集合A到它自己函數(shù)。如果A是有限的，那么f是一對(duì)一的當(dāng)且僅當(dāng)它是映上的。二、一對(duì)一函數(shù)和映上函數(shù)例：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是滿(mǎn)射。例：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既是單射又是滿(mǎn)射，所以是雙射函數(shù)。二、一對(duì)一函數(shù)和映上函數(shù)例：判定下列函數(shù)是單射、滿(mǎn)射函數(shù)，還是雙射函數(shù)?設(shè)A是正整數(shù)集合，B是正偶數(shù)集合，f是A到B的函數(shù)，且對(duì)于任意的正整數(shù)n有f(n)=2n。 單射 滿(mǎn)射 雙射設(shè)Z是整數(shù)集合，N是自然數(shù)集合，f是Z到N的函數(shù)，對(duì)于任意的整數(shù)x，f (x)=x2。 單射 滿(mǎn)射 雙射二、一對(duì)一函數(shù)和映上函數(shù)設(shè)X是工人的

9、集合，Y表示工作的集合；從X到Y(jié)的滿(mǎn)射：每項(xiàng)工作至少分配有一個(gè)工人從X到Y(jié)的單射：沒(méi)有兩個(gè)工人做同一項(xiàng)工作從X到Y(jié)的雙射：每一項(xiàng)工作都分配有工人，而且沒(méi)有兩個(gè)工人分配相同的工作abcd12345一對(duì)一函數(shù)abcd123映上函數(shù)123123二、一對(duì)一函數(shù)和映上函數(shù)例：P61 圖112。令A(yù)為集合。A上的恒等函數(shù)是函數(shù)A：AA，其中A(a)=a，或者寫(xiě)成 IA ：AA 。三、反函數(shù)和函數(shù)組合令f 為從集合A到集合B的一一對(duì)應(yīng)，f的反函數(shù)：它指派給B中元素b的是A中使得f (a)=b唯一元素a。f的反函數(shù)用f1表示f (a)=b時(shí)，f1(b)=a。三、反函數(shù)和函數(shù)組合如果函數(shù)f 不是一一對(duì)應(yīng)，就無(wú)法

10、定義反函數(shù)。若f 不是一對(duì)一的，則伴域中的某元素b是定義域中多個(gè)元素的像；若f 不是映上的，那么伴域中某個(gè)元素b不是定義域中任何元素的像。三、反函數(shù)和函數(shù)組合一一對(duì)應(yīng)關(guān)系稱(chēng)為可逆的，否則，就說(shuō)它是不可逆的。P61 例1416。令g為從集合A到集合B的函數(shù)，f是從集合B到集合C的函數(shù)，函數(shù)f和g的組合用f g表示，定義為：(f g)(a)=f ( g (a) )三、反函數(shù)和函數(shù)組合如果g的值域不是f 的定義域的子集，就無(wú)法定義f g。P62 例1718。對(duì)函數(shù)組合而言交換律不成立。三、反函數(shù)和函數(shù)組合令gf 是一個(gè)復(fù)合函數(shù)若f 和g都是滿(mǎn)射的，則gf是滿(mǎn)射的；若f 和g都是單射的，則gf是單射的

11、；若f 和g都是雙射的，則gf是雙射的；三、反函數(shù)和函數(shù)組合證明：設(shè)f :XY, g: Y Z，令z為Z的任一元素，因g是滿(mǎn)射，故必有某個(gè)元素yY使得g(y)=z，又因?yàn)閒是滿(mǎn)射，故必有某個(gè)元素xX，使得f(x)=y，故(gf )(x)=g (f (x)=g (y)=z。令x1,x2為X的元素，假定x1x2，因?yàn)閒是單射的，故f (x1)f (x2)。又因g是單射的且f(x1)f(x2)，故g(f (x1)g(f (x2)，于是x1x2(gf )(x1) (gf )(x2)。因?yàn)間 和f 是雙射，故根據(jù)上面的證明， gf為滿(mǎn)射和單射的，即gf是雙射的。三、反函數(shù)和函數(shù)組合函數(shù)和它的反函數(shù)組合，

12、不論以什么次序組合，得到的都是恒等函數(shù)。(f1f )(a)= f1(f (a)= f1(b)=a(ff1 )(b)= f (f1(b)= f1(a)=b(f1)1 =f三、反函數(shù)和函數(shù)組合若f: XY, g: Y Z均為一一對(duì)應(yīng)函數(shù)，則(gf )-1=f -1g -1。證明：因f: XY, g: Y Z均為一一對(duì)應(yīng)函數(shù)，故f -1和g -1均存在，且f -1: YX， g-1: ZY，所以f -1g -1: ZX。因?yàn)閒 和g 都是雙射的，所以gf: XZ是雙射的，故(gf )-1存在且(gf )-1: ZX。有 dom(f -1g -1)=dom(gf )-1=Z三、反函數(shù)和函數(shù)組合對(duì)任意z

13、Z存在唯一yY，使得g(y)=z存在唯一xX，使得f (x)=y，故(f -1g -1)(z)= f -1(g -1(z)=f -1 (y)=x 同時(shí)：(gf )(x)=g(f (x)=g(y)=z 故: (gf )-1(z)=x 因此，對(duì)任一zZ有 (gf )-1(z) = (f -1g -1)(z)綜上，(gf )-1=f -1g -1四、函數(shù)的圖像令f 為從集合A到集合B的函數(shù)，函數(shù)f的圖像是有序偶集合(a,b)|aAf (a)=b。P63 例19、例20五、幾個(gè)重要函數(shù)底函數(shù)指派給實(shí)數(shù)x的是小于或等于x的最大整數(shù)，記作： x。頂函數(shù)指派給實(shí)數(shù)x的是大于或等于x的最小的整數(shù)，記作：五、幾

14、個(gè)重要函數(shù)P64 例21-23底函數(shù)和頂函數(shù)的有用性質(zhì)表1-191.7 序列和求和Sequence and Summation一、序列用于表示有序表的離散結(jié)構(gòu)。序列是從整數(shù)集合的一個(gè)子集到某個(gè)集合S的函數(shù)。我們用an表示整數(shù)n的像，并稱(chēng)an為該序列的一個(gè)項(xiàng)。記作：an一、序列計(jì)算機(jī)科學(xué)中常用的序列格式是：a1,a2,an這種有限的序列也稱(chēng)為串。串S的長(zhǎng)度是串中項(xiàng)的個(gè)數(shù)?？沾遣话魏雾?xiàng)的串?？沾L(zhǎng)度為0。二、特殊的整數(shù)序列找出構(gòu)造序列項(xiàng)的公式和通用規(guī)則。已知解題序列的幾個(gè)項(xiàng)，目標(biāo)是找出整個(gè)序列。例：如果序列的頭10項(xiàng)是1,2,2, 3,3,3,4,4,4,4，求產(chǎn)生序列項(xiàng)的規(guī)則。整數(shù)n恰出現(xiàn)

15、n次二、特殊的整數(shù)序列是否是同一個(gè)值的反復(fù)出現(xiàn)？能否在前項(xiàng)上加一常量，或加一與項(xiàng)在序列中位置有關(guān)的量，就得到后項(xiàng)？能否將前項(xiàng)乘以某個(gè)特定的量得到后項(xiàng)？能否以某種方式組合前面的項(xiàng)以得到后項(xiàng)？將問(wèn)題中的序列項(xiàng)與熟知的某個(gè)整數(shù)序列的項(xiàng)比較。P72-表1-20給出了若干常用的序列。二、特殊的整數(shù)序列例：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;二、特殊的整數(shù)序列例：1, 5, 11, 27, 65, 157, 379, 915例：0,2,10,30,68,130,222The On-Line Encyclopedia of Integer Sequenceshttp:/njas/sequences二、特殊的整數(shù)序列算術(shù)序列a,a+d,a+2d,a+3d,a+nd幾何序列a,ar,ar2,ar3,arn三、求和序列an的項(xiàng)am,am-1,an之和可以用符號(hào)表示為：我們可以用任何字母表示求和下標(biāo)：三、求和求和符號(hào)中的下標(biāo)移位： 想讓下標(biāo)從0到4，可令k=j-1 三、求和幾何序列的求和稱(chēng)為幾何級(jí)數(shù)。例：求 若r=1S=(n+1)a三、求和雙重求和：三、求和函數(shù)值f (s)對(duì)S中所有元素s求和：求幾個(gè)有用的求和公式（表1-21）小結(jié)函數(shù)定義域、伴域、值