《計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)》離散數(shù)學(xué)試題

1、1《計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(1)》離散數(shù)學(xué)試題一、單項(xiàng)選擇題一、單項(xiàng)選擇題(每小題每小題2分，共分，共10分)1.命題公式P?(P??P)的類型是（）（A）永真式（B）矛盾式（C）非永真式的可滿足式（D）析取范式2.設(shè)個(gè)體域是整數(shù)集合，P代表?x?y((x?y)?(x?y?x))，下面4個(gè)命題中為真的是()(A)P是真命題(B)P是假命題(C)P是一階邏輯公式，但不是命題(D)P不是一階邏輯公式3.設(shè)ABC都是集合，如果A?C＝B?C，則有()

2、(A)A＝B(B)A?B(C)當(dāng)A－C＝B－C時(shí)有A=B(D)當(dāng)C=U時(shí)有A?B4.設(shè)集合A＝?，a，則P(A)＝())D()C()B()A(aaAaaaaaa??????????5.給定無向圖如第5題圖所示，下面給出的頂點(diǎn)集子集中，不是點(diǎn)割集的為（）(A)bd(B)d(C)ac(D)ge二、填空題二、填空題(每小題每小題3分，共分，共15分)6.設(shè)F(x)：x是素?cái)?shù)，E(x)：x是偶數(shù)，命題“不是所有的素?cái)?shù)都不是偶數(shù)”符號(hào)化為：7.設(shè)

3、AB為任意集合，命題A?B???A??的真值為8.設(shè)A、B為有限集，且?A??m????n那末A與B間存在雙射，當(dāng)且僅當(dāng)9.在有向圖的鄰接矩陣中，第i行元素之和與第j列元素之和分別為10.無向圖G為歐拉圖，當(dāng)且僅當(dāng)G是連通的，且G中無結(jié)點(diǎn)三、化簡(jiǎn)解答題三、化簡(jiǎn)解答題(每小題每小題8分，共分，共32分)11.指出謂詞公式中?x和?x的轄域，并指出)())())()(((xSxxRyxQxPx?????該公式的約束變?cè)妥杂勺冊(cè)约凹s束出現(xiàn)

4、次數(shù)和自由出現(xiàn)次數(shù)12.化簡(jiǎn)集合表達(dá)式：((A?B?C)?(A?B))－((B?(B－C))－A)13.設(shè)集合A=01234，定義A上的二元關(guān)系R為：R＝?xy?A?(x=y?xy?A)試寫出二元關(guān)系R的集合表達(dá)式，并指出R具有的性質(zhì)14.(1)求命題公式(P??Q)?(P?Q)的成真賦值(2)已知集合A上的二元關(guān)系R的關(guān)系圖如第14題圖，試寫出R的集合表達(dá)式和R的關(guān)系矩陣四計(jì)算題四計(jì)算題(每小題每小題8分，共分，共24分)15.已知帶

5、權(quán)圖G，如第15題圖所示0??21?第14題圖agbdfce第5題圖?192?8?7?4?3?第15題圖56103權(quán)數(shù)為1816.?xyz?R，①(xy)z=(xy2xy)z=(xy2xy)z2(xy2xy)z=x(yz2yz)2x(yz2yz)=x(yz)可結(jié)合.②xy=xy2xy=yx可交換.③設(shè)單位元為e，?x?Rex=xe=xe2xe=x，由x的任意性得e=0?R單位元為0.17.((ab)?(ac))((ab)?(bc))＝(

6、ab)?((ac)(bc))(分配律)=(ab)?((ab)c)(冪等律)=ab(吸收律)五、證明題五、證明題(第18題10分，第分，第19題9分)18.(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q?(?P??P?Q)?(Q??P?Q)?(?R??P?Q)?(?P?Q)?(?P?Q)?(?P?Q??R)??P?Q??(P??Q)19.假設(shè)完全有向圖D有n個(gè)結(jié)點(diǎn)對(duì)任意結(jié)點(diǎn)vk?D有deg＋(vk)deg－(vk)=2(

7、n－1)對(duì)于完全有向圖，)1()(deg)(deg11?????????nnvvnkknkk于是，?????????nknkkkvnv1122))(deg)1(2())((deg＝????????nkkkvvnn122))((deg))(deg)1(4)1(4(＝??????????nkknkkvvnnn1212))((deg)(deg)1(4)1(4＝?????????nkkvnnnnn122))((deg)1()1(4)1(4＝??