离散数学试卷二

台州学院201学年第学期级专业《离散数学》期末试卷(B卷)(闭卷)班级姓名学号题号一二三四总分分值20102050100得分一、是非题（“是”打1,“非”打0,每题2分,共20分）1.设p,q为真命题,r,s为假命题,则复合命题()pqrs的真值是1.2.设A是永假式,则Apq是永真式.3.公式(()())AxHxPx既不是重言式也不是矛盾式.4.{,}Sab上共有22个不同的二元关系.5.非零有理数集*Q对除法构成半群.6.8(,,)Z的所有零因子是2、4、6.7.任一无向树一定是二部图.8.任何无向图中所有顶点的度数之和等于边数的2倍.9.Gn,m是树的充要条件是G中任一边都是桥且n=m-1.10.无向图G是哈密顿图当且仅当G是连通图且没有奇度顶点.二、选择题（每题2分,共10分）1.下面句子是命题的是()A.,,xyxyRB.2020年的十月一号是晴天C.我正在说假话D.请安静！2.下列式子为永真式的是()A.()()pqpqB.()()pqpqC.()pqD.()()pqqp3．整数集上的关系R={x，y|x+y=10，x∈A，y∈A}，则R的性质是()A．自反的B．对称的、传递的C．对称的D．反自反的、传递的4.对于((),,)PS,构成()A.整环B.交换环C.无零因子环D.域5.下列度数列可简单图化的是()A.(5,4,3,3,2,2)B.(4,4,3,3,2,2)C.(5,3,3,2,2)D.(3,3,3,1)三、填空题（每题2分,共20分）1.命题()()qppq的成真赋值是10,11.2.设F(x):x具有性质F；G(x):x具有性质G.命题“若所有的x都有性质G,则所有的x都有性质F”的符号化形式是(()())xGxFx.3.{1,2},AA的幂集为{,{1},{2},{1,2}}.4.设A={l,2,3,4},A上的二元关系R={3,4,4,3,1,4},S={4,1,3,4},则(RS)-1=___{3,4,4,1}_____.5.设{,,,},{(,),(,),(,)}AAabcdRbacdbdI是A上的偏序关系,它的极大元a,d.6.设Ga是24元循环群,则G的四阶子群是61218{,,,}eaaa.7.设S是非空有限集,代数系统P（S）,中,其中P（S）为集合S的幂集,则P（S）对运算的单位元是__S______.8．在Z6,○+中,5的阶是___6_____.9.在下图中,结点3v的度数是____4____.10.有3片树叶,1个3度顶点,其余顶点数不等于1和3的7阶无向树的度数列（度数从小到大排列）为(1,1,1,2,2,2,3).四、计算题（每题10分,共50分）1.求命题公式()pqr的主析取范式.1.求命题公式rqp)(的主析取范式和主合取范式.解:51100100005101)()())(()())(()()(MMMMMrqrpMrqprqprqprqprqp主析取范式是1347mmmm…………………………………………………………5分主合取范式是0256MMMM………………………………………………………5分2.设集合A＝{-5,3,-3,5},A上的关系R规定为xRy当且仅当xy0.(1)写出关系R以及R的关系矩阵.(1)写出关系R以及R的关系矩阵.(2)判断R是否为等价关系,写出理由.若是，还要写出商集A/R.解:(1){(5,3),(3,5),(3,5),(5,3)}ARI,关系矩阵是1010010110100101……………4分(2)判断R是否为等价关系,写出理由.若是,还要写出商集A/R.(2)是等价关系，因为满足：自反性:2,0;xAxxx对称性:,,00;xyAxyyx传递性:,,,0000.xyzAxyyzxyyzxz…………………………3分{{5,3},{3,5}}AR………………………………………………………………………3分3.设{3,},AababQ运算为实数加法和乘法,判断集合A是否构成环,整环和域.4.写出模15的剩余类加群15(,)Z的所有生成元和所有子群.(1)大于0小于15的素数有:1,2,4,7,8,11,13,14,所以15(,)Z的所有生成元是:1,2,4,7,8,11,13,14,…………………………………………………………………………………5分(2)15的正因子是1,3,5,15,因此它的子群为:0={0},5={0,5,10},3={0,3,6,9,12},1=6Z.……………………………………………………………………………………5分5.写出所有不同构的4条边5阶无向连通简单图的度数列,并画出简单图图形.解:由握手定理，所画的无向简单图各顶点度数之和为428,最大度小于等于4,最小度大于等于1,这样度数列有三种情况:(a)4,1,1,1,1;(b)3,2,1,1,1;(c)2,2,2,1,1.将每个度数列所有非同构的图都画出来即得所要求的全部非同构的图……………………………………5分图略.……………………………………………………………………………………………5分