離散數(shù)學AB卷

1、離散數(shù)學黃金AB卷A卷一、選擇題：（30分）1、取個體域為整數(shù)集，給定下列公式（1）xy（x*y=0）（2）xy（x*y=1）（3）yx（x*y=2）（4）xy z（x y = z）（5）x y = - y + x（6）xy（x *y = y）（7）x（x*y = x）（8）xy（x + y = 2y）在上面的公式中，真命題的為A ，假命題的為B 。A：（1）、（3）、（4）、（6）；（3）、（4）、（5）； （1）、（3）、（4）、（5）；（3）、（4）、（6）、（7）B：（2）、（3）、（6）；（2）、（6）、（8）； （1）、（2）、（6）、（7）；（2）、（6）、（8）、（7）2、設(shè)S

2、1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5。確定在以下條件下X可能與S1,S5中哪個集合相等。（1）若XS5 = ，則A ；（2）若XS4但XS2 = ，則B ；（3）若XS1但XS3，則C ；（4）若X - S3= ，則D ；（5）若XS3但XS1，則E ；A、B、C、D、E：X=S2或者S3；X= S4或者S5；X=S1，S2或者S4；X與其中任何集合都不等；X=S2；X=S5；X=S3或者S5；X=S2或者S4；3、（1）設(shè)S=1，2，R為S上的二元關(guān)系，且xRy。如果R=Is，則A ；如果R是數(shù)的小于等于關(guān)系，則B ；如果R=Es

3、，則C 。（2）設(shè)有序?qū)?lt; x+2，4 > 與有序?qū)?lt;5，2x+y >相等，則x=D ，y=E 。A、B、C：x與y可任意選擇1或2；x=1，y=1；x=1，y=1或2；x=y=2；x=2，y=2；x=y=1或x=y=2；x=1，y=2；x=2，y=1；D、E：3；9； -24、設(shè)S=<1，2，3，4>，R為S上的關(guān)系，其關(guān)系矩陣是，則（1）R的關(guān)系表達式是A ；（2）domR=B ；ranR=C ；（3）RR中有D 個有序?qū)?；?）R-1的關(guān)系圖中有E 個環(huán)。A：<1，1>，<1，2>，<1，4>，<4，1>

4、，<4，3>；<1，1>，<1，4>，<2，1>，<4，1>，<3，4>；B、C：1，2，3，4；1，2，4；1，4；1，3，4；D、E：1；3；6；75、在有理數(shù)集合Q上定義二元運算*，x，yQ有 x * y = x + y - xy則（1）2*（-5）=A ，7*1/2 = B 。（2）*在Q上是C ；（3）關(guān)于*的幺元是D ；（4）Q中滿足E ；A、B：4；7；-13；C：可結(jié)合的；不可結(jié)合的；D：1；0；E：所有的元素都有逆元；只有唯一的逆元；xQ，x1時，有逆元x-1。6、下圖給出一個格L，則（1）L是A 元格；

5、（2）L是B ；（3）b的補元是C ，a的補元是D ，1的補元是E 。A：5；6；B：分配格；有補格；布爾格；以上都不對；C、D、E：不存在；c和d；0；c；7、6個頂點11條邊的所有可能的非同構(gòu)的連通的簡單的非平面圖有A 個，其中有B 個含子圖K33，有C 個含與K5同胚的子圖。A、B、C：1；2；3；4；5；6；7；8；二、填空題：（20分）1、設(shè)p=1，q=0，r=1，s=0，有下列命題公式（1）（pq）（sr）（2）（pqrs）(sq)（3）（pqr）（ps）那么，（1）的真值為 ；（2）的真值為 ；（3）的真值為 ；2、已知命題公式A含有3個命題變項，其成真賦值為000，010，10

6、0，110。則A的主析取范式為 ，主合取范式為 。3、設(shè)S=1，2，3，定義S×S上的等價關(guān)系R，<a，b>，<c，d>S×S有：<a，b><c，d>a + d = b + c則由R產(chǎn)生了S×S的一個劃分。在該劃分中共有 個劃分塊，其中最大的塊有 個元素，并且含有元素 。最小的劃分塊有 塊，每塊含有 個元素。4、設(shè)V1=<1，2，3，1>，其中xy表示取x和y之中較大的數(shù)，V2=<5，6，*，6>，其中x*y表示取x和y之中較小的數(shù)。（1）V1含有 個子代數(shù)，其中平凡的真子代數(shù)有 個；V2含有

7、 個平凡的子代數(shù)。（2）積代數(shù)V1×V2中有 個元素，其幺元是 。5、在下面所示的各圖中， 為歐拉圖， 為哈密頓圖。6、在下面所示的各圖中，是二部圖的為 ，在二部圖中存在完美匹配的是 ，它的匹配數(shù)是 。三、判斷下列句子中哪些是命題（5分）（1）2是素數(shù)（2）血是黑色的（3）明年10月1日是晴天（4）這朵花多好看呀！（5）X + y > 5四、求下面命題公式的主析取范式和主合取范式（6分）（pq）r）p 五、一公安人員審查一件盜竊案，已知的事實如下：（1）甲或乙盜竊了錄音機（2）若甲盜竊了錄音機，則作案時間不能發(fā)生在午夜前（3）若乙的證詞正確，則午夜時屋里燈光未滅（4）若乙的證詞

8、不正確，則作案時間發(fā)生在午夜前（5）午夜時屋里燈光滅了推理證明，誰盜竊了錄音機。（6分）六、將下列語句用謂詞表達式符號化（4分）（1）如果2大于3，則2大于4（2）沒有不吃飯的人（3）有些人喜歡所有的花（4）凡是對頂角都相等七、設(shè)A=1，2，3，11，12，R為A上整除關(guān)系，畫出哈斯圖。（6分）八、對于給定集合A和B，構(gòu)造從A到B的雙射函數(shù)。（4分） A=Z，B=N，其中Z，N分別表示整數(shù)集和自然數(shù)集；九、設(shè)R的關(guān)系圖如所示，試給出r（R）、s（R）、t（R）的關(guān)系圖。（4分）十、設(shè)A=1，2，3，4，5，<P（A），>構(gòu)成群，其中為集合的對稱差。（6分）（1）求解方程1，3X=3

9、，4，5；（2）令B=1，4，5，求由B生成的循環(huán)子群<B>；十一、一個n（n2）階無向簡單圖G中，n為奇數(shù)，已知G中有r 個奇數(shù)度頂點，問G的補圖中有幾個奇數(shù)度頂點？（5分）12、 畫出度數(shù)列為1，1，1，1，2，2，4的所有非同構(gòu)的7階無向樹。（4分）A卷答案一、選擇題：（30分）1、A：；B：；2、A：；B：；C：；D：；E：；3、A：；B：；C：；D：；E：；4、A：；B：；C：；D：；E：；5、A：；B：；C：；D：；E：；6、A：；B：；C：；D：；E：；7、A：；B：；C：；二、填空題：（20分）1、（1）1；（2）1；（3）0；2、主析取范式為 m0m2m4m6；主

10、合取范式為 M1M3M5M7；3、5；3；<1，1>，<2，2>，<3，3>；2；1；4、（1）4；2；2；（2）6；<1，6>；5、（c）、（e）為歐拉圖；（b）、（c）、（d）、（e）、（f）為哈密頓圖；6、二部圖的為（c）、（d）、（e）；完美匹配的是（d）；3；三、是命題：（1）、（2）、（3）；不是命題（4）、（5）；四、主析取范式：m2m4m5m6m7；或者：（pqr）（pqr）（pqr）（pqr）（pqr）主合取范式：M0M1M3；或者：（pqr）（pqr）（pqr）五、p：甲盜竊了錄音機；q：乙盜竊了錄音機；r：作案時間發(fā)生在午夜

11、前；s：乙的證詞正確；t：午夜時屋里燈光滅；則前提為：pq；pr；st；sr；t；推理過程：（1）t 前提（2）st 前提（3）s （1）（2）（4）sr 前提（5）r （3）（4）（6）pr 前提（7）p （5）（6）（8）pq 前提（9）q （7）（8）結(jié)論為：乙盜竊了錄音機六、 （1）p（x，y）：表示x大于y；a=2；b=3；c=4；p（a，b）p（a，c）（2）m（x）：x是人； e（x）：x吃飯；x（m（x）e（x）或者（x（m（x）e（x）（3）m（x）：x是人；h（x）：x是花；p（x，y）：x喜歡y；x（m（x）y（h（y）p（x，y）（4）p（x，y）：x與y是對頂角，q（

12、x，y）：x與y相等；xy（p（x，y）q（x，y）七、8、 f：ZN，f（x）=9、十、（1）由于<P（A），>構(gòu)成群，群方程ax=b在群中有唯一解x=a-1b；方程1，3X=3，4，5，有X=1，3-13，4，5=1，33，4，5=1，4，5（2）由于對任何BP（A）有BB=，因此Bn=B（n為奇數(shù)）或者Bn=（n為偶數(shù)）；所以，由B生成的循環(huán)子群為1，4，5，十一、對于n個頂點的完全圖，n個頂點的度數(shù)均為n-1，由于n為奇數(shù)，正好n-1為偶數(shù)；由于G中有r 個奇數(shù)度頂點，所以，補圖中有r個奇數(shù)度頂點。十二、B卷一、選擇題：（30分）1、給定語句如下：（1）15是素數(shù)（2）10

13、能被2整除，3是偶數(shù)（3）你下午有會嗎？（4）2x+3> 0（5）2是素數(shù)或是合數(shù)（6）這個男孩真勇敢呀?。?）如果2+2=6，則5是奇數(shù)（8）只有4是偶數(shù)，3才能被2整除（9）明年5月1日是晴天（10）圓的面積等于半徑的平方與的乘積以上10個語句中，是簡單命題的為A ，是復(fù)合命題的為B ，是真命題的為C ，是假命題的為D ，真值待定（真值客觀存在，只是現(xiàn)在不知道）的命題為E 。A：（1）、（4）、（8）（4）、（6）、（9）、（10）（1）、（9）、（10）B：（3）、（10）（2）、（5）、（7）、（8）（7）、（8）C：（2）、（5）、（9）、（10）（7）、（8）、（10）（2）

14、、（9）、（10）（5）、（7）、（8）、（10）D：（1）、（2）、（8）（1）、（2）（1）、（5）E：（4）、（9）（9）（7）、（8）2、設(shè)S=1，2，則S上可定義A 個不同的二元關(guān)系，其中B 個等價關(guān)系，C 個偏序關(guān)系，Is是D 。A、B、C：1；2；3；4；8；16D：等價關(guān)系但不是偏序關(guān)系；偏序關(guān)系但不是等價關(guān)系；等價關(guān)系和偏序關(guān)系；既不是等價關(guān)系也不是偏序關(guān)系；3、設(shè)S=1，2，9，10，是S上的整除關(guān)系，則<S, >的哈斯圖是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。A：一棵樹；一條鏈；以上都不對；B、C、D、E：；1；10；6，7，8

15、，9，10；6；0；不存在4、設(shè)Z+=x|xZx>0，*表示求兩個數(shù)的最小公倍數(shù)的運算，則（1）4*6=A ；（2）*在Z+上B ；（3）對于*運算的幺元是C ，零元是D ；（4）在Z+中E ；A：24；12；B：只滿足交換率；只滿足結(jié)合律；滿足交換率、結(jié)合律和冪等律；C、D：0；1；不存在；E：不存在逆元；只有唯一的逆元5、對以下定義的集合和運算判斷它們是不是代數(shù)系統(tǒng)。如果是，是哪一種？（1）S1=1，1/2，2，1/3，3，1/4，4，*為普通乘法，則S1是A ；（2）S2=a1，a2，an，n2，aiR，i=1，2，n， ai，ajS2，有aiaj=ai，則S2是B ；（3）S3=

16、0，1，*為普通乘法，則S3是C ；（4）S4=1，2，3，6，為整除關(guān)系，則S4是D ；（5）S5=0，1，+、*分別為模2加法和乘法，則S5是E 。A、B、C、D、E：半群，但不是獨異點；是獨異點，但不是群；群；環(huán)，但不是域；域；格，但不是布爾代數(shù)；布爾代數(shù)；代數(shù)系統(tǒng)，但不是以上7種；不是代數(shù)系統(tǒng)；6、給定有向帶權(quán)圖如圖所示，圖中b到a的最短路徑的權(quán)為A ；b到d的最短路徑的權(quán)為B ；b 到e的最短路徑的權(quán)為C ；b到g的最短路徑的權(quán)為D ；A、B、C、D：4；5；6；7；8；9；10；7、（1）非同構(gòu)的無向的4階自補圖有A 個；（2）非同構(gòu)的無向的5階自補圖有B 個；A、B：0；1；2；

17、3；二、填空題：（20分）1、給定命題公式如下：（pq）（pq）該命題公式的主析取范式中含極小項的個數(shù)為 ，主合取范式中含極大項的個數(shù)為 ，成真賦值個數(shù)為 ，成假賦值個數(shù)為 。2、對于下面的語句，（1）只要43，就有32。真值是 。（3）只有43，才有32。真值是 。（6）43僅當32。真值是 。（7）43當且僅當32。真值是 。3、下列命題（1）；（2）；（3）；（4）正確的是 ；錯誤的是 。4、設(shè)A、B為集合，（1）A B = B，成立的充分必要條件是 ；（2）A B = B - A，成立的充分必要條件是 ；（3）AB = AB，成立的充分必要條件是 ；5、設(shè)S=a，b，則S上可以定義 個

18、二元運算，其中有4個運算f1，f2，f3，f4，其運算表如下：則只有 滿足交換律， 滿足冪等律， 有幺元， 有零元。6、下列各組數(shù)中，哪些 能構(gòu)成無向圖的度數(shù)列？哪些 能構(gòu)成無向簡單圖的度數(shù)列？（1）1，1，1，2，3；（2）2，2，2，2，2；（3）3，3，3，3；（4）1，2，3，4，5；（5）1，3，3，3；三、將下列命題符號化（6分）（1）2是素數(shù)和偶數(shù)（2）李芳學過英語或日語（3）小王是游泳冠軍或者百米賽跑冠軍（4）小王現(xiàn)在在宿舍或者在圖書館（5）如果明天天氣好，我們?nèi)ソ加?。否則，不去郊游（6）你愛我，我就嫁給你四、利用真值表求主析取范式和主合取范式（4分）（pq）r五、指出下列各合

19、式公式中的指導變項、量詞的轄域、個體變項的自由出現(xiàn)和約束出現(xiàn)。（6分）（1）x（F（x）yH（x，y）（2）x F（x）G（x，y）六、計算以下冪集（6分）（1）P（）；（3）P（，）；七、設(shè)A=1，2，3，求出A上的所有的等價關(guān)系（4分）八、設(shè)S=1，2，9，10，問下面定義的二元運算*是否為S上的二元運算？（5分）（1）x*y = gcd（x，y），x與y的最大公約數(shù)；（2）x*y = lcm（x，y），x與y的最小公倍數(shù)；（3）x*y =大于等于xy的最小整數(shù)；（4）x*y =max（x，y）；（5）x*y =質(zhì)數(shù)P的個數(shù)，其中xpy。九、設(shè)<B，0，1>是布爾代數(shù)，（1）a

20、，bB，公式f為b（a（a（bb）,在B中化簡f；（2）在B中等式（ab）（ab）=0 成立的條件是什么？（5分）十、畫出3個頂點2條邊的所有可能非同構(gòu)的有向簡單圖；（4分）十一、某中學有3個課外小組：物理組、化學組、生物組。今有張、王、李、趙、陳5名同學。若已知：（1）張、王為物理組成員，張、李、趙為化學組成員，李、趙、陳為生物組成員；（2）張為物理組成員，王、李、趙為化學組成員，王、李、趙、陳為生物組成員；（3）張為物理組和化學組成員，王、李、趙、陳為生物組成員；問在以上3中情況下能否各選出3名不兼職的組長？（5分）十二、求帶權(quán)為2、3、5、7、8、8的最優(yōu)二元樹；（5分）B卷答案一、選擇

21、題：（30分）1、 A：；B：；C：；D：；E：；2、 A：；B：；C：；D：；3、 A：；B：；C：；D：；E：；4、 A：；B：；C：；D：；E：；5、 A：；B：；C：；D：；E：；6、 A：；B：；C：；D：；7、 A：；B：；二、填空題：（20分）1、極小項的個數(shù)3；極大項的個數(shù)1；3；1；2、（1）1；（2）0；（3）0；（4）0；3、正確的是（1）、（3）、（4）；錯誤的是（2）；4、（1）A = B =；（2）A = B；（3）A = B；5、16；f1、f2、f3；f4；f2；f1；6、（1）、（2）、（3）、（5）；（1）、（2）、（3）；三、將下列命題符號化（6分）（1）p：2是素數(shù)；q：2是偶數(shù)；pq；（2）p：李芳學過英語；q：李芳學過日語；可兼或；pq；（3）p：小王是游泳冠軍；q：小王是百米賽跑冠軍；可兼或；pq；（4）p：小王現(xiàn)在在宿舍；q：小王現(xiàn)在在圖書館；不可兼或；（pq）；（5）p：明天天氣好；q：我們?nèi)ソ加?；（pq）（pq）；（6）p：你愛我；q：我就嫁給你；pq；主析取范式為：m7m6m5m3m1；主合