【正文】 xA。對, x,xBB。 若B，則BB。故A=。證明：若B=，則BB=。(3) R={1,1,1,1,2,2,3,3}。（3）A={1,2,3}，B={3,2,1,0,1}，R={x,y||x|=|y|且x且yB}。答：（1）x（G(x,0)M（0,0,x）） 或x L(x,0)（2）xyz ((L(x,y)L(y,z))L(x,z))（3）xy ((L(x,y)z(L(z,0)G(xz,yz)))（4）xyM（x,y,y）（5）xyA(x,y,x)列出下列二元關(guān)系的所有元素：（1）A={0,1,2}，B={0,2,4}，R={x,y|x,y}。（4）存在x，對任意y 使得xy=y。（2）xz是xy且yz的必要條件。設(shè)A(x,y,z): x+y=z, M（x,y,z）: xy=z, L(x,y): xy, G(x,y): xy， 個(gè)體域?yàn)樽匀粩?shù)。（6）存在自然數(shù)x，對任意自然數(shù)y滿足xy=x。（4）存在自然數(shù)x，對任意自然數(shù)y滿足xy=1。（2）對每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=1。 (6) xy（xy=x）。 (4) xy（xy=0）。 (2) xy(xy=1)。故這與已知（AB）B=（AB）B矛盾。因?yàn)閎B且b AB，所以b（AB）B。 用反證法證明。 故P(AB)=P(A)P(B)1（AB）B=（AB）B當(dāng)且僅當(dāng)B=。從而SP(A)且SP(B)，故SP(A)P(B)。即P(A)P(B)P(AB)。即P(A)P(B)P(AB) 1P(A)P(B)=P(AB) （P(S)表示S的冪集）證明：SP(A)P(B)，有SP(A)且SP(B)，所以SA且SB。從而(AB)CA(BC) 1P(A)P(B)P(AB) （P(S)表示S的冪集）證明：SP(A)P(B)，有SP(A)或SP(B)，所以SA或SB。1(AB)CA(BC)證明：x(AB)C，有AB且xC，即A，xB且xC。 因?yàn)锽=，所以AB=A且BA=。但(BA)A=，故BA=。而A(BC)= (AB)(AC)， 所以A=(AB)(AC)。1(AB)(AC)=ABC證明： 因?yàn)?AB)(AC) =(A)(A) =A()=A= A(BC)，且(AB)(AC)=， 所以= A(BC)，故ABC。 因?yàn)锳BC=，所以A(BC)=A。從而A=AB=B=。故AB=，BA=，從而AB，BA，故A=B。 AB= 　　證明：設(shè)A=B，則AB=（AB）（BA）==。 本題即證明 A（BC），CA，DB，AD（1） A 前提 （2） A（BC）前提 （3） BC （1），（2） （4） CA 前提 （5） C （1），（4） （6） B （3），（5） （7） DB 前提 （8） D （6），（7）2用推理規(guī)則證明PQ, (QR),PR不能同時(shí)為真。D: D隊(duì)獲亞軍。B: B隊(duì)獲亞軍。結(jié)論: (5) D隊(duì)不是亞軍。(3) 若D隊(duì)獲亞軍，則B隊(duì)不能獲亞軍。從而(P→Q)(QR) P2為慶祝九七香港回歸祖國，四支足球隊(duì)進(jìn)行比賽，已知情況如下，問結(jié)論是否有效?前提: (1) 若A隊(duì)得第一，則B隊(duì)或C隊(duì)獲亞軍。故P→Q，Q和R)都為T，即P→Q為T，Q和R都為F。(P→Q)(QR) P證明：設(shè)(P→Q)(QR)為T，則P→Q和(QR)都為T。所以P→QP→(PQ)。1P→QP→(PQ)證明：設(shè)P→(PQ)為F，則P為T，PQ為F。(1) 無簡單回路的連通圖　　(2) 有n個(gè)頂點(diǎn)n1條邊的連通圖 (3) 每對頂點(diǎn)間都有通路的圖 　(4) 連通但刪去一條邊便不連通的圖答：（3）80、連通圖G是一棵樹當(dāng)且僅當(dāng)G中（ ）。(1) 5　　(2) 7 (3) 8 　(4) 9答：（4）7若一棵完全二元（叉）樹有2n1個(gè)頂點(diǎn)，則它（ ）片樹葉。答：偶數(shù)7具有6 個(gè)頂點(diǎn)，12條邊的連通簡單平面圖中，每個(gè)面都是由(　　)條邊圍成？(1) 2　　(2) 4　　(3) 3　　(4) 5答：（3）7在有n個(gè)頂點(diǎn)的連通圖中，其邊數(shù)（ ）。 (1) 10 (2) 4 (3) 8 (4) 16答：（4）7設(shè)無向圖G有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是3，則圖G有( )個(gè)頂點(diǎn)。答：（1）70、設(shè)T是一棵樹，則T是一個(gè)連通且( )圖。答：26任何連通無向圖G至少有( )棵生成樹，當(dāng)且僅當(dāng)G 是( )，G的生成樹只有一棵。答：它是連通圖6設(shè)G是一棵樹，n,m分別表示頂點(diǎn)數(shù)和邊數(shù)，則(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能確定。(1) {a，ab，110，a1b11} (2) {01，001，000，1}(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}答：(1)6n個(gè)結(jié)點(diǎn)的有向完全圖邊數(shù)是( )，每個(gè)結(jié)點(diǎn)的度數(shù)是( )。答：所有邊一次且恰好一次6有n個(gè)結(jié)點(diǎn)的樹，其結(jié)點(diǎn)度數(shù)之和是(　　　　)。答：, n160、一棵無向樹的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是(　　　　)。答：以v為起點(diǎn)的邊的條數(shù)， 以v為終點(diǎn)的邊的條數(shù)5設(shè)G是一棵樹，則G 的生成樹有( )棵。(1) 歐拉圖 (2) 樹 　(3) 平面圖 (4)　連通圖 答：(4)（考察圖的定義）5下面給出的集合中，哪一個(gè)是前綴碼？(　　　　　　)(1) {0，10，110，101111}　　　(2) {01，001，000，1}(3) {b，c，aa，ab，aba}　　　 (4) {1，11，101，001，0011}答：（2）5一個(gè)圖的哈密爾頓路是一條通過圖中( )的路。(1) 2階　　(2) 3 階 (3) 4 階 　(4) 6 階答：(3)（格與布爾代數(shù)部分）5下列哪個(gè)偏序集構(gòu)成有界格（ ）(1) （N,）　(2) （Z,） (3) （{2,3,4,6,12},|（整除關(guān)系）） 　(4) (P(A),)答：(4)（考查冪集的定義）5有限布爾代數(shù)的元素的個(gè)數(shù)一定等于（ ）。答：k4在自然數(shù)集N上，下列哪種運(yùn)算是可結(jié)合的？（ ） (1) a*b=ab　　(2) a*b=max{a,b}　(3) a*b=a+2b　(4) a*b=|ab|答：(2)50、任意一個(gè)具有2個(gè)或以上元的半群，它（ ）。答：H,是群 或 a，b G， abH，a1H 或 a,b G，ab1H 4群＜A,*＞的等冪元有(　　　)個(gè)，是(　　　)，零元有(　　　)個(gè)。所以G等于它的任一非單位元生成的循環(huán)群）4設(shè)〈G,*〉是一個(gè)群，a,b,c∈G，則(1) 若ca=b，則c=( )；(2) 若ca=ba，則c=( )。G中只有一個(gè)單位元，其它元素的階都不等于1，所以都是p。答：循環(huán)群，任一非單位元（證明如下：任一元素的階整除群的階。并且一元素的階整除群的階）4群G,*的等冪元是(　　)，有(　　　)個(gè)。答： 6,44代數(shù)系統(tǒng)G,*是一個(gè)群，則G的等冪元是(　　　　)。x=θ）3設(shè)A={3,6,9}，A上的二元運(yùn)算*定義為：a*b=min{a,b}，則在獨(dú)異點(diǎn)A,*中，單位元是( )，零元是( )；答：9，3（半群與群部分）3設(shè)〈G,*〉是一個(gè)群，則(1) 若a,b,x∈G，ax=b，則x=( )；(2) 若a,b,x∈G，ax=ab，則x=( )。答：2，6（單位元和零元的定義，單位元：e。答：R的關(guān)系矩陣= R的關(guān)系矩陣=3集合A={1,2,…,10}上的關(guān)系R={x,y|x+y=10,x,yA}，則R 的性質(zhì)為（ ）。t,y∈G)}）R1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝3設(shè)Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除關(guān)系，求R= {(　　　　　)}R={1,1,2,2,3,3,4,4,5,5,6,6,1,2,1,3,1,4,1,5,1,6,2,4,2,6,3,6}3設(shè)Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R (2) R1 。(　　　　)答：A上的恒等關(guān)系集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是什么？( )答：自反性、對稱性和傳遞性3集合A上的偏序關(guān)系的三個(gè)性質(zhì)是什么？( )答：自反性、反對稱性和傳遞性(題29，30，31全是考查定義)3設(shè)S={１,２,３,４}，Ａ上的關(guān)系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)RR (2) R1 。答：=（等于）2判斷下列命題哪幾個(gè)正確？(　　　　　)(1) 若A∪B＝A∪C，則B＝C (2) {a,b}={b,a} (3) P(A∩B)P(A)∩P(B) （P(S)表示S的冪集）(4) 若A為非空集，則AA∪A成立。(1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c}(5) A5={x|(xa)(xb)(xc)=0} (6) A6={x|x2(a+b)x+ab=0}答：A1=A2=A3=A6， A4=A5（集合具有無序性、確定性和互異性）2若AB=Ф，則下列哪個(gè)結(jié)論不可能正確？( )(1) A=Ф (2) B=Ф　(3) AB (4) BA答：（4）（差集的定義）2判斷下列命題哪個(gè)為真?( )(1) AB=BA = A=B (2) 空集是任何集合的真子集(3) 空集只是非空集合的子集 (4) 若A的一個(gè)元素屬于B，則A=B答：（1）（考查空集和差集的相關(guān)知識(shí)）2判斷下列命題哪幾個(gè)為正確？(　　　)　(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}{Ф,{{Ф}}} (3) Ф∈{{Ф}}(4) Ф{Ф} (5) {a,b}∈{a,b,{a},}答：（2），（4）2判斷下列命題哪幾個(gè)正確？(　　　　　)(1) 所有空集都不相等 (2) {Ф}Ф (4) 若A為非空集，則AA成立。(1) =　(2) 　(3) 　(4) 答：(4)（空集沒有任何元素，且是任何集合的子集）1若集合S的基數(shù)|S|=5，則S的冪集的基數(shù)|P(S)|=（ ）。答：x(R(x)Q(x))（集合論部分）1設(shè)A={a,{a}}，下列命題錯(cuò)誤的是（ ）。 $yR(y)（一對括號(hào)就是一個(gè)轄域）1令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。 $yR(y))Q(x)中量詞x的轄域是（ ）。1永真式的否定是（ ）(1) 永真式　(2) 永假式　(3) 可滿足式　(4) (1)(3)均有可能答：（2）（這個(gè)記住就行了）1公式(PQ)(PQ)化簡為（ ），公式 Q(P(PQ))可化簡為（ ）。Q(x))在哪個(gè)個(gè)體域中為真?( )(1) 自然數(shù)　　(2) 實(shí)數(shù)　　 (3) 復(fù)數(shù)　　(4) (1)(3)均成立答：（1）（在某個(gè)體域中滿足不是奇數(shù)就是偶數(shù)，在整數(shù)域中才滿足條件，而自然數(shù)子整數(shù)的子集，當(dāng)然滿足條件了）1命題“2是偶數(shù)或3是負(fù)數(shù)”的否定是（ ）。(1)　只有在生病時(shí)，我才不去學(xué)校 (2) 若我生病，則我不去學(xué)校(3)　當(dāng)且僅當(dāng)我生病時(shí)，我才不去學(xué)校(4) 若我不生病，則我一定去學(xué)校答：（1） （注意“只有……才……”和“除非……就……”兩者都是一個(gè)形式的） （2） （3） （4）設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式的意義是( )。）命題“存在一些人是大學(xué)生”的否定是( )，而命題“所有的人都是要死的”的否定是( )?！?3) 你喜歡唱歌嗎？ (4) 若7+8＞18，則三角形有4條邊。( )(1) 北京是中華人民共和國的首都。于是A(x)、B(y，x)和$z C(y，z)中y為自由變元，x和z為約束變元，在D(x)中x為自由變元）判斷下列語句是不是命題。答：x,y, x,z（考察定義在公式x A和$x A中，稱x為指導(dǎo)變元，A為量詞的轄域。 $z C(y，z))174。 《離散數(shù)學(xué)》題庫與答案一、選擇或填空（數(shù)理邏輯部分）下列哪些公式為永真蘊(yùn)含式？(　　A　)(1)Q=Q→P (2)Q=P→Q (3)P=P→Q (4)P(PQ)=P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蘊(yùn)含等值式求出（注意與吸收律區(qū)別）下列公式中哪些是永真式？( )(1)(┐PQ)→(Q→R) (2)P→(Q→Q) (3)(PQ)→P (4)P→(PQ)答：（2），