离散数学练习

本文格式为Word版，下载可任意编辑——离散数学练习《离散数学》综合练习题

一、判断题

（正确）1．命题规律中任何命题公式的主析取范式假使存在一定是唯一的。（错误）2．A、B、C是任意集合，假使A?B及B?C，则A?C。（错误）3．整数集是不可数集。（错误）4．实数集是可数集。

（正确）5．代数系统中，假使二元运算*是封闭的、可结合的，则是半群。（正确）6．任意平面图最多是四色的。

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

（正确）8．R是集合A上的二元关系，若R是反自反的，则Rc也是反自反的。（错误）9．任何阿贝尔群必是循环群。

（正确）10．一个地图中相邻国家着以不同颜色，最多需用四种颜色。（正确）11．每个有向图中，结点入度数总和等于结点出度总和。

（正确）12．图G的邻接矩阵A，Al中的i行j列表示结点vi到vj长度为l路的数目。（正确）13．任何图中必有偶数个度数为奇数的结点。

（正确）14．有向图中，它的每一个结点位于且只位于一个单侧分图中。（正确）15．任意平面图最多是四色的。

二、填空题

1．设P：“天下雨〞，Q：“他骑自行车上班〞，R：“他乘公共汽车上班〞。则命题“除非下雨，否则他就骑自行车上班〞可符号化为?P?Q。“他或者骑自行车，或者乘公共汽车上班〞可符号化为Q?R或(?Q?R)?(Q??R)

2．设N(x)：x是自然数；J(x)：x是奇数；Q(x)：x是偶数，用谓词公式符号化命题“任何自然数不是偶数就是奇数〞。(?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，则不同的函数个数为23个。10．Q为有理数集，Q上定义运算*为a*b=a+b-ab，则的幺元为0。

1

11．代数系统，其中Sk={x|x?Z?x>=K}，+为普通加法，则是一个半群的必要条件是K>=0。

12．设G为v个结点e条边的连通平面图，则面r等于e-v+2。

13．一棵树有n2个结点度数为2，n3个结点度数为3，??，nk个结点度数为k，则度数为1的结点的个数为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．设代数系统，其中A={a,b,c}，*是A上的二元运算，运算表如下表，求该代数系统的幺元，

所有可逆元素的逆元。

*abcaabcbbcaccab解：幺元为：a，b的逆元为c，c的逆元为b。4．设集合A有3个元素，B有4个元素，则A到B的关系有多少个？A到B的函数有多少个？解：1）A到B的关系有212个。

2）A到B的函数有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度结点，求树根的度数。解：设树根的度数为x，由于有17条边，所以结点数=17+1=18，由握手定理得：

12*1+4*4+1*3+1*x=2*17解得x=3所以树根度数为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，则根据定义有：?R??S和?R??S由于R和S具备传递性，所以由?R??S??R?S，即R?S具备传递性。综上所述，R?S为集合A上的等价关系。

课程名称

考试形式场次

考试时间2023-12-25

概率论与数理统计闭卷第三场

13:3015:002023-12-25离散数学闭卷第四场15:3017:002023-