第一篇：離散數(shù)學(xué)特色項(xiàng)目[模版]

離散數(shù)學(xué)特色項(xiàng)目

在2009年離散數(shù)學(xué)這門課成為中國(guó)計(jì)量學(xué)院校重點(diǎn)建設(shè)課程后,課程組的老師們積極進(jìn)行教學(xué)改革,在很多方面對(duì)課程進(jìn)行了完善,在原有的基礎(chǔ)上呈現(xiàn)出了本課程的一些特色.現(xiàn)總結(jié)如下:（１）在教師隊(duì)伍上 該課程組的四位教師近三年均參與過(guò)離散數(shù)學(xué)的教學(xué)，而且４位教師里有２位教師通過(guò)了教學(xué)“免檢”認(rèn)證，還有１位是中國(guó)計(jì)量學(xué)院“我最喜愛的教師”稱號(hào)獲得者。

（２）在上課方式上

首先,由以前的“板書式”轉(zhuǎn)變?yōu)椤岸嗝襟w與板書相結(jié)合”的方式.我們課程組的老師在確定上課內(nèi)容為數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論后，每個(gè)人承擔(dān)一部分的多媒體課件制作，這就有了現(xiàn)在再用的教學(xué)課件，多媒體課件使得老師們?cè)谕瓿山虒W(xué)基本內(nèi)容的同時(shí)，可以提供給學(xué)生更多的信息。在授課方式上，我們采取“合作”的方式，每位老師上自己比較擅長(zhǎng)、自己相關(guān)專業(yè)的部分，這樣可以使教學(xué)深入，使教學(xué)與相關(guān)專業(yè)的最新研究動(dòng)態(tài)聯(lián)系起來(lái)，從而激發(fā)學(xué)生的學(xué)習(xí)興趣，提高教學(xué)效果。

（３）在考核方式上 在課程建設(shè)以前，我們都采取平時(shí)占20﹪，考試占80﹪的考核方式。在具體操作時(shí)，本課程是由四部分組成的，內(nèi)容分散，所涉及的理論較多，學(xué)生普遍覺得考試較難。經(jīng)過(guò)課程組討論后，將考核方式進(jìn)行了改革，加大對(duì)平時(shí)的考核力度，降低考試難度。這體現(xiàn)在平時(shí)成績(jī)提高到占總成績(jī)的30﹪，其中10分用于課堂考核，10分用于作業(yè)考核，10分用于網(wǎng)絡(luò)平臺(tái)的參與。經(jīng)我們改革的這一年來(lái)看，學(xué)生能充分利用網(wǎng)絡(luò)平臺(tái)，包括提問(wèn)題，提建議，網(wǎng)絡(luò)平臺(tái)成為學(xué)生與老師交流的另一種渠道。

（４）在網(wǎng)絡(luò)平臺(tái)建設(shè)上 在平時(shí)成績(jī)考核上，本課程加大了對(duì)網(wǎng)絡(luò)平臺(tái)的利用要求。在兩年的使用過(guò)程中，我們發(fā)現(xiàn)了網(wǎng)絡(luò)平臺(tái)有很多優(yōu)點(diǎn)：課程組上傳的課堂錄像，學(xué)生隨時(shí)可以打開教師的教學(xué)錄像，對(duì)所學(xué)知識(shí)進(jìn)行復(fù)習(xí)；課程組上傳本課程的部分習(xí)題答案（教材后沒有付答案），便于學(xué)生鞏固所學(xué)知識(shí)；課程組組織教師輪流值班，與學(xué)生進(jìn)行網(wǎng)絡(luò)交流，及時(shí)解決學(xué)生疑問(wèn)；網(wǎng)絡(luò)平臺(tái)也提供了課程的一些相關(guān)信息，加深了學(xué)生對(duì)課程的理解。

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

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

一、（10分）

（1）證明(P?Q)∧(Q?R)?(P?R)（2）求(P∨Q)?R的主析取范式與主合取范式，并寫出其相應(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è)喜歡步行的人都不喜歡做汽車，每個(gè)人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。

解

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

?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是滿射。(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是滿射。

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)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。

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

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

經(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上滿足結(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分）用公式法判斷下列公式的類型：(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)為可滿足式。

（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))為可滿足式。

二、（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ì)稱的，則R*S也是對(duì)稱的。(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ì)稱的，但R*S＝{<1，3>，<3，2>}不是對(duì)稱的。

(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滿足什么條件時(shí)，存在單射，且有多少個(gè)不同的單射？(3)當(dāng)n、m滿足什么條件時(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是喜歡聽音樂的學(xué)生}.試描述下列各集合中學(xué)生的特征:

(A?D)? ~ C={ x | x是北京人或喜歡聽音樂,但不是數(shù)學(xué)系學(xué)生} ~ A?B={ x | x是外地走讀生}(A-B)? D={ x | x是北京住校生, 并且喜歡聽音樂} ~ D ? ~ B={ x | x是不喜歡聽音樂的住校生} 例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ì)開車嗎？

(5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請(qǐng)關(guān)上門！(8)我正在說(shuō)謊話.(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è)蘋果或一個(gè)梨.(5)王曉紅生于1975年或1976年.解

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

p∨q, 真值: 1(3)r∨s,真值: 0(4)記t:元元拿一個(gè)蘋果,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)樘炖洌孕⊥醮┯鸾q服.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 方法一

真值表法（見例2）

方法二

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

先用等值演算化簡(jiǎn)公式, 再觀察.例5 用等值演算法判斷下列公式的類型(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

（同一律）

非重言式的可滿足式.如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 用主析取范式判斷公式的類型:(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

非重言式的可滿足式 例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ó)考察, 需滿 足下述條件:(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)造推理的證明: 若明天是星期一或星期三, 我就有 課.若有課, 今天必需備課.我今天下午沒備課.所以, 明天 不是星期一和星期三.解 設(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)人類集合,(b)全總個(gè)體域.解:(a)(1)設(shè)F(x): x愛美，符號(hào)化為 ?x F(x)

(2)設(shè)G(x): x用左手寫字，符號(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)稱作特性謂詞

例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 判斷下列公式的類型:(1)?x(F(x)?G(x))取解釋I1, D1=R，:x是整數(shù)，:x是有理數(shù), 取解釋I2, D2=R，:x是整數(shù)，:x是自然數(shù), 非永真式的可滿足式(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},jdb3l39rxn9>,}, 則

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ì)稱、反對(duì)稱.R2 對(duì)稱，不反對(duì)稱.R3 反對(duì)稱，不對(duì)稱.R4 不對(duì)稱、也不反對(duì)稱 例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ì)稱.證

任取

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

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

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

任取

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

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

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

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

任取，

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

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

(1)不自反也不反自反；對(duì)稱, 不反對(duì)稱；不傳遞.(2)反自反, 不是自反；反對(duì)稱, 不是對(duì)稱；傳遞.(3)自反，不是反自反；反對(duì)稱，不是對(duì)稱；不傳遞.例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},jdb3l39rxn9}，? 2={{a, b},{c},jdb3l39rxn9}  ? 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ù)劃分寫出

對(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；沒有最小元與最大元.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ù)是否為單射, 滿射, 雙射的, 為什么?（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.既不是單射也不是滿射的.(2)f : Z+→R, f(x)=lnx

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

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

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

有極小值f(1)=2.該函數(shù)既不是單射的也不是滿射的.例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 畫出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 畫出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

不滿足定理6.15的條件

例

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

與K5同胚也可收縮到K5 例6 畫出所有非同構(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ī)組和生物組.有趙,錢,孫,李,周5名學(xué)生, 問(wèn)分別在下述3種情況下, 能否選出3人各任一個(gè)組的組長(zhǎng)?(1)趙, 錢為數(shù)學(xué)組成員, 趙,孫,李為計(jì)算機(jī)組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學(xué)組成員, 錢,孫,李為計(jì)算機(jī)組成員, 錢,孫,李,周為生物組成員.(3)趙為數(shù)學(xué)組和計(jì)算機(jī)組成員, 錢,孫,李,周為生物組成員.解

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

趙 錢 孫 李 周 趙 錢 孫 李 周

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

趙 錢 孫 李 周

(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

此外, 該圖滿足定理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是一條哈密頓回路,按此順序就坐即可.

第四篇：特色項(xiàng)目

特色項(xiàng)目——學(xué)生創(chuàng)業(yè)教育PPT匯報(bào)

陳 述 材 料

尊敬的各位評(píng)委、各位專家：

大家上午好，今天我匯報(bào)的是我校國(guó)家示范建設(shè)項(xiàng)目中的特色項(xiàng)目——學(xué)生創(chuàng)業(yè)教育。

下面我從八個(gè)方面匯報(bào)我們學(xué)校為什么要進(jìn)行特色項(xiàng)目建設(shè)？怎樣進(jìn)行特色項(xiàng)目建設(shè)？特色項(xiàng)目建設(shè)取得了那些可喜的成績(jī)？特色項(xiàng)目對(duì)其他工作有哪些帶動(dòng)引領(lǐng)作用？歸納為12345678（展示ｐ２），即1個(gè)戰(zhàn)略思想，2個(gè)促進(jìn)作用，3個(gè)基本原則，4個(gè)培養(yǎng)目標(biāo)，5個(gè)重點(diǎn)突破，6個(gè)實(shí)施步驟，7個(gè)貢獻(xiàn)示范，8個(gè)帶動(dòng)引領(lǐng)作用。

特色項(xiàng)目建設(shè)的一個(gè)戰(zhàn)略思想（展示ｐ3）：全面提高師生的創(chuàng)新能力，為建設(shè)創(chuàng)新型國(guó)家作出新的貢獻(xiàn)。這是國(guó)際形勢(shì)所趨，現(xiàn)在全球都在搞改革創(chuàng)新，誰(shuí)處于挺先地位，誰(shuí)就能贏得至高點(diǎn)。我們中國(guó)也不例外，國(guó)家領(lǐng)導(dǎo)人胡錦濤、習(xí)近平分別在黨的十七大、十八大報(bào)告中指出“提高自主創(chuàng)新能力，建設(shè)創(chuàng)新型國(guó)家，是國(guó)家發(fā)展戰(zhàn)略的核心，是提高綜合國(guó)力的關(guān)鍵。”國(guó)家興亡，匹夫有責(zé)；國(guó)家使命，每一個(gè)公民應(yīng)強(qiáng)力執(zhí)行！我們學(xué)校積極響應(yīng)國(guó)家號(hào)召，在中職招生生源萎縮，就業(yè)持續(xù)低迷的情況下，搶抓機(jī)遇，提出了我校新的戰(zhàn)略發(fā)展要求，抓質(zhì)量、創(chuàng)特色、促發(fā)展，對(duì)學(xué)生進(jìn)行特色創(chuàng)業(yè)教育，以提高學(xué)生的就業(yè)競(jìng)爭(zhēng)力。

特色項(xiàng)目建設(shè)的二個(gè)促進(jìn)作用。（展示ｐ4）：一是促進(jìn)學(xué)校人才培養(yǎng)模式改革；二是促進(jìn)學(xué)校就業(yè)模式改革。改革的核心：建設(shè)新專業(yè)，改造舊專業(yè)，從事新職業(yè)，服務(wù)新行業(yè)。人才培養(yǎng)模式改革：專業(yè)圍繞市場(chǎng)轉(zhuǎn)，教學(xué)圍繞企業(yè)轉(zhuǎn)，學(xué)生圍繞崗位轉(zhuǎn)；培養(yǎng)對(duì)接需求，專業(yè)對(duì)接市場(chǎng)，教學(xué)對(duì)接企業(yè)，學(xué)生對(duì)接崗位。（展示ｐ5）就業(yè)模式改革：建立“一點(diǎn)多線，以點(diǎn)帶面”的就業(yè)網(wǎng)絡(luò)：即以武漢為立足點(diǎn)，輻射珠三角、長(zhǎng)三角、渤海灣、海西地區(qū)多條線；各專業(yè)以中心企業(yè)為依托，輻射周邊企業(yè)，形成就業(yè)面。二年改革成效顯著，就在2013年史上稱為最難的就業(yè)年，我們學(xué)校的就業(yè)率也達(dá)到了95%以上，引起了省市領(lǐng)導(dǎo)專家的關(guān)注，他們紛紛來(lái)校調(diào)研，向其他單位推廣經(jīng)驗(yàn)。

特色項(xiàng)目建設(shè)的三個(gè)原則。（展示ｐ6）：以服務(wù)為宗旨，以就業(yè)為導(dǎo)向，以創(chuàng)業(yè)帶動(dòng)積極就業(yè)。全心全意為人民服務(wù)是我黨的根本宗旨，創(chuàng)業(yè)帶動(dòng)積極就業(yè)是創(chuàng)業(yè)教育的目的。我們始終把握住這三個(gè)原則，通過(guò)二年創(chuàng)業(yè)教育特色項(xiàng)目建設(shè)（展示ｐ7），我們服務(wù)學(xué)生達(dá)到4602人，服務(wù)教師301人，服務(wù)企業(yè)達(dá)到50家，自主創(chuàng)業(yè)學(xué)生達(dá)到125人。

特色項(xiàng)目建設(shè)的四個(gè)培養(yǎng)目標(biāo)。（展示ｐ8）即：培養(yǎng)學(xué)生的創(chuàng)業(yè)意識(shí)、創(chuàng)新精神、創(chuàng)業(yè)能力、就業(yè)能力。創(chuàng)業(yè)意識(shí)是基礎(chǔ)，創(chuàng)新精神是發(fā)展，創(chuàng)業(yè)能力是提升，就業(yè)能力是目的。通過(guò)二年建設(shè)，2014年6月對(duì)全校4602名學(xué)生統(tǒng)計(jì)，95%的學(xué)生有創(chuàng)業(yè)意識(shí)，50%的學(xué)生具有創(chuàng)新精神，5%的學(xué)生有自主創(chuàng)業(yè)能力，就業(yè)能力達(dá)到95%以上。

特色項(xiàng)目建設(shè)的五個(gè)突破。為了達(dá)到以上目標(biāo)，我們特色創(chuàng)業(yè)教育主要從以下5個(gè)方面突破（展示ｐ9）：保障機(jī)制；師資隊(duì)伍；課程體系；創(chuàng)業(yè)基地；創(chuàng)業(yè)服務(wù)。（展示ｐ10）為了保障創(chuàng)業(yè)教育的順利實(shí)施，我們制訂了12個(gè)綱領(lǐng)性文件，修訂或制訂了41個(gè)規(guī)章制度，建立了學(xué)校創(chuàng)業(yè)教育管理網(wǎng)絡(luò)；聘請(qǐng)了章方良等12位企業(yè)老板或創(chuàng)業(yè)資深專家作為兼職教師，加上我們學(xué)校精選的14位有創(chuàng)業(yè)經(jīng)驗(yàn)的教師，組成了一支26人的創(chuàng)業(yè)師資團(tuán)隊(duì)；開發(fā)了2本校本教材，形成了以公共選修課、活動(dòng)課為主，以文化課、專業(yè)選修課為輔的廣覆蓋、文體化的課程教材體系；興建或改建了7個(gè)校內(nèi)外創(chuàng)業(yè)基地，為學(xué)生創(chuàng)業(yè)搭建了服務(wù)平臺(tái)；通過(guò)各種活動(dòng)載體，如立業(yè)創(chuàng)業(yè)報(bào)告會(huì)、就業(yè)指導(dǎo)、職生生涯設(shè)計(jì)大賽、才藝節(jié)等形式多樣的活動(dòng)，引領(lǐng)學(xué)生樹立創(chuàng)業(yè)意識(shí)，發(fā)揚(yáng)創(chuàng)業(yè)精神，提升創(chuàng)業(yè)能力，二年來(lái)，師生在各級(jí)大賽中取得了驕人的佳績(jī)，業(yè)績(jī)輝煌！

特色項(xiàng)目建設(shè)的六個(gè)實(shí)施步驟（展示ｐ11）：構(gòu)建創(chuàng)業(yè)教育模式，優(yōu)化整合創(chuàng)業(yè)資源，健全創(chuàng)業(yè)管理網(wǎng)絡(luò)，完善創(chuàng)業(yè)保障機(jī)制，開展創(chuàng)業(yè)實(shí)踐活動(dòng)，扶持創(chuàng)業(yè)成果轉(zhuǎn)化。

特色項(xiàng)目建設(shè)的七個(gè)貢獻(xiàn)示范（展示ｐ12）：創(chuàng)業(yè)教育覆蓋了全校12個(gè)專業(yè)，實(shí)現(xiàn)了全覆蓋；受益學(xué)生人數(shù)達(dá)到4602人，實(shí)現(xiàn)了全參與；參與教職工達(dá)到301人，實(shí)現(xiàn)了全投入；參與企業(yè)達(dá)50個(gè)，實(shí)現(xiàn)了總?cè)蝿?wù)；打造了一支由26人組成的專兼結(jié)合的優(yōu)秀創(chuàng)業(yè)師資團(tuán)隊(duì)，保證了創(chuàng)業(yè)教育質(zhì)量；興建或改建了7個(gè)創(chuàng)業(yè)基地，保障了創(chuàng)業(yè)教育的實(shí)效性；師生多次勇摘省市大賽桂冠，發(fā)表創(chuàng)業(yè)教育論文50余篇，吸引企業(yè)投資學(xué)校或本地達(dá)到5家以上，省市領(lǐng)導(dǎo)專家、有關(guān)兄弟學(xué)校多次實(shí)地考察指導(dǎo)，輻射引領(lǐng)作用強(qiáng)勁。展示主要成果一覽表（展示ｐ13）。

特色項(xiàng)目建設(shè)的八個(gè)帶動(dòng)引領(lǐng)（展示ｐ14）：帶動(dòng)引領(lǐng)教育模式改革；帶動(dòng)引領(lǐng)管理模式改革；帶動(dòng)引領(lǐng)德育模式改革；帶動(dòng)引領(lǐng)師生評(píng)價(jià)模式改革；帶動(dòng)引領(lǐng)課堂教學(xué)模式改革；帶動(dòng)引領(lǐng)招生就業(yè)模式改革；帶動(dòng)引領(lǐng)人才培養(yǎng)模式改革；帶動(dòng)引領(lǐng)教師招聘模式改革。（展示ｐ15經(jīng)費(fèi)開支）

總之（ｐ15），通過(guò)二年的特色項(xiàng)目建設(shè)，學(xué)生創(chuàng)業(yè)教育在各級(jí)領(lǐng)導(dǎo)專家的關(guān)注和支持下，取得了一個(gè)又一個(gè)可喜的成績(jī)。但改革創(chuàng)新從來(lái)都不是一帆風(fēng)順的，現(xiàn)在有些人談職教色變，談創(chuàng)業(yè)教育變色，認(rèn)為學(xué)生的主要任務(wù)是讀書、讀書、還是讀書，至于立業(yè)創(chuàng)業(yè)是將來(lái)的事。正是因?yàn)槿绱耍覀儗W(xué)校學(xué)生創(chuàng)業(yè)教育敢為人先，開創(chuàng)了中職學(xué)校搞創(chuàng)業(yè)教育的先河，無(wú)論將來(lái)發(fā)展如何，我們將一如既往的探索，尋求成功的經(jīng)驗(yàn)，為職校學(xué)生謀求一個(gè)燦爛的明天！我的匯報(bào)到此結(jié)束，不當(dāng)之處，請(qǐng)各位評(píng)委專家批評(píng)指正，謝謝！

匯報(bào)單位:湖北省崇陽(yáng)職業(yè)技術(shù)學(xué)校

匯報(bào)人：陳 華 二0一四年七月十八日

第五篇：特色項(xiàng)目主題

特色項(xiàng)目主題

敲響幸福的鼓點(diǎn) 敲響幸福的人生鼓點(diǎn) 敲響生命的鼓點(diǎn)

敲響生命的每一個(gè)鼓點(diǎn) 敲響人生的每一個(gè)鼓點(diǎn) 敲響人生的鼓點(diǎn) 敲響歡快的人生鼓點(diǎn)