離散數(shù)學練習

本文格式為Word版，下載可任意編輯——離散數(shù)學練習《離散數(shù)學》綜合練習題

一、判斷題

（正確）1．命題規(guī)律中任何命題公式的主析取范式假使存在一定是唯一的。（錯誤）2．A、B、C是任意集合，假使A?B及B?C，則A?C。（錯誤）3．整數(shù)集是不可數(shù)集。（錯誤）4．實數(shù)集是可數(shù)集。

（正確）5．代數(shù)系統(tǒng)中，假使二元運算*是封閉的、可結合的，則是半群。（正確）6．任意平面圖最多是四色的。

（正確）7．A、B是任意命題公式，假使?A??B，一定有A?B。

（正確）8．R是集合A上的二元關系，若R是反自反的，則Rc也是反自反的。（錯誤）9．任何阿貝爾群必是循環(huán)群。

（正確）10．一個地圖中相鄰國家著以不同顏色，最多需用四種顏色。（正確）11．每個有向圖中，結點入度數(shù)總和等于結點出度總和。

（正確）12．圖G的鄰接矩陣A，Al中的i行j列表示結點vi到vj長度為l路的數(shù)目。（正確）13．任何圖中必有偶數(shù)個度數(shù)為奇數(shù)的結點。

（正確）14．有向圖中，它的每一個結點位于且只位于一個單側分圖中。（正確）15．任意平面圖最多是四色的。

二、填空題

1．設P：“天下雨〞，Q：“他騎自行車上班〞，R：“他乘公共汽車上班〞。則命題“除非下雨，否則他就騎自行車上班〞可符號化為?P?Q?！八蛘唑T自行車，或者乘公共汽車上班〞可符號化為Q?R或(?Q?R)?(Q??R)

2．設N(x)：x是自然數(shù)；J(x)：x是奇數(shù)；Q(x)：x是偶數(shù)，用謂詞公式符號化命題“任何自然數(shù)不是偶數(shù)就是奇數(shù)〞。(?x)(N(x)?(J(x)?Q(x)))

3．設P(x)：x是運動員，Q(x)：x是教練。則命題“不是所有運動員都是教練〞可符號化為?(?x)(P(x)?Q(x))或(?x)(P(x)??Q(x))。

4．設D={a,b}；P(a,a)=P(b,b)=T；P(a,b)=P(b,a)=F。則公式(?x)(?y)(P(x,y)?P(y,x))的真值是T。5．集合A={?,{?}}的冪集P(A)為{?,{?},{{?}},{?,{?}}}

6．集合A={1,2}，B={a,b,c,d}，C={c,d,e}，則A?(B-C)為{,,,}7．試用空集?構成集合A（A??）={?}和B={?，{?}}，使得A?B且A?B都成立。并且A?B={，}。

8．設A={1,2,3}，R={,,,}，傳遞閉包t(R)為{,,,,,}。

9．設A={1,2,3}，B={x,y}，f：A?B，則不同的函數(shù)個數(shù)為23個。10．Q為有理數(shù)集，Q上定義運算*為a*b=a+b-ab，則的幺元為0。

1

11．代數(shù)系統(tǒng)，其中Sk={x|x?Z?x>=K}，+為普通加法，則是一個半群的必要條件是K>=0。

12．設G為v個結點e條邊的連通平面圖，則面r等于e-v+2。

13．一棵樹有n2個結點度數(shù)為2，n3個結點度數(shù)為3，??，nk個結點度數(shù)為k，則度數(shù)為1的結點的個數(shù)為n3+2n4+?+(k-2)nk+2。

三、基此題

1．設P：“天下雨〞，Q：“他騎自行車上班〞，R：“他乘公共汽車上班〞，試符號化以下命題：

1）只要不下雨，他就騎自行車上班

2）他或者騎自行車上班，或者乘公共汽車上班解：1）?P?Q2)Q?R或(Q??R)?(?Q?R)2．設A={1,{1}}，計算P(A)-{?}解：P(A)={?,{1},{{1}},{1,{1}}}

P(A)-{?}={?,{1},{{1}},{1,{1}}}-{?}={{1},{{1}},{1,{1}}}

3．設代數(shù)系統(tǒng)，其中A={a,b,c}，*是A上的二元運算，運算表如下表，求該代數(shù)系統(tǒng)的幺元，

所有可逆元素的逆元。

*abcaabcbbcaccab解：幺元為：a，b的逆元為c，c的逆元為b。4．設集合A有3個元素，B有4個元素，則A到B的關系有多少個？A到B的函數(shù)有多少個？解：1）A到B的關系有212個。

2）A到B的函數(shù)有43個。

5．判斷公式?(P?Q)??(P?Q)的類型（重言式、矛盾式、可滿足）解：原式?((P?Q)?(Q?P))?(?P??Q)???((?P?Q)?(?Q?P))?(?P??Q)

?((?P?Q)?(?Q?P))?(?P??Q)?(?P?Q??P??Q)?(?Q?P??P??Q)?T?T?T所以公式為重言式

6．設A={?,{1}}，計算P(A)-{?}解：P(A)={?,{?},{{1}},{?,{1}}}

P(A)-{?}={?,{?},{{1}},{?,{1}}}-{?}={{?},{{1}},{?,{1}}}

7．設樹T有17條邊，除樹根外有12片樹葉，4個4度結點，1個3度結點，求樹根的度數(shù)。解：設樹根的度數(shù)為x，由于有17條邊，所以結點數(shù)=17+1=18，由握手定理得：

12*1+4*4+1*3+1*x=2*17解得x=3所以樹根度數(shù)為3。

2

8．求命題公式?(P?Q)的主合取范式。解：?(P?Q)??(?P?Q)?P??Q

?(P?(Q??Q))?((P??P)??Q)?(P?Q)?(P??Q)?(?P??Q)

9．求命題公式P?(P?Q)的主析取范式。解：原式?P?(?P?Q)?(P??P)?(P?Q)?P?Q

四、證明題

1．構造下面推理的證明

(?x)(P(x)?(Q(x)?H(x)))，(?x)(P(x)?R(x))?(?x)(P(x)?Q(x)?R(x))證明：(1)(?x)(P(x)?R(x))P(2)P(a)?R(a)ES(1)(3)P(a)T(2)I(4)(?x)(P(x)?(Q(x)?H(x)))P(5)P(a)?(Q(a)?H(a))US(4)(6)Q(a)?H(a)T(3)(5)I(7)Q(a)T(6)I(8)R(a)T(2)I(9)P(a)?Q(a)?R(a)T(3)(7)(8)I(10)(?x)(P(x)?Q(x)?R(x))EG(9)

2．設是一個獨異點，并且對于G中的每一個元素x都有x*x=e，其中e是幺元，證明是一

個阿貝爾群。

證明：是獨異點，*運算封閉，且滿足結合律，且有幺元，

只須證中每個元素都有逆元，并且*運算滿足交換律。

由于對于G中的每一個元素x都有x*x=e，所以x的逆元就是x，故是群。對于?x,y?G，則x*y?G，

所以(x*y)*(x*y)=e，而(x*y)*(y*x)=x*(y*y)*x=x*e*x=x*x=e故(x*y)*(x*y)=(x*y)*(y*x)，所以x*y=y*x，即*運算滿足交換律。所以是一個阿貝爾群。

3．試證明命題公式((P?Q)?(Q?R))?(P?R)為永真式。

證明：((P?Q)?(Q?R))?(P?R)

?((?P?Q)?(?Q?R))?(?P?R)??((?P?Q)?(?Q?R))?(?P?R)?((P??Q)?(Q??R))??P?R?((P??Q)??P)?((Q??R)?R)

3

?(?Q??P)?(Q?R)?(?Q?Q)??P?R?1??P?R?1

所以是永真式。

4．若R和S是集合A上的等價關系，試證明R?S也是A上的等價關系。證明：即證明R?S具有自反性、對稱性和傳遞性

由于R,S是等價關系，所以R,S具有自反性、對稱性和傳遞性1）自反性

對?a?A，R,S具有自反性，故?R，且?S，所以?R?S，即R?S具有自反性。2）對稱性

若a,b?A，有?R?S所以?R且?S

又由于R,S具有對稱性，故?R且?S

3）傳遞性

??R?S，??R?S，則根據(jù)定義有：?R??S和?R??S由于R和S具備傳遞性，所以由?R??S??R?S，即R?S具備傳遞性。綜上所述，R?S為集合A上的等價關系。

課程名稱

考試形式場次

考試時間2023-12-25

概率論與數(shù)理統(tǒng)計閉卷第三場

13:3015:002023-12-25離散數(shù)學閉卷第四場15:3017:002023-