離散數(shù)學(xué)復(fù)習(xí)題

PAGEPAGE4離散數(shù)學(xué)復(fù)習(xí)資料一、填空命題“對于任意給定的正實數(shù)，都存在比它大的實數(shù)”令F(x)：x為實數(shù)，則命題的邏輯謂詞公式為。設(shè)p：王大力是100米冠軍，q：王大力是500米冠軍，在命題邏輯中，命題“王大力不但是100米冠軍，而且是500米冠軍”的符號化形式為。命題“存在一個人不但是100米冠軍，而且是500米冠軍”的符號化形式為____。選擇合適的論域和謂詞表達(dá)集合A=“直角坐標(biāo)系中，單位元（不包括單位圓周）的點(diǎn)集”則A=。設(shè)P（x）：x是素數(shù)，E(x)：x是偶數(shù)，O(x)：x是奇數(shù)N(x,y)：x可以整數(shù)y。則謂詞的自然語言是對于任意一個素數(shù)都存在一個奇數(shù)使該素數(shù)都能被整除。設(shè)個體域是，謂詞公式寫成不含量詞的形式是。謂詞的前束范式為。命題公式的主合取范式為，其編碼表示為。設(shè)E為全集，，稱為A的絕對補(bǔ)，記作～A，且～（～A）=，～E=，

～=。設(shè)，則A-B=，A?B=，A×C=。設(shè)考慮下列子集，，

，，，

則A的覆蓋有，A的劃分有。設(shè)，，則，。設(shè)A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},則=，=。A={1，2，3，4，5，6}，A上二元關(guān)系，則用列舉法T=；T的關(guān)系圖為，T具有性質(zhì)。偏序集的哈斯圖為，則=。設(shè)，定義A上的二元運(yùn)算為普通乘法、除法和加法，則代數(shù)系統(tǒng)<A,*>中運(yùn)算*關(guān)于運(yùn)算具有封閉性。A，B，C表示三個集合，文圖中陰影部分的集合表達(dá)式為。ABABC設(shè)圖G=<V，E>，的鄰接矩陣，則的入度=，的出度=，從到的長度為2的路徑有條。結(jié)點(diǎn)數(shù)n（）的簡單連通平面圖的邊數(shù)為m，則m與n的關(guān)系為m<=3n-6。設(shè)f，g是自然數(shù)集N上的函數(shù)，則。設(shè)I是整數(shù)集合，Z3是由模3的同余類組成的同余類集，在Z3上定義+3如下：，則+3的運(yùn)算表為；<Z+,+3>是否構(gòu)成群。集合S={α，β，γ，δ}上的二元運(yùn)算*為*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代數(shù)系統(tǒng)<S,*>中的幺元是，α的逆元是。三、按要求解答將謂詞公式化為前束析取范式與前束合取范式。用推理規(guī)則論證：如果今天是星期六，我們就要到頤和園或圓明園玩，如果頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤和園游人太多，所以，我們?nèi)A明園玩。符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。用推理規(guī)則論證：或者邏輯難學(xué)，或者有少數(shù)學(xué)生不喜歡它；如果數(shù)學(xué)容易學(xué)，那么邏輯并不難學(xué)。因此，如果許多學(xué)生喜歡邏輯，那么數(shù)學(xué)并不難學(xué)。設(shè)有下列情況，用推理規(guī)則論證結(jié)論是否有效？（a）或者天晴，或者下雨。（b）如果天晴，我去看電影。（c）如果我去看電影，我就不看書。結(jié)論：如果我在看書則天在下雨。符號化語句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論。給定3個命題：P：北京比天津人口多；Q：2大于1；R：15是素數(shù)。求復(fù)合命題：的真值。將化為與其等價的前束范式。把公式轉(zhuǎn)化為前束范式求的主合取范式。求(A?BùC)ù(?A?(?B?ùC))的主析取范式與主合取范式。求(P∨Q)R的主析取范式與主合取范式。設(shè)命題A1，A2的真值為1，A3，A4真值為0，求命題

的真值。求集合的并與交。設(shè)X={1,2,3,4,5}，X上的關(guān)系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}，求R的傳遞閉包t(R)。設(shè)集合上的關(guān)系。求的傳遞閉包。在實數(shù)平面上，畫出關(guān)系，并判定關(guān)系的特殊性質(zhì)。設(shè)X={a，b，c，d}，R是X上的二元關(guān)系,R={<a，c>，<a，d>，<b，c>，<b，d>，<c，d>}設(shè)S={1,2,3,4,6,8,12,24}，“”為S上整除關(guān)系，問：（1）偏序集的哈斯圖如何？（2）偏序集(1)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。(3)說明R的性質(zhì)A={a,b,c,d}，R={<a,b>,<b,c>,<b,d>,<c,b>}為A上的關(guān)系，利用矩陣乘法求R的傳遞閉包，并畫出t（R）的關(guān)系圖。的極小元、最小元、極大元、最大元是什么?集合上的偏序關(guān)系為整除關(guān)系。設(shè)，，試畫出哈斯圖，并求A，B，C的最大元素、極大元素、下界、上確界。對于實數(shù)集合R，在下表所列的二元遠(yuǎn)算是否具有左邊一列中的性質(zhì)，請在相應(yīng)位上填寫“Y”或“N”。MaxMin+可結(jié)合性可交換性存在幺元存在零元設(shè)B4={e,a,b,ab}，運(yùn)算*如下表，*則<B4,*>是一個群（稱作Klein四元群）。設(shè)S=R-{-1}（R為實數(shù)集），。（1）說明是否構(gòu)成群；（2）在中解方程。設(shè)，R是X上的二元關(guān)系，

畫出R的關(guān)系圖。寫出R的關(guān)系矩陣。說明R是否是自反、反自反、對稱、傳遞的。設(shè)是負(fù)整數(shù)集合，定義二個雙射函數(shù)，, ，求，并說明其是否是雙射函數(shù)。設(shè)M={0o,60o,120o,240o,300o,180o}表示平面上幾何圖形順時針旋轉(zhuǎn)的六種位置，定義一個二元運(yùn)算*，對M中任一元素a,b有a*b=圖形旋轉(zhuǎn)(a+b)的角度，并規(guī)定當(dāng)旋轉(zhuǎn)到360o時即為0o。<M,*>是否是群。240o240o180o120o60o0o300o300o180o120o60o0o300o240o240o120o60o0o300o240o180o180o60o0o300o240o180o120o120o0o300o240o180o120o60o60o300o240o180o120o60o0o0o300o240o180o120o60o0o*求圖中的一棵最小生成樹。已知某有向圖的鄰接矩陣如下：試求：到的長度為4的有向路徑的條數(shù)。下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長度（郵局在D點(diǎn)）。求圖的可達(dá)矩陣，并判斷圖的連通性。有向圖G如圖所示，試求：(1)求G的鄰接矩陣A。(2)求出A2、A3和A4（3）v1到v4長度為1、2、3和4的路徑有多少？(4)求出可達(dá)矩陣P。V3畫一個有一條漢密爾頓回路的圖。畫一個有一條