【正文】 )A．5 Ｂ．10 Ｃ. 15 Ｄ．2019. 在自然數(shù)集合上，下列哪種運(yùn)算不是可交換的 （ D ）A. B. C. D. 20. 設(shè)簡(jiǎn)單圖的最大結(jié)點(diǎn)度數(shù)為，圖的結(jié)點(diǎn)數(shù)為,則與的關(guān)系為 ( B )A. B. C. D. 與沒關(guān)系21．下列各項(xiàng)中錯(cuò)誤的是 （ A ） A． B． C． D．22．設(shè)，下列各式成立的是 （ C ）A． B． C． D．23．連通平面圖中，所有面的次數(shù)之和是 （ C ） A．邊數(shù) B．邊數(shù)的一半 C．邊數(shù)的兩倍 D．邊數(shù)的一倍24．無向圖 具有一條歐拉回路，那么圖 的所有結(jié)點(diǎn)的度數(shù)都是 （ B ）A．奇數(shù) B．偶數(shù)C．素?cái)?shù) D．125. 下列集合哪個(gè)是最小聯(lián)結(jié)詞集 （ D ）A. B. C. D. 26. 設(shè)簡(jiǎn)單圖的最大結(jié)點(diǎn)度數(shù)為，圖的結(jié)點(diǎn)數(shù)為,則與的關(guān)系為 （ B ）A. B. C. D. 與沒關(guān)系27. 設(shè)集合A={1,2,3}，B={2,3,4,5}，C={2,4,8,16},D={1,2,3,4},設(shè)“|”是集合上的“整除”關(guān)系，則下列偏序集中能構(gòu)成格的是 （ C ）A. A,|。28．設(shè) 上的二元關(guān)系,則關(guān)系具有的性質(zhì)是哪一個(gè) （ B ）A. 自反性 B. 對(duì)稱性C. 傳遞性 D. 反對(duì)稱性29．判斷下列各式中不是合式公式的是哪一個(gè) （ C ）A. B. C. D. 30. 代數(shù)系統(tǒng)(S,)中以下斷言正確的是 （ C ）A. 單位元與零元總是不相等； B. 可能有二個(gè)左單位元和一個(gè)右單位元；C. 單位元總有逆元； D. 若S39。C. 明天下午我乘Z86次或K256次列車去北京。C. 如果天不下雨，我就騎車上班。 B. {1,2,3} A。 B. R1。C. 請(qǐng)勿吸煙！ D. 李白是唐朝的詩人。5. 若集合中有201個(gè)元素，則的子集有 2201 個(gè)。9. 在根樹中，若每個(gè)結(jié)點(diǎn)的出度 小于等于m ，則稱這棵樹為叉樹。J8814. 一個(gè)映射，如果對(duì)任意，若，則有 f(xi)≠f(xj) ，則此映射叫從 到的入射?！　?x216。20. 設(shè)，的冪集。24. 是 永真 式（填永真，永假或可滿足）。28. 若關(guān)系是反對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以主對(duì)角線為對(duì)稱的元素不能同時(shí)為 1 。32. 給定集合上的關(guān)系，若是 自反的 、對(duì)稱的，則稱是上的相容關(guān)系。36. 無向圖G具有一條歐拉圖，當(dāng)且僅當(dāng)G是連通的且___有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)_______.37. 個(gè)結(jié)點(diǎn)的無向完全圖的邊數(shù)為。216。 Q )217。42. 設(shè)為根樹，若每個(gè)結(jié)點(diǎn)的出度都小于等于，則稱為 叉樹。45. 8個(gè)結(jié)點(diǎn)的無向完全圖的邊數(shù)為　28 。49. 在根樹中，入度為零的結(jié)點(diǎn)稱為 根 。4. 強(qiáng)連通圖：在簡(jiǎn)單有向圖G中，任何一對(duì)結(jié)點(diǎn)的兩者之間相互可達(dá)，則稱G為強(qiáng)連通圖。8. 命題公式A和B是等價(jià)的：設(shè)P1,P2,…,Pn為所有出現(xiàn)在A和B中的原子變?cè)? 若給 P1,P2,…,Pn的任一組指派, A和B的真值都相等, 稱A和B是等價(jià)的.9. 子群：設(shè)是一個(gè)群，S是G的非空子群，如果也構(gòu)成群，則稱是的一個(gè)子群。14. 歐拉回路：給定有向圖G，通過圖中每邊一次且一次的一條回路稱作歐拉回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。則稱為R的對(duì)稱閉包。25. 命題公式的對(duì)偶式：命題公式A中含聯(lián)結(jié)詞，將互換，T與F互換所得公式A*稱為A的對(duì)偶式。B(y)) 219。B(4)) 219。T) 219。5． 別講話了！6． 小王和小李是同學(xué)。Q ) 的析取范式和合取范式。 P217。 (P217。Q) 析取范式 4. 設(shè)A是18的除1以外的正因數(shù)組成的集合，“|”為整除關(guān)系，畫出（A，|）的哈斯圖；若存在的話，分別求出其最大元、最小元，極大元，極小元，上確界，下確界，上界和下界。解： 6. 在一階邏輯中，將下面命題符號(hào)化，并且要求只能使用全稱量詞：（1） 沒有人長(zhǎng)著綠色頭發(fā)。8. 設(shè)的關(guān)系為：，求以及。解：11. 在一階邏輯中，將下面命題符號(hào)化，并且要求只能使用全稱量詞：（1） 沒有人長(zhǎng)著綠色頭發(fā)。 解：（1）R={1,1,1,3,1,4,1,12,1,24,3,3,3,12,3,24,4,4,4,12,4,24,12,12,12,24,24,24}（2）畫出哈斯圖得2分。（1）已知，問嗎？（2）已知，問嗎？解：（1）設(shè)有某種指派，使公式的真值為，但的真值為，的真值為，則和的真值為，故成立，但不一定成立。（3） 畫一個(gè)沒有一條歐拉回路，但有一條漢密爾頓回路的圖。19. 設(shè) X={a,b,c} 上關(guān)系 R={a,b,a,c,b,c} , 求R的自反閉包 r(R) , 對(duì)稱閉包 s(R) , 和傳遞閉包 t(R) 。解：(1). R={1,1,1,2,1,3,1,5,1,6,1,12,2,2,2,6,2,12,3,3,3,6, 3,12, 5,5, 6,6,6,12,12,12} (2). (X,R)的哈斯圖為：(3). X無最大元； 有最小元1； 極大元5,12； 極小元1. 21. 設(shè)，其上關(guān)系為，寫出關(guān)系中的各元素，并求出dom, ran及。 因?yàn)?滿足交換律，所以右單位元就是單位元，元素的右逆元就是該元素的逆元。解：dom，（1分）ran，（1分）。如取，則。30. 求公式 ┐(P∨ ┐Q)∧(P → Q) 的主析取范式和主合取范式。 (Q174。R。R) 219。(216。P218。(216。 (P217。4． 設(shè)函數(shù)；若是滿射的，則是滿射的。H，且為H, *的幺元；又因?yàn)镵, *是H, *的子群，所以H, *的幺元e206。K，a1206。7． 用CP規(guī)則證明證明： （1） （附加前提）（2） （3） （4） （5） （6） 8． 形式化下命題，并用推理規(guī)則證明其結(jié)論每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù)；自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被2整除；并不是所有自然數(shù)都能被2整除。證明：設(shè)G=V,E，|V|=v，|E|=,若每一個(gè)結(jié)點(diǎn)的度數(shù)≥6, 又（2分） ∴2≥6v ，所以≥3v＞3v6， 與＜3v6矛盾10． 設(shè)（G，*）是一個(gè)群，定義關(guān)系R是GG的子集，其中R={(a,b)|c∈G,使b=c*a*c1 }. 試證R是G上的等價(jià)關(guān)系。 另一方面，(x,y) (AC) (BC)，有 (x,y) AC，(x,y) BC，即 xA，yC， xB，于是 (x,y) (A B)C，因此 (AC) (BC) (A B)C。因此，（Z4,+4）為群13． 證明前提P∨Q, P→R, Q→S 的結(jié)論是S∨R.證：(1). P∨Q P (2). P→Q T,(1),E (3). Q→S P (4). P→S T,(2),(3),I (5). S→P T,(4),E (6). P→R P (7). S→R T,(5),(6),I (8). S∨R T,(7),E 14． 符號(hào)化證明 人總是要死的，蘇格拉底是人，因此，蘇格拉底是