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

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

一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？(寫過程)1)P?(P∨Q∨R)2)?(P?Q)∧Q 3)(P?Q)∧?R 解：1)重言式；2)矛盾式；3)可滿足式

二、（10分）求命題公式(?P?Q)?(?Q∨P)的主析取范式，并求成真賦值。

解：(?P?Q)?(?Q∨P)?(P∨Q)?(?Q∨P)??(P∨Q)∨(?Q∨P)?(?P∧?Q)∨?Q∨P??Q∨P?((P∨?P)∧?Q)∨(P∧?Q)∨(P∧Q)?(?P∧?Q)∨(P∧?Q)∨(P∧?Q)∨(P∧Q)? m0∨m2∨m3 成真賦值為：00、10、11。

三、（10分）證明下列命題的等值關(guān)系：(P∨Q)∧?(P∧Q)??(P?Q）

證明：(P∨Q)∧?(P∧Q)?(P∨Q)∧(?P∨?Q)?(P∧?Q)∨(Q∧?P)??((?P∨Q)∧(?Q∨P))??((P?Q)∧(Q?P))??(P?Q）

四、（10分）敘述并證明蘇格拉底三段論

解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號(hào)化：F（x）：x是一個(gè)人。G（x）：x要死的。A：蘇格拉底。命題符號(hào)化為?x（F（x）?G（x）），F(xiàn)（a）?G（a）證明：

（1）?x(F(x)?G(x))P（2）F(a)?G(a)T(1)，US（3）F(a)P（4）G(a)T(2)(3)，I

五、（10分）已知A、B、C是三個(gè)集合，證明A∩(B∪C)=(A∩B)∪(A∩C)證明：∵x? A∩（B∪C）? x? A∧x?（B∪C）

? x? A∧（x?B∨x?C）

?（x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C ? x?（A∩B）∪（A∩C）

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

六、（10分）R為集合X上的二元關(guān)系，X={1，2，3，4，5，6，7}，R={<1，1>，<1，2>，<2，4>，<6，3>，<6，6>，<7，1>}，求:R的等價(jià)閉包R(即包含R的最小的等價(jià)關(guān)系)。

解：R={<1，1>，<2，2>，<3，3>，<4，4>，<5，5>，<6，6>，<7，7>，<1，2>，<2，1>，<2，4>，<4，2>，<6，3>，<3，6>，<7，1>，<1，7>，<1，4>，<4，1>，<2，7>，<7，2>，<7，4>，<4，7>}

七、（10分）設(shè)函數(shù)f：R×R?R×R，R為實(shí)數(shù)集，f定義為：f()=。1)證明f是雙射。

解：1）?，∈R×R，若f()=f()，即=，/ 4 *

*則x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2從而f是單射。

2）?

∈R×R，由f()=

，通過計(jì)算可得x=(p+q)/2；y=(p-q)/2；從而

的原象存在，f是滿射。

八、（10分）設(shè)G是一群，H是G的子群，x∈G，證明x●H●x={x●h●x| h∈H }是G的子群。

解：由H非空，知x●H●X非空。

?a，b∈x●H●x，即存在h1，h2∈H，使得a=x●h1●x，b=x●h2●x，有a●b=(x●h1●x)●(x●h2●x)=x●h1●x-1●-

1-1

-1-1-1

-1（X）-1-1-1-1-1●2●hx=x●(h1●h2)●x因H為G的子群，有h1●h2=h3∈H從而a●b= x●h3●x∈x●H●x。所

-1-1-1-1-1-1以x●H●x為子群。

九、（10分）若G是連通平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系： m?l(n?2)l?2證明：設(shè)G有r個(gè)面，則2m=?d(fi)?lr，2m≥lr。

i?1r由歐拉公式得，n-m+r=2，r=2-n+m。于是

m? l(n?2)l?

2十、（10分）求葉的權(quán)分別為7、8、9、12、16的最優(yōu)二叉樹及其權(quán)。

解：最優(yōu)二叉樹如圖所示：

樹的權(quán)為(9+12+16)×2+(7+8)×3=119/ 4

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

一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？(寫過程)1)P?(P∨Q∨R)2)?((Q?P)∨?P)∧(P∨R)3)((?P∨Q)?R)?((P∧Q)∨R)解：1)重言式；2)矛盾式；3)可滿足式

二、（10分）求命題公式（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)∨(?P∧?R)∨(P∨Q)∨R ?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R ?1∨((?P∧?R)∨R)?1 ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 該式為重言式，全部賦值都是成真賦值。

三、（10分）證明((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(A∧(P?Q))?C 證明：((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(?(P∧Q∧A)∨C)∧(?A∨(P∨Q∨C))?((?P∨?Q∨?A)∨C)∧((?A∨P∨Q)∨C)?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((?P∨?Q∨?A)∧(?A∨P∨Q))?C ?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))?C ?((P∧Q∧A)∨(A∧?P∧?Q))?C ?(A∧((P∧Q)∨(?P∧?Q)))?C ?(A∧((P∨?Q)∧(?P∨Q)))?C ?(A∧((Q?P)∧(P?Q)))?C ?(A∧(P?Q))?C

四、（10分）個(gè)體域?yàn)閧1，2}，求?x?y（x+y=4）的真值。

解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））

?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））?（0∨0）∧（0∨1）?0∧1?0

五、（10分）對(duì)于任意集合A，B，試證明：P(A)∩P(B)=P(A∩B)解：?x?P(A)∩P(B)，x?P(A)且x?P(B)，有x?A且x?B，從而x?A∩B，x?P(A∩B)，由于上述過程可逆，故P(A)∩P(B)=P(A∩B)/ 4

六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}

七、（10分）設(shè)函數(shù)f：R×R?R×R，R為實(shí)數(shù)集，f定義為：f()=。1)證明f是雙射。

解：1）?，∈R×R，若f()=f()，即=，則x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2從而f是單射。

2）?

∈R×R，由f()=

，通過計(jì)算可得x=(p+q)/2；y=(p-q)/2；從而

的原象存在，f是滿射。

八、（10分）是個(gè)群，u∈G，定義G中的運(yùn)算“?”為a?b=a*u*b，對(duì)任意a，b∈G，求證：也是個(gè)群。

證明：1）?a，b∈G，a?b=a*u*b∈G，運(yùn)算是封閉的。

2）?a，b，c∈G，（a?b）?c=（a*u*b）*u*c=a*u*（b*u*c）=a?（b?c），運(yùn)算是可結(jié)合的。3）?a∈G，設(shè)E為?的單位元，則a?E=a*u*E=a，得E=u，存在單位元u。

4）?a∈G，a?x=a*u*x=E，x=u*a*u，則x?a=u*a*u*u*a=u=E，每個(gè)元素都有逆元。所以也是個(gè)群。

九、（10分）已知：D=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的鄰接距陣A和可達(dá)距陣P。

解：1）D的鄰接距陣A和可達(dá)距陣P如下：

A= 0 0 0 0 1 1 0 0 0 0

0 1 0 0 0 0 1 0 0

0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1-

1-1

P= 1

十、（10分）求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹及其權(quán)。

解：最優(yōu)二叉樹為

權(quán)＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148 / 4

第二篇：題目3（推薦）

題目

21世紀(jì)是一個(gè)信息的時(shí)代,當(dāng)前,我國信息化建設(shè)已經(jīng)進(jìn)入了全方位、多層次推進(jìn)的新階段,面臨著新形勢(shì)、新任務(wù)、新挑戰(zhàn),公安工作信息化建設(shè)也取得了顯著實(shí)效。2009年3月17日到4月20日,筆者隨山西省公安廳科技強(qiáng)警示范建設(shè)督導(dǎo)組到全省二十多個(gè)科技強(qiáng)警示范縣(市、區(qū))進(jìn)行了督導(dǎo)檢查,對(duì)山西省公安信息化建設(shè)情況作了專題調(diào)研和分析,以期推動(dòng)山西省公安信息化建設(shè)進(jìn)一步發(fā)展,提高公安機(jī)關(guān)駕馭社會(huì)治安和維護(hù)社會(huì)穩(wěn)定的能力。

一、山西省公安信息化建設(shè)基本情況公安信息化就是將現(xiàn)代信息技術(shù)引入公安業(yè)務(wù)領(lǐng)域,有效開發(fā)利用公安業(yè)務(wù)信息資源,建設(shè)先進(jìn)的信息基礎(chǔ)設(shè)施,發(fā)展信息技術(shù)和產(chǎn)業(yè),不斷提高打擊犯罪和維護(hù)社會(huì)治安的綜合實(shí)力,使信息科技含量在公安工作中的比重逐步上升的過程。完整的信息化內(nèi)涵包括四部分內(nèi)容,即信息網(wǎng)絡(luò)體系、信息產(chǎn)業(yè)基礎(chǔ)、社會(huì)支持環(huán)境和效用積累過程。信息網(wǎng)絡(luò)體系是大量信息資源、各種專用信息系統(tǒng)及其公用通信網(wǎng)絡(luò)和信息平臺(tái)的總稱;信息產(chǎn)業(yè)基礎(chǔ)即信息科學(xué)技術(shù)的研究、軟件開發(fā)與利用,各類信息系統(tǒng)的集成及信息服務(wù);社會(huì)支持環(huán)境指相關(guān)的管理體制、政策法律、規(guī)章制度等;效用積累過程指公安信息化發(fā)揮出應(yīng)有的效力“金盾工程”一期建設(shè)已近尾聲,公安信息化建設(shè)取得了巨大的進(jìn)展。從浙江情況看,“金盾工程”一期建設(shè)解決了幾個(gè)重要問題:一是形成了良好的公安信息網(wǎng)絡(luò)基礎(chǔ);二是建設(shè)了以部、省、市三級(jí)公安信息中心為核心的公安信息化技術(shù)體系;三是基本實(shí)現(xiàn)了主要公安業(yè)務(wù)的信息化;四是初步構(gòu)建了以八大信息資源庫和應(yīng)用支撐平臺(tái)為基礎(chǔ)的信息共享平臺(tái);五是培養(yǎng)了一批公安信息化技術(shù)和應(yīng)用人才以及一個(gè)相當(dāng)大的信息化應(yīng)用群體;六是全警信息化作戰(zhàn)的意識(shí)得到了培育和加強(qiáng),初步形成了信息化工作機(jī)制;七是公安信息化運(yùn)行維護(hù)保障機(jī)制初步建立。這些成就的取得,極大地提升了各級(jí)公安機(jī)關(guān)履行職責(zé)的能力,也為今后公安事業(yè)的發(fā)展奠定了重要基礎(chǔ)。但就公安信息通信部門而言,仍要再接再厲,進(jìn)一步推進(jìn)公安信息化建設(shè)。

一、認(rèn)真消化、吸收“金盾工程”一期建設(shè)的成果“金盾工程”一期建設(shè)對(duì)于公安信息化來講,無疑是一頓“大餐”。以浙江公安信息化建設(shè)為例,2003年至2005年三年間,全省投入公安信息化建設(shè)的資金高達(dá)10億元,從網(wǎng)絡(luò)、省市兩級(jí)公安信息中心的技術(shù)體系,到各“條”“塊”的業(yè)務(wù)信息化建設(shè),都可說是突飛猛進(jìn),把公安信息化推向了一個(gè)新的高度,對(duì)公安工作的理念，公安信息應(yīng)用即現(xiàn)代信息技術(shù)在現(xiàn)代警務(wù)工作領(lǐng)域的應(yīng)用,是指在統(tǒng)一的規(guī)劃與組織下,在公安警務(wù)工作中較全面地運(yùn)用以計(jì)算機(jī)、多媒體和網(wǎng)絡(luò)通訊為基礎(chǔ)的現(xiàn)代信息技術(shù),深入開發(fā)、廣泛利用信息資源,促進(jìn)現(xiàn)代警務(wù)機(jī)制改革,提高公安機(jī)關(guān)打擊、防范、管理、決策的效率與水平,從而實(shí)現(xiàn)全警協(xié)作的現(xiàn)代警務(wù)工作模式。它包括三層含義:一是應(yīng)用信息技術(shù);二是開發(fā)利用警務(wù)信息資源;三是有效履行警務(wù)職能。近年來,隨著電子技術(shù)的不斷發(fā)展和計(jì)算機(jī)網(wǎng)絡(luò)的廣泛應(yīng)用,警務(wù)信息化正逐步影響和改變著公安工作的傳統(tǒng)思維模式和工作方式,信息化在服務(wù)實(shí)戰(zhàn)、加強(qiáng)管理等方面發(fā)揮了巨大的“網(wǎng)絡(luò)效應(yīng)”,一種全新的警務(wù)模式正在逐步建立。目前,溫州各級(jí)公安機(jī)關(guān)、各警種、各部門的信息應(yīng)用十分活躍,根據(jù)業(yè)務(wù)應(yīng)用的實(shí)際需要,建立了大量的應(yīng)用系統(tǒng),并在實(shí)際工作中發(fā)揮了重要作用,積累了大量的基礎(chǔ)數(shù)據(jù),為提升和強(qiáng)化信息應(yīng)用提供了可能。

一、溫州公安信息應(yīng)用的總體趨勢(shì)溫州公安信息資源的應(yīng)用已經(jīng)涵蓋了采集、存儲(chǔ)、整合、關(guān)聯(lián)、二次開發(fā)、增值應(yīng)用等業(yè)務(wù)環(huán)節(jié)。目前,公安機(jī)關(guān)內(nèi)外網(wǎng)的信息資源共享、交互工作正在逐步實(shí)施,公安行業(yè)的信息資源開發(fā)已經(jīng)進(jìn)入了一個(gè)嶄新的、更具實(shí)際應(yīng)用價(jià)值的(我國除了公安部直屬院校外,各省(自治區(qū))和直轄市都有公安院校。這些公安院校擔(dān)負(fù)著為各地培養(yǎng)公安人才、培訓(xùn)在職民警的重任。公安院校是公安教育的主陣地,肩負(fù)著培養(yǎng)政治素質(zhì)、執(zhí)法水平和實(shí)戰(zhàn)本領(lǐng)適應(yīng)公安戰(zhàn)線發(fā)展需要的公安隊(duì)伍的重要使命。因此,公安院校師資隊(duì)伍建設(shè)必須相對(duì)穩(wěn)定、高素質(zhì)和高標(biāo)準(zhǔn)[1]。為了達(dá)到此目的,公安院校教師必須通過公安實(shí)踐鍛煉提高師資隊(duì)伍的素質(zhì),使公安教育適應(yīng)社會(huì)形勢(shì)發(fā)展的要求。通過公安一線實(shí)踐鍛煉可以使教師熟悉公安工作的最新動(dòng)態(tài),強(qiáng)化教師的政治素質(zhì)和作風(fēng),提高警務(wù)業(yè)務(wù)素質(zhì)和實(shí)踐能力,同時(shí)公安院校教師參加業(yè)務(wù)實(shí)踐也可以幫助一線公安機(jī)關(guān)解決實(shí)際問題。公安院校的教學(xué)水平在各種公安理念的基礎(chǔ)上,也很大程度取決于教官隊(duì)伍的整體素質(zhì)[2]。因此,為了進(jìn)一步加強(qiáng)公安院校教師隊(duì)伍的建設(shè),克服目前公安院校教學(xué)工作中不同程度的理論和實(shí)踐脫軌現(xiàn)象,促進(jìn)公安教育更好的在與時(shí)俱進(jìn)的基礎(chǔ)上理論聯(lián)系實(shí)踐,促進(jìn)公安教育培訓(xùn)工作更好地符合公安一線工作,促進(jìn)地方公安業(yè)務(wù)理論和實(shí)踐能力的提升,開展公安院校教師參加業(yè)務(wù)實(shí)踐工作就更能體現(xiàn)其重要的理論價(jià)值和實(shí)踐價(jià)值。

一、以業(yè)務(wù)實(shí)踐為交流平臺(tái),幫助一線公安機(jī)關(guān)解決實(shí)際。情報(bào)信息主導(dǎo)警務(wù)是當(dāng)今國際、國內(nèi)警務(wù)發(fā)展的主流和趨勢(shì),是公安機(jī)關(guān)應(yīng)對(duì)日益嚴(yán)峻的社會(huì)治安形勢(shì)的需要,也是公安機(jī)關(guān)“三項(xiàng)重點(diǎn)工作”能否取得實(shí)效的關(guān)鍵。在新的歷史條件下,公安機(jī)關(guān)面臨的社會(huì)治安形勢(shì)更加復(fù)雜嚴(yán)峻,擔(dān)負(fù)的維護(hù)社會(huì)穩(wěn)定的任務(wù)十分繁重。如何更好地發(fā)揮“大情報(bào)、大信息”的作用,引領(lǐng)公安工作走向現(xiàn)代化、信息化、正規(guī)化,筆者嘗試通過對(duì)情報(bào)處理中應(yīng)把握的幾個(gè)重要環(huán)節(jié)的分析,探討加強(qiáng)情報(bào)信息工作的對(duì)策。

一、情報(bào)處理的循環(huán)流程情報(bào)處理流程由通過各種手段獲取大量情報(bào)素材開始。(一)情報(bào)來源情報(bào)來源是指獲取情報(bào)的渠道。情報(bào)來源于信息,有無海量的信息庫容量與內(nèi)容反映準(zhǔn)確、齊全的信息質(zhì)量,是決定情報(bào)信息主導(dǎo)警務(wù)能否發(fā)揮最大效益的基礎(chǔ)性因素。政治穩(wěn)定、經(jīng)濟(jì)安全和社會(huì)治安形勢(shì)的諸因素都要納入公安情報(bào)工作的視線,都屬于情報(bào)采集的范圍?？梢?公安機(jī)關(guān)獲取情報(bào)的渠道相當(dāng)廣泛,可以說涉及社會(huì)各個(gè)領(lǐng)域。因此,既要充分發(fā)揮公安機(jī)關(guān)點(diǎn)多面廣的優(yōu)勢(shì),不斷建立和完善內(nèi)部的情報(bào)網(wǎng)絡(luò),又要廣泛接觸社會(huì)各個(gè)方面。(二)情報(bào)采集情報(bào)采集是指通過各種渠道獲得涉及、影響社會(huì)政治穩(wěn)定、經(jīng)濟(jì)發(fā)展和人民群眾安居樂業(yè)的情報(bào)的活動(dòng)。信息化是提高公安政治工作實(shí)效的重要途徑和手段。隨著整個(gè)社會(huì)信息化的快速發(fā)展,特別是“金盾工程”二期建設(shè)的啟動(dòng),公安政治工作迎來創(chuàng)新發(fā)展的良好機(jī)遇,信息化在人事、教育、宣傳等方面有著廣泛的運(yùn)用,也讓各級(jí)政工干部和廣大民警感受到政治工作信息化建設(shè)產(chǎn)生的巨大成果。如何緊跟公安信息建設(shè)的大潮流,做好公安政治工作信息化建設(shè)是需要深入研究的一個(gè)重要課題。

一、公安政治工作信息化的涵義及基本特征(一)公安政治工作信息化的概念對(duì)公安政治工作信息化的概念可以從狹義和廣義兩個(gè)方面來理解。狹義的概念就是指為提高公安政治工作的效率,把信息技術(shù)運(yùn)用于公安政治工作的過程狀態(tài)。如公安政治工作網(wǎng)絡(luò)平臺(tái),即“四庫、三平臺(tái)”(人事訓(xùn)練業(yè)務(wù)信息庫、警員資源庫、民警職業(yè)健康信息庫、辦公信息庫等四個(gè)基礎(chǔ)信息庫和人事訓(xùn)練業(yè)務(wù)應(yīng)用平臺(tái)、民警身心健康管理平臺(tái)、辦公管理信息平臺(tái)等三個(gè)應(yīng)用平臺(tái))的應(yīng)用,給公安政治工作提供了工具型、運(yùn)用性幫助。從廣義上來說,公安政治工作信息化不僅僅局限于公安政治工作網(wǎng)絡(luò)平臺(tái)的建設(shè)和運(yùn)用,還包括公安政治工作信息化相關(guān)決策政策的制定和完善、基礎(chǔ)設(shè)備的保障、政工信息資源的采集、主體素質(zhì)的培養(yǎng)、相關(guān)管理機(jī)制的確立和 總之，伴隨著知識(shí)經(jīng)濟(jì)、全球一體化及企業(yè)的生存與發(fā)展，企業(yè)產(chǎn)業(yè)不斷拓展，進(jìn)一步提高信息化認(rèn)識(shí)，加快信息化建設(shè)步伐已成為必然，只要我們轉(zhuǎn)變觀念，提高對(duì)信息化建設(shè)的重視度，以管理信息化為主導(dǎo)（領(lǐng)導(dǎo)層），以實(shí)現(xiàn)企業(yè)信息化為基礎(chǔ)，以實(shí)現(xiàn)企業(yè)產(chǎn)品走向世界為目標(biāo)，一定會(huì)使企業(yè)有著燦爛的明天!

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

離散數(shù)學(xué)課件作業(yè)

第一部分 集合論

第一章集合的基本概念和運(yùn)算

1-1 設(shè)集合 A ={1，{2}，a，4，3}，下面命題為真是[ B ]

A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} ? A。

1-2 A,B,C 為任意集合，則他們的共同子集是[ D ]

A．C；B．A；C．B；D．?。

1-3 設(shè) S = {N，Z，Q，R}，判斷下列命題是否成立 ？

（1）N ? Q，Q ∈S，則 N ? S［不成立］

（2）-1 ∈Z，Z ∈S，則-1 ∈S［不成立］

1-4 設(shè)集合 A ={3，4}，B = {4，3} ∩ ?，C = {4，3} ∩{ ? }，D ={ 3，4，? }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F(xiàn) = { 4，?，3，3}，試問哪兩個(gè)集合之間可用等號(hào)表示 ？

答：A = E；B = C；D = F

1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

答：（1）A = { 0，1，2，3 }；

（2）A = { 1，2，3，4，……} = Z+；

第二章二元關(guān)系

2-1 給定 X =（3, 2，1），R 是 X 上的二元關(guān)系，其表達(dá)式如下：

R = {〈x，y〉x，y ∈X 且 x≤ y }

求：(1)domR =?;(2)ranR =?;(3)R 的性質(zhì)。

答：R = {<2，3>，<1,2>，<1,3>}；

DomR={R中所有有序?qū)Φ膞}={2,1,1}={2,1};

RanR={R中所有有序?qū)Φ膟}={3,2,3}={3,2}；

R 的性質(zhì):反自反,反對(duì)稱,傳遞性質(zhì).2-2 設(shè) R 是正整數(shù)集合上的關(guān)系，由方程 x + 3y = 12 決定，即

R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，試求：

（1）R 的列元表達(dá)式；（2）給出 dom（R。R）。

答：根據(jù)方程式有：y=4-x/3，x 只能取 3，6,9。

（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家認(rèn)真完成合成運(yùn)算 R。R={<3,3>}.然后,給出 R。R 的定義域,即

（2）dom（R。R）= {3}。

2-3 判斷下列映射 f 是否是 A 到 B 的函數(shù)；并對(duì)其中的 f：A→B 指出他的性質(zhì)，即

是否單射、滿射和雙射，并說明為什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R，f=x。

（4）A = B = N，f=x2。

（5）A = B = N，f = x + 1。

答：（1）是 A 到 B 的函數(shù)，是滿射而不是單射；

（2）是雙射；

（3）是雙射；

（4）是單射，而不是滿射；

（5）是單射而不是滿射。

2-4 設(shè) A ={1，2，3，4}，A 上的二元關(guān)系

R ={〈x，y〉︱（x-y）能被3整除}，則自然映射 g：A→A/R使 g(1)=[C]

A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。

2-5 設(shè) A ={1，2，3}，則商集A/IA =[D]

A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。

2-6．設(shè)ｆ(x)＝x+1，ｇ(x)＝x-1 都是從實(shí)數(shù)集合Ｒ到Ｒ的函數(shù)，則ｆ。ｇ＝[C]

A．x+1；B．x-1；C．x；D．x2。

第三章 結(jié)構(gòu)代數(shù)(群論初步)

3-1 給出集合及二元運(yùn)算，闡述是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元運(yùn)算 *是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元運(yùn)算。定義如下：對(duì)于所有 ai，aj ∈S2，都有 ai。aj = ai。

（3）S3 = {0，1}，二元運(yùn)算 * 是普通乘法。

答：（1）二元運(yùn)算*在S1上不封閉．所以，＂S1，*＂不能構(gòu)成代數(shù)系統(tǒng)。

（2）由二元運(yùn)算的定義不難知道。在 S2 內(nèi)是封閉的，所以，〈S2。〉構(gòu)成代數(shù)

系統(tǒng)；然后看該代數(shù)系統(tǒng)的類型：該代數(shù)系統(tǒng)只是半群。

（3）很明顯，〈{0，1}，*〉構(gòu)成代數(shù)系統(tǒng)；滿足結(jié)合律，為半群；1是幺元，為獨(dú)異

點(diǎn)；而 0 為零元；結(jié)論：僅為獨(dú)異點(diǎn)，而不是群。

3-2 在自然數(shù)集合上，下列那種運(yùn)算是可結(jié)合的［A］

A．x*y = max(x,y)；B．x*y = 2x+y ；

C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 設(shè) Z 為整數(shù)集合，在 Z 上定義二元運(yùn)算。，對(duì)于所有 x，y ∈Z都有

x。y=x + y，試問〈Z?！的芊駱?gòu)成群，為什麼 ？

答：由題已知，集合Z滿足封閉性；二元運(yùn)算滿足結(jié)合律，依此集合Z為半群；有幺元為 －5，為獨(dú)異點(diǎn).假設(shè)代數(shù)系統(tǒng)的幺元是集合中的元素 e,則一個(gè)方程來自于二元運(yùn)算定義, 即e。x= e + x，一個(gè)方程來自該特殊元素的定義的性質(zhì),即e。x = x.由此而來的兩個(gè)方程聯(lián)立結(jié)果就有: e+x=x 成立.削去 x,e=0 的結(jié)果不是就有了嗎!；每個(gè)元素都有逆.求每個(gè)元素的逆元素,也要解聯(lián)方程,如同求幺元一樣的道理；結(jié)論是：代數(shù)系統(tǒng)〈 Z?！禈?gòu)成群。

第二部分圖論方法

第四章 圖

4-1 10 個(gè)頂點(diǎn)的簡單圖 G 中有 4 個(gè)奇度頂點(diǎn)，問 G 的補(bǔ)圖中有幾個(gè)偶數(shù)度頂點(diǎn) ？ 答：因?yàn)?0階完全圖的每個(gè)頂點(diǎn)的度數(shù)都是n-1=9――為奇數(shù)。這樣一來，一個(gè)無向簡單圖 G 的某頂點(diǎn)的度數(shù)是奇數(shù)，其補(bǔ)圖的相應(yīng)頂點(diǎn)必偶數(shù)，因?yàn)橐粋€(gè)偶數(shù)與一個(gè)奇數(shù)之和才是奇數(shù)．所以，Ｇ的補(bǔ)圖中應(yīng)有 10-4＝6 個(gè)奇數(shù)度頂點(diǎn)。

4-2 是非判斷：無向圖G中有10條邊,4個(gè)3度頂點(diǎn),其余頂點(diǎn)度數(shù)全是2,共有 8 個(gè)頂點(diǎn).[是]

4-3 填空補(bǔ)缺：1條邊的圖 G 中，所有頂點(diǎn)的度數(shù)之和為[2]

第五章樹

5-1握手定理的應(yīng)用（指無向樹）

（1）在一棵樹中有 7 片樹葉，3 個(gè) 3 度頂點(diǎn)，其余都是 4 度頂點(diǎn)，問有(有1個(gè)4度頂點(diǎn))個(gè)？

（2）一棵樹有兩個(gè) 4 度頂點(diǎn)，3 個(gè) 3 度頂點(diǎn)，其余都是樹葉，問有(9個(gè)1度頂點(diǎn))片？

5-2 一棵樹中有 i 個(gè)頂點(diǎn)的度數(shù)為 i（i=2，…k），其余頂點(diǎn)都是樹葉(即一度頂點(diǎn))，問樹葉多少片？設(shè)有x片,則 x=

答：假設(shè)有 x 片樹葉，根據(jù)握手定理和樹的頂點(diǎn)與邊數(shù)的關(guān)系，有關(guān)于樹葉的方程，解方程得到樹葉數(shù) x = Σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最優(yōu) 2 元樹：用 Huffman 算法求帶權(quán)為 1，2，3，5，7，8 的最優(yōu) 2 元樹 T。試問：（1）T 的權(quán) W（T）？（2）樹高幾層 ？

答：用 Huffman 算法，以 1，2，3，5，7，8 為權(quán)，最優(yōu) 2 元樹 T ；然后，計(jì)算并回答所求問題：（1）T 的權(quán) W（T）= 61；（2）樹高幾層：4 層樹高。

5-4以下給出的符號(hào)串集合中，那些是前綴碼？將結(jié)果填入[]內(nèi).B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]

5-5(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 [非]

5-6(是非判斷題)二元正則樹有奇數(shù)個(gè)頂點(diǎn)。[是]

5-7 在某次通信中 a，b，c，d，e 出現(xiàn)的頻率分別為 5%;10%;20%;30%;35%.求傳輸他們的最佳前綴碼。

1、最優(yōu)二元樹 T；2.每個(gè)字母的碼字；

答：每個(gè)字母出現(xiàn)頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號(hào)

出現(xiàn)次數(shù)即為權(quán)，如右下圖).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。

第三部分邏輯推理理論

第六章 命題邏輯

6-1 判斷下列語句是否命題，簡單命題或復(fù)合命題。

（1）2月 17 號(hào)新學(xué)期開始。[真命題]

（2）離散數(shù)學(xué)很重要。[真命題]

（3）離散數(shù)學(xué)難學(xué)嗎 ？[真命題]

（4）C 語言具有高級(jí)語言的簡潔性和匯編語言的靈活性。[復(fù)合命題]

（5）x + 5 大于 2。[真命題]

（6）今天沒有下雨，也沒有太陽，是陰天。[復(fù)合命題]

6-2 將下列命題符號(hào)化.（1）2 是偶素?cái)?shù)。

（2）小李不是不聰明，而是不好學(xué)。

（3）明天考試英語或考數(shù)學(xué)。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符號(hào)化為： p ∧ q。

（2）符號(hào)化為：p ∧ ﹃q。

（3）符號(hào)化為：p ∨ q。

（4）符號(hào)化為：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）Σ（0，1，2，3）；

（3）Σ（1，3）。

以下兩題(6-4;6-5)為選擇題,將正確者填入[]內(nèi).6-4 令 p：經(jīng)一塹；q：長一智。命題’’只有經(jīng)一塹，才能長一智’’符號(hào)化為[B]

A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p

6-5 p：天氣好；q：我去游玩．命題 ”如果天氣好，則我去游玩” 符號(hào)化為［B］

A． p→q；B．q→p；C．p∧q；D．﹁q→p

6-6證明題:用不同方法(必須有構(gòu)造證明法)判斷推理結(jié)果是否正確。

如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒有上體育課。答：將公式分成前提及結(jié)論。

前提：（p→﹃q），p；

結(jié)論：﹃q；

證明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要證明的結(jié)論與證明結(jié)果一致，所以推理正確。

第七章謂詞邏輯

7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號(hào)化

（1）這臺(tái)機(jī)器不能用。

（2）如果 2 ＞ 3，則 2 ＞ 5。

答：（1）﹃F（a）。

（2）L（a，b）→ H（a，z）。

7-2 填空補(bǔ)缺題：設(shè)域?yàn)檎麛?shù)集合Ｚ，命題?x?y彐z（x-y=z）的真值為（0）

7-3在謂詞邏輯中將下列命題符號(hào)化

（1）有的馬比所有的牛跑得慢。

（2）人固有一死。

答：（1）符號(hào)化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。

（2）與（1）相仿，要注意量詞、聯(lián)結(jié)詞間的搭配：

x（F（x）→y（G（y）→ H（x，y）））。

《附錄》習(xí)題符號(hào)集

? 空集, ∪ 并, ∩ 交,⊕ 對(duì)稱差,～ 絕對(duì)補(bǔ),∑ 累加或主析取范式表達(dá)式縮寫 , － 普通減法, ÷ 普通除法, ㏑ 自然對(duì)數(shù), ㏒ 對(duì)數(shù)，﹃ 非，?量詞 ”所有”，”每個(gè)”，∨ 析取聯(lián)結(jié)詞，∧ 合取聯(lián)結(jié)詞，彐 量詞”存在”，”有的”。

2010年8月12號(hào)。

第四篇：淺談離散數(shù)學(xué)專題

淺談離散數(shù)學(xué)

【摘要】離散數(shù)學(xué)是一門理論性強(qiáng),知識(shí)點(diǎn)多,概念抽象的基礎(chǔ)課程,學(xué)生學(xué)習(xí)起來普遍感到難度很高。本文從離散數(shù)學(xué)內(nèi)容、學(xué)生學(xué)習(xí)興趣的激發(fā)、教學(xué)內(nèi)容的安排、教學(xué)方式方法的使用等方面,探討了如何上好、學(xué)好離散數(shù)學(xué)課。

【關(guān)鍵詞】離散數(shù)學(xué)教學(xué)方法教師 學(xué)生

離散數(shù)學(xué)研究的是離散量，是計(jì)算機(jī)科學(xué)與技術(shù)系各專業(yè)的核心課程。課程內(nèi)容具有知識(shí)點(diǎn)多、散、抽象等特點(diǎn),加之學(xué)生不能認(rèn)識(shí)到該課程的重要性,缺乏學(xué)習(xí)興趣和學(xué)習(xí)主動(dòng)性,不僅忽視該課程的學(xué)習(xí),甚至害怕這門課程。因此,創(chuàng)新教學(xué)方法,提高學(xué)生自主學(xué)習(xí)的積極性,對(duì)提高學(xué)生的能力、提升教學(xué)質(zhì)量和水平具有重要的意義。通過一學(xué)期的學(xué)習(xí)和專研,我積累了少許經(jīng)驗(yàn),總結(jié)了一些關(guān)于離散數(shù)學(xué)的教學(xué)方法，僅供大家參考。

一、離散數(shù)學(xué)的特點(diǎn)

本課程介紹計(jì)算機(jī)科學(xué)與技術(shù)系各專業(yè)所需要的離散數(shù)學(xué)基礎(chǔ)知識(shí),主要有以下兩點(diǎn)特點(diǎn)：

1、知識(shí)點(diǎn)集中，概念和定理多：《離散數(shù)學(xué)》是建立在大量概念之上的邏輯推理學(xué)科，概念的理解是我們學(xué)習(xí)這門學(xué)科的核心。掌握、理解和運(yùn)用這些概念和定理是學(xué)好這門課的關(guān)鍵。要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的則是定理和性質(zhì)。

2、方法性強(qiáng)：離散數(shù)學(xué)的特點(diǎn)是抽象思維能力的要求較高。培養(yǎng)學(xué)生抽象思維能力、邏輯推理能力、縝密概括能力以及分析和解決實(shí)際問題能力的主干課程,對(duì)學(xué)習(xí)其他諸多課程,具有重要的指導(dǎo)作用?！峨x散數(shù)學(xué)》的證明題多，不同的題型會(huì)需要不同的證明方法，同一個(gè)題也可能有幾種方法，具有很強(qiáng)的方法性。

二、教學(xué)困難所在1、離散數(shù)學(xué)是一門理論性強(qiáng),知識(shí)點(diǎn)多,概念抽象的基礎(chǔ)課程, 內(nèi)容具有知

識(shí)點(diǎn)多、散、抽象等特點(diǎn)，學(xué)生學(xué)者困難；

2、學(xué)生不能認(rèn)識(shí)到該課程的重要性,缺乏學(xué)習(xí)興趣和學(xué)習(xí)主動(dòng)性,不僅忽視該課程的學(xué)習(xí),甚至害怕這門課程。

3、離散數(shù)學(xué)課程在課堂教學(xué)難度、教學(xué)時(shí)間等方面的原因,很多學(xué)校都出現(xiàn)師生、學(xué)生之間的交流較少，從而使學(xué)生學(xué)習(xí)困難。

三、離散數(shù)學(xué)的教學(xué)方法引導(dǎo)學(xué)生提高對(duì)離散數(shù)學(xué)課程應(yīng)用性的認(rèn)識(shí),激發(fā)學(xué)生學(xué)習(xí)的興趣和愛好,增強(qiáng)汲取知識(shí)的自主性

離散數(shù)學(xué)課程是一門基礎(chǔ)性課程,學(xué)習(xí)離散數(shù)學(xué)課程對(duì)學(xué)生今后的學(xué)習(xí)和工作,具有重要的作用,例如培養(yǎng)學(xué)生的抽象思維能力和縝密的邏輯推理能力,為學(xué)生今后處理離散信息,提高專業(yè)理論水平,從事計(jì)算機(jī)的實(shí)際工作提供必備的數(shù)學(xué)工具;通過學(xué)習(xí),可以掌握數(shù)理邏輯,集合論,代數(shù)結(jié)構(gòu)和圖論的基本概念和原理,并會(huì)運(yùn)用離散數(shù)學(xué)的方法,分析和解決計(jì)算機(jī)理論和應(yīng)用中的一些問題等。學(xué)習(xí)主動(dòng)性是學(xué)生的力量之源,因此,引導(dǎo)學(xué)生充分認(rèn)識(shí)學(xué)習(xí)離散數(shù)學(xué)課程的作用,能夠激發(fā)學(xué)生學(xué)習(xí)的愛好和熱情,提升學(xué)生學(xué)習(xí)的積極性和主動(dòng)性,從而使學(xué)生學(xué)有成效。認(rèn)真?zhèn)湔n,合理準(zhǔn)備教學(xué)內(nèi)容和安排教學(xué)環(huán)節(jié),優(yōu)化教學(xué)方式方法

備好課是教學(xué)取得預(yù)期效果的前提和基礎(chǔ),針對(duì)學(xué)生學(xué)習(xí)具體情況,合理準(zhǔn)備教學(xué)內(nèi)容和安排教學(xué)環(huán)節(jié),使用恰當(dāng)?shù)慕虒W(xué)方法,在教學(xué)中可以起到事半功倍的效果。

(1)合理地準(zhǔn)備教學(xué)內(nèi)容。根據(jù)課程教學(xué)大綱和離散數(shù)學(xué)課程定理定義比較多、知識(shí)比較抽象的特點(diǎn)以及學(xué)生的實(shí)際情況,準(zhǔn)備深度和廣度適合學(xué)生特點(diǎn)的教學(xué)內(nèi)容。

(2)合理地講解課程內(nèi)容,重難點(diǎn)突出講解,注意輕重緩急。對(duì)于離散數(shù)學(xué)中比較重要、比較抽象的概念和定理,如邏輯的推理理論、關(guān)系的性質(zhì)、群、圖等,認(rèn)真分析,用多種方式和方法深入

講解,可以使用解析法、圖示法、矩陣法舉實(shí)例等多種方法講解。對(duì)于比較容易理解和掌握的內(nèi)容,可以一筆帶過。這樣,學(xué)生對(duì)所學(xué)內(nèi)容就會(huì)有重點(diǎn)地學(xué)習(xí),主次分明,學(xué)生不僅可以對(duì)所學(xué)內(nèi)容掌握透徹,更能熟練把握離散數(shù)學(xué)中分析問題和解決問題的思路、方式和方法。

(3)啟發(fā)式教學(xué)和教師講授相結(jié)合。很多人認(rèn)為,大學(xué)教學(xué)課時(shí)緊,內(nèi)容多,關(guān)鍵靠學(xué)生自主學(xué)習(xí),我卻認(rèn)為并不完全是這樣的。如果教師不顧學(xué)生的理解情況,只顧在講臺(tái)上講授知識(shí),課堂氛圍會(huì)很沉悶,很多同學(xué)不能專注于該門課程的學(xué)習(xí),經(jīng)常走神,教學(xué)很難達(dá)到預(yù)期的效果。因此,有針對(duì)性地提問和展開討論,不僅能夠培養(yǎng)學(xué)生的思考能力,更能調(diào)動(dòng)學(xué)生學(xué)習(xí)的興趣和積極性,從而使教學(xué)達(dá)到最佳效果。也可以引進(jìn)有趣生動(dòng)的例子說明概念，既活躍課堂，又鞏固了學(xué)生的記憶。3 合理布置作業(yè),認(rèn)真批改作業(yè),有針對(duì)性地安排習(xí)題課和課后答疑

學(xué)數(shù)學(xué)就要做數(shù)學(xué)，《離散數(shù)學(xué)》的學(xué)習(xí)也不例外。學(xué)習(xí)數(shù)學(xué)不僅限于學(xué)習(xí)數(shù)學(xué)知識(shí)，更重要的還在于學(xué)習(xí)數(shù)學(xué)思維方法。為了強(qiáng)化學(xué)生能力的訓(xùn)練,培養(yǎng)學(xué)生的抽象思維能力、邏輯推理能力、實(shí)際問題的解決能力等,在保證作業(yè)數(shù)量的同時(shí),更要提高布置作業(yè)的質(zhì)量,增加典型簡答題、討論題、推理題、實(shí)際應(yīng)用題等習(xí)題在作業(yè)中的分量,使學(xué)生在掌握各種基本知識(shí)和基本技能的同時(shí),提高自身的綜合能力。

認(rèn)真檢查和批改作業(yè),是督促學(xué)生學(xué)習(xí)的主要途徑,也是教師了解學(xué)生理解和掌握所學(xué)課程情況的主渠道。必要時(shí),教師可以批改一部分作業(yè),其他作業(yè)讓同學(xué)們之間互相檢查和批改,不僅可以督促學(xué)生學(xué)習(xí),更能讓學(xué)生在批改其他同學(xué)作業(yè)時(shí)逐步認(rèn)識(shí)到自身的缺陷和不足,以備今后更有針對(duì)性地學(xué)習(xí)。

教師在作業(yè)檢查和批改過程中發(fā)現(xiàn)的主要問題和疑難以及學(xué)生提出的有代表性的問題,有必要安排習(xí)題課進(jìn)行講解,幫助學(xué)生對(duì)解決疑難,加深對(duì)所知識(shí)的理解。對(duì)于學(xué)生比較爭論的問題,可以展開討論,鼓勵(lì)學(xué)生大膽發(fā)言,培養(yǎng)學(xué)生探索未知的精神和創(chuàng)造性解決實(shí)際問題的能力。

四、總結(jié)

從此上看，上好離散數(shù)學(xué)課,關(guān)鍵是根據(jù)學(xué)生具體實(shí)際,有針

對(duì)性地安排教學(xué)內(nèi)容,合理使用教學(xué)方式方法,最大限度地激發(fā)學(xué)生的學(xué)習(xí)興趣,充分發(fā)揮教師的主導(dǎo)作用和學(xué)生的主體作用,達(dá)到教與學(xué)和諧。

參考文獻(xiàn)

[1] 屈婉玲,耿素云,張立昂.離散數(shù)學(xué)[M].北京:高等教育出版社.2008.[2] 黃巍,金國祥.”離散數(shù)學(xué)”課程教學(xué)改革的探討[J].中國電力教育,2009(8):82-83.[3] 周小燕,胡豐華.對(duì)提高離散數(shù)學(xué)教學(xué)質(zhì)量的探討[J].浙江科技學(xué)院學(xué)報(bào),2007,19(2):156-158.[4] 龍浩,張佳佳.怎樣教好《離散數(shù)學(xué)》課[J].貴陽學(xué)院學(xué)報(bào),2007,2(1):53-57.[5] 廖仲春.離散數(shù)學(xué)的教學(xué)探討[J].湖南工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報(bào),2008,8(5)http://

第五篇：離散數(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)說明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)過計(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}。問(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è)元素，問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分）給定連通簡單平面圖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。