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