【正文】 若B=，則AB=。故B=A。故BA。因?yàn)锳A=BB，則x,xA。從而AA。從而B=A。從而AA =。對任意集合A,B，證明：若AA=BB，則B=B。解：(1) R={0,0,0,2,2,0,2,2}(2) R={1,1,1,2,2,1,2,2,3,1}。（2）A={1,2,3,4,5}，B={1,2}，R={x,y|2x+y4且x且yB}。（5）對任意x，存在y使x+y=x。（3）若xy，則存在某些z，使z0, xzyz。將下列命題符號化：（1）沒有小于0的自然數(shù)。（7）對任意自然數(shù)x,y，存在自然數(shù)z滿足xy=z。（5）對每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=x。（3）對每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=0。(7) xyz (xy=z)答：（1）存在自然數(shù)x，對任意自然數(shù)y滿足xy=1。(5) xy (xy=x)。(3) xy (xy=0)。五、證明或解答：（數(shù)理邏輯、集合論與二元關(guān)系部分）設(shè)個(gè)體域是自然數(shù)，將下列各式翻譯成自然語言：(1) xy（xy=1）。而顯然b（AB）B。假設(shè)B，則存在bB。證明： 當(dāng)B=時(shí)，因?yàn)椋ˋB）B=（A）=A，（AB）B=（A） =A，所以（AB）B=（AB）B。即P(AB)P(A)P(B)。SP(AB)，有SAB，所以SA且SB。從而SAB，故SP(AB)。從而SAB，故SP(AB)。從而A，xBC，故xA(BC)。從而(AB)(BA)=A。 即BA，從而B=（否則ABA，從而與(AB)(BA)=A矛盾）。1(AB)(BA)=A B=證明： 因?yàn)?AB)(BA)=A，所以BAA。 因?yàn)锳BC，所以A(BC)=A。而A(BC)= (AB)(AC)， 所以A=(AB)(AC)。1A=(AB)(AC)ABC=證明： 因?yàn)?AB)(AC) =(A)(A) =A()=A= A(BC)，且A=(AB)(AC)， 所以A= A(BC)，故ABC=。AB = AC，AB=AC，則C=B證明：B=B(AB)= B(AC)= (BA)(BC)= (AC)(B∩C)= C(AB)= C(AC)=CAB=AC，B=C，則C=B 證明：B=B(A)=(BA)(B)=(CA)(C)=C(A)=CA－(BC)＝(A－B)－C　　證明：A－(BC)= A=A()=(A)=(AB)=(AB)C(A－B)(A－C)=A－(BC)　證明：(AB)(A－C)=(A)(A)=(AA)()=A=A－(BC)AB=B，則A=B=證明： 因?yàn)锽=AB，所以B=BB=（AB）B=。設(shè)AB=，則AB=（AB）（BA）=。證明、 (1) PR 前提 (2) P (1) (3) PQ 前提 (4) Q (2),(3) (5) (QR) 前提 (6) QR (5) (7) Q (6) (8) (4),(7)(集合論部分)四、設(shè)Ａ，Ｂ，Ｃ是三個(gè)集合，證明：A (B－C)＝(AB)－(AC) 證明：(AB)－(AC)= (AB) =(AB) （）=(AB)(AB)= AB=A（B）=A（BC）(A－B)(A－C)=A－(BC)證明：(AB)(AC)=(A)(A) =A ()=A= A(BC)AB=AC，B=C，則C=B　　證明：B=B(A)=(B) (BA)=(C) (CA)=C(A)=C AB=A(BA)證明： A(BA)=A(B)=(AB)(A)=(AB)U= ABA=B 243。 本題即證明 A（BC），CA，DB，AD。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è)。答：循環(huán)群，任一非單位元4設(shè)〈G,*〉是一個(gè)群，a,b,c∈G，則(1) 若ca=b，則c=( )；(2) 若ca=ba，則c=( )。答：5，104群G,*的等冪元是(　　)，有(　　　)個(gè)。答： 6,44代數(shù)系統(tǒng)G,*是一個(gè)群，則G的等冪元是(　　　　)。答：2，63設(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=( )。答：R的關(guān)系矩陣= R的關(guān)系矩陣=3集合A={1,2,…,10}上的關(guān)系R={x,y|x+y=10,x,yA}，則R 的性質(zhì)為（ ）。答：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ì)是什么？( )答：自反性、反對稱性和傳遞性3設(shè)S={１,２,３,４}，Ａ上的關(guān)系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)RR (2) R1 。答：（2） 2Ａ，Ｂ，Ｃ是三個(gè)集合，則下列哪幾個(gè)推理正確：(1) AB，BC= AC (2) AB，BC= A∈B (3) A∈B，B∈C= A∈C答：（1） （二元關(guān)系部分）2設(shè)Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R (2) R1 。答：（2）2設(shè)A∩B=A∩C，∩B=∩C，則B(　)C。答：321設(shè)P={x|(x+1)4且xR},Q={x|5x+16且xR},則下列命題哪個(gè)正確（ ） (1) QP　　(2) QP　(3) PQ　(4) P=Q答：（3）下列各集合中，哪幾個(gè)分別相等( )。(1) {a}P(A)　(2) {a}P(A)　(3) {{a}}P(A)　(4) {{a}}P(A)答：(2)1在0（ ）之間寫上正確的符號。則命題“并非每個(gè)實(shí)數(shù)都是有理數(shù)”的符號化表示為（ ）。答：P(x)218。答：P ，QP1謂詞公式x(P(x)218。答：2不是偶數(shù)且3不是負(fù)數(shù)。(1) x$y(x+y=0) (2) $yx(x+y=0)答：（1）對任一整數(shù)x存在整數(shù) y滿足x+y=0（2）存在整數(shù)y對任一整數(shù)x滿足x+y=0設(shè)全體域D是正整數(shù)集合，確定下列命題的真值：(1) x$y (xy=y)　　(　　)　　(2) $xy(x+y=y)　　(　　)(3) $xy(x+y=x) 　(　　)　　(4) x$y(y=2x)　　 (　　)答：（1） F （2） F （3）F （4）T設(shè)謂詞P(x)：x是奇數(shù)，Q(x)：x是偶數(shù)，謂詞公式 $x(P(x)218。答：所有人都不是大學(xué)生，有些人不會死設(shè)P：我生病，Q：我去學(xué)校，則下列命題可符號化為( )。　(3) 你喜歡唱歌嗎？ (4) 若7+8＞18，則三角形有4條邊。( )(1) 北京是中華人民共和國的首都。答：x,y, x,z判斷下列語句是不是命題。 $z C(y，z))174。 《離散數(shù)學(xué)》題庫答案一、選擇或填空（數(shù)理邏輯部分）下列哪些公式為永真蘊(yùn)含式？(　　　)(1)Q=Q→P (2)Q=P→Q (3)P=P→Q (4)P(PQ)=P 答：（1），（4）下列公式中哪些是永真式？( )(1)(┐PQ)→(Q→R) (2)P→(Q→Q) (3)(PQ)→P (4)P→(PQ)答：（2），（3），（4）設(shè)有下列公式，請問哪幾個(gè)是永真蘊(yùn)涵式?( )(1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(P→Q)=Q (5) (P→Q)=P (6) P(PQ)=P答：（2），（3），（4），（5），（6）公式x((A(x)174。B(y，x))217。D(x)中，自由變元是( )，約束變元是( )。若是，給出命題的真值。 (2) 陜西師大是一座工廠?！?5) 前進(jìn)！ (6) 給我一杯水吧！ 答：（1） 是，T （2） 是，F(xiàn) （3） 不是（4） 是，T （5） 不是 （6） 不是命題“存在一些人是大學(xué)生”的否定是( )，而命題“所有的人都是要死的”的否定是( )。(1)　只有在生病時(shí)，我才不去學(xué)校 (2) 若我生病，則我不去學(xué)校(3)　當(dāng)且僅當(dāng)我生病時(shí)，我才不去學(xué)校(4) 若我不生病，則我一定去學(xué)校答：（1） （2） （3） （4）設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式的意義是( )。Q