廣東技術(shù)師范學(xué)院模擬試題科目：失散數(shù)學(xué)考試形式：閉卷考試時(shí)間:120分鐘系別、班級(jí)：姓名：學(xué)號(hào)：一．填空題（每題2分,共10分）1。謂詞公式的前束范式是__?x?y?P(x)∨Q（y)__________.2.設(shè)全集則A∩B=__{2｝__，_｛4,5｝____，__{1,3，4,5}_____3.設(shè)，則__{｛c},｛a，c},{b，c｝,｛a，b，c｝}__________，_____Φ_______。4。在代數(shù)系統(tǒng)（N,+）中，其單位元是0，僅有_1___有逆元。5．若是連通平面圖G有個(gè)極點(diǎn),條邊,則G有___e+2-n____個(gè)面。二．選擇題(每題2分，共10分）1。與命題公式等價(jià)的公式是（)（A）（B）（C)(D）2。設(shè)會(huì)集，A上的二元關(guān)系不具備關(guān)系（）性質(zhì)（A）(A）傳達(dá)性（B）反對(duì)稱(chēng)性(C）對(duì)稱(chēng)性(D)自反性3.在圖中,結(jié)點(diǎn)總度數(shù)與邊數(shù)的關(guān)系是（)（A)（B)(C)（D)4.設(shè)D是有n個(gè)結(jié)點(diǎn)的有向完好圖，則圖D的邊數(shù)為（）（A）（B)(C）(D)5.無(wú)向圖G是歐拉圖，當(dāng)且僅當(dāng)(）(A)G的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)(B)G的所有結(jié)點(diǎn)的度數(shù)都是奇數(shù)(C）G連通且所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)（D)G連通且G的所有結(jié)點(diǎn)度數(shù)都是奇數(shù)。三．計(jì)算題（共43分）1。求命題公式的主合取范式與主析取范式。(6分）解：主合取方式: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）∨(p∧?q∧r）=∑1。3。第1頁(yè)共3頁(yè)2。設(shè)會(huì)集上的二元關(guān)系R的關(guān)系矩陣為，求的關(guān)系矩陣，并畫(huà)出R,的關(guān)系圖。(10分）3無(wú)向圖G有12條邊，G中有6個(gè)3度結(jié)點(diǎn),其余結(jié)點(diǎn)的度數(shù)均小于3,問(wèn)G中最少有多少個(gè)結(jié)點(diǎn)？（10分）解：∵G（V，E），|E｜=V,d（Vi）<3,設(shè)最少有x個(gè)節(jié)點(diǎn)，由握手定理得：2×12=∑d（Vi)<6×3+（x—6)×32〈(x-6）=＞x〉8故G中最少有9個(gè)節(jié)點(diǎn)。求下面兩個(gè)圖的最小生成樹(shù)。（12分)試判斷可否為格?說(shuō)明原由。（5分）解：（Z，≤）是格,原由以下:對(duì)于任意a∈Z，a≤a成立，滿(mǎn)足自反性；對(duì)于任意a∈Z，b∈Z,若a≤b且b≤a，則a=b,滿(mǎn)足反對(duì)稱(chēng)性;對(duì)于任意a，b，c∈Z,若a≤b，b≤c，則a≤c，滿(mǎn)足傳達(dá)性；而對(duì)于任意a，b∈Z,a≤b，b為最小上界，a為最大下界，故（Z,≤）是格。（注：什么是格？)四．證明題（共37分）1。用推理規(guī)則證明。（10分）證明:編號(hào)公式依據(jù)（1)(?B∨C）∧?C前提(2）?B∨C，?C（1）（3）?B（2）（4）A→B(3）(5）?A（3）（4）(6）?（?A∧D）前提（7）A∨?D(6）(8)?D（5)（6）2.設(shè)R是實(shí)數(shù)集，,。求證：都是滿(mǎn)射，但不是單射。（10分）證明：要證f是滿(mǎn)射,即?y∈R,都存在（x1,x2）∈R×R,使f（x1，x2）=y，而f(x1，x2）=x1+x2，可取x1=0,x2=y，即證得；再證g是滿(mǎn)射,即?y∈R,，都存在（x1，x2)∈R×R，使g（x1，x2）=y，而g(x1，x2）第2頁(yè)共3頁(yè)=x1x2，可取x1=1，x2=y,即證得；最后證f不是單射，f（x1,x2)=f(x2，x1）取x1≠x2，即證得,同理：g(x1，x2）=g（x2，x1)，取x1≠x2，即證得.無(wú)向圖G有9個(gè)結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)的度數(shù)不是5就是6，求證：G中最少有5個(gè)6度結(jié)點(diǎn)或6個(gè)5度結(jié)點(diǎn)。（10分）證明：設(shè)G中至多有4個(gè)6度結(jié)點(diǎn)且5個(gè)5度結(jié)點(diǎn),d(Vi）=49不是偶數(shù)，故它不是一個(gè)圖,矛盾。(下面只供參照，個(gè)人答案)4。設(shè)平面上有100個(gè)點(diǎn),期中任意兩點(diǎn)間的距離最少是1,則最多有300對(duì)點(diǎn)距離恰好為1。(7