2023年自學(xué)考試離散數(shù)學(xué)試題匯編

全國2023年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．下列命題公式為重言式的是（）A．p→(p∨q)B．(p∨┐p)→qC．q∧┐q D．p→┐q2．下列語句中不是命題的只有（）A．這個(gè)語句是假的。B．1+1=1.0C．飛碟來自地球外的星球。D．凡石頭都可練成金。3．設(shè)p：我很累，q：我去學(xué)習(xí)，命題：“除非我很累，否則我就去學(xué)習(xí)”的符號(hào)化對(duì)的的是A．┐p∧qB．┐p→qC．┐p→┐q D．p→┐q4．下列等價(jià)式對(duì)的的是（）A．┐┐AB．C．┐┐AD．5．在公式中變元y是（）A．自由變元B．約束變元C．既是自由變元，又是約束變元D．既不是自由變元，又不是約束變元6．設(shè)A={1，2，3}，A上二元關(guān)系S={<1，1>，<1，2>，<3，2>，<3，3>}，則S是（）A．自反關(guān)系 B．反自反關(guān)系C．對(duì)稱關(guān)系 D．傳遞關(guān)系7．設(shè)集合X為人的全體，在X上定義關(guān)系R、S為R={<a，b|a，b∈X∧a是b的父親}，S={<a，b>|a，b∈X∧a是b的母親}，那么關(guān)系{<a，b>|a，b∈x∧a是b的祖母}的表達(dá)式為（）A．RS B．R-1SC．SR D．RS-18．設(shè)A是正整數(shù)集，R={(x，y)|x，y∈A∧x+3y=12}，則R∩({2，3，4，6}×{2，3，4，6})=（）A． B．{<3，3>}C．{<3，3>，<6，2>} D．{<3，3>，<6，2>，<9，1>}9．下列式子不對(duì)的的是（）A．(A-B)-C=(A-C)-B B．(A-B)-C=A-(B∪C)C．(A-B)-C=(A-C)-(B-C) D．A-(B∪C)=(A-B)∪C10．下列命題對(duì)的的是（）A．{l，2}{{1，2}，{l，2，3}，1} B．{1，2}{1，{l，2}，{l，2，3}，2}C．{1，2}{{1}，{2}，{1，2}} D．{1，2}∈{1，2，{2}，{l，2，3}}11．在下列代數(shù)系統(tǒng)中，不是環(huán)的只有（）A．<Z，+，*)，其中Z為整數(shù)集，+，*分別為整數(shù)加法和乘法。B．(Q，+，*)，其中Q為有理數(shù)集，+，*分別為有理數(shù)加法和乘法。C．<R，+，*>，其中R為實(shí)數(shù)集，+為實(shí)數(shù)加法，a*b=a+2b。D．<Mn(R)，+，*>，其中Mn(R)為實(shí)數(shù)集n×n階矩陣結(jié)合，+，*是矩陣加法和乘法。12．下列整數(shù)集對(duì)于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（）A．{l，2，3，4，5} B．{1，2，3，6，12}C．{2，3，7} D．{l，2，3，7}13．結(jié)點(diǎn)數(shù)為奇數(shù)且所有結(jié)點(diǎn)的度數(shù)也為奇數(shù)的連通圖必然是（）A．歐拉圖 B．漢密爾頓圖C．非平面圖 D．不存在的14．無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且（）A．G中各頂點(diǎn)的度數(shù)均相等B．G中各頂點(diǎn)的度數(shù)之和為偶數(shù)C．G中各頂點(diǎn)的度數(shù)均為偶數(shù)D．G中各頂點(diǎn)的度數(shù)均為奇數(shù)15．平面圖(如下)的三個(gè)面的次數(shù)分別是（）A．11，3，4 B．11，3，5C．12，3，6 D．10，4，3二、填空題（本大題共10小題，每小題2分，共20分） 請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16．求一個(gè)公式的主析取或主合取范式的方法，有______________法和______________法。17．給定謂詞合式公式A，其中一部分公式形式為()B(x)或(x)B(x)，則量詞，后面所跟的x稱為______________，而稱B為相應(yīng)量詞的______________。18．設(shè)X，U，V，Y都是實(shí)數(shù)集，f1：X→U，且fl(x)→ex；f2：U→V，且f2(u)＝u(1+u)；f3：V→Y，且f3(v)=cosv。那么f3f2f1的定義域是______________，而復(fù)合函數(shù)(f3f2f1)(x)=______________。19．集合X={a，b，c，d}上二元關(guān)系R={<a，b>，<a，c>，<a，d>，<b，c>，<b，d>，<e，d>}，則R的自反閉包r(R)=______________，對(duì)稱閉包s(R)=______________。20．已知G=<{l，-1，i，-i}，·>(其中i=，是數(shù)的乘法)是群，則-l的階是______________；i的階是______________。21．對(duì)代數(shù)系統(tǒng)<S，*>，其中*是S上的二元運(yùn)算，若a，b∈S，且對(duì)任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，則稱a為運(yùn)算“*”的______________，稱b為運(yùn)算“*”的______________。22．設(shè)<S，*>是群，則<S，*>滿足結(jié)合律和______________；若｜S｜>l，S中不也許有______________。23．寫出如右有向圖的一條初級(jí)回路：______________，其長度是______________。24．一個(gè)______________且______________的無向圖稱為樹。25．在簡樸無向圖G=<V，E>中，假如V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖稱為______________，假如V有n個(gè)結(jié)點(diǎn)，那么它還是______________度正則圖。三、計(jì)算題(本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分)26．若集合A={a，{b，c}}的冪集為P(A)，集合B={，{}}的冪集為P(B)，求P(A)∩P(B)。27．構(gòu)造命題公式(p→(q∧r))→┐p的真值表。28．求圖G＝<V，E>的可達(dá)矩陣，其中V＝｛v1,v2,v3,v4｝ E＝｛(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)｝29．求下列公式的主析取范式和主合取范式：（P∧Q）∨（┐P∧R）30．設(shè)A＝｛2，3，4，6，8，12，24｝，R為A上整除關(guān)系，試畫<A，R>的哈斯圖，并求A中的最大元，最小元，極大元，極小元。四、證明題（本大題共3小題，第31、32小題各6分，第33題8分，共20分）31．設(shè)M是偶數(shù)集，＋和·是數(shù)的加、乘運(yùn)算，證明<M，＋，·>是一個(gè)環(huán)。32．設(shè)R是集合X上的二元關(guān)系，證明R是X上傳遞關(guān)系當(dāng)且僅當(dāng)RRR。33．設(shè)G是簡樸平面圖，G有n個(gè)頂點(diǎn)m條邊，且m<30，證明G中存在一項(xiàng)點(diǎn)v，d（v）≤4。五、應(yīng)用題（本大題共2小題，第34題6分，第35題9分，共15分）34．判斷下面推理是否對(duì)的，并證明你的結(jié)論。 假如小王今天家里有事，則他不會(huì)來開會(huì)。假如小張今天看到小王，則小王今天來開會(huì)了。小張今天看到小王。所以小王今天家里沒事。35．有6個(gè)村莊Vi，i=l，2，…，6欲修建道路使村村可通?，F(xiàn)已有修建方案如下帶權(quán)無向圖所示，其中邊表達(dá)道路，邊上的數(shù)字表達(dá)修建該道路所需費(fèi)用，問應(yīng)選擇修建哪些道路可使得任二個(gè)村莊之間是可通的且總的修建費(fèi)用最低?規(guī)定寫出求解過程，畫出符合規(guī)定的最低費(fèi)用的道路網(wǎng)絡(luò)圖并計(jì)算其費(fèi)用。2023年7月全國自考離散數(shù)學(xué)試題試卷真題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．下列語句中不是命題的只有（）A．雞毛也能飛上天？ B．或重于泰山，或輕于鴻毛。C．不經(jīng)一事，不長一智。 D．牙好，胃口就好。2．從真值角度看，命題公式的所有類型是（）A．永真式 B．永假式C．永真式，永假式 D．永真式，永假式，可滿足式3．設(shè)M（x）：x是人；F（x）：x要吃飯。用謂詞公式表達(dá)下述命題：所有的人都要吃飯，其中錯(cuò)誤的表達(dá)式是（）A． B．C． D．4．下列公式是前束范式的是（）A． B．C． D．5．設(shè)論域?yàn)檎麛?shù)集，下列真值為真的公式是（）A． B．C． D．6．下列是謂詞演算中的合式公式的是（）A． B．C． D．（）．（）（）A．B．C．D．．（）8．下列式子對(duì)的的是（）A．（A－B）-C=A-（B∪C） B．A－（B∪C）=（A－B）∪CC．~（A－B）=~（B－A） D．~（A∩B）A9．下列集合對(duì)所給的運(yùn)算是封閉的只有（）A．非零整數(shù)集合Z*上的除法運(yùn)算B．全體n×n實(shí)可逆矩陣集合Mn（R）上的矩陣加法和乘法運(yùn)算C．全體n×n實(shí)矩陣集合Mn（R）上的矩陣加法和乘法運(yùn)算D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍數(shù)10．設(shè)<A，eq\o\ac(○,+)，*>是環(huán)，則下列說法不對(duì)的的是（）A．<A，eq\o\ac(○,+)>是互換群 B．<A，*>是半群C．*對(duì)eq\o\ac(○,+)是可分派的 D．eq\o\ac(○,+)對(duì)*是可分派的11．下列四個(gè)格，是分派格的是（）C．D．．（）A．B．12．下列各圖是無向完全圖的是（）13．下列各有向圖是強(qiáng)連通圖的是（）14．設(shè)Ｇ是具有n個(gè)結(jié)點(diǎn)的無向簡樸圖，若在Ｇ中存在一條漢密爾頓路，則Ｇ中每一對(duì)結(jié)點(diǎn)的度數(shù)之和與n-1的關(guān)系為（）A．大于 B．大于等于C．等于 D．小于15．設(shè)連通平面圖Ｇ，共有n個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則歐拉證明成立的公式是（）A．e-n+r=2 B．n+r-e=2C．n-r+e=2 D．n-e-r=2二、填空題（本大題共10小題，每小題2分，共20分） 請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16．所謂____是指不能再分解的命題，而復(fù)合命題是由一些____通過聯(lián)結(jié)詞復(fù)合而成的命題。17．在命題演算中，兩個(gè)____的合取、析取、條件、雙條件均為____。18．使公式成立的條件是____中不含y，____中不含x。19．設(shè)A={1，2，3，4}，R是A上的二元關(guān)系，R={<x,y>|x/y是素?cái)?shù)}，則domR=_____;ranR=____。20．設(shè)無向圖Ｇ有n個(gè)結(jié)點(diǎn)m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)為k或k+1，記Nk為度數(shù)等于k的結(jié)點(diǎn)數(shù)，則Nk=_____。假如無向簡樸圖C的結(jié)點(diǎn)的度數(shù)均為相同的偶數(shù)，且m=7，則n=____。21．設(shè)X={1，3，5，9，15，45}，R是X上的整除關(guān)系，則R是X上的偏序，其最大元是___，極小元是____。22．設(shè)<>是有界格，a,bL,若ab=0,則a=b=_____；若ab=1,則a=b=____。23．設(shè)e是群G上的幺元，若aG且a2=e,則a-1=____,a-2=__________。24．代數(shù)系統(tǒng)<A,。>，其中A為命題公式集合，。為析取運(yùn)算，則<A，。>中零元素是____，幺元是____。25．樹是不包含_____的___圖。三、計(jì)算題（本大題共6小題，第26、27題各4分，第28、29題各5分，第30、31題各6分，共30分）26．假如論域是集合{a,b,c}，試消去下面公式中的量詞：27．求公式（的主析取范式。28．設(shè)A={a,b,c},A上二元關(guān)系R={<a,a>,<a,c>,<b,a>},用關(guān)系矩陣法求最小的自然數(shù)m,n,m<n使Rm=Rn。29．根據(jù)下列條件假如能畫則請畫出一個(gè)歐拉圖，假如不能畫則請說明理由。（1）偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊（2）奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊（3）偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊（4）奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊30．下列各整數(shù)集合對(duì)于整除關(guān)系“|”都構(gòu)成偏序集，判斷哪些偏序集能構(gòu)成格？并說明理由。1)L={1,2,3,4,5}2)L={1,2,3,6,12}3)L={1,2,3,4,6,9,12,18,36}4)L={1,2,22,23,…,2n}31．設(shè)A={2，3，5，12，19}，等價(jià)關(guān)系R={<x,y>|x,(mod3)},寫出各元素的等價(jià)類，并求A/R。四、證明題（本大題共3小題，第32、33題各6分，第34題8分，共20分）32．用等價(jià)變換法證明：是永真式。33．若無向圖G是歐拉圖，G中是否存在割邊？為什么？34．設(shè)A是一個(gè)集合，X=P（A），R是X上元素之間的包含關(guān)系，試證明<X,R>是偏序集。（注：P（A）為A的冪集）五、應(yīng)用題（本大題共2小題，第35題6分，第36題9分，共15分）35．設(shè)有n個(gè)村莊要修路，（1）若要使所有村莊之間都有通路，問需在兩村之間至少修幾條路？（2）若要使任意兩村莊之間有一條直接的路，則至少修幾個(gè)路？（3）若修一條連接所有村莊的環(huán)路，問有多少種修路方案？36．設(shè)有推理：(a)沒有不守信用的人是可信賴的；(b)有些可以信賴的人是受過教育的人；(c)因此有些受過教育的人是守信用的。試構(gòu)造推理的證明，規(guī)定把推理的前提，結(jié)論符號(hào)化為謂詞形式，并寫出推理過程。（個(gè)體域：人的集合）提醒：設(shè)F（x）表達(dá)x是守信用的人；G（x）表達(dá)x是可信賴的人；H（x）表達(dá)x是受過教育的人。全國2023年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．下列命題公式中不是重言式的是（）A．p→(q→r) B．p→(q→p)C．p→(p→p) D．(p→(q→r))(q→(p→r))2．下列語句中為命題的是（）A．這朵花是誰的？ B．這朵花真美麗??！C．這朵花是你的嗎？ D．這朵花是他的。3．設(shè)個(gè)體域是整數(shù)集，則下列命題的真值為真的是（）A．yx(x·y=1) B．xy(x·y≠0)C．xy(x·y=y2) D．yx(x·y=x2)4．關(guān)于謂詞公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯(cuò)誤的是（）A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）B．z是該謂詞公式的約束變元C．（x）的轄域是P（x,y） D．x是該謂詞公式的約束變元5．設(shè)論域D={a,b}，與公式xA（x）等價(jià)的命題公式是（）A．A（a）∧A（b） B．A（a）→A（b）C．A（a）∨A（b） D．A（b）→A（a）6．集合A={1，2，3}上的下列關(guān)系矩陣中符合等價(jià)關(guān)系條件的是（）A． B．C． D．7．設(shè)A={?}，B=P（P（A）），以下不對(duì)的的式子是（）A．{{?}，{{?}}，{?，{?}}}包含于B B．{{{?}}}包含于BC．{{?，{?}}}涉及于B D．{{?}，{{?，{?}}}}包含于B8．設(shè)Z是整數(shù)集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，則f（）A．僅是滿射 B．僅是入射C．是雙射 D．無逆函數(shù)9．設(shè)A={1，2，3，4，5}，A上二元關(guān)系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，則S-1R-1的運(yùn)算結(jié)果是（）A．{〈4，1〉，〈2，3〉，〈4，2〉} B．{〈2，4〉，〈2，3〉，〈4，2〉}C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}10．設(shè)有代數(shù)系統(tǒng)G=〈A，*〉，其中A是所有命題公式的集合，*為命題公式的合取運(yùn)算，則G的幺元是（）A．矛盾式 B．重言式C．可滿足式 D．公式p∧q11．在實(shí)數(shù)集合R上，下列定義的運(yùn)算中不可結(jié)合的是（）A．a(chǎn)*b=a+b+2ab B．a(chǎn)*b=a+bC．a(chǎn)*b=a+b+ab D．a(chǎn)*b=a-b12．下列集合關(guān)于所給定的運(yùn)算成為群的是（）A．已給實(shí)數(shù)a的正整數(shù)次冪的全體，且a{0，1，-1}，關(guān)于數(shù)的乘法B．所有非負(fù)整數(shù)的集合，關(guān)于數(shù)的加法C．所有正有理數(shù)的集合，關(guān)于數(shù)的乘法D．實(shí)數(shù)集，關(guān)于數(shù)的除法13．設(shè)無向圖中有6條邊，有一個(gè)3度頂點(diǎn)和一個(gè)5度頂點(diǎn)，其余頂點(diǎn)度為2，則該圖的頂點(diǎn)數(shù)是（）A．3 B．4C．5 D．614．下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）A．B．C．D．15．設(shè)無向圖G的邊數(shù)為m，結(jié)點(diǎn)數(shù)為n，則G是樹等價(jià)于（）A．G連通且m=n+1 B．G連通且n=m+1C．G連通且m=2n D．每對(duì)結(jié)點(diǎn)之間至少有一條通路二、填空題（本大題共10小題，每小題2分，共20分） 請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16．不能再分解的命題稱為____________，至少包含一個(gè)聯(lián)結(jié)詞的命題稱為____________。17．在命題演算中，五個(gè)聯(lián)結(jié)詞的含義是由其____________表唯一擬定的，而不是由其類似的____________語言的含義擬定。18．使公式（x）（y）（A（x）→B（y））（（x）A（x）→（y）B（y））成立的條件是____________不具有y，____________不具有x。19．設(shè)A為任意集合，請?zhí)钊脒m當(dāng)?shù)倪\(yùn)算符，使式子A____________A=?；A____________~A=?成立。20．設(shè)A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod3)}，則domR=____________，ranR=____________。21．稱集合S是給定非空集合A的覆蓋：若S={S1，S2，…，Sn}，其中SiA，Si≠?，i=1，2，…，n，且____________；進(jìn)一步若____________，則S是集合A的劃分。22．對(duì)實(shí)數(shù)的普通加法和乘法，____________是加法的冪等元，____________是乘法的冪等元。23．在代數(shù)系統(tǒng)〈A，*〉中，A={a}，*是A上二元運(yùn)算，則該代數(shù)系統(tǒng)的單位元是____________，零元是____________。24．設(shè)〈A，≤〉是偏序集，若A中____________都有最小上界和____________則稱A關(guān)于偏序≤構(gòu)成格。25．若一條路中，所有邊均不相同，則此路稱作____________；若一條路中所有的結(jié)點(diǎn)均不相同，則稱此路為____________。三、計(jì)算題（本大題共6小題，第26、27小題各4分，第28、29小題各5分，第30、31小題各6分，共30分）36．試畫出結(jié)點(diǎn)數(shù)為3的（1）強(qiáng)連通圖；（2）單向連通圖；（3）弱連通圖；（4）非連通圖。27．設(shè)A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。試求RSR28．在全體正整數(shù)集合Z+中規(guī)定∩，∪為：對(duì)任意的a,b∈Z+， a∪b=[a,b]，即求a,b的最小公倍數(shù)； a∩b=(a,b)，即求a,b的最大公約數(shù)； 則運(yùn)算∩，∪滿足結(jié)合律，互換律和吸取律，于是〈Z+，∩，∪〉是一個(gè)格。判斷下列集合是否是<Z+，∩，∪>的子格？ 1）A={1，2，3，9，12，72} 2）A={1，2，3，12，18} 3）A={5，52，53，…，5n} 4）T=2Z+={2k|k∈Z+}29．求命題公式（p→q）→（q∨p）的主析取范式。30．結(jié)出命題公式（p∨(p∧q)）∧((p∨q)∧q)的二叉樹表達(dá)。31．設(shè)A={a,b,c,d},R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，求R，r(R),s(R),t(R)的關(guān)系圖。四、證明題（本大題共3小題，第32、33小題各6分，第34小題8分，共20分）32．設(shè)A是非空集合，P（A）是A的冪集，是集合的包含關(guān)系，則〈P（A），〉是格，證明：〈P（A），〉是有補(bǔ)格。33．設(shè)〈{a,b},*〉是半群，其中a*a=b，證明：（1）a*b=b*a；（2）b*b=b。34．若一棵樹恰有2個(gè)結(jié)點(diǎn)的度數(shù)為1，則它必是一條歐拉路。五、應(yīng)用題（本大題共2小題，第35小題6分，第36小題9分，共15分）35．設(shè)I是整數(shù)集，<，>，＝，≤，≥，≠是Ｉ上的二元關(guān)系，分別表達(dá)小于，大于、等于、小于等于，大于等于，不等于，那么這些關(guān)系會(huì)滿足什么性質(zhì)？試填寫下表自反反自反對(duì)稱反對(duì)稱傳遞<>=≤≥≠≤∩≥≤∪≥36．設(shè)R=，Z是整數(shù)集，則： （1）R對(duì)矩陣的加法和乘法構(gòu)成一個(gè)環(huán)； （2）R中存在元素x是右零因子但不是左零因子。全國2023年7月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）A．P→Q B．P∨QC．P∧Q D．P∧Q2．下列命題公式為重言式的是（）A．Q→（P∧Q） B．P→（P∧Q）C．（P∧Q）→P D．（P∨Q）→Q3．下列4個(gè)推理定律中，不對(duì)的的是（）A．A（A∧B） B．（A∨B）∧ABC．（A→B）∧AB D．（A→B）∧BA4．謂詞公式x(P(x)∨yR(y))→Q(x)中量詞的轄域是（）A． B．P（x）C．(P(x)∨yR(y)) D．P(x),Q(x)5．設(shè)個(gè)體域A={a,b}，公式xP(x)∧xS(x)在A中消去量詞后應(yīng)為（）A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)6．下列選項(xiàng)中錯(cuò)誤的是（）A．?? B．?∈?C．?{?} D．?∈{?}7．設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則相應(yīng)于R的A的劃分是（）A．{{a},{b,c},bdhvl7v} B．{{a,b},{c},fv7vl7p}C．{{a},,{c},pdfhxvx} D．{{a,b},{c,d}}8．設(shè)R為實(shí)數(shù)集，函數(shù)f：R→R，f(x)=2x，則f是（）A．滿射函數(shù) B．入射函數(shù)C．雙射函數(shù) D．非入射非滿射9．設(shè)R為實(shí)數(shù)集，R+={x|x∈R∧x>0}，*是數(shù)的乘法運(yùn)算，<R+，*>是一個(gè)群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是（）A．{R+中的有理數(shù)} B．{R+中的無理數(shù)}C．{R+中的自然數(shù)} D．{1，2，3}10．下列運(yùn)算中關(guān)于整數(shù)集不能構(gòu)成半群的是（）A．a(chǎn)b=max{a,b} B．a(chǎn)b=bC．a(chǎn)b=2ab D．a(chǎn)b=|a-b|11．設(shè)Z是整數(shù)集，+，分別是普通加法和乘法，則（Z，+，）是（）A．域 B．整環(huán)和域C．整環(huán) D．含零因子環(huán)12．設(shè)A={a,b,c}，R是A上的二元關(guān)系，R={<a,a>,<a,b>,<a,c>,<c,a>}，那么R是（）A．反自反的 B．反對(duì)稱的C．可傳遞的 D．不可傳遞的13．設(shè)D=<V,E>為有向圖，V={a,b,c,d,e,f},E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）A．強(qiáng)連通圖 B．單向連通圖C．弱連通圖 D．不連通圖14．在有n個(gè)結(jié)點(diǎn)的連通圖中，其邊數(shù)（）A．最多有n-1條 B．至少有n-1條C．最多有n條 D．至少有n條15．連通圖G是一棵樹，當(dāng)且僅當(dāng)G中（）A．有些邊不是割邊 B．每條邊都是割邊C．無割邊集 D．每條邊都不是割邊二、填空題（本大題共10小題，每小題2分，共20分） 請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16．任意兩個(gè)不同的小項(xiàng)的合取為________________式，全體小項(xiàng)的析取式必為________________式。17．公式x(P(x)→Q(x,y)∨zR(y,z))→S(x)中的自由變元為________________，約束變元為________________。18．設(shè)集合M={x|1≤x≤12,x被2整除，x∈Z},N={x|1≤x≤12,x被3整除，x∈Z}，則M∩N=________________，M∪N=________________。19．設(shè)X={1，2，3}，f：X→X，g：X→X，f={<1,2>,<2,3>,<3,1>}, g={<1,2>,<2,3>,<3,3>}，則fg=________________，gf=________________。20．設(shè)A={a,b,c}，R是A上的二元關(guān)系，且給定R={<a,b>,<b,c>,<c,a>}，則R的自反閉包r(R)=________________，對(duì)稱閉包s(R)=________________。21．設(shè)Q為有理數(shù)集，笛卡爾集S=Q×Q，*是S上的二元運(yùn)算，<a,b>,<x,y>∈S,<a,b>*<x,y>=<ax,y+b>,則*運(yùn)算的幺元是________________。<a,b>∈S,若a≠0，則<a,b>的逆元是________________。22．設(shè)*是集合S上的二元運(yùn)算，若運(yùn)算*滿足________________且存在________________，則稱<S，*>為獨(dú)異點(diǎn)。23．令A(yù)={a,b,c}，<A,*>是循環(huán)群，a是單位元，則b2=________________，c的階是________________。24．如下無向圖割點(diǎn)是________________，割邊是________________。25．無向圖G具有生成樹，當(dāng)且僅當(dāng)________________。G的所有生成樹中________________的生成樹稱為最小生成樹。三、計(jì)算題（本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分）26．集合A={a,b,c,d,e}上的二元關(guān)系R為 R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<b,e>, <c,c>,<c,d>,<c,e>,<d,d>,<d,e>,<e,e>} （1）寫出R的關(guān)系矩陣； （2）判斷R是不是偏序關(guān)系，為什么？27．運(yùn)用真值表判斷公式（（P∨Q）∧（Q→R））→（P∧R）是否為重言式。28．給定圖G如下所示，（1）寫出G的可達(dá)矩陣；（2）G中長度為4的路有幾條？29．求下列公式的主析取范式和主合取范式：（P→Q）∧（Q→R）30．設(shè)A為54的因子構(gòu)成的集合，RA×A，x,y∈A,xRyx整除y。畫出偏序集<A,R>的哈斯圖，并求A中的最大元，最小元，極大元，極小元。五、證明題（本大題共3小題，第31、32小題各6分，第33小題8分，共20分）31．設(shè)R是A上的一個(gè)自反關(guān)系，證明：R是一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng)若<a,b>∈R，<a,c>∈R，則<b,c>∈R。32．設(shè)<G，*>是一個(gè)群，x∈G，定義：ab=a*x*b，a,b∈G。證明：<G,>也是一個(gè)群。33．設(shè)圖G是具有6個(gè)結(jié)點(diǎn)，12條邊的無向簡樸圖，證明圖G是漢密爾頓圖。五、應(yīng)用題（本大題共2小題，第34小題8分，第35小題7分，共15分）34．構(gòu)造下面推理的證明。假如今天是星期六，我們就要到頤和園或圓明園去玩。假如頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤和園游人太多，所以我們?nèi)A明園玩。35．n個(gè)城市用k條公路的網(wǎng)絡(luò)連結(jié)。一條公路定義為兩個(gè)城市間的一條不穿過任何中間城市的道路。任意兩個(gè)城市之間至多修一條公路。證明假如k>(n-1)(n-2)，則人們總能通過連結(jié)的公路，在任何兩個(gè)城市間旅行。全國2023年4月自考離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1.設(shè)P：天下大雨,Q：他在室內(nèi)運(yùn)動(dòng),命題“除非天下大雨，否則他不在室內(nèi)運(yùn)動(dòng)”可符合化為（）A.P∧Q B.P→QC.P→Q D.P→Q2.下列命題聯(lián)結(jié)詞集合中，是最小聯(lián)結(jié)詞組的是（）A.{，} B.{，∨，∧}C.{，∧} D.{∧，→}3.下列命題為假命題的是（）A.假如2是偶數(shù)，那么一個(gè)公式的析取范式惟一B.假如2是偶數(shù)，那么一個(gè)公式的析取范式不惟一 C.假如2是奇數(shù)，那么一個(gè)公式的析取范式惟一D.假如2是奇數(shù)，那么一個(gè)公式的析取范式不惟一4.謂詞公式x(P(x)∨yR(y))→Q(x))中變元x是（）A.自由變元 B.約束變元C.既不是自由變元也不是約束變元 D.既是自由變元也是約束變元5.若個(gè)體域?yàn)檎麛?shù)減，下列公式中值為真的是（）A.xy(x+y=0) B.yx(x+y=0) C.xy(x+y=0) D.xy(x+y=0)6.下列命題中不對(duì)的的是（）A.x∈{x}-{{x}} B.{x}{x}-{{x}} C.A={x}∪x,則x∈A且xA D.A-B=A=B7.設(shè)P={x|(x+1)2≤4}，Q={x|x2+16≥5x},則下列選項(xiàng)對(duì)的的是（）A.PQ B.PQC.QP D.Q=P8.下列表達(dá)式中不成立的是（）A.A∪(BC)=(A∪B)(A∪C) B.A∩(BC)=(A∩B)(A∩C)C.(AB)×C=(A×C)(B×C) D.(A-B)×C=(A×C)-(B×C)9.半群、群及獨(dú)異點(diǎn)的關(guān)系是（）A.{群}{獨(dú)異點(diǎn)}{半群} B.{獨(dú)異點(diǎn)}{半群}{群}C.{獨(dú)異點(diǎn)}{群}{半群} D.{半群}{群}{獨(dú)異點(diǎn)}10.下列集合對(duì)所給的二元運(yùn)算封閉的是（）A.正整數(shù)集上的減法運(yùn)算 B.在正實(shí)數(shù)的集R+上規(guī)定為ab=ab-a-b a,b∈R+C.正整數(shù)集Z+上的二元運(yùn)算為xy=min(x,y) x,y∈Z+D.全體n×n實(shí)可逆矩陣集合Rn×n上的矩陣加法11.設(shè)集合A={1，2，3}，下列關(guān)系R中不是等價(jià)關(guān)系的是（）A.R={<1,1>,<2,2>,<3,3>}B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} C.R={<1,1>,<2,2>,<3,3>,<1,2>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函數(shù)中為雙射的是（）A.f：Z→Z,f(j)=j(mod) B.f：N→N,f(j)=C.f：Z→N,f(j)=|2j|+1 D.f：R→R,f(r)=2r-1513.設(shè)集合A={a,b,c}上的關(guān)系如下，具有傳遞性的是（）A.R={<a,c>,<c,a>,<a,b>,<b,a>} B.R={<a,c>,<c,a>} C.R={<a,b>,<c,c>,<b,a>,<b,c>} D.R={<a,a>}14.具有5個(gè)結(jié)點(diǎn)，3條邊的不同構(gòu)的簡樸圖有（）A.2個(gè) B.3個(gè)C.4個(gè) D.5個(gè)15.設(shè)D的結(jié)點(diǎn)數(shù)大于1，D=<V,E>是強(qiáng)連通圖，當(dāng)且僅當(dāng)（）A.D中至少有一條通路 B.D中至少有一條回路C.D中有通過每個(gè)結(jié)點(diǎn)至少一次的通路 D.D中有通過每個(gè)結(jié)點(diǎn)至少一次的回路二、填空題(本大題共10小題，每小題2分，共20分)請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16.設(shè)A={1,2,3}，B={3,4,5}，則AA=___________，AB=___________。17.設(shè)A={1,2,3,4,5}，RA×A，R={<1,2>，<3,4>,<2,2>}，則R的自反閉包r(R)=__________。對(duì)稱閉包t(R)=__________。18.設(shè)P、Q為兩個(gè)命題，德摩根律可表達(dá)為_____________，吸取律可表達(dá)為____________。19.對(duì)于公式x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,當(dāng)論域?yàn)閧1,2}時(shí)，其真值為_____________,當(dāng)論域?yàn)閧0,1,2}時(shí)，其真值為_____________。20.設(shè)f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,則復(fù)合函數(shù),。21.3個(gè)結(jié)點(diǎn)可構(gòu)成_________個(gè)不同構(gòu)的簡樸無向圖，可構(gòu)成________個(gè)不同構(gòu)的簡樸有向圖。22.無向圖G=<V,E>如左所示，則G的最大度Δ(G)=_____________，G的最小度δ(G)=_____________。23.設(shè)圖G<V,E>,V={v1,v2,v3,v4},若G的鄰接矩陣，則deg-(v1)=_________,deg+(v4)=____________。24.格L是分派格，當(dāng)且僅當(dāng)L既不具有與_______同構(gòu)的子格，也不具有與______同格的子格。25.給定集合A={1,2,3,4,5}，在集合A上定義兩種關(guān)系：R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}，則，。三、計(jì)算題（本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分）26.設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，畫出R的關(guān)系圖，并求出A中各元素的等價(jià)類。27.構(gòu)造命題公式（P∨Q）（P∧Q）的真值表。28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q））29.設(shè)A={a,b,c,d,e}，R為A上的關(guān)系，R={<a,d>，<a,c>，<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}∪IA，試畫<A，R>的哈斯圖，并求A中的最大元，最小元，極大元，極小元。30.給定圖G如圖所示，（1）G中長度為4的路有幾條？其中有幾條回路？（2）寫出G的可達(dá)矩陣。四、證明題（本大題共3小題，第31、32題各6分，第33題8分，共20分）31.設(shè)（L，≤）是格，試證明：a,b,c∈L,有a∧（b∨c）≥（a∧b）∨（a∧c）；a∨（b∧c）≤（a∨b）∧（a∨c）。32.設(shè)R是A上的自反和傳遞關(guān)系，如下定義A上的關(guān)系T，使得x,y∈A，<x,y>∈T<x,y>∈R∧(y,x)∈R。證明T是A上的等價(jià)關(guān)系。33.設(shè)有G=<V,E>,V的結(jié)點(diǎn)數(shù)|V|=n，稱該圖為n階圖，若從結(jié)點(diǎn)vi到vj存在路，證明從vi到vj必存在長度小于等于n-1的一條路。五、應(yīng)用題（本大題共2小題，第34題7分，第35題8分，共15分）34.構(gòu)造下面推理的證明。每個(gè)喜歡步行的人都不喜歡坐汽車，每個(gè)人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。35.今要將6人提成3組（每組2個(gè)人）去完畢3項(xiàng)任務(wù)。已知每個(gè)人至少與其余5個(gè)人中的3個(gè)人能互相合作。（1）能否使得每組的2個(gè)人都能互相合作？（2）你能給出幾種不同的分組方案？全國2023年7月自考試題離散數(shù)學(xué)課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．設(shè)P：他聰明，Q：他用功，命題“他雖聰明但不用功”的符號(hào)化對(duì)的的是（）A．P∧Q B．P∧QC．P→Q D．P∨Q2．下面聯(lián)結(jié)詞運(yùn)算不可互換的是（）A．∧ B．→C．∨ D．3．下列命題公式不是重言式的是（）A．Q→（P∨Q） B．（P∧Q）→PC．（P∧Q）∧（P∨Q） D．（P→Q）（P∨Q）4．下列等價(jià)式不對(duì)的的是（）A． B．C． D．5．設(shè)A（x）:x是人，B（x）：x犯錯(cuò)誤，命題“沒有不犯錯(cuò)誤的人”符號(hào)化為（）A． B．B（x））C． D．B(x))6．設(shè)M={x|f1(x)=0},N={x|f2(x)=0}，則方程f1(x)·f2(x)=0的解為（）A．M∩N B．M∪NC．MN D．M-N7．設(shè)A-B=，則有（）A．B= B．B≠C．AB D．AB8．A，B是集合，P（A），P（B）為其冪集，且A∩B=，則P(A)∩P(B)為（）A． B．{}C．{{}} D．{，{}}9．設(shè)集合A={1，2，3，……，10}，下列定義的運(yùn)算關(guān)于集合A是不封閉的是（）A．x*y=max{x,y} B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公約數(shù) D．x*y=LCM{x,y},即x,y的最小公倍數(shù)10．設(shè)H，K是群（G，）的子群，下面代數(shù)系統(tǒng)是（G，）的子群的是（）A．（H∩K，） B．（H∪K，）C．（K-H，） D．（H-K，）11．設(shè)A={1，2，3，4，5}，B={6，7，8，9，10}，以下關(guān)系是從A到B的入射函數(shù)的是（）A．f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}B．f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}C．f={<1,6>,<2,7>,<4,9>,<3,8>}D．f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}12．設(shè)簡樸圖G所有結(jié)點(diǎn)的度數(shù)之和為12，則G一定有（）A．3條邊 B．4條邊C．5條邊 D．6條邊13．下列不一定是樹的是（）A．無回路的連通圖 B．有n個(gè)結(jié)點(diǎn)，n-1條邊的連通圖C．每對(duì)結(jié)點(diǎn)之間都有通路的圖 D．連通但刪去一條邊則不連通的圖14．下面關(guān)于關(guān)系R的傳遞閉包t(R)的描述最確切的是（）A．t(R)是包含R的二元關(guān)系 B．t(R)是包含R的最小傳遞關(guān)系C．t(R)是包含R的一個(gè)傳遞關(guān)系 D．t(R)是任何包含R的傳遞關(guān)系15．歐拉回路是（）A．途徑 B．跡C．既是初級(jí)回路也是跡 D．既非初級(jí)回路也非跡二、填空題（本大題共10小題，每小題2分，共20分） 請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16．設(shè)A={1，2}，B={2，3}，則AA=__________，AB=__________。17．設(shè)A={1，2，3，4}上關(guān)系R={<1,2>,<2,4>,<3,3>,<1,3>}，則R的自反閉包r(R)=_________，對(duì)稱閉包S（R）=__________。18．命題公式（PQ）→P的成真指派為__________，成假指派為__________。19．公式（）（F（x）→G(y)）→()(H(x))中的自由變元為_________，約束變元為__________。20．設(shè)f:R→R,f(x)=x2-2,g:R→R,g(x)=x-1,那么復(fù)合函數(shù)=__________，=__________。21．有理數(shù)集Q中的*運(yùn)算定義如下：a*b=a+b-ab，則*運(yùn)算的單位元是__________，設(shè)a有逆元，則其逆元a-1=__________。22．設(shè)A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)=__________。23．如下圖的有補(bǔ)格中，c的補(bǔ)元是__________，b的補(bǔ)元是__________。24．在根樹中，若每一個(gè)結(jié)點(diǎn)的出度__________m,則稱這棵樹為m叉樹。假如每一個(gè)結(jié)點(diǎn)的出度__________m或0，則稱這棵樹為完全m叉樹。25．<Zn,>是一個(gè)群，其中Zn={0,1,2,……,n-1},xy=(x+y)modn，則在<Z6,>中，1的階是__________，4的階是__________。三、計(jì)算題（本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分）26．構(gòu)造命題公式（）→PR的真值表。27．若集合A={1，{2，3}}的冪集為P（A），集合B={{，2}，{2}}的冪集為P（B），求P(A)∩P(B)。28．設(shè)X={1，2，3，4}，R是X上的二元關(guān)系，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。（1）畫出R的關(guān)系圖；（2）寫出R的關(guān)系矩陣；（3）說明R是否具有自反、反自反、對(duì)稱、傳遞性質(zhì)。29．求下列公式的主析取范式和主合取范式：（P→（QR））（P→（Q→R））。30．設(shè)A={a,b,c},P(A)是A的冪集，R為A上的包含關(guān)系，試給出<P(A),R>的哈斯圖，并給出子集{{a,b},{a,c},{c}}的極大元、極小元、最大元、最小元。四、證明題（本大題共3小題，第31、32小題各6分，第33小題8分，共20分）31．設(shè)H是形如的2×2階矩陣的集合，H中定義通常的矩陣乘法運(yùn)算。驗(yàn)證H是群，=。32．設(shè)R為N×N上的二元關(guān)系，∈N×N，證明R為等價(jià)關(guān)系。33．簡樸圖G有n個(gè)結(jié)點(diǎn)，m條邊，設(shè)m>(n-1)(n-2)，證明：G是連通的。五、應(yīng)用題（本大題共2小題，第34小題7分，第35小題8分，共15分）34．構(gòu)造下面推理的證明。只要A曾到過受害者房間并且11點(diǎn)以前沒離開，A就犯了謀殺罪。A曾到過受害者房間。假如在11點(diǎn)以前離開，看門人會(huì)看見他?？撮T人沒有看見他。所以A犯了謀殺罪。35．在某次國際會(huì)議的預(yù)備會(huì)中，共有8人參與，他們來自不同的國家。已知他們中任何兩個(gè)無共同語言的人中的每一個(gè)，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。全國2023年4月自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1．下列為兩個(gè)命題變元P，Q的小項(xiàng)是（）A．P∧Q∧P B．P∨QC．P∧Q D．P∨P∨Q2．下列語句中是真命題的是（）A．我正在說謊 B．嚴(yán)禁吸煙C．假如1+2=3，那么雪是黑的 D．假如1+2=5，那么雪是黑的3．設(shè)P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號(hào)化為（）A．P∧Q B．P∨QC．（PQ） D．（P∨Q）4．命題公式（P∧（P→Q））→Q是（）A．矛盾式 B．蘊(yùn)含式C．重言式 D．等價(jià)式5．命題公式（P∧Q）→R的成真指派是（）A．000，001，110， B．001，011，101，110，111C．全體指派 D．無6．在公式（）F（x，y）→（y）G（x，y）中變元x是（）A．自由變元 B．約束變元C．既是自由變元，又是約束變元 D．既不是自由變元，又不是約束變元7．集合A={1，2，…，10}上的關(guān)系R={<x，y>|x+y=10，x∈A，y∈A}，則R的性質(zhì)是（）A．自反的 B．對(duì)稱的C．傳遞的、對(duì)稱的 D．反自反的、傳遞的8．若R和S是集合A上的兩個(gè)關(guān)系，則下述結(jié)論對(duì)的的是（）A．若R和S是自反的，則R∩S是自反的B．若R和S是對(duì)稱的，則RS是對(duì)稱的C．若R和S是反對(duì)稱的，則RS是反對(duì)稱的D．若R和S是傳遞的，則R∪S是傳遞的9．R={<1，4>，<2，3>，<3，1>，<4，3>}，則下列不是t（R）中元素的是（）A．<1，1> B．<1，2>C．<1，3> D．<1，4>10．設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列選項(xiàng)對(duì)的的是（）A．1∈A B．{1，2，3}AC．{{4，5}}A D．∈A11．在自然數(shù)集N上，下列運(yùn)算是可結(jié)合的是（）A．a(chǎn)b=a-2b B．a(chǎn)b=min{a，b}C．a(chǎn)b=-a-b D．a(chǎn)b=|a-b|12．在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系是（）A．整環(huán)一定是域 B．域不一定是整環(huán)C．域一定是整環(huán) D．域一定不是整環(huán)13．下列所示的哈斯圖所相應(yīng)的偏序集中能構(gòu)成格的是（）A． B．C． D．14．設(shè)G為有n個(gè)結(jié)點(diǎn)的簡樸圖，則有（）A．Δ(G)＜n B．Δ(G)≤nC．Δ(G)＞n D．Δ(G)≥n15．具有4個(gè)結(jié)點(diǎn)的非同構(gòu)的無向樹的數(shù)目是（）A．2 B．3C．4 D．5二、填空題（本大題共10小題，每小題2分，共20分） 請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的轄域?yàn)開_______，x的轄域?yàn)開_______。17．兩個(gè)重言式的析取是________式，一個(gè)重言式與一個(gè)矛盾式的析取是________式。18．設(shè)N是自然數(shù)集合，f和g是N到N的函數(shù)，且f（n）=2n+1，g（n）=n2，那么復(fù)合函數(shù)（ff）（n）=________（gf）（n）=________。19．設(shè)復(fù)合函數(shù)gf是從A到C的函數(shù)，假如gf是滿射，那么________必是滿射，假如gf是入射，那么________必是入射。20．設(shè)A={1，2}，B={2，3}，則A-A=________，A-B=________。21．設(shè)S是非空有限集，代數(shù)系統(tǒng)<P（S），∪>中，其中P（S）為集合S的冪集，則P（S）對(duì)∪運(yùn)算的單位元是________，零元是________。22．在<Z6,eq\o\ac(○,+)>中，2的階是________。23．設(shè)<A，≤>是格，其中A={1，2，3，4，6，8，12，24}，≤為整除關(guān)系，則3的補(bǔ)元是________。24．在下圖中，結(jié)點(diǎn)v2的度數(shù)是________。25．________，從v2到v4長度為2的路有________條。三、計(jì)算題（本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分）26．已知A={{}，{，1}}，B={{，1}，{1}}，計(jì)算A∪B，Aeq\o\ac(○,+)B，A的冪集P（A）。27．構(gòu)造命題公式（（P∧Q）→P）∨R的真值表。28．29．求下列公式的主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））30．設(shè)A={1，2，3，4，6，8，12，24}，R為A上的整除關(guān)系，試畫<A，R>的哈斯圖，并求A中的最大元、最小元、極大元、極小元。四、證明題（本大題共3小題，第31、32小題各6分，第33小題8分，共20分）31．在整數(shù)集Z上定義：，證明：<Z，>是一個(gè)群。32．R是集合A上自反和傳遞的關(guān)系，試證明：RR=R。33．證明：邊e是圖G的一條割邊，當(dāng)且僅當(dāng)圖G中不存在包含邊e的簡樸回路。五、應(yīng)用題（本大題共2小題，第34小題6分，第35小題9分，共15分）34．構(gòu)造下面推理的證明。假如小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。35．今有n個(gè)人，已知他們中任何2人的朋友合起來一定包含其余n-2人。試證明：（1）當(dāng)n≥3時(shí)，這n個(gè)人能排成一列，使得中間任何人是其兩旁的人的朋友，而兩頭的人是其左邊（或右邊）的人的朋友。（2）當(dāng)n≥4時(shí)，這n個(gè)人能排成一圓圈，使得每個(gè)人是其兩旁的人的朋友。全國2023年7月自考離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目規(guī)定的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1.下列句子為命題的是()A.走，看電影去 B.x+y>0C.空集是任意集合的真子集 D.你明天能來嗎?2.下列式子不是謂詞合式公式的是()A.(x)(P(x)→(x)(Q(x)∧A(x，y))) B.(x)∧(y)∨P(x，y)C.(x)P(x)→R(y) D.(x)P(x)∧Q(y，z)3.下列式子為重言式的是()A.P→P∨Q B.(﹁P∧Q)∧(P∨﹁Q)C.﹁(PQ) D.(P∨Q)(P→Q)4.設(shè)個(gè)體域?yàn)閷?shí)數(shù)集，特定元素a=0，函數(shù)f(x，y)=x-y，特定謂詞F(x，y)為x<y，下列公式真值為真的是()A.(x)(y)F(x，f(f(x，y)，y))B.(x)(y)(﹁F(f(x，y)，x))C.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z)))D.(x)F(f(a，x)，a)5.對(duì)于公式(x)(y)P(x，y)∨Q(x，z)∧(x)P(x，y)，下列說法對(duì)的的是()A.x是自由變元 B.x是約束變元C.(x)的轄域是P(x，y)∨Q(x，z) D.(x)的轄域是P(x，y)6.設(shè)論域?yàn)閧1，2}，與公式(x)﹁A(X)等價(jià)的是()A.﹁A(1)∨﹁A(2) B.﹁A(1)→﹁(A2)C.﹁A(1)∧﹁A(2) D.A(1)→A(2)7.設(shè)Z+是正整數(shù)集，f：Z+×Z+→Z+，f(n，m)=nm，則f()A.僅是入射 B.僅是滿射C.是雙射 D.不是函數(shù)8.下列哪個(gè)關(guān)系矩陣所相應(yīng)的關(guān)系具有自反性()A. B.C. D.9.設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)系哪個(gè)也許不是相容關(guān)系()A.R1R2 B.RlR2C.R1-1 D.RlR210.在整數(shù)集上，下面哪個(gè)運(yùn)算不是二元運(yùn)算()A.加法 B.減法C.乘法 D.除法11.設(shè)A是奇數(shù)集合，×為乘法運(yùn)算，則<A，×>是()A.半群 B.群C.循環(huán)群 D.互換群12.下面不滿足結(jié)合律的運(yùn)算是()A.a*b=min(a，b) B.a*b=max(a，b)C.a*b=2(a+b) D.a*b=2ab13.右圖的最小入度是()A.0B.1C.2D.314.下面既是漢密爾頓圖又是歐拉圖的圖形是()15.一棵樹有3個(gè)5度點(diǎn)、1個(gè)4度點(diǎn)、3個(gè)2度點(diǎn)，其它的都是1度，那么它的邊數(shù)是()A.17 B.18C.19 D.20二、填空題(本大題共10小題，每小題2分，共20分)請?jiān)诿啃☆}的空格中填上對(duì)的答案。錯(cuò)填、不填均無分。16.設(shè)命題變元為P，Q，R，則小項(xiàng)m100=________，大項(xiàng)M010=________。17.置換規(guī)則：在證明的任何環(huán)節(jié)上，命題公式中的任何子命題公式都可以________，記為________規(guī)則。18.一個(gè)公式，假如量詞均在全式的________，其作用域延伸到整個(gè)公式的________，則該公式稱為前束范式。19.請用聯(lián)結(jié)詞﹁，∧表達(dá)聯(lián)結(jié)詞∨和聯(lián)結(jié)詞：________，________。20.設(shè)A={l，2，3，4}，A上的二元關(guān)系R={<1，2>，<3，4>，<4，3>}，S={<l，3>，<3，4>，<4，1>}，則R～S=________，(RS)-1=________。21.代數(shù)系統(tǒng)<A，*，>是整環(huán)，則<A，*>是________，<A，>是________，且無零因子。22.在實(shí)數(shù)集R上定義運(yùn)算ab=a+b+ab，則幺元為________，元素2的逆元為________。23.若回路中，除________外________各不相同，則此回路稱為圈(或初級(jí)回路)。24.偶圖記為Kn,m那么當(dāng)________時(shí)，Kn,m是平面圖，當(dāng)________時(shí)，Kn,m是非平面圖。25.若圖中存在________，它通過圖中所有的邊恰好________次，則稱該圖為歐拉圖。三、計(jì)算題(本大題共6小題，每小題5分，共30分)26.用等值演算求(P→Q)→R的主合取范式。27.列出(P→(Q∨R))(P→Q)的真值表。28．設(shè)A={a,b,c,d}，R={<a，b>，<a，d>，<b，c>，<c，a>，<d，a>}，求R的傳遞閉包。29.設(shè)A={2，3，6，12，24，36}，請畫出A上整除關(guān)系的哈斯圖，并給出子集{6，1