離散數(shù)學(xué)：4-6 二元關(guān)系與函數(shù)

請(qǐng)交作業(yè)四P113:2,3,4P114:5,6,8P115:13,14,15P116:16二元關(guān)系性質(zhì)運(yùn)算補(bǔ)充題：作業(yè)講評(píng)三P54:15(2)一階邏輯推理補(bǔ)充題：1，2P75:15，17(1)，21P54.15(2)求下列公式的前束范式

x(F(x)y(G(x,y,z))zH(x,y,z)原式x(F(x)y(G(x,y,z))sH(t,u,s)

(換名)

xy(F(x)G(x,y,z))sH(t,u,s)xys((F(x)G(x,y,z))H(t,u,s))

(x)(A(x)B)=(x)A(x)B(y)(A(y)B)=(y)A(y)B(s)(BA(s))=

B(s)A(s)一階邏輯推理補(bǔ)充題1構(gòu)造下述推理證明:

前提:(x)(A(x)B(x)),(x)B(x)

結(jié)論:(x)A(x)證明：①(x)(A(x)B(x))前提引入②A(a)B(a)①-

規(guī)則

③xB(x)

前提引入

④B(a)③-

規(guī)則

⑤A(a)②④拒取式

⑥(x)A(x)

⑤+

規(guī)則一階邏輯推理補(bǔ)充題2構(gòu)造下面命題的推理證明:所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。解：令Q(x):x是有理數(shù),R(x):x是實(shí)數(shù),Z(x):x是整數(shù)。前提：x(Q(x)R(x))，x(Q(x)Z(x))結(jié)論：x(R(x)Z(x))一階邏輯推理補(bǔ)充題2前提：x(Q(x)R(x))，x(Q(x)Z(x))結(jié)論：x(R(x)Z(x))證明：

①x(Q(x)Z(x))

前提引入

②Q(a)Z(a)①

-

規(guī)則

③x(Q(x)R(x))前提引入

④Q(a)R(a)③-

規(guī)則⑤Q(a)

②化簡(jiǎn)律⑥R(a)

④⑤假言推理⑦Z(a)

②化簡(jiǎn)律⑧

R(a)Z(a)⑥⑦合取

⑨

x(R(x)Z(x))⑧+規(guī)則P75:15請(qǐng)用文氏圖表示集合~A(BC)(AB)C(A~B)(CB)A(C~B)P75:17(1)A

B

C

D

T

A

C

B

D

x

AC

x

A

x

C

x

BxD

x

BD所以，

A

C

B

D

A

C

B

DxX…xYXY的證明方法P75:17(1)A

B

C

D

T

A

C

B

D當(dāng)BD≠、A

C=時(shí)，命題成立：設(shè)B

D={0}，B={1，0}，D={2，0}取A={1}，C={2}AC=

{0}=BD

成立P75:17(1)A

B

C

D

T

A

C

B

D當(dāng)BD=時(shí)，命題不成立：設(shè)B={1，0}，D={2，3}，BD=，取A={1}，C={2}，AC=，

不成立A

B

C

D

T

A

C

B

D

當(dāng)BD≠、AC≠時(shí),命題不一定成立當(dāng)BD=

AC時(shí),命題不成立設(shè)B={3,1,0},D={4,2,0}

A={1,0},C={2,0}

BD=

AC={0}{0}

{0}

不成立當(dāng)BDAC時(shí),命題成立設(shè)B={3,1,0},D={3,2,0}A={1,0},C={2,0}BD={3,0},AC={0}

{0}

{3,0}

成立P75:21求不超過(guò)120的素?cái)?shù)個(gè)數(shù)因?yàn)樗?對(duì)于不超過(guò)120的合數(shù),其素因子只可能是2、3、5、7，考慮集合:

S={x|xZ,1x120}S中不能被2、3、5、7中任何一個(gè)數(shù)整除的數(shù)都屬于不超過(guò)120的素?cái)?shù)。

令能被2、3、5或7整除的數(shù)的集合分別記為A2、A3、A5、A7，則題目所求數(shù)N為“+3”——因2、3、5、7不屬于

集合，而“1”不是素?cái)?shù)，所以+4-1=3|A2|=[120/2]=60|A3|=[120/3]=40,

|A5|=[120/5]=24,|A7|=[120/7]=17

P75:21求不超過(guò)120的素?cái)?shù)個(gè)數(shù)|A2A3|=[120/6]=20|A2A5|=[120/10]=12|A2A7|=[120/14]=8|A3A5|=[120/15]=8|A3A7|=[120/21]=5|A5A7|=[120/35]=3|A2A3A5|=[120/30]=4|A2A3A7|=[120/42]=2|A2A5A7|=[120/70]=1|A3A5A7|=[120/105]=1|A2A3A5A7|=[120/210]=014156=120－141＋56－8＋0＋3＝30第4章二元關(guān)系與函數(shù)4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運(yùn)算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價(jià)關(guān)系和偏序關(guān)系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù)

集合論在計(jì)算機(jī)科學(xué)中的應(yīng)用構(gòu)造從A到B的雙射函數(shù)一、有窮集之間的構(gòu)造例:A=P({1,2,3}),B={a,b}{1,2,3}解：

A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={f0,f1,f

2,

f

3,

f

4,

f

5,

f

6,f7},其中

f0={<1,a>,<2,a>,<3,a>},f1={<1,a>,<2,a>,<3,b>},

f2={<1,a>,<2,b>,<3,a>},f3={<1,a>,<2,b>,<3,b>},

f4={<1,b>,<2,a>,<3,a>},f5={<1,b>,<2,a>,<3,b>},

f6={<1,b>,<2,b>,<3,a>},f7={<1,b>,<2,b>,<3,b>}.令f：AB,

f()=f0,f({1})=f1,f({2})=f2,f({3})=f3,

f({1,2})=f4,f({1,3})=f5,f({2,3})=f6,f({1,2,3})=f7構(gòu)造從A到B的雙射函數(shù)（續(xù)）解1：令f：[,2][-1,1]

f(x)=2x/-3解2：令f：[,2][-1,1]

f(x)=cosx二、實(shí)數(shù)區(qū)間之間構(gòu)造雙射例:A=[,2]

B=[-1,1]構(gòu)造雙射f

:A→B構(gòu)造方法：直線方程0

2

x12x/-3-1構(gòu)造從A到B的雙射函數(shù)（續(xù)）三、A與自然數(shù)集合之間構(gòu)造雙射例:

構(gòu)造雙射f：Z→N(Z:整數(shù)集,N:自然數(shù)集)方法：將A中元素排成有序圖形，然后從第一個(gè)元素開(kāi)始按照次序與自然數(shù)對(duì)應(yīng)將Z中元素以下列順序排列，并與N中元素對(duì)應(yīng)：

Z：0112

2

33…

↓↓↓↓↓

↓↓

N：01234

5

6…則這種對(duì)應(yīng)所表示的函數(shù)是

構(gòu)造方法不唯一，無(wú)論采用何方法都要保證函數(shù)的單射性常函數(shù)、恒等函數(shù)、單調(diào)函數(shù)

1.

設(shè)f：AB,若存在cB

使得xA

都有

f(x)=c,則稱f：A→B是常函數(shù).2.稱A

上的恒等關(guān)系IA為A

上的恒等函數(shù),對(duì)所有的xA

都有IA(x)=x.3.設(shè)f：RR，如果對(duì)任意的x1,x2R，x1<x2,就有f(x1)<f(x2),則稱f

為單調(diào)遞增的；如果對(duì)任意的x1,x2A,x1<x2,就有f(x1)<f(x2),則稱f

為嚴(yán)格單調(diào)遞增的.

類似可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù).集合的特征函數(shù)定義：設(shè)A為集合,A’A,A’的特征函數(shù)

A’：A{0,1}定義為實(shí)例：集合：X={A,B,C,D,E,F,G,H},

子集：T={A,C,F,G,H}

T的特征函數(shù)T：

x

ABCDEFGHT(x)

10100111

AA’集合的特征函數(shù)可以證明，A的每一個(gè)子集A’都對(duì)應(yīng)于一個(gè)特征函數(shù)，不同的子集對(duì)應(yīng)于不同的特征函數(shù)。例如：A={a，b，c}，則它的每個(gè)子集的特征函數(shù)均不相同由A的子集與特征函數(shù)的對(duì)應(yīng)關(guān)系，可以用特征函數(shù)來(lái)標(biāo)記A的不同子集。

A的子集特征函數(shù)0,0,0{a}1,0,00,1,0{c}0,0,1{a,b}1,1,0{a,c}1,0,1{b,c}0,1,1{a,b,c}1,1,1定義：設(shè)R是A上的等價(jià)關(guān)系,

令

g：AA/R

g(a)=[a],aA

稱g是從A到商集A/R的自然映射.恒等關(guān)系確定的自然映射是雙射,其他的自然映射一般來(lái)說(shuō)是滿射.

自然映射

例如：A={1,2,3},R={<1,2>,<2,1>}IA則有：g(1)={1,2},

g(2)={1,2},

g(3)={3}4.7函數(shù)的復(fù)合與反函數(shù)函數(shù)復(fù)合的定理

設(shè)F,G是函數(shù),則F°G也是函數(shù),且滿足

(1)dom(F°G)={x|xdomG

G(x)domF}兩個(gè)函數(shù)的復(fù)合仍為一個(gè)函數(shù)。約定：只有當(dāng)兩個(gè)函數(shù)中一個(gè)的定義域與另一個(gè)函數(shù)的值域相同時(shí)，它們的復(fù)合才有意義。若不滿足條件時(shí)，可利用函數(shù)的限制與擴(kuò)充來(lái)彌補(bǔ)。

(2)xdom(F°G)，有F°G(x)=F(G(x))即dom(G)=dom(F°G)函數(shù)復(fù)合的定理例：設(shè)g:RR,f:R+R,g(x)=x+1,

f(x)=lnx

，則

g°f(x)

=g(f(x))=g(lnx)=lnx+1推論1

設(shè)F,G,H為函數(shù),則(F°G)°H和F°(G°H)都是函數(shù),且

(F°G)°H=F°(G°H)(滿足結(jié)合律)推論2

設(shè)g：AB，f：BC,則f°g：AC,且xA都有f°g(x)=f(g(x))

f°g(x)=f(g(x))=f(x+1)=ln(x+1)

一般地，g°f≠f°gg°f

和f°g的定義域不同函數(shù)復(fù)合的定理

實(shí)例：設(shè)f,g,h

均為R上的函數(shù):

f(x)=x+1,g(x)=x2+1,h(x)=3x

h°(g°f)(x)=h((g°f)(x))=h(g(f(x)))=h(g(x+1))=h((x+1)2+1)=3x2+6x+6

h°(g°f)=(h°g)°f(h°g)°f

(x)=(h°g)(f(x))=(h°g)(x+1)=h(g(x+1))=h((x+1)2+1)=3x2+6x+6

函數(shù)復(fù)合運(yùn)算的性質(zhì)定理4.7

設(shè)f：BC,g：AB.

則有若f

和g都是滿射的,則f°g也是滿射.若f

和g都是單射的,則f°g也是單射.若f

和g都是雙射的,則f°g也是雙射.證明：若f和g都是滿射,則f°g也是滿射.

證：cC,∵

f

是滿射,

∴

必bB,使得f(b)=c.對(duì)這個(gè)b,又∵

g是滿射,

∴

必aA,使得g(a)=b.

由合成定理有：c=f(b)=f

(g(a))=f°g(a)

說(shuō)明——函數(shù)的復(fù)合運(yùn)算的性質(zhì)能夠分別保持函數(shù)單射、滿射、雙射的性質(zhì)b3a1a2a3a4b1c1ABCc2b2gf函數(shù)復(fù)合運(yùn)算的性質(zhì)注意：函數(shù)復(fù)合運(yùn)算性質(zhì)的逆命題不為真。即若f°g：AC是單射（滿射或雙射），不一定有f：BC

和g：AB都是單射（滿射或雙射）。設(shè)f:BC,g:AB,舉例說(shuō)明:f°g是滿射，但

g不一定是滿射。a1a2a3b1b2b3c1c2fgA

B

C函數(shù)復(fù)合運(yùn)算的性質(zhì)注意：函數(shù)復(fù)合運(yùn)算性質(zhì)的逆命題不為真。即若f°g：AC是單射（滿射或雙射），不一定有f：BC

和g：AB都是單射（滿射或雙射）。設(shè)f:BC,g:AB,舉例說(shuō)明:f°g是單射，但

f

不一定是單射。A

B

Ca1a2b1b2

b3c1c2c3fg函數(shù)復(fù)合運(yùn)算的性質(zhì)注意：函數(shù)復(fù)合運(yùn)算性質(zhì)的逆命題不為真。即若f°g：AC是單射（滿射或雙射），不一定有f：BC

和g：AB都是單射（滿射或雙射）。設(shè)f:BC,g:AB,舉例說(shuō)明:f°g是雙射，但f、g不一定是雙射。a1a2b1b2b3c1c2fgA

B

C反函數(shù)存在的條件任給函數(shù)F,它的逆F1不一定是函數(shù),是二元關(guān)系.實(shí)例：F={<a,b>,<c,b>}，F(xiàn)1={<b,a>,<b,c>}

任給單射函數(shù)f：A→B,則f

1是函數(shù),且是從ranf

到A的雙射函數(shù),但不一定是從B到A的雙射函數(shù).實(shí)例：

f

:N→N,f(x)=2x,

f

1:ranf→N,f

1(x)=x/2

一個(gè)函數(shù)是否有反函數(shù)，要看此函數(shù)的逆關(guān)系是否滿足函數(shù)的兩個(gè)條件——全域性，唯一性反