离散数学综合练习（二）
一、判断题设代数系统<S，*>是<G,*>的子代数，则S ( G。 （ ）
如果一个有向图D是欧拉图，则D是强连通图。 （ ）
设G为n阶无向图简单图，则其补图也为n阶无向图简单图。 （ ）
“如果地球体积比太阳大，那么雪是白色的。”是假命题。 （ ）
假设A上二元关系R是自反的，?则R的逆关系也是自反的。 （ ）
4个顶点的简单无向图一定是平面图。 （ ）
设A，B是任意集合，则|A|+|B|=|A∪B| -|A∩B|。 （ ）
设函数，,g为满射，则一定是满射。（ ）
偏序关系中一定存在极大元。 （ ）
群中不可能有零元。 （ ）
二、填空题
1．设A={2,3,4,5,6}，定义R是A上的关系，且〈x,y〉∈R当且仅当x=y+2，那么R=___________________________________________。.
2．(yF(x,y)( (xG(x)的前束范式为________________________________。
3．设F(x):x为整数；G（x）：x是自然数；L(x,y),x<y。则命题“有些整数比所有的自然数都小。” 在一阶逻辑中的符号化形式为 。
4．设集合A={1,2}，则A上可定义______________?个不具有传递性的二元关系。
5．设集合A＝{a,b,c},B={a,b},那么 P(B)－P (A) =___________________。
6．命题公式 (P∨Q)→(P∧Q)的类型是_____________。（重言、矛盾、可满足式）
7．设解释I为,定义域D={－2，3，6}； F(x)：x≤3; G(x)：x＞5；在解释I下求公式的真值是____________________。
8．无向完全图K3含有________________个不同的边割集。
9．设A={1,2,3,4}，A上的等价关系R={<1,2>,<1,3>,<3,1>,<2,1>,<2,3>,<3,2>}∪IA，其中IA为恒等关系，则其商集A / =______________________________。
10,Klein四元群中每个元素的逆元为______________。
三、设A、B、C为任意集合，证明：
（A∩B）－(A∩C）= A ∩ (B－C)
四、设集合A＝{1,2,3}，R 是A上的关系，它的关系矩阵为：
(1) 画出R的关系图；
(2) 说明R满足关系的哪些性质；
(3) 写出关系R2 的集合表达式。
五、求命题公式的主析取范式、主合取范式以及成真赋值。
六、设无向图G有12条边，2个4度顶点，其余顶点度数均为3或2。
（1）计算该图最少有多少个顶点？
（2）画出一棵具有最少顶点的无向图。
七、设A={1，2，3，4，5}，A上的二元关系R={<1，2>，<3，2>，<4，1>，<4，2>，<4，3>，<3，5>，<4，5>}∪IA （其中IA为A上的恒等关系）：
（1）画出关系R的关系图；
（2）验证R为偏序关系，并画出哈斯图；
（3）令集合B={1，2，3，5}，求B的极大元，极小元，下界。
八、在一阶逻辑中证明以下推理（个体域为人类集合）：
“每个有知识并且爱思考的人都有创造性。有些有知识、爱思考的人是科学家。因此，有些有创造性的人是科学家。”
九、右图是具有四个结点的有向图：
（1）写出该图的邻接矩阵、可达矩阵；
（2）求长度为2的通路总数。
（3）判断该图为单向连通还是强连通？
（4）判断该图是否为哈密尔顿图？
十、设<G，*>是群，u为G中一固定元素，现定义一新的二元运算(，(a，b(G，有：a(b=a*u*b。证明：〈G，(〉是群。
一、判断题设代数系统<S，*>是<G,*>的子代数，则S ( G。 （ ）
如果一个有向图D是欧拉图，则D是强连通图。 （ ）
设G为n阶无向图简单图，则其补图也为n阶无向图简单图。 （ ）
“如果地球体积比太阳大，那么雪是白色的。”是假命题。 （ ）
假设A上二元关系R是自反的，?则R的逆关系也是自反的。 （ ）
4个顶点的简单无向图一定是平面图。 （ ）
设A，B是任意集合，则|A|+|B|=|A∪B| -|A∩B|。 （ ）
设函数，,g为满射，则一定是满射。（ ）
偏序关系中一定存在极大元。 （ ）
群中不可能有零元。 （ ）
二、填空题
1．设A={2,3,4,5,6}，定义R是A上的关系，且〈x,y〉∈R当且仅当x=y+2，那么R=___________________________________________。.
2．(yF(x,y)( (xG(x)的前束范式为________________________________。
3．设F(x):x为整数；G（x）：x是自然数；L(x,y),x<y。则命题“有些整数比所有的自然数都小。” 在一阶逻辑中的符号化形式为 。
4．设集合A={1,2}，则A上可定义______________?个不具有传递性的二元关系。
5．设集合A＝{a,b,c},B={a,b},那么 P(B)－P (A) =___________________。
6．命题公式 (P∨Q)→(P∧Q)的类型是_____________。（重言、矛盾、可满足式）
7．设解释I为,定义域D={－2，3，6}； F(x)：x≤3; G(x)：x＞5；在解释I下求公式的真值是____________________。
8．无向完全图K3含有________________个不同的边割集。
9．设A={1,2,3,4}，A上的等价关系R={<1,2>,<1,3>,<3,1>,<2,1>,<2,3>,<3,2>}∪IA，其中IA为恒等关系，则其商集A / =______________________________。
10,Klein四元群中每个元素的逆元为______________。
三、设A、B、C为任意集合，证明：
（A∩B）－(A∩C）= A ∩ (B－C)
四、设集合A＝{1,2,3}，R 是A上的关系，它的关系矩阵为：
(1) 画出R的关系图；
(2) 说明R满足关系的哪些性质；
(3) 写出关系R2 的集合表达式。
五、求命题公式的主析取范式、主合取范式以及成真赋值。
六、设无向图G有12条边，2个4度顶点，其余顶点度数均为3或2。
（1）计算该图最少有多少个顶点？
（2）画出一棵具有最少顶点的无向图。
七、设A={1，2，3，4，5}，A上的二元关系R={<1，2>，<3，2>，<4，1>，<4，2>，<4，3>，<3，5>，<4，5>}∪IA （其中IA为A上的恒等关系）：
（1）画出关系R的关系图；
（2）验证R为偏序关系，并画出哈斯图；
（3）令集合B={1，2，3，5}，求B的极大元，极小元，下界。
八、在一阶逻辑中证明以下推理（个体域为人类集合）：
“每个有知识并且爱思考的人都有创造性。有些有知识、爱思考的人是科学家。因此，有些有创造性的人是科学家。”
九、右图是具有四个结点的有向图：
（1）写出该图的邻接矩阵、可达矩阵；
（2）求长度为2的通路总数。
（3）判断该图为单向连通还是强连通？
（4）判断该图是否为哈密尔顿图？
十、设<G，*>是群，u为G中一固定元素，现定义一新的二元运算(，(a，b(G，有：a(b=a*u*b。证明：〈G，(〉是群。
