离散数学》试题及答案

一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; ?(A)-?(B)＝__________________________. 2.设有限集合A,|A|=n,则|?(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是_______________________________________,其中双射的是__________________________. 4.已知命题公式G＝?(P?Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从A?B＝_________________________;A?B＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________,________________________,_______________________________. 8.设命题公式G＝?(P?(Q?R))，则使公式G为真的解释有__________________________，_____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系R1={(1,4),(2,3),(3,2)},R2={(2,1),(3,2),(4,3)},则 R1?R2=________________________,R2?R1=____________________________, R12=________________________. 10.设有限集A,B，|A|=m,|B|=n,则||?(A?B)|=_____________________________. 11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,x?R},B={x|0≤x<2,x?R},则A-B=__________________________,B-A=__________________________, A∩B=__________________________,. 13.设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式(列举法)记为__________________________________________________________________. 14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G的前束范式是_______________________________. 16.设谓词的定义域为{a,b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A＝{1,2,3,4}，A上的二元关系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。则R?S＝_____________________________________________________, R2＝______________________________________________________. 二、选择题 1设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是()。 (A){2}?A(B){a}?A (C)??{{a}}?B?E(D){{a},1,3,4}?B. 2设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备(). (A)自反性 (B)传递性 (C)对称性 (D)反对称性 3设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B={2,3,4,5},则元素6为B的()。 (A)下界 (B)上界 (C)最小上界(D)以上答案都不对 4下列语句中，()是命题。 (A)请把门关上(B)地球外的星球上也有人 (C)x+5>6(D)下午有会吗？ 5设I是如下一个解释：D＝{a,b},
则在解释I下取真值为1的公式是(). (A)?x?yP(x,y)(B)?x?yP(x,y) (C)?xP(x,x)(D)?x?yP(x,y). 6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是(). (A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5) (C)(1,1,1,2,3)(D)(2,3,3,4,5,6). 7.设G、H是一阶逻辑公式，P是一个谓词，G＝?xP(x),H＝?xP(x),则一阶逻辑公式G?H是(). (A)恒真的(B)恒假的 (C)可满足的(D)前束范式. 8设命题公式G＝?(P?Q)，H＝P?(Q??P)，则G与H的关系是()。 (A)G?H(B)H?G (C)G＝H(D)以上都不是. 9设A,B为集合，当()时A－B＝B. (A)A＝B (B)A?B (C)B?A (D)A＝B＝?. 10设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有()。 (A)自反性 (B)传递性 (C)对称性(D)以上答案都不对 11下列关于集合的表示中正确的为()。 (A){a}?{a,b,c} (B){a}?{a,b,c} (C)??{a,b,c}(D){a,b}?{a,b,c} 12命题?xG(x)取真值1的充分必要条件是(). 对任意x，G(x)都取真值1.(B)有一个x0，使G(x0)取真值1. (C)有某些x，使G(x0)取真值1.(D)以上答案都不对. 13.设G是连通平面图，有5个顶点，6个面，则G的边数是(). (A)9条(B)5条 (C)6条(D)11条. 15.设图G的相邻矩阵为 EMBED Equation.3 
，则G的顶点数与边数分别为(). (A)4,5 (B)5,6 (C)4,10 (D)5,8. 三、计算证明题 1.设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。 画出半序集(A,R)的哈斯图； 写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界； 写出A的最大元，最小元，极大元，极小元。 设集合A＝{1,2,3,4}，A上的关系R＝{(x,y)|x,y?A且x?y},求 画出R的关系图； 写出R的关系矩阵. 设R是实数集合，?,?,?是R上的三个映射，?(x)=x+3,?(x)=2x,?(x)＝x/4,试求复合映射???，???,???,???，?????. 4.设I是如下一个解释：D={2,3}, a b f(2) f(3) P(2,2) P(2,3) P(3,2) P(3,3) 3 2 3 2 0 0 1 1 试求(1)P(a,f(a))∧P(b,f(b)); (2)?x?yP(y,x). 5.设集合A＝{1,2,4,6,8,12}，R为A上整除关系。 画出半序集(A,R)的哈斯图； 写出A的最大元，最小元，极大元，极小元； 写出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界. 6.设命题公式G=?(P→Q)∨(Q∧(?P→R)),求G的主析取范式。 7.(9分)设一阶逻辑公式：G=(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式. 9.设R是集合A={a,b,c,d}.R是A上的二元关系,R={(a,b),(b,a),(b,c),(c,d)}, 求出r(R),s(R),t(R)； 画出r(R),s(R),t(R)的关系图. 11.通过求主析取范式判断下列命题公式是否等价： (1)G=(P∧Q)∨(?P∧Q∧R) (2)H=(P∨(Q∧R))∧(Q∨(?P∧R)) 13.设R和S是集合A＝{a,b,c,d}上的关系，其中R＝{(a,a),(a,c),(b,c),(c,d)}, S＝{(a,b),(b,c),(b,d),(d,d)}. (1)试写出R和S的关系矩阵； (2)计算R?S,R∪S,R－1,S－1?R－1. 四、证明题 参考答案 一、填空题 1.{3};{{3},{1,3},{2,3},{1,2,3}}.  EMBED Equation.DSMT4 
. ?1={(a,1),(b,1)},?2={(a,2),(b,2)},?3={(a,1),(b,2)},?4={(a,2),(b,1)};?3,?4. (P∧?Q∧R). 12,3. {4},{1,2,3,4},{1,2}. 自反性；对称性；传递性. (1,0,0),(1,0,1),(1,1,0). {(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}. 2m?n. {x|-1≤x<0,x?R};{x|1