2019電大《離散數(shù)學》本科期末復習題資料考試必考重點

1、113電大離散數(shù)學（本）期末復習資料小抄電大離散數(shù)學（本）期末復習資料小抄一、單項選擇題一、單項選擇題1設設P：a是偶數(shù)，是偶數(shù)，Q：b是偶數(shù)。是偶數(shù)。R：ab是偶數(shù)，則命題“若是偶數(shù)，則命題“若a是偶數(shù)，是偶數(shù)，b是偶數(shù)，則是偶數(shù)，則ab也是偶數(shù)”符號化為（也是偶數(shù)”符號化為（DPQ→R）。2表達式表達式?x（P（x，y）?Q（z））??y（Q（x，y）→）→?zQ（z））中）中?x的轄域是（的轄域是（P（x，y）Q（z））。3設設)

2、()(4321????????PSPSSS則命題為假的是（則命題為假的是（42SS?）。4設設G是有是有n個結(jié)點的無向完全圖，則個結(jié)點的無向完全圖，則G的邊數(shù)（的邊數(shù)（12n（n1））。5設設G是連通平面圖，有是連通平面圖，有v個結(jié)點，個結(jié)點，e條邊，條邊，r個面，則個面，則r=（ev2）。6若集合若集合A=1，2，1，2，則下列表述正確的是，則下列表述正確的是(1?A)7已知一棵無向樹已知一棵無向樹T中有中有8個頂點，個頂點，4度、度

3、、3度、度、2度的分支點各一個，度的分支點各一個，T的樹葉數(shù)為的樹葉數(shù)為(5)8設無向圖設無向圖G的鄰接矩陣為的鄰接矩陣為則G的邊數(shù)為的邊數(shù)為(7)????????????????01011100110000111001111109設集合設集合A=a，則，則A的冪集為的冪集為(?，a)10下列公式中下列公式中(?A????B??(A?B))為永真式為永真式11若若G是一個漢密爾頓圖，則是一個漢密爾頓圖，則G一定是一定是(連通圖連通圖)1

4、2集合集合A=1234上的關系上的關系R=|x=y且xyA，則，則R的性質(zhì)為（傳遞的的性質(zhì)為（傳遞的）?13設集合設集合A=1，2，3，4，5，偏序關系，偏序關系?是A上的整除關系，則偏序集上的整除關系，則偏序集上的元素上的元素5是集合是集合A的（極大元的（極大元）14圖圖G如圖一所示，以下說法正確的是如圖一所示，以下說法正確的是((ad)(bd)是邊割集是邊割集)圖一圖一15設設A（x）：）：x是人，是人，B（x）：）：x是工人，則命

5、題“有人是工人”可符號化為（是工人，則命題“有人是工人”可符號化為（(x)(A(x)∧B(x))）?16若集合若集合A=1，2，B=1，2，1，2，則下列表述正確的是，則下列表述正確的是(A?B，且，且A?B)17設有向圖（設有向圖（a）、（b）、（c）與（）與（d）如圖一所示，則下列結(jié)論成立的是）如圖一所示，則下列結(jié)論成立的是(（d）是強連通的）是強連通的)18設圖設圖G的鄰接矩陣為的鄰接矩陣為則G的邊數(shù)為的邊數(shù)為(5)???????

6、?????????010101001000001110010011019無向簡單圖無向簡單圖G是棵樹，當且僅當是棵樹，當且僅當(G連通且邊數(shù)比結(jié)點數(shù)少連通且邊數(shù)比結(jié)點數(shù)少1)20下列公式下列公式((P?(?Q?P))?(?P?(P?Q)))為重言式為重言式21若集合若集合A＝a，a，1，2，則下列表述正確的是，則下列表述正確的是(a?A)22設圖設圖G＝，v?V，則下列結(jié)論成立的是，則下列結(jié)論成立的是()EvVv2)deg(???23命

7、題公式（命題公式（P∨Q）→）→R的析取范式是的析取范式是(（?P∧?Q）∨）∨R)24下列等價公式成立的為下列等價公式成立的為(P?(?Q?P)????P?(P?Q))25設設A=ab，B=12，R1，R2，R3是A到B的二元關系，且的二元關系，且R1=，R2=，R3=，則（，則（R2）不是從）不是從A到B的函數(shù)的函數(shù)26設設A=12345678，R是A上的整除關系，上的整除關系，B=246，則集合，則集合B的最大元、最小元、上界、下

8、界依次為的最大元、最小元、上界、下界依次為(無、無、2、無、、無、2)31327如果如果R1和R2是A上的自反關系，則上的自反關系，則R1∪R2，R1∩R2，R1R2中自反關系有中自反關系有2個個28設圖設圖G是有是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從，則可從G中刪去中刪去4條邊后使之變成樹條邊后使之變成樹29設連通平面圖設連通平面圖G的結(jié)點數(shù)為的結(jié)點數(shù)為5，邊數(shù)為，邊數(shù)為6，則面數(shù)為，則面數(shù)為3

9、30設個體域設個體域D＝ab，則謂詞公式，則謂詞公式(?x)A(x)∧（∧（?x）B（x）消去量詞后的等值式為消去量詞后的等值式為(A(a)∧A(b))∧(B（a）∨B（b）)31.設集合設集合A=0，1，2，B=l，2，3，剖，剖，R是A到B的二元關系，的二元關系，R=|x∈A且y∈B且x，y∈A∩B則R的有序?qū)挠行驅(qū)蠟楹蠟開_____32.設G是連通平面圖，是連通平面圖，v，e，r分別表示分別表示G的結(jié)點數(shù)，的結(jié)點數(shù)，邊數(shù)和

10、面數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關系式滿足的關系式__ver=2_____33.G=是有是有20個結(jié)點，個結(jié)點，25條邊的連通圖條邊的連通圖則從則從G中刪去中刪去__6__條邊，可以確定圖條邊，可以確定圖G的一棵生成樹的一棵生成樹.34.無向圖無向圖G存在歐拉回路，存在歐拉回路，當且僅當當且僅當G所有結(jié)點的度數(shù)全為偶數(shù)且所有結(jié)點的度數(shù)全為偶數(shù)且_連通連通____35.設個體域設個體域D=12，則謂詞公式則謂詞公式?xA(x)消去量詞

11、后的等值式為消去量詞后的等值式為__A(1)∧A(2)___三、化簡解答題三、化簡解答題1111設集合設集合A=1A=1，2，3，44，A上的二元關系上的二元關系R，R=R=〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉，說明，說明R是A上的等價關系。上的等價關系。解從R的表達式知，的表達式知，)(RxxAx???即R具有自反性；具有自反性；三、邏輯公式翻譯三、邏輯公式翻譯1將語句將語句“

12、今天上課今天上課”翻譯成命題公式翻譯成命題公式設P：今天上課，：今天上課，則命題公式為：則命題公式為：P2將語句將語句“他去操場鍛煉，僅當他有時間他去操場鍛煉，僅當他有時間”翻譯成命題公式翻譯成命題公式設P：他去操場鍛煉，：他去操場鍛煉，Q：他有時間，：他有時間，則命題公式為：則命題公式為：P?Q3將語句“他是學生將語句“他是學生”翻譯成命題公式”翻譯成命題公式設P：他是學生，：他是學生，則命題公式為：則命題公式為：P4將語句“如果明天

13、不下雨，我們就去郊游將語句“如果明天不下雨，我們就去郊游”翻譯成命題公式”翻譯成命題公式設P：明天下雨，：明天下雨，Q：我們就去郊游，：我們就去郊游，則命題公式為：則命題公式為：?P?Q5將語句“他不去學校將語句“他不去學校”翻譯成命題公式”翻譯成命題公式設P：他去學校，：他去學校，?P6將語句“他去旅游，僅當他有時間將語句“他去旅游，僅當他有時間”翻譯成命題公式”翻譯成命題公式設P：他去旅游，：他去旅游，Q：他有時間，：他有時間，P?

14、Q7將語句“所有的人都學習努力將語句“所有的人都學習努力”翻譯成命題公式”翻譯成命題公式設P(x)：x是人，是人，Q(x)：x學習努力，學習努力，（?x）(P(x)?Q(x))8將語句“如果你去了，那么他就不去將語句“如果你去了，那么他就不去”翻譯成命題公式”翻譯成命題公式設P：你去，：你去，Q：他去，：他去，P????Q9將語句“小王去旅游，小李也去旅游將語句“小王去旅游，小李也去旅游”翻譯成命題公式”翻譯成命題公式設P：小王去旅游，

15、：小王去旅游，Q：小李去旅游，：小李去旅游，P?Q10將語句“所有人都去工作將語句“所有人都去工作”翻譯成謂詞公式”翻譯成謂詞公式設P(x)：x是人，是人，Q(x)：x去工作，去工作，(?x)(P(x)?Q(x))11將語句“如果所有人今天都去參加活動，則明天的會議取消將語句“如果所有人今天都去參加活動，則明天的會議取消”翻譯成命題公式”翻譯成命題公式設P：所有人今天都去參加活動，：所有人今天都去參加活動，Q：明天的會議取消，：明天的會

16、議取消，P?Q12將語句“今天沒有人來將語句“今天沒有人來”翻譯成命題公式翻譯成命題公式設P：今天有人來，：今天有人來，?P13將語句“有人去上課將語句“有人去上課”翻譯成謂詞公式翻譯成謂詞公式設P(x)：x是人，是人，Q(x)：x去上課，去上課，(?x)(P(x)?Q(x))11.將語句將語句“如果小李學習努力，那么他就會取得好成績?nèi)绻±顚W習努力，那么他就會取得好成績.“翻譯成命題公式翻譯成命題公式.設P：小李學習努力，：小李學習努