第一篇：離散數(shù)學(xué)例題

離散數(shù)學(xué)例題

一、證明對(duì)任意集合A，B，C，有 a）A-B）-C=A-（B∪C）； b）（A-B）-C=（A-C）-B；

c）（A-B）-C=（A-C）-（B-C）。

證明

a）（A-B）-C=（A∩～B）∩～C =A∩（～B∩～C）=A∩～（B∩C）=A-B∪C）

b）（A-B）-C= A∩～B∩～C = A∩～C∩～B =（A-C）-B

c）（A-C）-（B-C）

=（A∩～C）∩～（B∩～C）=（A∩～C）∩（～B∪C）

=（A∩～C∩～B）∪（A∩～C∩C）= A∩～B∩～C =（A-B）-C

二、設(shè)命題公式G =(P→Q)∨(Q∧(P→R)), 求G的主析取范式 G =(P→Q)∨(Q∧(P→R))=(P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧ R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 =(3, 4, 5, 6, 7).三、假設(shè)f和g是函數(shù)，證明f∩g也是函數(shù)。

證明

f∩g＝{| x∈dom f∧x∈dom g∧y=f（x）∧y=g（x）} ＝{| x∈dom f∩dom g∧y=f（x）=g（x）} 令h=f∩g，則

dom h={ x | x∈dom f∩dom g，f（x）=g（x）}

若y1 =y2，因?yàn)閒是函數(shù)，故必有y1 ＝／f（x1），y2 ＝／f（x2），且x1 ≠x2，所以h=f∩g

是一個(gè)函數(shù)。

因?yàn)閐om h存在且y1 ≠y2 時(shí)x1 ≠x2，即 h＝{| x∈ Dom h，y=h（x）=f（x）=g（x）}

四、設(shè)函數(shù)f：R→R，若x≤y＝＞f（x）≤f（y），則稱(chēng)函數(shù)f是單調(diào)遞增的。設(shè)f和g是在R上單調(diào)遞增，證明

1)若(f十g)(x)=f(x)+g(x)，則f+g是單調(diào)遞增； 2)復(fù)合函數(shù)f○g是單調(diào)遞增：

3)f和g的乘積不一定是單調(diào)遞增。

證明

1)因?yàn)閒和g是單調(diào)遞增，若x≤y，則有f（x）≤f(y)，g(x)≤g(y)，(f+g)(x)=f(x)十g(x)≤f(y)+g（y）=(f十g)(y)所以f+g是單調(diào)遞增。

2)若x≤y，則f(x)≤f(y)且g(x)≤ g（y），f○g（x）＝f(g(x))≤f(g(y))＝f○g(y)所以f○g是單凋遞增。

3）令f(x)=g（x）=x，則f和g是單調(diào)遞增，但其積函數(shù)

g*g(x)=f（x）*g（x）=x2 在R上不是單凋遞增。

五、設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝{(a, b),(b, c),(b, d),(d, d)}.計(jì)算R?S, R∪S, R－ 1, S－ 1?R－ 1.R?S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－ 1＝{(a, a),(c, a),(c, b),(d, c)}, S－ 1?R－ 1＝{(b, a),(d, c)}.六、若f：A→B是雙射，則f－1 ：B→A是雙射。

證明

因?yàn)閒：A→B是雙射，則f－1 是B到A的函數(shù)。下證f－1是雙射。

對(duì)任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f－1(y)＝x，所以f－1 是滿(mǎn)射。對(duì)任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因?yàn)閒：A→B 是函數(shù)，則y1＝y(tǒng)2。所以f－1 是單射。綜上可得，f－1 ：B→A是雙射。

七、設(shè)函數(shù)g：A→B，f：B→C，則：(1)f。g是A到C的函數(shù)；

(2)對(duì)任意的x∈A，有fg(x)＝f(g(x))。

證明

(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對(duì)于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈。所以Df。g＝A。

對(duì)任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。

綜上可知，f。g是A到C的函數(shù)。

(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f。g。又因f。g是A到C的函數(shù)，則可寫(xiě)為 f。g(x)＝f(g(x))。

第二篇：離散數(shù)學(xué)

離散數(shù)學(xué)試題（A卷答案）

一、（10分）

（1）證明(P?Q)∧(Q?R)?(P?R)（2）求(P∨Q)?R的主析取范式與主合取范式，并寫(xiě)出其相應(yīng)的成真賦值和成假賦值。解：（1）因?yàn)?(P?Q)∧(Q?R))?(P?R)??((?P∨Q)∧(?Q∨R))∨(?P∨R)?(P∧?Q)∨(Q∧?R)∨?P∨R ?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R))?(P∧?Q)∨(Q∨?P∨R)?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R)?T 所以，(P?Q)∧(Q?R)?(P?R)。

（2）(P∨Q)?R??(P∨Q)∨R?(?P∧?Q)∨R ?(?P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R)?M2∧M4∧M6 ?m0∨m1∨m3∨m5

所以，其相應(yīng)的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。

二、（10分）分別找出使公式?x(P(x)??y(Q(y)∧R(x，y)))為真的解釋和為假的解釋。

解：設(shè)論域?yàn)閧1，2}。

若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((F∧F)∨(F∧F)))∧(T?((F∧F)∨(F∧F)))?(T?F)∧(T?F)?F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((T∧T)∨(T∧T)))∧(T?((T∧T)∨(T∧T)))?(T?T)∧(T?T)?T

三、（10分）

在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)喜歡步行的人都不喜歡做汽車(chē)，每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē)。有的人不喜歡騎自行車(chē)，因而有的人不喜歡步行。

解

論域：所有人的集合。A(x)：x喜歡步行；B(x)：x喜歡坐汽車(chē)；C(x)：x喜歡騎自行車(chē)；則推理化形式為：

?x(A(x)??B(x))，?x(B(x)∨C(x))，??xC(x)?x?A(x)下面給出證明：(1)??xC(x)

P(2)?x?C(x)

T(1)，E(3)?C(c)

T(2)，ES(4)?x(B(x)∨C(x))

P(5)B(c)∨C(c)

T(4)，US(6)B(c)

T(3)(5)，I(7)?x(A(x)??B(x))

P(8)A(c)??B(c)

T(7)，US(9)?A(c)

T(6)(8)，I(10)?x?A(x)

T(9)，EG

四、（10分）

下列論斷是否正確？為什么？(1)若A∪B＝A∪C，則B＝C。(2)若A∩B＝A∩C，則B＝C。(3)若A?B＝A?C，則B＝C。

解(1)不一定。例如，令A(yù)＝{1}，B＝{1，2}，C＝{2}，則A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A(yù)＝{1}，B＝{1，2}，C＝{1，3}，則A∩B＝A∩C，但B＝C不成立。(3)成立。因?yàn)槿鬉?B＝A?C，對(duì)任意的x∈B，當(dāng)x∈A時(shí)，有x∈A∩B?x?A?B?x?A?C＝(A∪C)－(A∩C)?x∈A∩C?x∈C，所以B?C；當(dāng)x?A時(shí)，有x?A∩B，而x∈B?x∈A∪B，所以x∈A∪B－A∩B＝A?B?x∈A?C，但x? A，于是x∈C，所以B?C。

同理可證，C ?B。

因此，當(dāng)A?B＝A?C時(shí)，必有B＝C。

五、（10分）若R是集合A上的自反和傳遞關(guān)系，則對(duì)任意的正整數(shù)n，R＝R。

證明 當(dāng)n＝1時(shí)，結(jié)論顯然成立。設(shè)n＝k時(shí)，Rk＝R。當(dāng)n＝k＋1時(shí)，Rk+1＝Rk*R＝R*R。下面由R是自反和傳遞的推導(dǎo)出R*R＝R即可。

由傳遞性得R*R?R。另一方面，對(duì)任意的∈R，由R自反得∈R，再由關(guān)系的復(fù)合得∈R*R，從而R?R*R。因此，R＝R*R。

由數(shù)學(xué)歸納法知，對(duì)任意的正整數(shù)n，Rn＝R。

n

六、（15分）設(shè)函數(shù)f：R×R?R×R，f定義為：f()＝。

(1)證明f是單射。(2)證明f是滿(mǎn)射。(3)求逆函數(shù)f。

(4)求復(fù)合函數(shù)f－1?f和f?f。

證明(1)對(duì)任意的x，y，x1，y1∈R，若f()＝f()，則＝，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y(tǒng)1，故f是單射。

(2)對(duì)任意的∈R×R，令x＝u?w2u?w2－

1，y＝

u?w2，則f()＝<

u?w2＋

u?w2，u?w2－>＝，所以f是滿(mǎn)射。

u?w2－1(3)f()＝<－1，u?w2>。

x?y?x?y2x?y?(x?y)2(4)f?f()＝f(f())＝f()＝<－1－1，>＝ f?f()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）設(shè)X＝{1，2，3，4}，R是X上的二元關(guān)系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫(huà)出R的關(guān)系圖。(2)寫(xiě)出R的關(guān)系矩陣。

(3)說(shuō)明R是否是自反、反自反、對(duì)稱(chēng)、傳遞的。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：

?1??0M(R)??1??1?101110110??0? 0??0??(3)對(duì)于R的關(guān)系矩陣，由于對(duì)角線(xiàn)上不全為1，R不是自反的；由于對(duì)角線(xiàn)上存在非0元，R不是反自反的；由于矩陣不對(duì)稱(chēng)，R不是對(duì)稱(chēng)的；

經(jīng)過(guò)計(jì)算可得 ?1??02M(R)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0??

八、（10分）若是群，H是G的非空子集，則是的子群?對(duì)任意的a、b∈H有a*b－1∈H。證明 必要性：對(duì)任意的a、b∈H，由是的子群，必有b－1∈H，從而a*b－1∈H。充分性：由H非空，必存在a∈H。于是e＝a*a∈H。任取a∈H，由e、a∈H得a－1＝e*a－1∈H。

對(duì)于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因?yàn)镠是G非空子集，所以*在H上滿(mǎn)足結(jié)合律。綜上可知，是的子群。

九、（10分）給定二部圖G＝，且|V1∪V2|＝m，|E|＝n，證明n≤m/4。

證明 設(shè)|V1|＝m1，則|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22

2－

1－1

－1

m12。因?yàn)?m2?m1)2?0，即4?mm1?m1，所以n≤m2/4。離散數(shù)學(xué)試題（B卷答案）

一、（20分）用公式法判斷下列公式的類(lèi)型：(1)(?P∨?Q)?(P??Q)(2)(P?Q)?(P∧?(Q∨?R))解：（1）因?yàn)??P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q)

?(P∧Q)∨(P∧?Q)∨(?P∧Q)?m1∨m2∨m3 ?M0

所以，公式(?P∨?Q)?(P??Q)為可滿(mǎn)足式。

（2）因?yàn)?P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R))

?(P∨Q)∨(P∧?Q∧R))

?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R)

?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1

?m2∨m3∨m4∨m5∨m6∨m7

所以，公式(P?Q)?(P∧?(Q∨?R))為可滿(mǎn)足式。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：每個(gè)科學(xué)家都是勤奮的，每個(gè)勤奮又身體健康的人在事業(yè)中都會(huì)獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。

Q(x)：x是勤奮的；x是科學(xué)家；C(x)：解：論域：所有人的集合。H(x)：x是身體健康的；S(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為：

?x(S(x)?Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧H(x))

?x(C(x)∨F(x))下面給出證明：

(1)?x(S(x)∧H(x))

P(2)S(a)∧H(a)

T(1)，ES(3)?x(S(x)?Q(x))

P(4)S(a)?Q(a)

T(1)，US(5)S(a)

T(2)，I(6)Q(a)

T(4)(5)，I(7)H(a)

T(2)，I(8)Q(a)∧H(a)

T(6)(7)，I(9)?x(Q(x)∧H(x)?C(x))

P(10)Q(a)∧H(a)?C(a)

T(9)，Us(11)C(a)

T(8)(10)，I(12)?xC(x)

T(11)，EG(13)?x(C(x)∨F(x))

T(12)，I

三、（10分）設(shè)A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解

P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}}

四、（15分）設(shè)R和S是集合A上的任意關(guān)系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對(duì)稱(chēng)的，則R*S也是對(duì)稱(chēng)的。(4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則R∩S是自反的。(6)若R和S是傳遞的，則R∪S是傳遞的。

解

(1)成立。對(duì)任意的a∈A，因?yàn)镽和S是自反的，則∈R，∈S，于是∈R*S，故R*S也是自反的。

(2)不成立。例如，令A(yù)＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，則R和S是反自反的，但R*S＝{<1，1>}不是反自反的。

(3)不成立。例如，令A(yù)＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，則R和S是對(duì)稱(chēng)的，但R*S＝{<1，3>，<3，2>}不是對(duì)稱(chēng)的。

(4)不成立。例如，令A(yù)＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，則R和S是傳遞的，但R*S＝{<1，3>，<1，1>，<2，1>}不是傳遞的。

(5)成立。對(duì)任意的a∈A，因?yàn)镽和S是自反的，則∈R，∈S，于是∈R∩S，所以R∩S是自反的。

五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。問(wèn)(1)有多少個(gè)不同的由X到Y(jié)的函數(shù)？

(2)當(dāng)n、m滿(mǎn)足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？(3)當(dāng)n、m滿(mǎn)足什么條件時(shí)，存在雙射，且有多少個(gè)不同的雙射？

解

(1)由于對(duì)X中每個(gè)元素可以取Y中任一元素與其對(duì)應(yīng)，每個(gè)元素有n種取法，所以不同的函數(shù)共n個(gè)。

(2)顯然當(dāng)|m|≤|n|時(shí)，存在單射。由于在Y中任選m個(gè)元素的任一全排列都形成X到Y(jié)的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個(gè)。

(3)顯然當(dāng)|m|＝|n|時(shí)，才存在雙射。此時(shí)Y中元素的任一不同的全排列都形成X到Y(jié)的不同的雙射，mm故不同的雙射有m!個(gè)。

六、（5分）集合X上有m個(gè)元素，集合Y上有n個(gè)元素，問(wèn)X到Y(jié)的二元關(guān)系總共有多少個(gè)？ 解

X到Y(jié)的不同的二元關(guān)系對(duì)應(yīng)X×Y的不同的子集，而X×Y的不同的子集共有個(gè)2mn，所以X到Y(jié)的二元關(guān)系總共有2mn個(gè)。

七、（10分）若是群，則對(duì)于任意的a、b∈G，必有惟一的x∈G使得a*x＝b。

證明 設(shè)e是群的幺元。令x＝a－1*b，則a*x＝a*(a－1*b)＝(a*a－1)*b＝e*b＝b。所以，x＝a－1*b是a*x＝b的解。

若x?∈G也是a*x＝b的解，則x?＝e*x?＝(a*a)*x?＝a*(a*x?)＝a*b＝x。所以，x＝a*b是a*x

－

1－1

－1

－1＝b的惟一解。

八、（10分）給定連通簡(jiǎn)單平面圖G＝，且|V|＝6，|E|＝12。證明：對(duì)任意f∈F，d(f)＝3。證明

由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝24。若存在f∈

f?FF，使得d(f)＞3，則3|F|＜2|E|＝24，于是|F|＜8，與|F|＝8矛盾。故對(duì)任意f∈F，d(f)＝3。

第三篇：離散數(shù)學(xué)

第一章

數(shù)學(xué)語(yǔ)言與證明方法

例1 設(shè)E={ x | x是北京某大學(xué)學(xué)生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走讀生}, C= { x | x是數(shù)學(xué)系學(xué)生}，D= { x | x是喜歡聽(tīng)音樂(lè)的學(xué)生}.試描述下列各集合中學(xué)生的特征:

(A?D)? ~ C={ x | x是北京人或喜歡聽(tīng)音樂(lè),但不是數(shù)學(xué)系學(xué)生} ~ A?B={ x | x是外地走讀生}(A-B)? D={ x | x是北京住校生, 并且喜歡聽(tīng)音樂(lè)} ~ D ? ~ B={ x | x是不喜歡聽(tīng)音樂(lè)的住校生} 例3 證明:(1)A?B=B?A(交換律)證 ?x

x?A?B

? x?A?x?B

(并的定義)

?x?B?x?A

(邏輯演算的交換律)

?x?B?A

(并的定義)(2)A?(B?C)=(A?B)?(A?C)(分配律)證 ?x

x?A?(B?C)

? x?A?(x?B? x?C)

(并,交的定義)

?(x?A?x?B)?(x?A?x?C)

(邏輯演算的分配律)

?x?(A?B)?(A?C)

(并,交的定義)(3)A?E=E(零律)證 ?x

x?A?E

? x?A?x?E

(并的定義)

? x?A?1

(全集E的定義)

?1

(邏輯演算的零律)

?x?E

(全集E的定義)(4)A?E=A(同一律)證 ?x

x?A?E

? x?A?x?E

(交的定義)

? x?A?1

(全集E的定義)

? x?A

(邏輯演算的同一律)例4 證明 A?(A?B)=A（吸收律）證 利用例3證明的4條等式證明

A?(A?B)

=(A?E)?(A?B)

(同一律)

= A?(E?B)

(分配律)

= A?(B?E)

(交換律)

= A?E

(零律)

= A

(同一律)例5 證明(A-B)-C=(A-C)-(B-C)證

(A-C)-(B-C)

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

(補(bǔ)交轉(zhuǎn)換律)

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

(德摩根律)

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

(雙重否定律)

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

(分配律)

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

(矛盾律)

= A ? ~C ? ~B

(零律,同一律)

=(A ? ~B)? ~C

(交換律,結(jié)合律)

=(A – B)– C

(補(bǔ)交轉(zhuǎn)換律)例6 證明(A?B)?(A?C)=(B?C)(A?C))?((A?C)A 例7 設(shè)A,B為任意集合, 證明:(1)A?A?B 證 ?x x?A ? x?A?x?B

(附加律)

? x?A?B

(2)A?B?A

證 ?x x?A?B ? x?A?x?B

? x?A

(化簡(jiǎn)律)(3)A-B?A

證 ?x x?A-B ? x?A?x?B

? x?A

(化簡(jiǎn)律)(4)若A?B, 則P(A)?P(B)證 ?x x?P(A)? x?A

? x?B

(已知A?B)

? x?P(B)例8 證明 A?B=A?B-A?B.證

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

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

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

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

=A?B-A?B 例3 若A-B=A, 則A?B=?

證 用歸謬法, 假設(shè)A?B??, 則存在x,使得

x?A?B ? x?A?x?B ? x?A-B?x?B

(A-B=A)

? x?A?x?B?x?B ? x?B?x?B，矛盾 例4 證明

是無(wú)理數(shù)

證

假設(shè)

是有理數(shù), 存在正整數(shù)n,m, 使得

=m/n,不妨設(shè)m/n為既約分?jǐn)?shù).于是m=n, m2=2n2, m2是偶數(shù), 從而m是偶數(shù).設(shè)m=2k, 得(2k)2=2n2, n2=2k2, 這又得到n也 是偶數(shù), 與m/n為既約分?jǐn)?shù)矛盾.例6 對(duì)于每個(gè)正整數(shù)n, 存在n個(gè)連續(xù)的正合數(shù).證

令x=(n+1)!

則 x+2, x+3,…, x+n+1是n個(gè)連續(xù)的正合數(shù):

i | x+i，i=2,3,…,n+1 例7 判斷下述命題是真是假:

若A?B=A?C, 則B=C.解

反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有

A?B=A?C = {a,b} 但B?C, 故命題為假.例8 證明:對(duì)所有n?1, 1+2+ … +n=n(n+1)/2 證

歸納基礎(chǔ).當(dāng)n=1時(shí), 1=1?(1+1)/2, 結(jié)論成立.歸納步驟.假設(shè)對(duì)n?1結(jié)論成立, 則有

1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)

(歸納假設(shè))

=(n+1)(n+2)/2 得證當(dāng)n+1時(shí)結(jié)論也成立.例9 任何大于等于2的整數(shù)均可表成素?cái)?shù)的乘積 證 歸納基礎(chǔ).對(duì)于2, 結(jié)論顯然成立.歸納步驟.假設(shè)對(duì)所有的k(2?k?n)結(jié)論成立, 要證結(jié)論 對(duì)n+1也成立.若n+1是素?cái)?shù), 則結(jié)論成立;否則n+1=ab, 2?a,b

命題邏輯

例1 下列句子中那些是命題？

(1)北京是中華人民共和國(guó)的首都.(2)2 + 5 ＝8.(3)x + 5 ＞ 3.(4)你會(huì)開(kāi)車(chē)嗎？

(5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請(qǐng)關(guān)上門(mén)！(8)我正在說(shuō)謊話(huà).(1),(2),(5)是命題,(3),(4),(6)~(8)都不是命題

例2 將下列命題符號(hào)化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).解

(1)p∧q

(2)p∧q

(3)p∧?q(4)記 r:張輝是三好生, s:王麗是三好生，r∧s(5)簡(jiǎn)單命題，記 t:張輝與王麗是同學(xué) 例3 將下列命題符號(hào)化(1)2或4是素?cái)?shù).(2)2或3是素?cái)?shù).(3)4或6是素?cái)?shù).(4)元元只能拿一個(gè)蘋(píng)果或一個(gè)梨.(5)王曉紅生于1975年或1976年.解

(1)p∨r, 真值:1(2)

p∨q, 真值: 1(3)r∨s,真值: 0(4)記t:元元拿一個(gè)蘋(píng)果,u:元元拿一個(gè)梨

(t∧?u)∨(?t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年

(v∧?w)∨(?v∧w)又可形式化為

v∨w

例4 設(shè)p:天冷, q:小王穿羽絨服，將下列命題符號(hào)化

(1)只要天冷，小王就穿羽絨服.p?q(2)因?yàn)樘炖?，所以小王穿羽絨服.p?q

(3)若小王不穿羽絨服，則天不冷.?q??p 或 p?q(4)只有天冷，小王才穿羽絨服.q?p(5)除非天冷，小王才穿羽絨服.q?p(6)除非小王穿羽絨服，否則天不冷.p?q

(7)如果天不冷，則小王不穿羽絨服.?p??q 或 q?p(8)小王穿羽絨服僅當(dāng)天冷的時(shí)候.q?p 例5 求下列復(fù)合命題的真值

(1)2+2＝4 當(dāng)且僅當(dāng) 3+3＝6.(2)2+2＝4 當(dāng)且僅當(dāng) 3是偶數(shù).0(3)2+2＝4 當(dāng)且僅當(dāng) 太陽(yáng)從東方升起.(4)2+2＝5 當(dāng)且僅當(dāng) 美國(guó)位于非洲.(5)f(x)在x0處可導(dǎo)的充要條件是它在 x0處連續(xù).0 例6 公式A=(? p1? ? p2? ? p3)?(p1? p2)

000是成真賦值，001是成假賦值

公式B=(p?q)?r

000是成假賦值，001是成真賦值 例3 證明 p?(q?r)?(p?q)?r 證

p?(q?r)

? ?p?(?q?r)

（蘊(yùn)涵等值式）

?(?p??q)?r

（結(jié)合律）

? ?(p?q)?r

（德摩根律）

?(p?q)?r

（蘊(yùn)涵等值式 例4 證明: p?(q?r)

(p?q)?r 方法一

真值表法（見(jiàn)例2）

方法二

觀察法.容易看出000使左邊成真, 使右邊成假.方法三

先用等值演算化簡(jiǎn)公式, 再觀察.例5 用等值演算法判斷下列公式的類(lèi)型(1)q??(p?q)解

q??(p?q)

? q??(?p?q)

（蘊(yùn)涵等值式）

? q?(p??q)

（德摩根律）

? p?(q??q)

（交換律，結(jié)合律）

? p?0

（矛盾律）

? 0

（零律）該式為矛盾式.(2)(p?q)?(?q??p)解

(p?q)?(?q??p)

?(?p?q)?(q??p)

（蘊(yùn)涵等值式）

?(?p?q)?(?p?q)

（交換律）

? 1 該式為重言式.(3)((p?q)?(p??q))?r)

解

((p?q)?(p??q))?r)

?(p?(q??q))?r

（分配律）

? p?1?r

（排中律）

? p?r

（同一律）

非重言式的可滿(mǎn)足式.如101是它的成真賦值,000是它的 成假賦值.例1 求?(p?q)??r 的析取范式與合取范式 解

?(p?q)??r

? ?(?p?q)??r

?(p??q)??r

析取范式

?(p??r)?(?q??r)

合取范式 注意: 公式的析取范式與合取范式不惟一.例1(續(xù))求?(p?q)??r 的主析取范式與主合取范式 解(1)?(p?q)??r ?(p??q)??r

p??q ?(p??q)?1

同一律

?(p??q)?(?r?r)

排中律

?(p??q??r)?(p??q?r)

分配律

? m4?m5

?r ?(?p?p)?(?q?q)??r

同一律, 排中律

?(?p??q??r)?(?p?q??r)?(p??q??r)?(p?q??r)

? m0? m2? m4? m6

得

?(p?q)??r ? m0? m2? m4 ?m5 ? m6 可記作

? ?(0,2,4,5,6)(2)?(p?q)??r ?(p??r)?(?q??r)

p??r ? p?0??r

同一律

? p?(q??q)??r

矛盾律

分配律

?(p?q??r)?(p??q??r)

分配律

? M1?M3

?q??r ?(p??p)??q??r

同一律, 矛盾律

?(p??q??r)?(?p??q??r)

分配律

? M3?M7 得

?(p?q)??r ? M1?M3?M7 可記作

? ?(1,3,7)例2(1)求 A ?(?p?q)?(?p??q?r)?r的主析取范式 解 用快速求法

(1)?p?q ?(?p?q??r)?(?p?q?r)? m2? m3

?p??q?r ? m1

r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r)

? m1? m3? m5? m7 得

A? m1? m2? m3? m5? m7 ? ?(1,2,3,5,7)(2)求 B? ?p?(p?q??r)的主合取范式

解 ?p ?(?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r)

? M4?M5?M6?M7

p?q??r ? M1 得

B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7)例3 用主析取范式判斷公式的類(lèi)型:(1)A? ?(p?q)?q

(2)B? p?(p?q)

(3)C?(p?q)?r 解(1)A ? ?(? p?q)?q ?(p??q)?q ? 0

矛盾式(2)B ? ? p?(p?q)? 1 ? m0?m1?m2?m3

重言式(3)C ? ?(p?q)?r ?(?p??q)?r

?(?p??q?r)?(?p??q??r)?(?p??q?r)

?(?p?q?r)?(p??q?r)?(p?q?r)

? m0?m1?m3? m5?m7

非重言式的可滿(mǎn)足式 例4 用主析取范式判斷下面2組公式是否等值:(1)p與(?p?q)?(p?q)解

p ? p?(?q?q)?(p??q)?(p?q)? m2?m3

(?p?q)?(p?q)? ?(?p?q)?(p?q)

?(p??q)?(p?q)? m2?m3 故

p ?(?p?q)?(p?q)(2)(p?q)?r 與 p?(q?r)解(p?q)?r ?(p?q??r)?(p?q?r)

?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r)

? m1?m3?m5? m6?m7

p?(q?r)?(p?q)?(p? r)

?(p?q??r)?(p?q?r)?(p??q?r)?(p?q?r)

? m5? m6?m7 故

(p?q)?r

p?(q?r)例5 某單位要從A,B,C三人中選派若干人出國(guó)考察, 需滿(mǎn) 足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問(wèn)有幾種可能的選派方案? 解

記p:派A去, q:派B去, r:派C去

(1)p?r，(2)q??r，(3)(p??q)?(?p?q)求下式的成真賦值

A=(p?r)?(q??r)?((p??q)?(?p?q))例6 求A=(?p??q?r)?(?p?q?r)?(p?q?r)的主合取范式 解

A ? m1?m3?m7

? M0?M2?M4?M5?M6 例1 判斷下面推理是否正確:(1)若今天是1號(hào), 則明天是5號(hào).今天是1號(hào).所以, 明天是5號(hào).解

設(shè) p: 今天是1號(hào), q: 明天是5號(hào)

推理的形式結(jié)構(gòu)為

(p?q)ùp?q 證明

用等值演算法

(p?q)ùp?q

? ?((?púq)ùp)úq

?((pù?q)ú?p)úq

? ?pú?qúq ? 1 得證推理正確

(2)若今天是1號(hào), 則明天是5號(hào).明天是5號(hào).所以, 今天是1號(hào).解

設(shè)p: 今天是1號(hào), q: 明天是5號(hào).推理的形式結(jié)構(gòu)為

(p?q)ùq?p 證明

用主析取范式法

(p?q)ùq?p

?(?púq)ùq?p

? ?((?púq)ùq)úp

? ?qúp

?(?pù?q)ú(pù?q)ú(pù?q)ú(pùq)

? m0úm2úm3

01是成假賦值, 所以推理不正確.例2 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明: 前提: púq, q?r, p?s, ?s 結(jié)論: rù(púq)證明 ① p?s

前提引入

② ? s

前提引入 ③ ? p

①②拒取式 ④ púq

前提引入

⑤ q

③④析取三段論

⑥ q?r

前提引入

⑦ r

⑤⑥假言推理 ⑧ rù(púq)

⑦④合取 推理正確, rù(púq)是有效結(jié)論

例3 構(gòu)造推理的證明: 若明天是星期一或星期三, 我就有 課.若有課, 今天必需備課.我今天下午沒(méi)備課.所以, 明天 不是星期一和星期三.解 設(shè) p:明天是星期一, q:明天是星期三，r:我有課，s:我備課 前提:(púq)?r, r?s, ?s 結(jié)論: ?pù?q

例4 構(gòu)造下面推理的證明: 前提: ?púq, ?qúr, r?s 結(jié)論: p?s

證明 ① p

附加前提引入 ② ?púq

前提引入

③ q

①②析取三段論 ④ ?qúr

前提引入

⑤ r

③④析取三段論

⑥ r?s

前提引入

⑦ s

⑤⑥假言推理 推理正確, p?s是有效結(jié)論 例5 構(gòu)造下面推理的證明

前提: ?(pùq)úr, r?s, ?s, p 結(jié)論: ?q

證明

用歸繆法

① q

結(jié)論否定引入 ② r?s

前提引入 ③ ?s

前提引入 ④ ?r

②③拒取式 ⑤ ?(pùq)úr

前提引入

⑥ ?(pùq)

④⑤析取三段論 ⑦ ?pú?q

⑥置換

⑧ ?p

①⑦析取三段論 ⑨ p

前提引入 ⑩ ?pùp

⑧⑨合取 推理正確, ?q是有效結(jié)論

例6 用歸結(jié)證明法構(gòu)造下面推理的證明: 前提:(p?q)?r, r?s, ?s 結(jié)論:(p?q)?(pùs)解

(p?q)?r ? ?(?púq)úr ?(pù?q)úr ?(púr)ù(?qúr)

r?s ? ?rús

?

(p?q)?(pùs)? ?(?púq)ú(pùs)?(pù?q)ú(pùs)?

? pù(?qús)推理可表成

前提: púr, ?qúr, ?rús, ?s 結(jié)論: pù(?qús)

第3章 一階邏輯 例1(1)4是偶數(shù)

4是個(gè)體常項(xiàng), “是偶數(shù)”是謂詞常項(xiàng), 符號(hào)化為: F(4)(2)小王和小李同歲

小王, 小李是個(gè)體常項(xiàng), 同歲是謂詞常項(xiàng).記a:小王，b: 小李, G(x,y): x與y同歲, 符號(hào)化為: G(a,b)(3)x< y

x,y是命題變項(xiàng), < 是謂詞常項(xiàng), 符號(hào)化為: L(x,y)(4)x具有某種性質(zhì)P

x是命題變項(xiàng), P是謂詞變項(xiàng), 符號(hào)化為: P(x)例2 將下述命題用0元謂詞符號(hào)化, 并討論它們的真值:(1)

是無(wú)理數(shù), 而

是有理數(shù)(2)如果2>3，則3<4 解

(1)設(shè)F(x): x是無(wú)理數(shù), G(x): x是有理數(shù) 符號(hào)化為 真值為0(2)設(shè) F(x,y): x>y, G(x,y): x

個(gè)體域分別取(a)人類(lèi)集合,(b)全總個(gè)體域.解:(a)(1)設(shè)F(x): x愛(ài)美，符號(hào)化為 ?x F(x)

(2)設(shè)G(x): x用左手寫(xiě)字，符號(hào)化為 ?x G(x)

(b)設(shè)M(x): x為人，F(xiàn)(x), G(x)同(a)中

(1)?x(M(x)?F(x))

(2)? x(M(x)?G(x))M(x)稱(chēng)作特性謂詞

例4 將下列命題符號(hào)化, 并討論其真值:(1)對(duì)任意的x, 均有x2-3x+2=(x-1)(x-2)(2)存在x, 使得x+5=3 分別取(a)個(gè)體域D1=N,(b)個(gè)體域D2=R 解 記F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3(a)(1)?x F(x)

真值為1

(2)?x G(x)

真值為0(b)(1)?x F(x)

真值為1

(2)?x G(x)

真值為1 例5 將下面命題符號(hào)化:(1)兔子比烏龜跑得快

(2)有的兔子比所有的烏龜跑得快(3)并不是所有的兔子都比烏龜跑得快(4)不存在跑得一樣快的兔子和烏龜

解

用全總個(gè)體域，令F(x): x是兔子, G(y): y是烏龜，H(x,y): x比y跑得快，L(x,y): x和y跑得一樣快(1)?x?y(F(x)?G(y)?H(x,y))(2)?x(F(x)?(?y(G(y)?H(x,y)))(3)? ?x?y(F(x)?G(y)?H(x,y))(4)? ?x?y(F(x)?G(y)?L(x,y))例6 公式 ?x(F(x,y)??yG(x,y,z))?x的轄域:(F(x,y)??yG(x,y,z))，指導(dǎo)變?cè)獮閤 ?y的轄域:G(x,y,z)，指導(dǎo)變?cè)獮閥 x的兩次出現(xiàn)均為約束出現(xiàn)

y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn) z為自由出現(xiàn).例7 公式 ?x(F(x)??xG(x))?x的轄域:(F(x)??xG(x))，指導(dǎo)變?cè)獮閤 ?x的轄域:G(x)，指導(dǎo)變?cè)獮閤 x的兩次出現(xiàn)均為約束出現(xiàn).但是, 第一次出現(xiàn)的x是?x中 的x, 第二次出現(xiàn)的x是?x中的x.例8 給定解釋I 如下:

(a)個(gè)體域 D=N

(b)

(c)

(d)謂詞

說(shuō)明下列公式在 I 下的含義, 并討論其真值

(1)?xF(g(x,a),x)?x(2x=x)

假命題

(2)?x?y(F(f(x,a),y)?F(f(y,a),x))?x?y(x+2=y?y+2=x)

假命題(3)?x?y?zF(f(x,y),z)

?x?y?z(x+y=z)

真命題

(4)?xF(f(x,x),g(x,x))

?x(2x=x2)

真命題(5)F(f(x,a), g(x,a))x+2=2x

不是命題

(6)?x(F(x,y)?F(f(x,a), f(y,a)))?x(x=y?x+2=y+2)

真命題

例8(1)~(4)都是閉式, 在I下全是命題.(5)和(6)不是閉式, 在I下(5)不是命題,(6)是命題

例9 判斷下列公式的類(lèi)型:(1)?x(F(x)?G(x))取解釋I1, D1=R，:x是整數(shù)，:x是有理數(shù), 取解釋I2, D2=R，:x是整數(shù)，:x是自然數(shù), 非永真式的可滿(mǎn)足式(2)?(?xF(x))?(?xF(x))

這是 ?p?p 的代換實(shí)例, ?p?p是重言式，永真式(3)?(?xF(x)??yG(y))? ?yG(y)這是?(p?q)?q的代換實(shí)例, ?(p?q)?q是矛盾式

矛盾式 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)

真命題 假命題

(1)?xF(x,y,z)? ?yG(x,y,z)? ?uF(u,y,z)? ?yG(x,y,z)

換名規(guī)則 ? ?uF(u,y,z)? ?vG(x,v,z)

換名規(guī)則

或者 ? ?xF(x,u,z)? ?yG(x,y,z)

代替規(guī)則

? ?xF(x,u,z)? ?yG(v,y,z)

代替規(guī)則(2)?x(F(x,y)? ?yG(x,y,z))? ?x(F(x,y)? ?tG(x,t,z))

換名規(guī)則

或者 ? ?x(F(x,t)? ?yG(x,y,z))

代替規(guī)則 例2 設(shè)個(gè)體域D={a,b,c}, 消去下面公式中的量詞:(1)?x(F(x)?G(x))?(F(a)?G(a))?(F(b)?G(b))?(F(c)?G(c))(2)?x(F(x)??yG(y))? ?xF(x)??yG(y)

量詞轄域收縮 ?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))(3)?x?yF(x,y)? ?x(F(x,a)?F(x,b)?F(x,c))?(F(a,a)?F(a,b)?F(a,c))?(F(b,a)?F(b,b)?F(b,c))

?(F(c,a)?F(c,b)?F(c,c))例3 給定解釋I:(a)D={2,3},(b)

(c)

:x是奇數(shù)，: x=2 ? y=2，: x=y.在I下求下列各式的真值:(1)?x(F(f(x))?G(x, f(x)))

解

(F(f(2))?G(2, f(2)))?(F(f(3))?G(3, f(3)))?(1?1)?(0?1)? 1(2)?x?yL(x,y)解

?yL(2,y)??yL(3,y)?(L(2,2)?L(2,3))?(L(3,2)?L(3,3))?(1?0)?(0?1)? 0 例4 證明下列等值式:

? ?x(M(x)?F(x))? ?x(M(x)? ?F(x))證

左邊 ? ?x ?(M(x)?F(x))

量詞否定等值式

? ?x(?M(x)??F(x))? ?x(M(x)? ?F(x))例5 求公式的前束范式(1)?xF(x)???xG(x)解

? ?xF(x)??x?G(x)

量詞否定等值式 ? ?x(F(x)??G(x))

量詞分配等值式 解2 ? ?xF(x)???yG(y)

換名規(guī)則 ? ?xF(x)??y?G(y)

量詞否定等值式 ? ?x(F(x)??y?G(y))

量詞轄域擴(kuò)張 ? ?x?y(F(x)??G(y))

量詞轄域擴(kuò)張

第4章 關(guān)系 例1 <2,x+5>=<3y?4,y>，求 x, y.解

3y?4=2, x+5=y ? y=2, x= ?3 例2

A={0, 1}, B={a, b, c}

A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>}

B?A ={,,,,,}

A = {?}, B = ?

P(A)?A = {, <{?},?>}

P(A)?B = ?

例3

(1)R={ | x,y?N, x+y<3}

={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}

(2)C={ | x,y?R, x2+y2=1}，其中R代表實(shí)數(shù)集合，C是直角坐標(biāo)平面上點(diǎn)的橫、縱坐標(biāo)之間的關(guān)系，C中的所有的點(diǎn)恰好構(gòu)成坐標(biāo)平面上的單位圓.(3)

R={ | x,y,z?R, x+2y+z=3}，R代表了空間直角坐標(biāo)系中的一個(gè)平面.例4 A={0,1}, B={1,2,3}，R1={<0,2>}, R2=A×B, R3=?, R4={<0,1>}，從A到B的關(guān)系: R1, R2, R3, R4, A上的關(guān)系R3和R4.計(jì)數(shù)：

|A|=n, |B|=m, |A×B|=nm, A×B 的子集有

個(gè).所以從A到B有

元關(guān)系.|A|=n, A上有

不同的二元關(guān)系.例如 |A|=3, 則 A上有512個(gè)不同的二元關(guān)系.例

5A={a, b, c, d}, R={,,,,}, R的關(guān)系矩陣 MR 和關(guān)系圖 GR 如下：

??1110??1000???0000???0100??例1

R={,,<{a},9zet2xa>,}, 則

domR =

ranR =

fldR =

例2

R={<1,2>, <2,3>, <1,4>, <2,2>}

S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}

R?1 =

R°S =

S°R =

個(gè)不同的二

例3 設(shè)A = {a, b, c, d}, R = {,,,}, 求R的各次冪, 分別用矩陣和關(guān)系圖表示.解 R與R2的關(guān)系矩陣分別為

?0100??0100??01 ???1010??1010102???M?? M???0001??0001??00 ?????00000000???00??

例1

A = {a, b, c}, R1, R2, R3 是 A上的關(guān)系, 其中  R1 = {,}  R2 = {,,,}  R3 = {}

00??1?010????01??0??00??0010?101??000??000?R2自反, R3 反自反, R1既不自反也不反自反.例2

設(shè)A＝{a,b,c}, R1, R2, R3和R4都是A上的關(guān)系, 其中



R1＝{,}，R2＝{,,}  R3＝{,}，R4＝{,,} R1 對(duì)稱(chēng)、反對(duì)稱(chēng).R2 對(duì)稱(chēng)，不反對(duì)稱(chēng).R3 反對(duì)稱(chēng)，不對(duì)稱(chēng).R4 不對(duì)稱(chēng)、也不反對(duì)稱(chēng) 例3 設(shè)A＝{a, b, c}, R1, R2, R3是A上的關(guān)系, 其中 

R1＝{,} 

R2＝{,} 

R3＝{} R1 和 R3 是A上的傳遞關(guān)系, R2不是A上的傳遞關(guān)系.例4

證明若 IA ?R，則 R 在 A 上自反.證

任取x，x?A ? ?IA ? ?R

因此 R 在 A 上是自反的.例5

證明若 R=R?1 , 則 R 在A上對(duì)稱(chēng).證

任取

?R ? ?R ?1 ? ?R

因此 R 在 A 上是對(duì)稱(chēng)的.例6

證明若 R∩R?1?IA , 則 R 在 A 上反對(duì)稱(chēng).證

任取

?R ??R ? ?R ??R ?1

? ?R∩R ?1 ? ?IA ? x=y

因此 R 在 A 上是反對(duì)稱(chēng)的.例7

證明若 R°R?R , 則 R 在 A 上傳遞.證

任取，

?R ??R ? ?R°R ? ?R

因此 R 在 A 上是傳遞的.例8 判斷下圖中關(guān)系的性質(zhì), 并說(shuō)明理由

(1)不自反也不反自反；對(duì)稱(chēng), 不反對(duì)稱(chēng)；不傳遞.(2)反自反, 不是自反；反對(duì)稱(chēng), 不是對(duì)稱(chēng)；傳遞.(3)自反，不是反自反；反對(duì)稱(chēng)，不是對(duì)稱(chēng)；不傳遞.例1 設(shè)A={a,b,c,d}, R={,,,,}, R和 r(R), s(R), t(R)的關(guān)系圖如下圖所示.(1)(2)(3)

例1 設(shè) A={1, 2, …, 8}, 如下定義 A上的關(guān)系R： 

R={| x,y?A∧x≡y(mod 3)} 其中 x≡y(mod 3)叫做 x與y 模3相等, 即 x 除以3的余數(shù)與 y 除以3的余數(shù)相等.不難驗(yàn)證R為A上的等價(jià)關(guān)系, 因?yàn)?

?x?A, 有x≡x(mod 3)

?x,y?A, 若x≡y(mod 3), 則有y≡x(mod 3)

?x,y,z?A, 若x≡y(mod 3), y≡z(mod 3), 則有

x≡z(mod 3)例2 令A(yù)={1, 2, …, 8}，A關(guān)于模 3 等價(jià)關(guān)系R 的商集為

A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：

A/IA = { {1},{2}, … ,{8}}

A/EA = { {1, 2, … ,8} }

例3 設(shè)A＝{a, b, c, d}, 給定? 1, ? 2, ? 3, ? 4, ? 5, ? 6如下： ? 1={{a, b, c},5dh70u6}，? 2={{a, b},{c},8hcrpp8}  ? 3={{a},{a, b, c, d}}，? 4={{a, b},{c}}  ? 5={?,{a, b},{c, d}}，? 6={{a,{a}},{b, c, d}} 則? 1和? 2是A的劃分, 其他都不是A的劃分.例4 給出A＝{1,2,3}上所有的等價(jià)關(guān)系

求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫(xiě)出

對(duì)應(yīng)的等價(jià)關(guān)系.A上的等價(jià)關(guān)系與劃 分之間的對(duì)應(yīng)：

? 4對(duì)應(yīng)于全域關(guān)系EA ? 5對(duì)應(yīng)于恒等關(guān)系IA ? 1, ? 2和? 3分別對(duì)應(yīng)于等價(jià)關(guān)系 R1, R2和R3.其中

R1={<2,3>,<3,2>}∪IA



R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IA 例5

設(shè)A={1,2,3,4}，在A?A上定義二元關(guān)系 R：

<,>?R ? x+y = u+v，求R 導(dǎo)出的劃分.解

A?A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>，<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>，<4,4>}

根據(jù)有序?qū)?x,y>的 x+y=2,3,4,5,6,7,8 將A?A劃分.(A?A)/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>}，{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>}，{<3,4>, <4,3>}, {<4,4>}}

例6

<{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除>

例7

已知偏序集的哈斯圖如下圖所示, 試求出集合A和關(guān)系R的表達(dá)式.A={a, b, c, d, e, f, g, h}

R={,,,,,,,，}∪IA

例8 設(shè)偏序集如下圖所示，求A 的極小元、最小元、極大元、最大元.設(shè)B＝{ b, c, d }, 求B 的下界、上界、下 確界、上確界.解：極小元：a, b, c, g；極大元：a, f, h；沒(méi)有最小元與最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界為 d.第5章 函數(shù)

例1 設(shè)A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , 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>} 例2

判斷下面函數(shù)是否為單射, 滿(mǎn)射, 雙射的, 為什么?（1）f : R→R, f(x)= ?x2+2x?1（2）f : Z+→R, f(x)=lnx, Z+為正整數(shù)集（3）f : R→Z, f(x)=?x?（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+為正實(shí)數(shù)集.解(1)f : R→R, f(x)= ?x2+2x?1

在x=1取得極大值0.既不是單射也不是滿(mǎn)射的.(2)f : Z+→R, f(x)=lnx

單調(diào)上升, 是單射的.但不滿(mǎn)射, ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= ?x?

是滿(mǎn)射的, 但不是單射的, 例如 f(1.5)=f(1.2)=1.(4)f : R→R, f(x)=2x+1

是滿(mǎn)射、單射、雙射的, 因?yàn)樗菃握{(diào)函數(shù)并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x

有極小值f(1)=2.該函數(shù)既不是單射的也不是滿(mǎn)射的.例3

A=P({1,2,3}), B={0,1}{1,2,3} 解

A={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={ f0, f1, … , f7 }, 其中

f0={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>}，f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>}，f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}.令

f : A→B，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 例4

A=[0,1]

B=[1/4,1/2] 構(gòu)造雙射 f : A→B解

令

f : [0,1]→[1/4,1/2]

f(x)=(x+1)/4

例5

A=Z, B=N，構(gòu)造雙射 f : A→B

將Z中元素以下列順序排列并與N中元素對(duì)應(yīng)： Z：0?11

?22?33 …  

 ↓

↓

↓

↓

↓

↓

↓ N：0 1 2 4 5 6 … 則這種對(duì)應(yīng)所表示的函數(shù)是： 

x?0?2xf:Z?N,f(x)????2x?1x?0例1 設(shè) f : R→R, g : R→R ?x2x?3f(x)?? x?3??2 g(x)?x?2

求

f °g, g°f.如果 f 和 g 存在反函數(shù), 求出它們的反函數(shù).解 f?g:R?R?x2?2x?3f?g(x)??x?3?0g?f:R?R?(x?2)2g?f(x)????2x?1x?1 f : R→R不存在反函數(shù)；g : R→R的反函數(shù)是 g?1: R→R, g?1(x)=x?2

第6章 圖

例1 下述2組數(shù)能成為無(wú)向圖的度數(shù)列嗎?(1)3,3,3,4;(2)1,2,2,3

解(1)不可能.有奇數(shù)個(gè)奇數(shù).(2)能

例2 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小 于等于2, 問(wèn)G至少有多少個(gè)頂點(diǎn)? 解 設(shè)G有n個(gè)頂點(diǎn).由握手定理，4?3+2?(n-4)?2?10 解得

n?8 例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解

2,1,1,1,2 例4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的 多面體.證

用反證法.假設(shè)存在這樣的多面體, 作無(wú)向圖G=, 其中 V={v | v為多面體的面}，E={(u,v)| u,v?V ? u與v有公共的棱 ? u?v}.根據(jù)假設(shè), |V|為奇數(shù)且?v?V, d(v)為奇數(shù).這與握手定理的推論矛盾.例5 設(shè)9階無(wú)向圖的每個(gè)頂點(diǎn)的度數(shù)為5或6, 證明它至少有 5個(gè)6度頂點(diǎn)或者至少有6個(gè)5度頂點(diǎn).證

討論所有可能的情況.設(shè)有a個(gè)5度頂點(diǎn)和b個(gè)6度頂點(diǎn)(1)a=0, b=9;

(2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)~(3)至少5個(gè)6度頂點(diǎn),(4)和(5)至少6個(gè)5度頂點(diǎn)

方法二

假設(shè)b<5, 則a>9-5=4.由握手定理的推論, a ? 6 例6 畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖

解 總度數(shù)為6, 分配給4個(gè)頂點(diǎn), 最大度為3, 且奇度頂點(diǎn)數(shù) 為偶數(shù), 有下述3個(gè)度數(shù)列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,3 1,1,2,2

例7 畫(huà)出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無(wú)向簡(jiǎn)單圖 0,2,2,2

例1 右圖有 個(gè)面 R1的邊界:a R2的邊界:bce R3的邊界:fg

R0的邊界:abcdde, fg

deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右邊2個(gè)圖是同一平面圖的平面嵌入.R1在(1)中是外部面, 在(2)中是內(nèi)部面;R2在(1)中是內(nèi)部面, 在(2)中是外部面.R3 R1 R3 R2(1)

R2

R1(2)

說(shuō)明:(1)一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入, 它們都同構(gòu).(2)可以通過(guò)變換(測(cè)地投影法)把平面圖的任何一面作為外部面 例3 證明 K5 和 K3,3不是平面圖

證 K5 : n=5, m=10, l=3

K3,3 : n=6, m=9, l=4

不滿(mǎn)足定理6.15的條件

例

5證明下面2個(gè)圖均為非平面圖.與K3,3同胚也可收縮到K3,3

與K5同胚也可收縮到K5 例6 畫(huà)出所有非同構(gòu)的6階11條邊的簡(jiǎn)單連通非平面圖 解

在K5(5階10條邊)上加一個(gè)頂點(diǎn)和一條邊

在K3,3(6階9條邊)上加2條邊

例1 某中學(xué)有3個(gè)課外活動(dòng)小組:數(shù)學(xué)組, 計(jì)算機(jī)組和生物組.有趙,錢(qián),孫,李,周5名學(xué)生, 問(wèn)分別在下述3種情況下, 能否選出3人各任一個(gè)組的組長(zhǎng)?(1)趙, 錢(qián)為數(shù)學(xué)組成員, 趙,孫,李為計(jì)算機(jī)組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學(xué)組成員, 錢(qián),孫,李為計(jì)算機(jī)組成員, 錢(qián),孫,李,周為生物組成員.(3)趙為數(shù)學(xué)組和計(jì)算機(jī)組成員, 錢(qián),孫,李,周為生物組成員.解

數(shù) 計(jì) 生 數(shù) 計(jì) 生

趙 錢(qián) 孫 李 周 趙 錢(qián) 孫 李 周

(1(數(shù) 計(jì) 生

趙 錢(qián) 孫 李 周

(3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖:

(a(b(c)

(c)中存在哈密頓通路

例3 證明右圖不是哈密頓圖

證

假設(shè)存在一條哈密頓回路, a,f,g是2度頂點(diǎn), 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點(diǎn)c出現(xiàn)3次, 矛盾.a b c f d

e

g

此外, 該圖滿(mǎn)足定理6.10的條件, 這表明此條件是必要、而不充分的.又, 該圖有哈密頓通路.例4 有7個(gè)人, A會(huì)講英語(yǔ), B會(huì)講英語(yǔ)和漢語(yǔ), C會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ), D會(huì)講日語(yǔ)和漢語(yǔ), E會(huì)講德語(yǔ)和意大利語(yǔ), F會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ), G會(huì)講法語(yǔ)和德語(yǔ).問(wèn)能否將他們沿圓桌安排就坐成一圈, 使得每個(gè)人都能與兩旁的人交談? 解

作無(wú)向圖, 每人是一個(gè)頂點(diǎn), 2人之間有邊?他們有共同的語(yǔ)言.G F E D

A B C

ACEGFDBA是一條哈密頓回路,按此順序就坐即可.

第四篇：離散數(shù)學(xué)自學(xué)

學(xué)習(xí)體會(huì)

專(zhuān)業(yè)：計(jì)算機(jī) 姓名：范文芳 學(xué)號(hào)： 成績(jī)： 院校：

離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的基礎(chǔ)核心課程。通過(guò)本課程的學(xué)習(xí)，使學(xué)生具有現(xiàn)代數(shù)學(xué)的觀點(diǎn)和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法。同時(shí)，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開(kāi)拓專(zhuān)業(yè)理論的素質(zhì)和使用所學(xué)知識(shí)，分析和解決實(shí)際問(wèn)題的能力，為學(xué)生以后學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)理論與專(zhuān)業(yè)課程打下良好的基礎(chǔ)。

學(xué)習(xí)離散數(shù)學(xué)有兩項(xiàng)最基本的任務(wù)：其一是通過(guò)學(xué)習(xí)離散數(shù)學(xué)，使學(xué)生了解和掌握在后續(xù)課程中要直接用到的一些數(shù)學(xué)概念和基本原理，掌握計(jì)算機(jī)中常用的科學(xué)論證方法，為后續(xù)課程的學(xué)習(xí)奠定一個(gè)良好的數(shù)學(xué)基礎(chǔ)；其二是在離散數(shù)學(xué)的學(xué)習(xí)過(guò)程中，培訓(xùn)自學(xué)能力、抽象思維能力和邏輯推理能力，以提高專(zhuān)業(yè)理論水平。因此學(xué)習(xí)離散數(shù)學(xué)對(duì)于計(jì)算機(jī)、通信等專(zhuān)業(yè)后續(xù)課程的學(xué)習(xí)和今后從事計(jì)算機(jī)科學(xué)等工作是至關(guān)重要的。但是由于離散數(shù)學(xué)的離散性、知識(shí)的分散性和處理問(wèn)題的特殊性，使部分學(xué)生在剛剛接觸離散數(shù)學(xué)時(shí)，對(duì)其中的一些概念和處理問(wèn)題的方法往往感到困惑，特別是在做證明題時(shí)感到無(wú)從下手，找不到正確的解題思路。因此，對(duì)離散數(shù)學(xué)的學(xué)習(xí)方法給予適當(dāng)?shù)闹笇?dǎo)和對(duì)學(xué)習(xí)過(guò)程中遇到的一些問(wèn)題分析是十分必要的。

一、認(rèn)知離散數(shù)學(xué)

離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程之一，是計(jì)算機(jī)及應(yīng)用、通信等專(zhuān)業(yè)的一門(mén)重要的基礎(chǔ)課。它以研究量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素，充分體現(xiàn)了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。學(xué)習(xí)離散數(shù)學(xué)的目的是為學(xué)習(xí)計(jì)算機(jī)、通信等專(zhuān)業(yè)各后續(xù)課程做好必要的知識(shí)準(zhǔn)備，進(jìn)一步提高抽象思維和邏輯推理的能力，為計(jì)算機(jī)的應(yīng)用提供必要的描述工具和理論

基礎(chǔ)。

1．定義和定理多

離散數(shù)學(xué)是建立在大量定義、定理之上的邏輯推理學(xué)科，因此對(duì)概念的理解是學(xué)習(xí)這門(mén)課程的核心。在學(xué)習(xí)這些概念的基礎(chǔ)上，要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的實(shí)體則是大量的定理和性質(zhì)。在考試中有一部分內(nèi)容是考查學(xué)生對(duì)定義和定理的識(shí)記、理解和運(yùn)用，因此要真正理解離散數(shù)學(xué)中所給出的每個(gè)基本概念的真正的含義。比如，命題的定義、五個(gè)基本聯(lián)結(jié)詞、公式的主析取范式和主合取范式、三個(gè)推理規(guī)則以及反證法；集合的五種運(yùn)算的定義；關(guān)系的定義和關(guān)系的四個(gè)性質(zhì)；函數(shù)（映射）和幾種特殊函數(shù)（映射）的定義；圖、完全圖、簡(jiǎn)單圖、子圖、補(bǔ)圖的定義；圖中簡(jiǎn)單路、基本路的定義以及兩個(gè)圖同構(gòu)的定義；樹(shù)與最小生成樹(shù)的定義。掌握和理解這些概念對(duì)于學(xué)好離散數(shù)學(xué)是至關(guān)重要的。2.方法性強(qiáng)

在離散數(shù)學(xué)的學(xué)習(xí)過(guò)程中，一定要注重和掌握離散數(shù)學(xué)處理問(wèn)題的方法，在做題時(shí)，找到一個(gè)合適的解題思路和方法是極為重要的。如果知道了一道題用怎樣的方法去做或證明，就能很容易地做或證出來(lái)。反之，則事倍功半。在離散數(shù)學(xué)中，雖然各種各樣的題種類(lèi)繁多，但每類(lèi)題的解法均有規(guī)律可循。所以在聽(tīng)課和平時(shí)的復(fù)習(xí)中，要善于總結(jié)和歸納具有規(guī)律性的內(nèi)容。在平時(shí)的講課和復(fù)習(xí)中，老師會(huì)總結(jié)各類(lèi)解題思路和方法。作為學(xué)生，首先應(yīng)該熟悉并且會(huì)用這些方法，同時(shí)，還要勤于思考，對(duì)于一道題，進(jìn)可能地多探討幾種解法。3.抽象性強(qiáng)

離散數(shù)學(xué)的特點(diǎn)是知識(shí)點(diǎn)集中，對(duì)抽象思維能力的要求較高。由于這些定義的抽象性，使初學(xué)者往往不能在腦海中直接建立起它們與現(xiàn)實(shí)世界中客觀事物的聯(lián)系。不管是哪本離散數(shù)學(xué)教材，都會(huì)在每一章中首先列出若干個(gè)定義和定理，接著就是這些定義和定理的直接應(yīng)用，如果沒(méi)有較好的抽象思維能力，學(xué)習(xí)離散數(shù)學(xué)確實(shí)具有一定的困難。因此，在離散數(shù)學(xué)的學(xué)習(xí)中，要注重抽象思維能力、邏輯推理能力的培養(yǎng)和訓(xùn)練，這種能力的培養(yǎng)對(duì)今后從事各種工作都是極其重要的。

在學(xué)習(xí)離散數(shù)學(xué)中所遇到的這些困難，可以通過(guò)多學(xué)、多看、認(rèn)真分析講課

中所給出的典型例題的解題過(guò)程，再加上多練，從而逐步得到解決。在此特別強(qiáng)調(diào)一點(diǎn)：深入地理解和掌握離散數(shù)學(xué)的基本概念、基本定理和結(jié)論，是學(xué)好離散數(shù)學(xué)的重要前提之一。所以，同學(xué)們要準(zhǔn)確、全面、完整地記憶和理解所有這些基本定義和定理。4.內(nèi)在聯(lián)系性

離散數(shù)學(xué)的三大體系雖然來(lái)自于不同的學(xué)科，但是這三大體系前后貫通，形成一個(gè)有機(jī)的整體。通過(guò)認(rèn)真的分析可尋找出三大部分之間知識(shí)的內(nèi)在聯(lián)系性和規(guī)律性。如：集合論、函數(shù)、關(guān)系和圖論，其解題思路和證明方法均有相同或相似之處。

二、認(rèn)知解題規(guī)范

一般來(lái)說(shuō)，離散數(shù)學(xué)的考試要求分為：了解、理解和掌握。了解是能正確判別有關(guān)概念和方法；理解是能正確表達(dá)有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。為了考核學(xué)生對(duì)這三部分的理解和掌握的程度，試題類(lèi)型一般可分為：判斷題、填空題、選擇題、計(jì)算題和證明題。判斷題、填空題、選擇題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡(jiǎn)單計(jì)算；計(jì)算題主要考核學(xué)生的基本運(yùn)用技能和速度，要求寫(xiě)出完整的計(jì)算過(guò)程和步驟；證明題主要考查應(yīng)用概念、性質(zhì)、定理及重要結(jié)論進(jìn)行邏輯推理的能力，要求寫(xiě)出嚴(yán)格的推理和論證過(guò)程。

學(xué)習(xí)離散數(shù)學(xué)的最大困難是它的抽象性和邏輯推理的嚴(yán)密性。在離散數(shù)學(xué)中，假設(shè)讓你解一道題或證明一個(gè)命題，你應(yīng)首先讀懂題意，然后尋找解題或證明的思路和方法，當(dāng)你相信已找到了解題或證明的思路和方法，你必須把它嚴(yán)格地寫(xiě)出來(lái)。一個(gè)寫(xiě)得很好的解題過(guò)程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經(jīng)過(guò)簡(jiǎn)單的推理而得到的。仔細(xì)地寫(xiě)解題過(guò)程或證明是很重要的，既能讓讀者理解它，又能保證解題過(guò)程或證明準(zhǔn)確無(wú)誤。一個(gè)好的解題過(guò)程或證明應(yīng)該是條理清楚、論據(jù)充分、表述簡(jiǎn)潔的。針對(duì)這一要求，在講課中老師會(huì)提供大量的典型例題供同學(xué)們參考和學(xué)習(xí)。

通過(guò)離散數(shù)學(xué)的學(xué)習(xí)和訓(xùn)練，能使同學(xué)們學(xué)會(huì)在離散數(shù)學(xué)中處理問(wèn)題的一般性的規(guī)律和方法，一旦掌握了離散數(shù)學(xué)中這種處理問(wèn)題的思想方法，學(xué)習(xí)和掌握離散數(shù)學(xué)的知識(shí)就不再是一件難事了。復(fù)習(xí)離散數(shù)學(xué)的整個(gè)過(guò)程可大致分為三個(gè)

階段。

第一階段，大量進(jìn)行知識(shí)儲(chǔ)備的階段。

離散數(shù)學(xué)是建立在大量定義上面的邏輯推理學(xué)科。因而對(duì)概念的理解是我們學(xué)習(xí)這門(mén)學(xué)科的核心。由于這些定義非常抽象，初學(xué)者往往不能在腦海中建立起它們與現(xiàn)實(shí)世界中客觀事物的聯(lián)系。對(duì)于跨專(zhuān)業(yè)自學(xué)的朋友來(lái)說(shuō)更是如此。這是離散數(shù)學(xué)學(xué)習(xí)中的第一個(gè)困難。因此，對(duì)于第一遍復(fù)習(xí)，我們提出一個(gè)最為重要的要求，即準(zhǔn)確、全面、完整地記憶所有的定義和定理。具體做法可以是：在進(jìn)行完一章的學(xué)習(xí)后，用專(zhuān)門(mén)的時(shí)間對(duì)該章包括的定義與定理實(shí)施強(qiáng)記，直到能夠全部正確地默寫(xiě)出來(lái)為止。無(wú)須強(qiáng)求一定要理解，記住并能準(zhǔn)確復(fù)述 各定義定理是此階段的最高要求。也不需做太多的題（甚至不做課后習(xí)題也是可以的，把例題看懂就行），重心要放在對(duì)定義和定理的記憶上。請(qǐng)牢記，這是為未來(lái)的向廣度和深度擴(kuò)張作必要的準(zhǔn)備。

這一過(guò)程視各人情況不同耗時(shí)約在一到兩個(gè)月內(nèi)。第二階段，深入學(xué)習(xí)，并大量做課后習(xí)題的階段。

這是最漫長(zhǎng)的一個(gè)階段，耗時(shí)也很難估計(jì)，一般來(lái)說(shuō)，若能熟練解出某一章75%以上的課后習(xí)題，可以考慮結(jié)束該章。

解離散數(shù)學(xué)的題，方法非常重要，如果拿到一道題，立即能夠看出它所屬的類(lèi)型及關(guān)聯(lián)的知識(shí)點(diǎn)，就不難選用正確的方法將其解決，反之則事倍功半。例如在命題邏輯部分，無(wú)非是這么幾種題目：將自然語(yǔ)言表述的命題符號(hào)化，等價(jià)命題的相互轉(zhuǎn)化（包括化為主合取范式與主析取范式），以給出的若干命題為前提進(jìn)行推理和證明。相應(yīng)的對(duì)策也馬上就可以提出來(lái)。以推理題為例，主要是利用P、T規(guī)則，加上蘊(yùn)涵和等價(jià)公式表，由給定的前提出發(fā)進(jìn)行推演，或根據(jù)題目特點(diǎn)采用真值表法、CP規(guī)則和反證法。由此可見(jiàn)，在平常復(fù)習(xí)中，要善于總結(jié)和歸納，仔細(xì)體會(huì)題目類(lèi)型和此類(lèi)題目的解題套路。如此多作練習(xí)，則即使遇到比較陌生的題也可以較快地領(lǐng)悟其本質(zhì)，從而輕松解出。

“熟讀唐詩(shī)三百首，不會(huì)做詩(shī)也會(huì)吟。”要是拿到一本習(xí)題集，從頭到尾做過(guò)，甚至背會(huì)的話(huà)。那么，在考場(chǎng)上就會(huì)發(fā)現(xiàn)絕大多數(shù)題見(jiàn)過(guò)或似曾相識(shí)。這時(shí)，要取得較好的成績(jī)也就不是太難的事情了。這一情況具有普遍性，對(duì)許多院校的考試都適用。

第三階段，進(jìn)行真題模擬訓(xùn)練，提高整體水平和綜合能力的階段。

這一階段從第二階段結(jié)束一直持續(xù)到考試。

除了我們使用的課本外，應(yīng)盡可能地弄到報(bào)考院校的專(zhuān)業(yè)課歷年試題。因?yàn)槊總€(gè)單位對(duì)該科目的側(cè)重點(diǎn)畢竟有不同，從歷年試題中可以獲取許多有用的信息。這些歷年試題此時(shí)就有了巨大的作用。

第五篇：離散數(shù)學(xué)第三章

第三章部分課后習(xí)題參考答案

14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：(2)前提：p?q,?(q?r),r 結(jié)論：?p(4)前提：q?p,q?s,s?t,t?r 結(jié)論：p?q

證明：（2）

①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊(yùn)含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p ⑤⑥拒取式

證明（4）：

①t?r 前提引入 ②t ①化簡(jiǎn)律 ③q?s 前提引入 ④s?t 前提引入

⑤q?t ③④等價(jià)三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡(jiǎn) ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取

15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：(1)前提：p?(q?r),s?p,q 結(jié)論：s?r 證明

①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：

(1)前提：p??q,?r?q,r??s 結(jié)論：?p 證明：

①p 結(jié)論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡(jiǎn)律 ⑥r(nóng)?￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r?﹁r ⑤⑦ 合取

由于最后一步r?﹁r 是矛盾式,所以推理正確.