《离散数学》同步练习答案

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题设：p：派小王去开会。q：派小李去开会。则命题：“派小王或小李中的一人去开会”可符号化为：(pv^q)a(^pvq)。设A,B都是命题公式，AnB，则AtB的真值是T。设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：—paq_。设A,B代表任意的命题公式，则蕴涵等值式为TOC\o"1-5"\h\zA—B^^-AvB。设，P：径一事；q：长一智。在命题逻辑中，命题：“不径一事，不长一智。”可符号化为：「pT「q—。设A,B代表任意的命题公式，则德•摩根律为-1(AaB)—IAv-1B)。设，P：选小王当班长；q：选小李当班长。则命题：“选小王或小李中的一人当班长。”可符号化为：(pviq)a(ipvq)。设，P：他聪明；Q：他用功。在命题逻辑中，命题：“他既聪明又用功。”可符号化为：PaQ。对于命题公式A，B，当且仅当AtB是重言式时，称“A蕴含B”,并记为AnB。设：P：我们划船。Q：我们跑步。在命题逻辑中，命题：“我们不能既划船又跑步。”可符号化为：i(PaQ)_。设P,Q是命题公式，德•摩根律为：-1(PvQ)o-iPa-1Q)。设P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。”可符号化为：iPtQ。设p：小王是100米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑冠军。”可符号化为：TOC\o"1-5"\h\zpvq。设A，C为两个命题公式，当且仅当AtC为一重言式时，称C可由A逻辑地推出。判断题设A，B是命题公式，则蕴涵等值式为AtBo「AaB。(x)命题公式^pAqA^r是析取范式。(V)陈述句“x+y>5”是命题。(x)110(p=l,q=l,r=0)是命题公式((「(pAq))Tr)vq的成真赋值。(V)命题公式pT(「pAq)是重言式。(x)设A,B都是合式公式，则AaBt「B也是合式公式。(V)Av(BaC)o(AvB)v(AvC)。(x)陈述句“我学英语，或者我学法语”是命题。(V)命题“如果雪是黑的，那么太阳从西方出”是假命题。(x)“请不要随地吐痰！”是命题。(x)PtQPaQ。(x)陈述句“如果天下雨，那么我在家看电视”是命题。(V)命题公式(PaQ)v(「RtT)是析取范式。(x)命题公式(Pa「Q)vRv(「PaQ)是析取范式。(V)三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。”可符号化为_(2)_。PtQQtP「Qt「PQv「P(1)明年国庆节是晴天。(2)在实数范围内，x+y〈3。(3)请回答这个问题！(4)明天下午有课吗？在上面句子中，是命题的只有—(1)—。命题公式A与B是等值的，是指—(4)_。A与B有相同的命题变元AoB是可满足式AtB为重言式AoB为重言式(1)雪是黑色的。(2)这朵花多好看呀！。(3)请回答这个问题！(4)明天下午有会吗？在上面句子中，是命题的是(1)。设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。”可符号化为_(2)_。QtPPtQ「QPQv^P6•设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。”在命题逻辑中可符号化为—(3)。(1)QtP(2)PtQ(3)「PtQ(4)Qv「P7.(1)现在开会吗？(2)在实数范围内，x+y>5。(3)这朵花多好看呀！(4)离散数学是计算机科学专业的一门必修课。在上面语句中，是命题的只有(4)—。设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游。”可符号化为—(1)—P可符号化为—(1)—PtQ「QP下列式子是合式公式的是(1)(PvtQ)(3)(P「Q)(1)1+101=110(3)全体起立！在上面句子中，是命题的是(2)QtP(4)Qv^P(2)「(Pt(QvR))aQtR(2)中国人民是伟大的。(4)计算机机房有空位吗？。设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功。”在命题逻辑中可符号化为—(3)。(1)PaQ(2)PtQ(3)Pv「Q(4)Pa「Q(1)如果天气好，那么我去散步。(2)天气多好呀！(3)x=3。(4)明天下午有会吗？在上面句子中(1)是命题。设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为—(4)—。(1)PvQ(2)PtQ(3)Pa「Q(4)PaQ

四、解答题1.设命题公式为(「pTq)T(qT「p)。求此命题公式的真值表；给出它的析取范式；(1)pq—p—p_qq^—p(-p-q)-T(q—T-p)TTFTFFTFFTTTFTTTTTFFTFTT(2)(―p—q)—t(q—T―p)o—>(「pTq)V(qT「p)o—<(pVq)V(「qV「p)o(—pA—q)V^qV^p2.设命题公式为(pTq)a(pvr)。(1)求此命题公式的真值表；(2)给出它的析取范式；p(1)qrp—qpVr(pTq)a(pvr)TTTTTTTTFTTTTFTFTFTFFFTFFTTTTTFTFTFFFFTTTTFFFTFF(2)(pTq)a(pvr)o(「pvq)a(pvr)o((「pvq)Ap)v((「pvq)Ar)o((「pAp)v(qAp))v((「pAr)v(qAr))o(qAp)v(「pAr)v(qAr)3.设命题公式为(「QA(PTQ)P。求此命题公式的真值表；求此命题公式的析取范式；(1)PQ-QP—Q-P-QA(P—Q)(-QA(P—Q))—-PTTFTFFTTFTFFFTFTFTTFTFFTTTTT(2)解：(「QA(PTQ))T「Po(「QA(-PVQ))T「Po―(—iQa(—PVQ))V—iPo(——iQV~~PVQ))VPoQV(Pa->Q)V「P完成下列问题求命题公式(PA(QfR))fS的析取范式。解：(PA(QfR))—So(PA(-QVR))-So-(PA(-QVR))VSo(―PV~(-QVR))VS

o-PV(-1-QA-R)VSo「PV(Q—R)VS5.设命题公式为(Pa(PtQ))tQ。求此命题公式的真值表；求此命题公式的析取范式；(1)PQP-QPA(P-Q)(Pa(PtQ))tQTTTTTTFFFTFTTFTFFTFT(2)解：(PA(P-Q))-Qo(PA(-PVQ))-Qo-(PA(-PVQ))VQo(-PV-(-PVQ))VQo-PV(--PA-Q)VQo-PV(PA-Q)VQ设命题公式为((PvQ)a「P)tQ。求此命题公式的真值表；给出它的析取范式；(1)PQPVQ-P(PVQ)A-P((PVQ)A-P)fQFFFTTTTTTOC\o"1-5"\h\zTTTFFFFTTTTTTFTFFFFTFTTT(2)解：((PVQ)A^P)tQ((PvQ)a「P)VQo(-(PvQ)V(--P))VQ^-pv-q)vpvqoT用直接证法证明前提：PvQ,PtR,QtS结论：SVR证明：1)PVQP2)「PfQT1)E3)QfSP4)「PfST2)3)I5)「SfPT4)E6)PfRP7)WT5)6)I8)SVRT7)E用直接证法证明前提：Pt(QvR),St「Q,P,So结论：R证明：1)Pt(QvR)P2)PP3)(QvR)T2)3)I4)St「QP5)SP6)-QT4)5)I7)RT3)6)E第二章谓词逻辑一填空题若个体域是含三个元素的有限域｛a,b,c｝，则^xA(x)。A(a)vA(b)vA(c)取全总个体域，令F(x)：x为人,G(x)：x爱看电影。则命题“没有不爱TOC\o"1-5"\h\z看电影的人。”可符号化为___「Gx(F(x)aG(x)))。若个体域是含三个元素的有限域｛a，b，c｝，则VxA(x)oA(a)aA(b)aA(c)。取全总个体域，令M(x)：x是人,G(y)：y是花，H(x,y)：x喜欢y。则命题“有些人喜欢所有的花。”可符号化为3x(M(x)A(Vy(G(y)TH(x,y))))。取个体域为全体人的集合。令F(x)：x在广州工作,G(x)：x是广州人。在一阶逻辑中，命题“在广州工作的人未必都是广州人。”可符号化为—<Vx(F(x)tG(x))。P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题：“每个学生都要参加考试”可符号化为：Vx(P(x)TQ(x))_。M(x)：x是人，B(x)：x勇敢。则命题“有人勇敢，但不是所有的人都勇敢”谓词符号化为3x(M(x)aB(x))a—Vx(M(x)TB(x))。P(x)：x是人，M(x)：x聪明。则命题“尽管有人聪明，但不是一切人都聪明”谓词符号化为3x(P(x)aM(x))a—Vx(P(x)TM(x))___。I(x)：x是实数，R(x)：x是正数，N(x)：x是负数。在谓词逻辑中，命题:“任何实数或是正的或是负的”可符号化为:_Vx(I(x)T(R(x)vN(x))_。P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题：“每个学生都要参加考试”可符号化为：Vx(P(x)TQ(x))—。令M(x)：x是大学生,P(y)：y是运动员，H(x,y)：x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为3x(M(x)A(Vy(P(y)TH(x,y)))。判断题设A,B都是谓词公式，则VxA^「B也是谓词公式。(V)TOC\o"1-5"\h\z设c是个体域中某个元素，A是谓词公式，则A(c)nVxA(x)。(x)VxVyA(x,y)oVyVxA(x,y)。(J)VxWyA(x,y)o3yVxA(x,y)。(x)取个体域为整数集，则谓词公式VxVy(xxy=y)是假命题。(J)(Vx)(P(x)tQ(x))o(Vx)(「P(x)vQ(x))o(J)命题公式(Pa「QvR)v(^PaQ)是析取范式。(x)谓词公式(Vx)(A(x)TB(x,y))aR(x)的自由变元为x,y。(J)((Vx)A(x)TB)oGx)(A(x)tB)。(x)R(x)：“x是大学生。"是命题。(x)三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。设F(x)：x是火车，G(x)：x是汽车，H(x,y)：x比y快。命题“某些汽车比所有火车慢”的符号化公式是(2)。3y(G(y)TVx(F(x)aH(x，y)))3y(G(y)aVx(F(x)tH(x，y)))Vx3y(G(y)T(F(x)aH(x，y)))3y(G(y)tVx(F(x)tH(x，y)))设个体域为整数集，下列真值为真的公式是(3)_。3yVx(x—y=2)VxVy(x—y=2)Vx3y(x—y=2)3xVy(x—y=2)设F(x)：x是人，G(x)：x早晨吃面包。命题“有些人早晨吃面包”在谓TOC\o"1-5"\h\z词逻辑中的符号化公式是(4)。(Vx)(F(x)TG(x))(Vx)(F(x)aG(x))(3x)(F(x)TG(x))(3x)(F(x)aG(x))下列式子中正确的是_(1)。「(Vx)P(x)o(3x)P(x)「(Vx)P(x)o(Vx)「P(x)「(3x)P(x)o(3x)「P(x)「(3x)P(x)o(Vx)「P(x)6•下面谓词公式是永真式的是b)。P(x)TQ(x)(Vx)P(x)T(3x)P(x)P(a)T(Vx)P(x)「P(a)T(3x)P(x)设S(x)：x是运动员，J(y)：y是教练员，L(x,y)：x钦佩y。命题“所有运动员都钦佩一些教练员”的符号化公式是c)。Vx(S(x)aVy(J(y)aL(x，y)))Vx3y(S(x)T(J(y)TL(x，y)))Vx(S(x)T3y(J(y)aL(x，y)))3yVx(S(x)T(J(y)aL(x，y)))下列式子是合式公式的是(2)。(1)(PVTQ)(2)「(Pa(QVR))(3)(P「Q)(4)aQtaR下列式子中正确的是_(1)_。「(Vx)P(x)o(3x)P(x)「(Vx)P(x)o(Vx)「P(x)「(3x)P(x)o(3x)「P(x)「(3x)P(x)o(Vx)「P(x)

四、解答题1.构造下面推理的证明:前提:3xF(x)TVy((F(y)vG(y))TR(y))，3xF(x)。结论::3xR(x)。证明:（1）3xF(x)TVy((F(y)vG(y))TR(y))前提引入（2）3xF(x)前提引入（3）Vy((F(y)vG(y))TR(y))(1)（2）假言推理（4）F(c)(2)EI（5）F(c)vG(c)（4）附加（6）(F(c)vG(c))TR(c)(3)UI（7）R(c)(5)（6）假言推理（8）3xR(x)(7)EG2.在一阶逻辑中构造下面推理的证明每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。令F（x）：x喜欢步行，G（x）：x喜欢坐汽车，H（x）：x喜欢骑自行车。前提:Vx(F(x)t「G(x)),Vx(G(x)vH(x)),3x(「H(x))结论:31x(「F(x))证明(1)3x(「H(x))前提引入(2)-1H(c)(1)EI(3)Vx(G(x)vH(x))前提引入(4)G(c)vH(c)(3)UI(5)G(c)(6)Vx(F(x)t「G(x))前提引入(7)F(c)T「G(c)(6)UI

「F(c)(8)EG3x(「F(x(8)EG在命题逻辑中构造下面推理的证明：如果他是理科学生，他必须学好数学。如果他不是文科学生，他必是理科学生。他没学好数学，所以他是文科学生。令F(x)：x是理科学生，G(x)：x学好数学，H(x)：x是文科学生。前提：Vx(F(x)TG(x)),Vx(「H(x)TF(x)),3x(「G(x))结论：3x(H(x))证明前提引入前提引入T(1)(2)I前提引入T(3前提引入前提引入T(1)(2)I前提引入T(3)(4)I3x(「G(x))3x(「F(x))Vx(「H(x)TF(x))3x(H(x))用直接证法证明：前提：(Vx)(C(x)—W(x)AR(x))，(3x)(C(x)AQ(x))结论：(3x)(Q(x)AR(x))。TOC\o"1-5"\h\z推理：1)(Vx)(C(x)fW(x)AR(x))P(3x)(C(x)AQ(x))pC(a)AQ(a)ES2)C(a)fW(a)AR(a)US1)C(a)T3)IW(a)AR(a)T4)5)IQ(a)T3)IR(a)T6)IQ(a)AR(a)T7)8)I(3x)(Q(x)AR(x))EG9)第三章集合与关系一填空题如果|A|=n,那么|AXA|=①。A上的二元关系有2n2个。TOC\o"1-5"\h\z集合A上关系R的自反闭包r(R)=RuI。设集合A上的关系R和S,R={(1,2),(1,3),(3,2)},S={(1,3),(2,1),(3,2)}，则S<R={(1,2),(2,2),(2,3)}。如果|A|=n,那么|P(A)|=2n。设集合A上的关系R和S,R={<1,2>,<2,1>,<3,4>,<4,3>},S={<1,3>,<3,1>,<2,4>,<4,2>},则RoS={v1,4>,v2,3>,v3,2>,v4,1>}。设集合E={a,b,c},E的幂集P(E)=。设R是定义在集合X上的二元关系，如果对于每个x,yeX,，则称集合X上的关系R是对称的。设关系R和S为，R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}，则RoS=—.一_。设R是定义在集合X上的二元关系，如果对于每个x,yeX,，则称集合X上的关系R是自反的。判断题设A、B、C为任意的三个集合，则Ax(BxC)=Ax(BxC)。(X)设S,T是任意集合，如果S-T=0,则S=T。(X)集合A=｛1,2,3,4｝上的关系｛<1,2>,<2,3>,<2,4>,<3,4>｝是一个函数。(X)集合A=｛1,2,3,4｝上的整除关系是等价关系。(X)集合A的幂集P(A)上的包含关系是偏序关系。(V)设A=｛a,b,c｝,ReAxA且R=｛<a,b>,<a,c>｝,则R是传递的。(V)设A,B是任意集合，如果B丰0则A-B丰A。(X)集合A=｛1,2,3｝上的关系｛<1,1>,<2,2>,<3,3>,<1,2>｝是传递的。(V)集合A=｛1,2,3,4｝上的小于关系是等价关系。(X)关系｛<X],x2>|x1,x2eN,X]+x2<6｝能构成一个函数。(X)10•集合A上的恒等关系是偏序关系。(V)集合A={1,2,3}上的关系S={vl,l>,vl,2>,v3,2>,v3,3>}是自反的。(X)设X={1,2,3},Y={a,b,c}。函数F={v1,a>,<2,c>,<3,b>}是双射。(V)TOC\o"1-5"\h\z集合A上的关系R的自反闭包r(R)=RUIA。(V)集合A上的偏序关系R是自反的、对称的、传递的。(X)设A,B是任意集合，则A㊉B=(A-B)U(B-A)。(V)三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。设A={a,b,c},B={a,b}，则下列命题不正确的是a)。A—B={a,b}AGB={a,b}A㊉B={c}BcA设A={a,b,c,d},A上的关系R={<a,b>,vb,a>,<b,c>,<c,d>}，则它的TOC\o"1-5"\h\z对称闭包为c)。R={va,a>,va,b>,vb,b>,vb,a>,vb,c>,vc,c>,vc,d>},R={va,b>,vb,a>,vb,c>,vc,b>,vc,d>},R={va,b>,vb,a>,vb,c>,vc,d>,vc,b>,vd,c>},R={va,a>,va,b>,vb,a>,vb,c>,vc,d>,vd,c>},对于集合{1,2,3,4}上的关系是偏序关系的是a)。R={v1,1>,v1,2>,v1,3>,v1,4>,v2,2>,v2,3>,v2,4>,v3,3>,v3,4>,v4,4>}R={v1,1>,v1,2>,v1,3>,v1,4>,v2,2>,v2,1>,v2,4>,v3,1>,v3,4>,v4,4>}R={v1,1>,v1,2>,v1,3>,v1,4>,v2,2>,v2,1>,v3,1>,v3,3>,v4,1>,v4,4>}R={v2,1>,v1,2>,v1,3>,v1,4>,v2,2>,v4,3>,v2,4>,v3,3>,v3,4>,v4,4>}设A={1,2,3,4,5},B={6,7,8,9,10},以下哪个关系是从A到B的单射函数。a)f={v1,7>,v2,6>,v3,5>,v1,9>,v5,10>}b)f={v1,8>,v2,6>,v3,7>,v4,9>,v5,10>}c)f={v1,7>,v2,6>,v3,5>,v4,6>}d)f={v1,10>,v2,6>,v3,7>,v4,8>,v5,10>}设A={a,b,c},要使关系{va,b>,vb,c>,vc,a>,<b,a>}UR具有对称性，则d)。R={vc,a>,va,c>}R={vc,b>,vb,a>}R={vc,a>,vb,a>}R={vc,b>,va,c>}设S={①，{1},{1,2}}，则S的幂集P(S)有(4)个元素(1)3(2)6(3)7(4)8设R为定义在集合A上的一个关系，若R是_(2)_,则R为等价关系。反自反的，对称的和传递的(2)自反的，对称的和传递的自反的，反对称的和传递的(4)对称的，反对称的和传递的设S，T，M为任意集合，下列命题正确的是c)。女口果SUT=SUM，贝VT=M女口果S-T=①，贝VS=TS-T匸SS㊉S=S设A={a,b,c}，要使关系{va,b>,vb,c>,vc,a>,vb,a>}UR具有对性，贝y(4)。(1)R={vc,a>,va,c>}(2)R={vc,b>,vb,a>}(3)R={vc,a>,vb,a>}(4)R={vc,b>,va,c>}设A={1，2，3，4，5}，B={a，b，c，d，e}，以下哪个函数是从A到B的入射函数b)。a)F={vl.b>,v2,a>,v3,c>,v1,d>,v5,e>}b)F={vl,c>,v2,a>,v3,b>,v4,e>,v5,d>}c)F={v1,b>,v2,a>,v3,d>,v4,a>}d)F={v1,e>,v2,a>,v3,b>,v4,c>,v5,e>}2121四、解答题已知偏序集(A,W),其中A={a,b,c,d,e},“三”为{(a,b),(a,c),(a,d),(c,e),(b,e),(d,e),(a,e)}UIAO画出偏序集(A,三)的哈斯图。求集合A的极大元，极小元，最大元，最小元。ea集合A的极大元是e,极小元a,最大元e,最小元a。2.设R是集合A={1,2,3,4,5,6,7,&9}上的整除关系。给出关系R;(2)画出关系R的哈斯图；指出关系R的最大、最小元，极大、极小元。(1)R={v1,1>,v1,2>,v1,3>,v1,4>,v1,5>,v1,6>,v1,7>,v1,8>,v1,9>,v2,2>,v2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<3,9>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>,<9,9>}(2)4646关系R的无最大，最小兀是1,极大兀是8和9,极小兀是1。3.设R是集合A={1,2,3,4,6,12}上的整除关系。给出关系R；给出COVA画出关系R的哈斯图；给出关系R的极大、极小元、最大、最小元。(1)R={v1,1>,v1,2>,v1,3>,v1,4>,v1,6>,v1,12>,v2,2>,v2,4>,v2,6>,v2,12>,v3,3>,<3,6>,<3,12>,<4,4>,<4,12>,<6,6>,<6,12>,<12,12>}(2)COVA={<1,2>,<1,3>,v2,4>,<2,6><3,6><4,12>,<6,6>,<12,12>}⑶663关系R的极大、最大兀是12,极小兀、最小兀是1。第五章代数结构一填空题TOC\o"1-5"\h\z集合S的幂集P(S)关于集合的并运算“U”的零元为S—。集合S的幂集P(S)关于集合的并运算“G”的零元为©。集合S的幂集P(S)关于集合的并运算“U”的么元为©。一个代数系统VS,*>，其中S是非空集合。*是S上的一个二元运算，如果*在S上是封闭的，则称代数系统VS,*>为广群。判断题含有零元的半群称为独异点。(x)运算“+”是整数集I上的普通加法，则群<1,+>的么元是1。(x)三、填空题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。下列群一定为循环群的是e)。<I，+>(运算“+”是整数集I上的普通加法)<R-{0}，X>(R是实数集，“X”是普通乘法)<Q，+>(运算“+”是有理数集Q上的普通加法)<P(S)，㊉>(