山东科技大学离散数学复习题

离散数学复习思考题一及答案一、选择题（每题2分，共20分）1、下列语句中，(B)是命题。A.请把门关上B.地球外的星球上也有人C.x+5>6D.下午有会吗？2、设命题公式G＝¬(P→Q)，H＝P→(Q→¬P)，则G与H的关系是(A)。A.GHB.HG C.G＝HD.以上都不是.3、设A,B为集合，当(D)时A-B＝B。A.A＝B B.AB C.BA D.A＝B＝∅.4、设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有(B)。A.自反性 B.传递性 C.对称性D.以上答案都不对5、设G是连通平面图，有5个顶点，6个面，则G的边数是(A)。A.9条B.5条 C.6条D.11条6、设G是5个顶点的完全图，则从G中删去(A)条边可以得到树。A.6B.5 C.10D.47、设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（C）集合相等。A.X=S2或S5；B.X=S4或S5；C.X=S1，S2或S4；D.X与S1，…，S5中任何集合都不等8、设R和S是集合A上的关系,R∩S必为反对称关系的是(A)。A.当R是偏序关系,S是等价关系B.当R和S都是自反关系C.当R和S都是等价关系D.当R和S都是传递关系9、设R和S是P上的关系，P是所有人的集合，,,则表示关系（A）。A.B.C.∅D.10、设，则有（A）。A.{{1,2}}B.{1,2}C.{1}D.{2}二、填空题（每空2分，共20分）1、设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,x∈R},B={x|0≤x<2,x∈R},则A-B=____,B-A=____,A∩B=____。-1≤x<0；{x|1<x<2,x∈R}；{x|0≤x≤1,x∈R}2、设集合A＝{2,3,4,5,6}，R是A上的整除关系，则R以集合形式(列举法)记为____。{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}3、设一阶逻辑公式G=∀xP(x)→∃xQ(x)，则G的前束范式是____。∃x(P(x)∨Q(x))4、设G是具有8个顶点的树，则G中增加____条边才能把G变成完全图。(完全图的边数，树的边数为n-1)215、设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为____，分枝点数为____。12；36、判断一个语句是否为命题，首先要看它是否为____，然后再看它是否具有唯一的____。陈述句；真值三、计算证明题（每题10分，共40分）1、设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)(2)R∙S＝{(a,b),(c,d)},R∪S＝{(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R-1＝{(a,a),(c,a),(c,b),(d,c)},S-1∙R-1＝{(b,a),(d,c)}。2、设一阶逻辑公式：G=(∀xP(x)∨∃yQ(y))→∀xR(x)，把G化成前束范式。解：G=(xP(x)∨yQ(y))→xR(x) =(xP(x)∨yQ(y))∨xR(x) =(xP(x)∧yQ(y))∨xR(x) =(xP(x)∧yQ(y))∨zR(z) =xyz((P(x)∧Q(y))∨R(z))3、设命题公式G=(P→Q)∨(Q∧(P→R)),求G的主析取范式。解：G=(P→Q)∨(Q∧(P→R))=(P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=m3∨m4∨m5∨m6∨m7=(3,4,5,6,7)。4、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解：设A、B、C分别表示会打排球、网球和篮球的学生集合。则：|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|-|A∩B∩C|＝|(A∩B)|+5-2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不会打这三种球的共5人。四、证明题（每题10分，共20分）1、A,B为两个任意集合，求证：A-(A∩B)=(A∪B)-B。证明：A－(A∩B)=A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B而(A∪B)－B=(A∪B)∩~B=(A∩~B)∪(B∩~B)=(A∩~B)∪=A－B所以：A－(A∩B)=(A∪B)－B2、利用形式演绎法证明：P→Q，¬QR，¬R，¬SP=>¬S。证明：(1)¬R前提(2)¬QR前提（3）¬Q（1），（2）（4）P→Q前提（5）¬P（3），（4）（6）¬SP前提(7)¬S（5），（6）

离散数学复习思考题二及答案一、选择题（每题2分，共20分）1、设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备(D)。A.自反性 B.传递性 C.对称性 D.反对称性2、设半序集(A,≤)关系≤的哈斯图如右图所示，若A的子集B={2,3,4,5},则元素6为B的(B)。A.下界B.上界 C.最小上界D.以上答案都不对3、下述命题公式中，是重言式的为（C）。A.B.C.D.4、设I是如下一个解释：D＝{a,b},,则在解释I下取真值为1的公式是(D)。A.∃x∃yP(x,y)B.∀x∀yP(x,y) C.∀xP(x,x)D.∀x∃yP(x,y)5、下列是两个命题变元p，q的小项是（C）。A.p∧┐p∧qB.┐p∨qC.┐p∧q D.┐p∨p∨q6、设A={1,2,3}，则A上有（D）个二元关系。A.23B.32C.D.。7、设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有(D)。A.<Z，+，/>B.<Z，/>C.<Z，-，/>D.<P(A)，∩>8、若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为(B)。A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q9、设（D）。A.3,8B.C.D.10、若X是Y的子集，则一定有（D）。A.X不属于YB.X∈YC.X真包含于YD.X∩Y=X二、填空题（每空2分，共20分）1、设有限集A,B，|A|=m,|B|=n,则||(AB)|=____。2、设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____；(A)-(B)＝____。{3};{3},{1,3},{2,3},{1,2,3}}3、设有限集合A,|A|=n,则|(A×A)|=____。4、若H1∧H2∧…∧Hn是____，则称H1,H2,…Hn是相容的，若H1∧H2∧…∧Hn是____，则称H1,H2,…Hn是不相容的。可满足式;永假式5、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为____；“虽然你努力了，但还是失败了”的翻译为____。;6、在一棵根树中，仅有一个结点的入度为____，称为树根，其余结点的入度均为____。0;1三、计算证明题（每题10分，共30分）1、设I是如下一个解释：D={2,3},abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)32320011试求(1)P(a,f(a))∧P(b,f(b));∀x∃yP(y,x).解：(1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2)) =P(3,2)∧P(2,3) =1∧0 =0(2)xyP(y,x)=x(P(2,x)∨P(3,x)) =(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3)) =(0∨1)∧(0∨1) =1∧1 =12、设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。画出半序集(A,R)的哈斯图；写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；写出A的最大元，最小元，极大元，极小元。解：（1）（2）B无上界，也无最小上界。下界1,3;最大下界是3（3）A无最大元，最小元是1，极大元8,12,9;极小元是13、求下列公式的主析取范式和主合取范式(P→Q)∧(P→R)解：(P→Q)∧(P→R)(PQ)∧(PR)(合取范式)(PQ(R∧R)∧(P(Q∧Q)R)(PQR)∧(PQR)(PQR)(PQR)(PQR)∧(PQR)(PQR)(主合取范式)(P→Q)∧(P→R)(PQ)(PR)P(QR)(合取范式)(P(QQ)(RR))((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)四、证明题（每题10分，共30分）1、利用形式演绎法证明：{P→Q,R→S,P∨R}蕴涵Q∨S。证明：(1)P∨R P(2)¬R→P Q(1)(3)P→Q P(4)¬R→Q Q(2)(3)(5)¬Q→R Q(4)(6)R→S P(7)¬Q→S Q(5)(6)(8)Q∨S Q(7)2、设<H，*>是<G，*>的子群，定义R＝{<a，b>|a、b∈G且a－1*b∈H}，则R是G中的一个等价关系，且[a]R＝aH。证明：对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以<a，a>∈R。若<a，b>∈R，则a－1*b∈H。因为H是G的子群，故(a－1*b)－1＝b－1*a∈H。所以<b，a>∈R。若<a，b>∈R，<b，c>∈R，则a－1*b∈H，b－1*c∈H。因为H是G的子群，所以(a－1*b)*(b－1*c)＝a－1*c∈H，故<a，c>∈R。综上可得，R是G中的一个等价关系。对于任意的b∈[a]R，有<a，b>∈R，a－1*b∈H，则存在h∈H使得a－1*b＝h，b＝a*h，于是b∈aH，[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a－1*b＝h∈H，<a，b>∈R，故aH[a]R。所以，[a]R＝aH。3、A,B为两个任意集合，求证：A-(A∩B)=(A∪B)-B。证明：A－(A∩B)=A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B而(A∪B)－B=(A∪B)∩~B=(A∩~B)∪(B∩~B)=(A∩~B)∪=A－B所以：A－(A∩B)=(A∪B)－B.

离散数学复习思考题三及答案一、选择题（每题2分，共20分）1、若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是(C)。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).2、设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x),H＝xP(x),则一阶逻辑公式G→H是(C)。A.恒真的B.恒假的 C.可满足的D.前束范式.3、下列关于集合的表示中正确的为(B)。A.{a}∈{a,b,c} B.{a}{a,b,c} C.∅∈{a,b,c}D.{a,b}{a,b,c}4、命题xG(x)取真值1的充分必要条件是(A)。A.对任意x，G(x)都取真值1B.有一个x0，使G(x0)取真值1C.有某些x，使G(x0)取真值1D.以上答案都不对5、设图G的相邻矩阵为，则G的顶点数与边数分别为(D)。A.4,5B.5,6 C.4,10 D.5,86、若A-B=∅，则下列哪个结论不可能正确？(D)A.A=∅B.B=∅C.ABD.BA7、下列关系中是等价关系的是（C）。A.不等关系B.空关系C.全关系D.偏序关系8、对于一个从集合A到集合B的映射，下列表述中错误的是（C）。A.对A的每个元素都要有象B.对A的每个元素都只有一个象C.对B的每个元素都有原象D.对B的元素可以有不止一个原象9、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（C）。A.p→qB.q→pC.┐q→┐pD.┐p→q10、设A={a,b,c},则A到A的双射共有（B）。A.3个B.6个C.8个D.9个二、填空题（每空2分，共20分）1、设谓词的定义域为{a,b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式是____。(R(a)∧R(b))→(S(a)∨S(b))2、设集合A＝{1,2,3,4}，A上的二元关系R＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}。则RS＝____,R2＝____。{(1,3),(2,2)};{(1,1),(1,2),(1,3)}3、设集合A={a,b},B={1,2},则从A到B的所有映射是____,其中双射的是____。1={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)},;3,44、已知命题公式G＝¬(P→Q)∧R，则G的主析取范式是____。(P∧¬Q∧R)5、设p:我们爬山,q:我们划船,在命题逻辑中，命题“我们不能既爬山又划船”的符号化形式为____。¬（p∧q）6、一个命题含有4个原子命题，则对其所有可能赋值有____种。1622、命题公式(P∨Q)→R的只含联结词¬和∧的等值式为：____。7、无向图G有11条边，4个3度结点，其余结点均为5度结点，则G的结点数为____。6三、计算证明题（每题10分，共30分）1、设集合A＝{1,2,4,6,8,12}，R为A上整除关系。画出半序集(A,R)的哈斯图；写出A的最大元，最小元，极大元，极小元；写出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.解：(1)哈斯图如下图(2)无最大元，最小元1，极大元8,12；极小元是1(3)B无上界，无最小上界。下界1,2；最大下界22、设集合A＝{1,2,3,4}，A上的关系R＝{(x,y)|x,y∈A且x≥y},求 （1）画出R的关系图；（2）写出R的关系矩阵.解：（1）（2）3、通过求主析取范式判断下列命题公式是否等价：(1)G=(P∧Q)∨(¬P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(¬P∧R))解：G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3＝(3,6,7)H=(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7G,H的主析取范式相同，所以G=H四、证明题（每题10分，共30分）1、证明：(A-B)-CA-(B-C)证明：∀x∈(A-B)-C，有x∈A-B且xC，即x∈A，xB且xC。从而x∈A，xB-C，故x∈A-(B-C)。从而(A-B)-CA-(B-C)2、用真值表法证明Ｐ↔Ｑ(Ｐ→Ｑ)∧(Ｑ→Ｐ)证明：列出两个公式的真值表：PQPQ（PQ）（QP）FFFTTFTTTTFFFFTT由定义可知，这两个公式是等价的。3、用推理规则证明P→Q,¬(Q∨R),P∧R不能同时为真。证明：(1)PR前提(2)P(1)(3)PQ前提(4)Q(2),(3)(5)(QR)前提(6)QR(5)(7)Q(6)(8)QQ(4),(7)

离散数学复习思考题四及答案一、选择题（每题2分，共20分）1、集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y∈A}，则R的性质为（B）。A.自反的B.对称的C.传递的，对称的D.传递的2、下列语句中是命题的只有（A）。A.1+1=10 B.x+y=10C.sinx+siny<0D.xmod3=23、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D）。A.p→┐q B.p∨┐qC.p∧qD.p∧┐q4、设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，则对应于R的A的划分是（D）。A.{{a},{b,c},{d}}B.{{a,b},{c},{d}}C.{{a},{b},{c},{d}}D.{{a,b},{c,d}}5、设,,则下列正确的是（A）。A.B.C.D.以上都不对6、在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是(A)。A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)7、以下命题公式中，为永假式的是(C)。A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)8、下列式子正确的是(B)。A.∅∈∅B.∅∅C.{∅}∅D.{∅}∈∅9、一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（A）。A.G没有奇数度结点B.G有1个奇数度结点C.G有2个奇数度结点D.G没有或有2个奇数度结点10、设〈G,*〉是群，且|G|>1，则下列命题不成立的是（B）。A.G中有幺元B.G中么元是唯一的C.G中任一元素有逆元D.G中除了幺元外无其他幂等元二、填空题（每空2分，共20分）1、设R是集合A上的等价关系，则R所具有的关系的三个特性是____，____，____。自反性;对称性;传递性2、设集合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=____。{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}3、谓词公式的前束范式为____。4、设集合A＝{1,2,3,4}，B={a，b，c}，则A×B＝____。125、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=____。326、若含有n个命题变项的公式A是矛盾式，则A的主合取范式含____个极小项。2n三、计算证明题（每题10分，共30分）1、设A={a,b},B={c}。求下列集合：(1)A×{0,1}×B；(2)B2×A；(3)(A×B)2;(4)P(A)×A。解：（1）A×{0,1}×B={<a,0,c>,<a,1,c>,<b,0,c>,<b,1,c>};（2）B2×A={<c,c,a>,<c,c,b>};（3）(A×B)2={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>};（4）P(A)×A={<∅,a>,<∅,b>,<{a},a>,<{a},b>,<{b},a>,<{b},b>,<A,a>,<A,b>}。2、求下列各公式的主析取范式和主合取范式（1）(P→Q)∧R（2）P→(P∧(Q→P))解：（1）(P→Q)R(PQ)R(PR)(QR)（析取范式）(P(QQ)R)((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）((P→Q)R)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）(P→Q)R(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）（2）P→(P(Q→P))P(P(QP))PPT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）3、设A,B,C是任意集合，证明或否定下列断言：（1）若AB，且BC，则AC；（2）若AB，且BC，则A∈C;（3）若A∈B，且B∈C，则A∈C；（4）若A∈B，且BC，则A∈C；解：(1)成立。对∀x∈A,因为AB，所以x∈B。又因为BC，所以x∈C。即AC。(2)不成立。反例如下：A={a},B={a,b},C={a,b,c}。虽然AB，且BC，但AC。(3)不成立。反例如下：A={a},B={{a},b},C={{{a},b},c}。虽然A∈B，且B∈C，但AC。(4)成立。因为A∈B,且BC，所以A∈C。四、证明题（每题10分，共30分）1、设A，B，C为任意集合，证明：A∩(B-C)＝(A∩B)-(A∩C)证明：(A∩B)-(A∩C)=(A∩B)∩=(A∩B)∩（∪）=(A∩B∩)∪(A∩B∩)=A∩B∩=A∩（B∩）=A∩（B-C）2、设R是A上的二元关系，则：R是传递的R*RR。证明：若R是传递的，则<x，y>∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有<x，y>∈R，所以R*RR。反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则<x，y>∈R*R，于是有<x，y>∈R，即有xRy，所以R是传递的。

离散数学复习思考题五及答案一、选择题（每题2分，共20分）1、判断下列命题中为真的是(A)。A.A-B=B-AA=BB.空集是任何集合的真子集C.空集只是非空集合的子集D.若A的一个元素属于B，则A=B2、下列等值式中不正确的是（D）。A.┐(∀x)A(∃x)┐AB.(∀x)(B→A(x))B→(∀x)A(x)C.(∃x)(A(x)∧B(x))(∃x)A(x)∧(∃x)B(x)D.(∀x)(∀y)(A(x)→B(y))(∀x)A(x)→(∀y)B(y)3、设R是A上的二元关系,且R·RR,则可以肯定R应是(D)。A.对称关系B.全序关系C.自反关系D.传递关系4、设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是(C)。A.{2}AB.{a}A C.∅{{a}}BED.{{a},1,3,4}B5、设X，Y，Z是集合，“-”是集合相对补运算，下列等式不正确的是（A）。A.(X-Y)-Z=X-(Y∩Z)B.(X-Y)-Z=(X-Z)-YC.(X-Y)-Z=(X-Z)-(Y-Z)D.(X-Y)-Z=X-(Y∪Z)6、设G是连通简单平面图，G中有11个顶点5个面，则G中的边是(D)。A.10B.12C.16D.147、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D）。A.p→┐qB.p∨┐qC.p∧qD.p∧┐q8、无向图G中有16条边，且每个结点的度数均为2，则结点数是（B）。A.8B.16C.4D.329、在由3个元素组成的集合上，可以有(B)种不同的关系。A.3B.8C.9D.2710、设,则=（B）。A.B.C.D.二、填空题（每空2分，共20分）1、设命题公式G＝¬(P→(QR))，则使公式G为真的解释有____，____，____。(1,0,0);(1,0,1);(1,1,0)。2、设p:小王走路,q:小王唱歌,在命题逻辑中，命题“小王