离散数学综合练习（一）
一、判断题(在括号内划“√”或“×”)
（ ）1、联结词集合{↓，﹁}是联结词全功能集。
（ ）2、(x F(x) ((y F(y)是永真式。
（ ）3,“x+4>0”是简单命题。
（ ）4、集合A,B，若A – B＝Φ，则B＝A。
（ ）5、若R为具有自反性的二元关系，则R的逆关系也具有自反性。
（ ）6、平面图中，所有面的次数之和等于所有顶点的度数之和。
（ ）7、集合上的除法运算为二元运算。
（ ）8、独异点一定不含零元。
（ ）9、群的运算表中每行或每列都不可能有重复出现的元素。
（ ）10、零图是简单图。
二、填空题
1、集合A = {Φ,{b,c}}，则P(A)＝_____________________。
2、﹁(xF(x)( (xG(x,y)的前束范式为__________________________________。
3、在一阶逻辑中，语句“有些大学生不钦佩任何运动员”。的符号化形式为__________________________________________________________________。
4、设A = {a,b,c}，A上的等价关系R＝{<a,a>,<a,c>,<b,b>,<c,a>,<c,c>}，
则商集A/R＝______________________________。
5、设集合A={1，2}，在A上最多可以定义__________个不同的偏序关系。
6、具有3个顶点2条边的所有非同构的有向简单图中有_______个是单向连通图。
7、具有p个连通分支的平面图中，若顶点数为n，边数为m，则其平面嵌入把所在平面划分成________________________个面。
8、设命题公式G＝((P((Q(R))，则使公式G为真的解释有__________________________。
9、假设左下图为全集E，请用文氏图表示集合表达式,(A－B)∩
10、设谓词的定义域为{a,b},将表达式(xR(x)→(xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.
三、用等值演算法求(p∨q)( ﹁r的主析取范式、主合取范式、成假赋值。
四、使用一阶逻辑推理方法，证明下列推理是正确的(个体域为所有旅客组成的集合)。
“每个旅客要么坐头等舱要么坐二等舱；每个旅客当且仅当他富裕时坐头等舱；并非所有的旅客都富裕。因此，有些旅客坐二等舱。”
五、N为自然数集合，R为实数集合，设函数f,R →R,f(x)=,
函数g,N →R，g(x)=。
（1）求f og的表达式,并判断其是否为单射、满射?
（2）能否求出g o f? 若能，写出表达式；否则，说明理由。
六、设集合S = {1,2,4,6,8,12,18,24,36,72},≤为整除关系，
（1）画出偏序集<S,≤>的哈斯图；
（2）求集合B＝{4,18,36}的上界；
七、设集合G={ an | n ∈Z}，其中a为一固定实数，a>0且a≠1。×为普通乘法运算；
证明：<G，×>是阿贝尔群。
八、以下是具有结点V1，V2，V3，V4的有向图的邻接矩阵：
（1）画出该图；
（2）求长度为3的通路总数和回路总数；
（3）该图是否为欧拉图?
九、右图为无向图：
（1）它是否为平面图？若是，请画出它的一个平面嵌入图；否则，说明理由。
（2）判断该图是否为哈密尔顿图？请说明理由。
（3）判断该图是否为二部图？请说明理由。
一、判断题(在括号内划“√”或“×”)
（ ）1、联结词集合{↓，﹁}是联结词全功能集。
（ ）2、(x F(x) ((y F(y)是永真式。
（ ）3,“x+4>0”是简单命题。
（ ）4、集合A,B，若A – B＝Φ，则B＝A。
（ ）5、若R为具有自反性的二元关系，则R的逆关系也具有自反性。
（ ）6、平面图中，所有面的次数之和等于所有顶点的度数之和。
（ ）7、集合上的除法运算为二元运算。
（ ）8、独异点一定不含零元。
（ ）9、群的运算表中每行或每列都不可能有重复出现的元素。
（ ）10、零图是简单图。
二、填空题
1、集合A = {Φ,{b,c}}，则P(A)＝_____________________。
2、﹁(xF(x)( (xG(x,y)的前束范式为__________________________________。
3、在一阶逻辑中，语句“有些大学生不钦佩任何运动员”。的符号化形式为__________________________________________________________________。
4、设A = {a,b,c}，A上的等价关系R＝{<a,a>,<a,c>,<b,b>,<c,a>,<c,c>}，
则商集A/R＝______________________________。
5、设集合A={1，2}，在A上最多可以定义__________个不同的偏序关系。
6、具有3个顶点2条边的所有非同构的有向简单图中有_______个是单向连通图。
7、具有p个连通分支的平面图中，若顶点数为n，边数为m，则其平面嵌入把所在平面划分成________________________个面。
8、设命题公式G＝((P((Q(R))，则使公式G为真的解释有__________________________。
9、假设左下图为全集E，请用文氏图表示集合表达式,(A－B)∩
10、设谓词的定义域为{a,b},将表达式(xR(x)→(xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.
三、用等值演算法求(p∨q)( ﹁r的主析取范式、主合取范式、成假赋值。
四、使用一阶逻辑推理方法，证明下列推理是正确的(个体域为所有旅客组成的集合)。
“每个旅客要么坐头等舱要么坐二等舱；每个旅客当且仅当他富裕时坐头等舱；并非所有的旅客都富裕。因此，有些旅客坐二等舱。”
五、N为自然数集合，R为实数集合，设函数f,R →R,f(x)=,
函数g,N →R，g(x)=。
（1）求f og的表达式,并判断其是否为单射、满射?
（2）能否求出g o f? 若能，写出表达式；否则，说明理由。
六、设集合S = {1,2,4,6,8,12,18,24,36,72},≤为整除关系，
（1）画出偏序集<S,≤>的哈斯图；
（2）求集合B＝{4,18,36}的上界；
七、设集合G={ an | n ∈Z}，其中a为一固定实数，a>0且a≠1。×为普通乘法运算；
证明：<G，×>是阿贝尔群。
八、以下是具有结点V1，V2，V3，V4的有向图的邻接矩阵：
（1）画出该图；
（2）求长度为3的通路总数和回路总数；
（3）该图是否为欧拉图?
九、右图为无向图：
（1）它是否为平面图？若是，请画出它的一个平面嵌入图；否则，说明理由。
（2）判断该图是否为哈密尔顿图？请说明理由。
（3）判断该图是否为二部图？请说明理由。
