離散數(shù)學(xué)AB卷.doc

《離散數(shù)學(xué)AB卷.doc》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)AB卷.doc（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

離散數(shù)學(xué)黃金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è)S1=｛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）若X∩S5 = ，則A ； （2）若XS4但X∩S2 = ，則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，則C 。 （2）設(shè)有序?qū)? x+2，4 > 與有序?qū)?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；⑩ -2 4、設(shè)S=<1，2，3，4>，R為S上的關(guān)系，其關(guān)系矩陣是 ， 則（1）R的關(guān)系表達(dá)式是A ； （2）domR=B ；ranR=C ； （3）RR中有D 個有序?qū)Γ? （4）R-1的關(guān)系圖中有E 個環(huán)。 A：①｛<1，1>，<1，2>，<1，4>，<4，1>，<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；⑩7 5、在有理數(shù)集合Q上定義二元運(yùn)算*，x，y∈Q有 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：⑧所有的元素都有逆元；⑨只有唯一的逆元； ⑩x∈Q，x1時，有逆元x-1。 6、下圖給出一個格L，則 （1）L是A 元格； （2）L是B ； （3）b的補(bǔ)元是C ，a的補(bǔ)元是D ，1的補(bǔ)元是E 。 A：①5；②6； B：③分配格；④有補(bǔ)格；⑤布爾格；⑥以上都不對； C、D、E： ⑦不存在；⑧c和d；⑨0；⑩c； 7、6個頂點(diǎn)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）（p∧q）→（s∧r） （2）（p∧q∧r∧s）∨(s→q) （3）（p∧q∧r）（p∨s） 那么，（1）的真值為 ；（2）的真值為 ；（3）的真值為 ； 2、已知命題公式A含有3個命題變項，其成真賦值為000，010，100，110。 則A的主析取范式為 ，主合取范式為 。 3、設(shè)S=｛1，2，3｝，定義S×S上的等價關(guān)系R， ，∈S×S有：～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含有 個平凡的子代數(shù)。 （2）積代數(shù)V1×V2中有 個元素，其幺元是 。 5、在下面所示的各圖中， 為歐拉圖， 為哈密頓圖。 6、在下面所示的各圖中，是二部圖的為 ，在二部圖中存在完美匹配的是 ，它的匹配數(shù)是 。 三、判斷下列句子中哪些是命題（5分） （1）2是素數(shù) （2）血是黑色的 （3）明年10月1日是晴天 （4）這朵花多好看呀！ （5）X + y > 5 四、求下面命題公式的主析取范式和主合取范式（6分） （（p∨q）→r）→p 五、一公安人員審查一件盜竊案，已知的事實(shí)如下： （1）甲或乙盜竊了錄音機(jī) （2）若甲盜竊了錄音機(jī)，則作案時間不能發(fā)生在午夜前 （3）若乙的證詞正確，則午夜時屋里燈光未滅 （4）若乙的證詞不正確，則作案時間發(fā)生在午夜前 （5）午夜時屋里燈光滅了 推理證明，誰盜竊了錄音機(jī)。（6分） 六、將下列語句用謂詞表達(dá)式符號化（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｝，構(gòu)成群，其中為集合的對稱差。（6分） （1）求解方程｛1，3｝X=｛3，4，5｝； （2）令B=｛1，4，5｝，求由B生成的循環(huán)子群； 十一、一個n（n≥2）階無向簡單圖G中，n為奇數(shù)，已知G中有r 個奇數(shù)度頂點(diǎn)，問G的補(bǔ)圖中有幾個奇數(shù)度頂點(diǎn)？（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、 主析取范式為 m0∨m2∨m4∨m6； 主合取范式為 M1∧M3∧M5∧M7； 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）； 四、主析取范式：m2∨m4∨m5∨m6∨m7； 或者：（p∧q∧r）∨（p∧q∧r）∨（p∧q∧r）∨（p∧q∧r）∨（p∧q∧r） 主合取范式：M0∧M1∧M3； 或者：（p∨q∨r）∧（p∨q∨r）∧（p∨q∨r） 五、 p：甲盜竊了錄音機(jī)；q：乙盜竊了錄音機(jī)；r：作案時間發(fā)生在午夜前；s：乙的證詞正確；t：午夜時屋里燈光滅； 則前提為： p∨q；p→r；s→t；s→r；t； 推理過程： （1）t 前提 （2）s→t 前提 （3）s （1）（2） （4）s→r 前提 （5）r （3）（4） （6）p→r 前提 （7）p （5）（6） （8）p∨q 前提 （9）q （7）（8） 結(jié)論為：乙盜竊了錄音機(jī) 六、 （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（x，y）：x與y相等； xy（p（x，y）→q（x，y）） 七、 8、 f：Z→N，f（x）= 9、 十、 （1）由于構(gòu)成群，群方程ax=b在群中有唯一解x=a-1b； 方程｛1，3｝X=｛3，4，5｝，有 X=｛1，3｝-1｛3，4，5｝=｛1，3｝｛3，4，5｝=｛1，4，5｝ （2）由于對任何B∈P（A）有BB=，因此Bn=B（n為奇數(shù)）或者Bn=（n為偶數(shù)）； 所以，由B生成的循環(huán)子群為｛｛1，4，5｝，｝ 十一、 對于n個頂點(diǎn)的完全圖，n個頂點(diǎn)的度數(shù)均為n-1，由于n為奇數(shù)，正好n-1為偶數(shù)； 由于G中有r 個奇數(shù)度頂點(diǎn)，所以，補(bǔ)圖中有r個奇數(shù)度頂點(diǎn)。 十二、 B卷 一、選擇題：（30分） 1、給定語句如下： （1）15是素數(shù) （2）10能被2整除，3是偶數(shù) （3）你下午有會嗎？ （4）2x+3> 0 （5）2是素數(shù)或是合數(shù) （6）這個男孩真勇敢呀！ （7）如果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）、（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；⑥16 D： ⑦等價關(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)系，則的哈斯圖是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。 A：①一棵樹；②一條鏈；③以上都不對； B、C、D、E： ④；⑤1；⑥10；⑦6，7，8，9，10；⑧6；⑨0；⑩不存在 4、設(shè)Z+=｛x|x∈Z∧x>0｝，*表示求兩個數(shù)的最小公倍數(shù)的運(yùn)算，則 （1）4*6=A ； （2）*在Z+上B ； （3）對于*運(yùn)算的幺元是C ，零元是D ； （4）在Z+中E ； A：①24；②12； B：③只滿足交換率；④只滿足結(jié)合律； ⑤滿足交換率、結(jié)合律和冪等律； C、D：⑥0；⑦1；⑧不存在； E：⑨不存在逆元；⑩只有唯一的逆元 5、對以下定義的集合和運(yùn)算判斷它們是不是代數(shù)系統(tǒng)。如果是，是哪一種？ （1）S1=｛1，1/2，2，1/3，3，1/4，4｝，*為普通乘法，則S1是A ； （2）S2=｛a1，a2，…，an｝，n≥2，ai∈R，i=1，2，…，n， ai，aj∈S2，有aiaj=ai，則S2是B ； （3）S3=｛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： ①半群，但不是獨(dú)異點(diǎn)；②是獨(dú)異點(diǎn)，但不是群；③群； ④環(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階自補(bǔ)圖有A 個； （2）非同構(gòu)的無向的5階自補(bǔ)圖有B 個； A、B：①0；②1；③2；④3； 二、填空題：（20分） 1、給定命題公式如下：（p→q）→（p∨q） 該命題公式的主析取范式中含極小項的個數(shù)為 ，主合取范式中含極大 項的個數(shù)為 ，成真賦值個數(shù)為 ，成假賦值個數(shù)為 。 2、對于下面的語句， （1）只要4＜3，就有3＞2。真值是 。 （3）只有4＜3，才有3＞2。真值是 。 （6）4≥3僅當(dāng)3≤2。真值是 。 （7）4＜3當(dāng)且僅當(dāng)3＞2。真值是 。 3、下列命題 （1）；（2）；（3）｛｝；（4）｛｝ 正確的是 ；錯誤的是 。 4、設(shè)A、B為集合， （1）A – B = B，成立的充分必要條件是 ； （2）A – B = B - A，成立的充分必要條件是 ； （3）A∪B = A∩B，成立的充分必要條件是 ； 5、設(shè)S=｛a，b｝，則S上可以定義 個二元運(yùn)算，其中有4個運(yùn)算f1，f2，f3，f4，其運(yùn)算表如下： 則只有 滿足交換律， 滿足冪等律， 有幺元， 有零元。 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）李芳學(xué)過英語或日語 （3）小王是游泳冠軍或者百米賽跑冠軍 （4）小王現(xiàn)在在宿舍或者在圖書館 （5）如果明天天氣好，我們?nèi)ソ加?。否則，不去郊游 （6）你愛我，我就嫁給你 四、利用真值表求主析取范式和主合取范式（4分） （p∧q）∨r 五、指出下列各合式公式中的指導(dǎo)變項、量詞的轄域、個體變項的自由出現(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｝，問下面定義的二元運(yùn)算*是否為S上的二元運(yùn)算？（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ù)，其中x≤p≤y。 九、設(shè)是布爾代數(shù)， （1）a，b∈B，公式f為b∧（a∨（a′∧（b∨b′）））,在B中化簡f； （2）在B中等式（a∧b′）∨（a′∧b）=0 成立的條件是什么？（5分） 十、畫出3個頂點(diǎn)2條邊的所有可能非同構(gòu)的有向簡單圖；（4分） 十一、某中學(xué)有3個課外小組：物理組、化學(xué)組、生物組。今有張、王、李、趙、陳5名同學(xué)。若已知： （1）張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員； （2）張為物理組成員，王、李、趙為化學(xué)組成員，王、李、趙、陳為生物組成員； （3）張為物理組和化學(xué)組成員，王、李、趙、陳為生物組成員； 問在以上3中情況下能否各選出3名不兼職的組長？（5分） 十二、求帶權(quán)為2、3、5、7、8、8的最優(yōu)二元樹；（5分） B卷答案 一、選擇題：（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ù)；p∧q； （2）p：李芳學(xué)過英語；q：李芳學(xué)過日語；可兼或；p∨q； （3）p：小王是游泳冠軍；q：小王是百米賽跑冠軍；可兼或；p∨q； （4）p：小王現(xiàn)在在宿舍；q：小王現(xiàn)在在圖書館；不可兼或；（pq）； （5）p：明天天氣好；q：我們?nèi)ソ加?；（pq）∧（pq）； （6）p：你愛我；q：我就嫁給你；pq； 主析取范式為：m7∨m6∨m5∨m3∨m1； 主合取范式為：M0∧M2∧M4； 五、（1）在yH（x，y）中，指導(dǎo)變項y、量詞的轄域H（x，y）、個體變項的自由出現(xiàn)x和約束出現(xiàn)y；在整個公式中，指導(dǎo)變項x、量詞的轄域（F（x）→yH（x，y））、約束出現(xiàn)x、y； （2）在x F（x）中，指導(dǎo)變項x、量詞的轄域F（x）、約束出現(xiàn)x；在G（x，y）中，自由出現(xiàn)x、y； 六、（1）P（）=｛｝； （2）P（｛，｛｝｝）=｛，｛｝，｛｛｝｝，｛，｛｝｝｝ 七、由集合A的所有5中劃分來確定其等價關(guān)系。 （1）IA=｛<1，1>，<2，2>，<3，3>｝ （2）EA=｛<1，1>，<2，2>，<3，3>，<1，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>｝ （3）R1={<1，2>，<2，1>}∪IA （4）R1={<1，3>，<3，1>}∪IA （5）R1={<2，3>，<3，2>}∪IA 八、 （1）是 （2）不是 （3）不是 （4）是 （5）不是 九、 （1）b∧（a∨（a′∧（b∨b′）））= b∧（a∨（a′∧1））= b∧（a∨a′）= b∧1= b （2）因為（a∧b′）∨（a′∧b）=0，所以a∧b′=0，a′∧b=0，而對a∧b′求補(bǔ)可以得到a′∨b=1，由a′∧b=0和a′∨b=1可知，b與a′為補(bǔ)元，而a與a′為補(bǔ)元，由布爾代數(shù)補(bǔ)元的唯一性，得到a=b。 十、 十一、 設(shè)v1、v2、v3、v4、v5分別表示張、王、李、趙、陳，u1、u2、u3分別表示物理組、化學(xué)生物組。在3中情況下作出其相應(yīng)的二部圖為G1、G2、G3， G1中滿足t=2的t條件，能選出； G2不滿足t條件，但滿足相異性條件，能選出； G3不能； 十二、