离散数学习题集

离散数学课外习题集编者：金鹏时间：2008-5-6目录：第一章、选择题由n个命题变元组成不等值的命题公式的个数为()A.2nB.2nC.n222nD设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为()PtQB.QtPC.PoQD.「Q—P下列各组公式中，哪组是互为对偶的？()a.p,pb.p,「pc.a,(a*)*d.a,a(其中P为单独的命题变元，a为含有联结词的命题变元)设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为()—ipA—iQB.—Pv—iQC.—i(PoQ)D.Po—iQ下面哪一个命题是命题“2是偶数或-3是负数”的否定？()A.2是偶数或-3不是负数C.2是奇数或-3不是负数C.2不是偶数且-3不是负数D.2是奇数且-3不是负数设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件事”符号化为()PvQB.Pv—Q下列语句中哪个是真命题？()我正在说谎。C.如果1+2=3,那么雪是黑的。下面哪个联结词运算不可交换？C.PoQD.—(—Pv—Q)严禁吸烟。D.如果1+2=5，那么雪是黑的。ab.—»C.vD.^o9・命题公式(Pa(P—Q))—Q是()。A.矛盾式B.蕴含式C.重言式D.等值式下面哪个命题公式是重言式？()(P—Q)A(Q—P)B.(PAQ)—PC.(—PvQ)A—(—PA—Q)D.—(PvQ)下列哪一组命题公式是等值的？()—PA—Q,PvQB.A—(B—A),—A—(A——B)C.Q—(PvQ),—QA(PvQ)D.—Av(AAB),BP—Q的逆反式是()Q——PB.P——QC.—Q—PD.—Q——P—P—Q的逆反式是()Q——PB.P——QC.Q——PD.P——Q下列命题联结词集合中，哪一个是最小联结词组？(){—,o}B.{—,v,a}C.{T}D.{a,—}下列联结词集合中，哪一个不是最小联结词组？(){—,a}B.{—,—}C.{—,a,v}D.{T}已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的()A.充分条件B.必要条件C.充要条件D.A、B、C都不对—P—Q的反换式是()A.Q——PB.—P——QC.—Q——PD.P——Q下面哪一个命题公式是重言式？()A.P—(QvR)B.(PvR)A(P—Q)(PvQ)o(QvR)D.(Pt(QtR))t((PtQ)t(PtR))下列哪个命题公式不是重言式？()Qt(PvQ)B.(PaQ)tPC.「(Pa「Q)a(^PvQ)D.(PtQ)o(「PvQ)重言式的否定式是()A.重言式B.矛盾式C.可满足式D.蕴含式下面哪一个命题是假命题？()如果2是偶数，那么一个公式的析取范式惟一如果2是偶数，那么一个公式的析取范式不惟一如果2是奇数，那么一个公式的析取范式惟一如果2是奇数，那么一个公式的析取范式不惟一下面哪一组命题公式不是等值的？()「(AtB),Aa「BB.「(AoB),(Aa「B)v(「AaB)C.At(BvC),「Aa(BvC)D.At(BvC),(Aa「B)tC命题公式PtQaR的对偶式为()Pt(QvR)B.Pv(QvR)C.「Pv(QaR)D.「Pa(QvR)命题公式Pt(Q/R)是()A.重言式B.可满足式C.矛盾式D.等值式Po「Qo()「Pt(Pt「Q)B.(「PvQ)v(「QvP)C.(「Pv「Q)a(「QvP)D.(「Pv「Q)a(QvP)命题公式「(PaQ)tR的主析取范式中含极小项的个数为()TOC\o"1-5"\h\zA.8B.3C.5D.0命题公式「(PaQ)tR的主析取范式中含极大项的个数为()A.0B.3C.5D.8命题公式「(PaQ)tR的成真赋值为()A.000,001,110B.001,011,101,110,111C.全体赋值D.无如果AnB成立，则以下各种蕴含关系哪一个成立？()A.BnAB.—An—BC.—Bn—AD.—AnB、填空题下列句子中，是命题的有.我是教师。.禁止吸烟！.蚊子是鸟类动物。.上课去！.月亮比地球大。设P：我生病，Q：我去学校TOC\o"1-5"\h\z.命题“我虽然生病但我仍去学校”符号化为。.命题“只有在生病的时候，我才不去学校”符号化为.命题“如果我生病，那么我不去学校”符号化为。设P：我有钱，Q：我去看电影。.命题“如果我有钱，那么我就去看电影”符号化为。.命题“虽然我有钱，但我不去看电影”符号化为。.命题“当且仅当我有钱时，我才去看电影”符号化为对于下列各式，是永真式的有。.(Pa(PtQ))tQ.Pt(PvQ).Qt(PaQ).(—Pa(PvQ))tQ（5）.（PtQ）tQTOC\o"1-5"\h\z（Pa（PvQ））tRo。Pt（PtQ）。对于下列各式（1）.（「PaQ）v（「Pa「Q）可化简为。（2）.Qt（Pv（PaQ））可化简为。（3）.（「PvQ）o（「Qt「P）aP可化简为。命题公式Pv（Qa「R）的成真赋值为，成假赋值为若且则称X是公式A的子公式。写出表中各列所定义的命题联结词。PQP至QP②Q1110100101010001由n个命题变元可组成个不等值的命题公式。TOC\o"1-5"\h\z用两种形式写出PtQ的对偶式①，②。两个重言式的析取是①，一个重言式与一个矛盾式的析取是②。A、B为两个命题公式，AoB当且仅当①，AnB当且仅当②。设P、Q为两个命题公式，德•摩根律可表示为①，吸收率可表示为②。设命题公式A中仅含有联结词「，a，v，若得到公式A*，则A*称为A的对偶式。公式（PvQ）tR的只含联结词「，a，v的等值式为①，它的对偶式为②。TOC\o"1-5"\h\z命题公式Ao（PaQaR）T0，则其对偶式A*o。在命题演算中，一个蕴含式与它的①式是等值的,它的②式与它的③是不等值的。公式「PtQ的反换式为①，逆反式为②。任意两个不同极小项的合取为①式，全体极小项的析取式必为②。命题公式「（PtQ）的主析取范式为①，主合取范式的编码表示为②。已知公式A（P,Q,R）的主合取范式为MoaM3aM5，它的主析取范式为（写成编码形式）。命题公式「（PoQ）的主析取范式为①，其编码表示为②，主合取范式的编码表示为③。对于前提：St「Q,SvR，「R,「PoQ，其有效结论为。对于前提：（PaQ）tR，「RvS,「S，其有效结论为。三、判断题“王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（）凡陈述句都是命题。（）语句3x+5y=0是一个命题。（）命题“两个角相等当且仅当它们是对顶角“的值为1。（）语句“x+y=4”是个命题。（）命题“十减四等于五”是一个原子命题。（）命题“如果1+2=3，那么雪是黑的”是真命题。（）（Pt（QaR））是一个命题演算的命题公式，其中P、Q、R是命题变元。（）（Pt（QaRt「Q））是一个命题公式，其中P、Q、R是命题变元。（）若A：张明和李红都是三好学生，则「A：张明和李红都不是三好学生。（）若A：张明和李红都是运动员，则「A：张明和李红不都是运动员。()若P：每一个自然数都是偶数，则「P:每一个自然数都不是偶数。()若P：每个自然数都是偶数，则「P:每个自然数不都是偶数。()如果AoB,贝9AaCoBaC,AvC^BvCo()如果AaCoBaC，贝9AoBo()联结词“/”是可结合的。()联结词“T”是可结合的。()联结词“/”是可交换的。()联结词“T”是可交换的。()联结词“T”是满足交换律。()“学习有如逆水行舟，不进则退”设P：学习如逆水行舟，Q：学习进步，R：学习退步。则命题符号化为Pa(「QtR)。()P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：Pt(「QtR)。()设P、Q是两个命题，当且仅当P、Q的真值均为1时，PoQ的值为1o()命题公式(Pa(PtQ))tQ是矛盾式。()命题公式(Pa(PtQ))tQ是重言式。()联结词a与v不是相互可分配的。()在命题的演算中，每个最小联结词组至少有两个联结词。()命题联结词集｛「,◎｝是最小联结词集。()命题联结词集｛「,a,v｝是最小联结词集。()命题联结词集｛a,t｝是最小联结词集。()命题联结词集｛?｝和｛/｝是最小联结词集。()A是命题公式，A与(A*)*互为对偶式。()A是命题公式，Ao(A*)*o()P是命题变元，P与P互为对偶式。()任一命题公式的主析取范式和它的主合取范式互为对偶式。()任一命题公式都可以表示成与其等值的若干极小项的析取式。()四、综合题使用命题：P：这个材料有趣。Q：这些习题很难。R：这门课程让人喜欢。将下列句子用符号形式写出：.这个材料有趣，并且这些习题很难。.这个材料无趣，习题也不难，而且这门课程也不让人喜欢。.如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。.这个材料有趣，意味着这些习题很难，并且反之亦然。.或者这个材料有趣，或者这些习题很难，并且两者恰具其一。用符号形式写出下列命题：.假如上午不下雨，我去看电影，否则就在家里读书或者看报；.我今天进城，除非下雨；.仅当你走，我将留下；.一个数是素数当且仅当它只能被1和它自身整除。判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。.2是无理数。.5能被2整除。.现在开会吗？.x+5>0o.这朵花真好看呀！.2是素数当且仅当三角形有三条边。.雪是黑色的当且仅当太阳从东方升起。(8).2000年10月1日天气晴好。(9).太阳系以外的星球上有生物。(10).小李在宿舍。(11).全体起立！(12).4是2的倍数或是3的倍数。(13).4是偶数且是奇数。(14).李明与王华是同学。(15).蓝色和黄色可以调配成绿色。确定下列命题的真值：.“如果太阳从西边出来，那么地球自转”；.“如果太阳从东边出来，那么地球自转停止”；(3).“如果8+9>30，那么三角形有三条边”；.“如果疑问句是命题，那么地球将停止转动”。判断下面语句是否是命题，若是，确定其真值：.喜马拉雅山比华山高；.如果时间静止不动，你就可以长生不老；.如果时间流失不止，你就可以长生不老；.伦敦是英国首都；.这盆茉莉花好香阿！给命题变元P、Q、R、S分别指派真值为1、1、0、0,求下列命题公式的真值：.(「(PaQ)v「R)v(((「PaQ)v「R)aS).(Pv(Qt(Ra「P)))o(Qv「S)设A*、B*分别是命题公式A和B的对偶式，判断下列各式是否成立，若不成立，请举例说明：.A*oA.AoB则A*oB*.AnB则A*nB*.(A*)*oA命题联结词“/”定义为P/Qo「(PvQ)•构造P/Q的真值表；•证明V.a.「可以用仅含联结词/的等值公式表示。化简下列命题公式：.Av(「Av(Ba「B)).(AaBaC)v(「AaBaC).((PtQ)o(「Qt「P))aR.((AtB)o(「BA)vC如果有AaCoBaC，是否一定有AoB?如果有AvCoBvC，是否一定有AoB?如果「Ao「B是否有AoB?用真值表判断下列各式是否为重言式：.((「PvQ)a(QtR))t「(Pa「R).(PaQtR)t(Pa「RaQ)设命题公式A的真值表如表所示，试求出A的主析取范式和主合取范式(用编码表示和公式表示)：PQA111101010001用等值演算法证明Pa(PtQ)tQ是重言式。证明下列命题的等值关系：.(PtQ)a(RtQ)^(PvR)tQ.(PaQaAtC)a(AtPvQvC)^(Aa(P^Q))tC.Pt(QtP)oQt(PtR).(PtQ)a(PtR)oPt(QaR).(PvQ)a「(PaQ)o「(PoQ)求证下面命题的蕴含关系：.PaQ=PtQ.(Pt(QtR))=(PtQ)t(PtR)求下面各式的主析取范式与主合取范式，并写出相应的为真赋值。.「(PtQ)o(Pt「Q).(「Rv(QtP))t(PtQvR)).((PtQ)tQ)t((QtP)tP).(Pt(QtR))o(Rt(QtP)).「((PtQ)a(RtP))v「((Rt「Q)t「P联结词f1，f2由表所示真值表定义，证明｛匸，fj是最小联结词组。PQfPPfQ1101100101100011 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一种简单的表决器，表决者每人座位旁边有一按钮,若同意则按下按钮，否则不按按钮，当表决结果超过半数时，会场电铃就会响，否则铃不响。试以表决人数为3人的情况设计表决器电路的逻辑关系。证明｛?｝时最小联结词组。设计一加法器，实现两自然数相加的功能。某勘探队有3名队员。有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，时铁。经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。观察下列推理过程，是否正确，结论是否有效，说明理由。TOC\o"1-5"\h\z.①PaQtRP⑵.②PtRT①I⑶•③PP.④RT②③I所以PaQtR，PnR。下列证明过程是否正确，若正确补足每一步推理依据，否则指出错误.①「DvA.②D.③A.④At(CtB).⑤CtB.⑥C.⑦B.⑧DtB证明At(BtC)，Bt(CtD)=At(BtD)。用CP 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 证明「Pv(「QvR),Qt(RtS),P^QtS。用推理规则说明AtB,「(BvC),AaC是否能同时为真。用推理规则说明(PvQ)tR,「SvU,^RvS,UtW,「W=「Pa「Q。用推理规则证明下列推理的正确性：如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作,则D不愉快。用等值演算法证明「Pa「(PtQ)是矛盾式。用CP规则证明At(BaC),(Et「F)t「C,Bt(Aa「S)=BtE。用反证法证明(AtB)a(CtD),(BtE)a(DtF),「(EaF),AtC=「A。用反证法证明AtB,(「BvC)a「C,「(「AaD)=「D。第二章、选择题谓词公式Vx(P(x)vmyR(y)IQ(x沖量词Vx的作用域是()A.Vx(P(x)v3yR(y))B.P(x)C.(P(x)v3yR(y))D.P(x),Q(x)谓词公式Vx(P(x)v3yR(y))^Q(x)中变元x是()A.自由变量B.约束变量既不是自由变量也不是约束变量既是自由变量也是约束变量若个体域为整体域，下列公式中哪个值为真？()A.Vx3y(x+y=0)B.3yVx(x+y=0)C.VxVy(x+y=O)D.^3x3y(x+y=0)设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式3x(P(x)aQ(x))在下面哪个论域中是可满足的？()A.自然数集B.整数集C.实数集D.以上均不成立设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可符号化为()A.「Vx(C(x)a「G(x))B.「Vx(C(x)t「G(x))C.「^x(C(x)a「G(x))D.「mx(C(x)T「G(x))设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为()A.Vx(A(x)aB(x))B.「mx(A(x)T「B(x))C.^3x(A(x)aB(x))D.「mx(A(x)A「B(x))设Z(x)：x是整数，N(x)：x是负数，S(x,y)：y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式()VxVy(Z(x)AS(x,y)T「N(y))Vx^y(Z(x)AS(x,y)T「N(y))VxVy(Z(x)—S(x,y)A「N(y))Vx(Z(x)AS(x,y)T「N(y))8.令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有的火车慢”可表示为()my(G(y)TVx(F(x)AH(x,y)))my(G(y)AVx(F(x)TH(x,y)))Vxmy(G(yI(F(x)AH(x,y)))my(G(y)TVx(F(x)TH(x,y)))设个体域A={a,b},公式VxP(x)a3xS(x)在A中消去量词后应为()P(x)AS(x)P(a)AP(b)A(S(a)vS(b))P(a)AS(b)P(a)AP(b)AS(a)AS(b)在谓词演算中，下列各式哪个是正确的？()mxVyA(x,y)oVymxA(x,y)3x3yA(x,y)^3y3xA(x,y)mxVyA(x,y)oVxmyA(x,y)VxVyA(x,y)oVyVxA(x,y)下列各式哪个不正确？()Vx(P(x)vQ(x))oVxP(x)vVxQ(x)Vx(P(x)aQ(x))uVxP(x)aVxQ(x)3x(P(x)vQ(x))^3xP(x)v3xQ(x)VxP(x)aQ)oVxP(x)aQ下面谓词公式哪个是前束范式？()VxVymz(B(x,y)—A(z))—VxmyB(x,y)3xVyVx(A(x,y)AB(x,y))Vx(A(x,y—myB(y))13.在谓词演算中：P(a)是VxP(x)的有效结论，其理论根据是()A.全称规定规则(US)B.全称推广规则(UG)C.存在规定规则(ES)D.存在推广规则(EG)、填空题令R(x)：x是实数，Q(x)：x是有理数。TOC\o"1-5"\h\z命题“并非每个实数都是有理数”其符号化为①。命题“虽然有些实数是有理数，但并非一切实数都是有理数”则其符号化可表示为②。设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化为。设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有智能工作都能由计算机来做”符号化为。设Q(x)：x是偶数，P(x)：x是素数，则命题“存在惟一一个偶素数”可符号化为—①，“至多存在一个偶素数”可符号化为―②。设Q(x)：x是奇数，Z(x)：x是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为。设个体域为自然数集，P(x)：x是奇数，Q(x)：x是偶数，则命题“不存在既是奇数又是偶数的自然数”可符号化为。设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数担不是整数”符号化分别为①，②，③。VxVy(P(x,y)AQ(y,z))A3xP(x,y)中Vx的作用域为①，Vy的作用域为②，3x的作用域为③。公式Vx(P(x)—Q(x,y)vmR(y,z)IS(x)中自由变量为①，约束变量为②。取个体域为整数集，给定下列公式：.Vx3y(x•y=0)(2).Vx3y(x•y=1)3x3y(x•y=2)(4)VxVy3z(x-y=z).x-y=-y+x(5).VxVy(x・y=y)(7)Vx(x・y=x)(8).3xVy(x+y=2y)上面公式中，真命题的有①，假命题的有②*11.下列谓词公式.—(3xA(x))与Vx—A(x).Vx(A(x)vB(x))与VxA(x)vVxB(x).Vx(A(x)aB(x))与VxA(x)aVxB(x).3xVyD(x,y)与Vy^xD(x,y)中是等值的。对公式Vx(P(x)vQ(x))，其中P(x):x=1,Q(x):x=2,当论域为｛1,2｝时，其真值为①，当论域为｛0,1,2｝时，其真值为②。设个体域为A=｛a,b,c｝，消去公式VxP(x)a3xQ(x)中的量词，可得。下列各式.Vx(P(x)vQ(x))t(VxP(x)v3xQ(x)).(Vx(A(x)tB(x))aA(c))tA(c).(Vx(—1A(x)tB(x))aVx—B(x))—mxA(x).Ux(P(x)AQ(x)))TmxP(x)T「Q(x))其中是永真式。下列各式.3yVxA(x,y)(2).3xVyA(x,y).Vx3yA(x,y)(4).3x3yA(x,y)它们之间存在着的推理关系。可供选择的项有：A.(1)n(2)；⑵n(3)B.⑵n(1)；⑶n⑷C.(1)n(3)；(4)n(3)D.(4)n(1)；(1)n(3)(1)n(3)；(2)n(4)填上联结词：VxP(x)vVxQ(x)Vx(P(x)vQ(x))*17.只用联结词—，V，T,表示以下的公式。TOC\o"1-5"\h\z.3x(P(x)aQ(x))=@；.3x(P(x)^VyQ(y))=②；.Vy(VxP(x)v—Q(y))=③。给定下面谓词公式：.Vx(—F(x)T—F(x)).VxF(x)T3xF(x).—(F(x)T(VyG(x,y)TF(x))).Vx3yF(x,y)T3xVyF(x,y).—VxF(x)^3x—F(x).Vx(F(x)aG(x))T(VxF(x)vVxG(x)).3x3yF(x,y)TVxVyF(x,y).Vx(F(x)vG(x))T(VxF(x)vVxG(x)).(VxF(x)vVxG(x))TVx(F(x)vG(x)).VxVyF(x,y)oVyVxF(x,y).—(VxF(x)TVyG(y))aVyG(y)上面11个公式中，为重言式的有①，为矛盾式的有②。给定下列各公式：.(—mxF(x)vVyG(y))A(F(u)TVzH(z)).3xF(y,x)rVyG(y).Vx(F(x,y)TVyG(x,y))则①是(1)的前束范式，②是(2)的前束范式，③是(3)的前束范式。供选择的 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 有3xVyVz((—F(x)vG(y))A(F(u)TH(z)))VxVyVz((—F(x)vG(y))A(F(u)TH(z)))3xVy(F(y,x)rG(y))VxVy(F(z,x)TG(y))VxVy(—F(z,x)vG(y))@Vx3y(F(x,z)TG(x,y))VxVy(F(x,z)TG(x,y))VyVx(F(x,z)TG(x,y))VyVx(—F(x,z)VG(y))TOC\o"1-5"\h\z谓词公式VxP(x)TVxQ(x)v3yR(y)的前束范式为。谓词公式Vx(P(x)TQ(x,y)v3zR(y,z))rS(x)的前束范式为。*22.谓词公式—％(—VyG(y,b)TH(x))的前束范式为。在谓词逻辑中给出四个推理：.前提：Vx(F(x)TG(x))，3yF(y)；结论：3yG(y).前提：3x(F(x)aG(x))；结论：VyF(y).前提：3xF(x)，3xG(x)；结论：3y(F(y)AG(y))•前提：Vx(F(x)tH(x)),「H(y)；结论：Vx(「F(x))以上四个推理中正确的有。在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢坐汽车,每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车,因而有的人不喜欢步行。命题符号化：F(x)：x喜欢步行；G(x)：x喜欢坐汽车；H(x)：x喜欢骑自行车。前提：Vx(F(x)t「G(x)),Vx(G(x)vH(x)),3x(^H(x))；结论：3x(^F(x))o三、判断题在谓词公式中，一个变量只能是自由变量或约束变量中的一种。()公式Vx(P(x)—Q(x))vR(y)中Vx的作用域为P(x)。()同一谓词公式，指定不同的论域，其真值不一定相同。()谓词公式VxP(x)dy(「P(y))是矛盾式。()*5.Vx(P(x)TQ(x))T0xP(x)TmxQ(x))为真。()对公式3z(P(z)aQ(x,z)AM(z,y))vR(z)中自由变量代入后，有3z(P(z)AQ(a,z)AM(z,b))vR(z)()VxVy(P(x)—Q(y))o3xP(x)TVyQ(y)()*8.P(x),Q(x)表示谓词，P表示命题，有Vx(P(x)tP)o3xP(x)tP()*9.Vx(A(x)aB(x))oVxA(x)aVxB(x)()*10.Vx(A(x)tB(x))=3xA(x)a3xB(x)()任意一个谓词公式都与一个前束范式等价。()公式VxP(x)—3yQ(x,y)前束范式VxVy(P(x)—Q(x,y))为()公式3x(「3yP(x,y)T(3zQ(z)tR(x)))的前束范式为3x3y3z(P(x,y)v「Q(z)vR(x))()下面的推理：条件：Vx(P(x)vQ(x)),根据全称规定(US)有：P(a)vQ(b)是正确的。()对公式3z(P(z)aQ(x,z)aM(z$))vR⑵中约束变量z改名后，得到的等价公式为：3t(P9t)AQ(x,t)AM(t,y))vR(t)()四、综合题1.用谓词和量词将下列命题符号化：.没有不犯错误的人；.尽管有人聪明，但未必一切人都很聪明；.每个计算机系的学生都学离散数学；.所有的人都学习和工作；.并非一切推理都能用计算机完成；.任何自然数都有惟一的一个后继数。*2.令S(x,y,z)表示“x+y=z”G(x,y)表示“x=y”L(x,y)表示“xvy”其中个体域为自然数集，用以上符号表示下列命题：(1).没有x<0,且若x>0当且仅当有这样的y,使得x±y。⑵.并非对一切x,都存在y,使得xWy。(3).对任意的x,若x+y=x，当且仅当y=0olimf(x)=A3.用谓词公式表示命题“’Ta”并写出该命题的否定命题。*4.设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化：.并不是外语学的好的都是三好学生。.有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。指出下列公式中量词每次出现的作用域，并指出个体变量是约束变量还是自由变量。.VxVy(R(x,y)vL(y,z))dxH(x,y).Vx(P(x)CxQ(x))v(VxP(x)tQ(x))设f,g,h是二元运算符号，E,L是二元谓词符号，考查的个体域为有理数集。给出解释如下：f(x,y)=x•y；g(x,y)=x+y；h(x,y)=x2-y2；a=0；b=1；E(x,y):x=y；L(x,y):x1”；A(x)表示“x>1”；B(x)表示“x是某个自然数的平方”。请在此基础上，求下面公式的真值：Vx(A(x)T(A(a)TB(x))T((P—VxA(x))TB(a))下列各式翻译成自然语言,然后在不同的个体域中确定它们的真值：.Vx3y(x•y=0).3xVy(x•y=0).Vx3y(x•y=1).3xVy(x•y=1).Vx3y(x・y=x).3xVy(x・y=x).VxVy3z(x-y=z)个体域分别为：①实数集②整数集③正整数集④非负实数集设解释T如下：个体域为实数集R,元素a=0,函数f(x,y)=x-y,特定谓词F(x,y)为xvy。根据解释T,下列哪些公式为真？哪些为假？.VxF(f(a,x),a).VxVy(「F(f(x,y),x)).VxVyVz(F(x,y)TF(f(x,z),f(y,z))).Vx3yF(x,f(f(x,y),y))求下面谓词公式mx(X(x)AVy(X(yI((Y(x,z)AY(y,z)Ap)TVt(X(t)T(Y(x,t)TY(y,t))))))在赋值(z;p;X(x);Y(x,y))=(2;1;x是自然数;xvy)下的值。设解释T为：个体域为D={-2,3,6},谓词F(x)：xW3,G(x)：x>5,R(x)：xW7。根据解释T,求下列各式的真值：.Vx(F(x)aG(x)).Vx(R(x)tF(x))vG(5).3x(F(x)vG(x))设A(x)是一个含有个体变量x的谓词公式，证明下面等值式成立：—iVxA(x)omx(—A(x))设A(x),B(x)均为含有自由变量x的任意谓词公式，证明：Vx(A(x)tB(x))=VxA(x)tVxB(x)证明：VxVy(G(x)oH(y))nVxG(x)oVxH(x)。设G(x),H(x)分别是谓词公式，试证明VxG(x)—mxH(x)omx(G(x)TH(x))下列公式是否成立，成立则证明，不成立，则举例说明之。.Vx3yA(x,y)^3x3yA(x,y).3xA(x)a3xB(x)^3x(A(x)aB(x))下面公式是否是永真式？说明理由。.(A—mxB(x))omx(ATB(x)).mx(A(x)TB(x))o(VxA(x)—mxB(x))下面的公式是否是永真式？是则证明之，不是，请举出反例：.3xVyA(x,y)^Vy3xA(x,y).(3xA(x)^3xB(x))^3x(A(x)^B(x))下面公式是否有效，对有效的公式加以证明，对无效的公式加以反驳。.Vx(P(x)vQ(x))^(VxP(x)vVxQ(x)).(VxP(x)vVxQ(x))tVx(P(x)vQ(x))航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明这个人一定不是航海家。22.指出下列推理中的错误：(1).①VxF(x)tG(x)②F(y)—G(y)前提引入①US(2).①Vx(F(x)vG(x))前提引入②F(a)vG(b)①us(3).①F(x)tG(x)前提引入②my(F(y)—G(y))①EG(4).①F(x)tG(c)前提引入②Tx(F(x)tG(x))①EG(5).①F(a—G(b)前提引入②mx(F(x)—G(x))①EG(6).®3x(F(x)aG(x))前提引入②3y(H(y)AR(y))前提引入③F(c)aG(c)①ES④F(c)③化简⑤H(c)aR(c)②ES⑥H(c)⑤化简⑦F(c)aH(c)④⑥合取®3x(F(x)aH(x))⑦EG试找出下列推理过程中的错误，写出正确的推导过程，①Vx(P(x)tQ(x))条件②P(yIQ(y)全称规定(US)③3xP(x)条件④P(y)存在规定(ES)⑤Q(y)由条件②④@3xQ(x)存在推广(EG)下面推理是否是一个有效的推理，为什么？①Vx3yQ(x,y)条件②3yQ(a,y)全称规定(US)③Q(a,b)存在规定(ES)④VxQ(x,b)全称推广(UG)⑤3yVxQ(x,y)存在推广(EG)下面推广是否正确，若有错，请指出：Vx(A(x)tB(x))oVx(—A(x)vB(x))①oVX「(A(x)a「B(x))②o—3x(A(x)a—B(x))③o—i(mxA(x)Amx—B(x))④说明理由：23.24.25.TOC\o"1-5"\h\zo—3xA(x)v—3x(—B(x))⑤o—3xA(x)vVxB(x)⑥o^xA(x)tVxB(x)⑦用谓词演算推理规则证明：Vx(P(x)T(Q(y)^R(x))),VxP(x)nQ(y)dx(P(x)AR(x))27．改正下面证明中的错误：前提：Vx(3y(S(x,y)AM(y))^3z(P(z)AR(x,z)))；结论：—TzP(z)TVxVy(S(x,y)T—M(y))。证明过程：①Vx(3y(S(x,y)AM(y))^3z(P(z)AR(x,z)))；P②3y(S(b,y)AM(y))^3z(P(z)AR(b,z))①US③VzP(z)P（附加前提）④Vz(—P(z))③T,E⑤—P(a)④USP(a)v—R(b,a)T,⑤I⑦Vz(—P(z)v—R(b,z))⑥UG⑧—mz(P(z)AR(b,z))⑦T,E⑨7y(S(b,y)AM(y))②，⑧T,L⑩Vy(—S(b,y)v—M(y))⑨T,E(ll)Vy(S(b,y)T—M(y))⑩T,E(12)VxVy(S(x,y)T—M(y))(UG(13)—mzP(z)TVxVy(S(x,y)T—M(y))CP第三章、选择题对任意集合A、B、C,下述论断正确的是（）若AgB,BcC，贝9AgC若AgB,BcC，贝9AcC若AcB,BgC，贝9AgC若AcB,BgC，贝VAcC设A-B=0，则有（）A.B=0B.BH0C.AcBD.AqB3.设P={xl(x+l)2W4},Q={xIx2+1625x},则下列选项正确的是()A.PnQB.P^QC.QnPD.Q=P设A={{1,2,3},{4,5},{6,7,8}}，下列选项正确的是()A.1gAB.{1,2,3}gAC.{{4,5}}gAD.0gA下列个选项错误的是()贝有（）A.0c0B.0g0C.0c{0}D.0g{0}设A={xlx3-x=0}，B={xlx2-4<0,xgZ}，C={xly=2x-1}，D={xlx+y=5,xy=6}A.A=BB.A=CC.C=DD.C=A在00之间填上正确的符号。8.A.=B.g设M={xlf1(x)=0}，N={xlf2(x)=0}A.MHNB.MUNC.cD.笑则方程f](x).f2(x)=0的解为()C.M㊉ND.M-NC.{{0}}gBB.{0,{0,{0}},{0}}D.{0,{0,{0}}}D.{0,{0}}gP(A)A.0B.1C.3D.4设A={a,{a}}，下列选项错误的是()A.{a}gP(A)B.{a}cP(A)C.{{a}}gP(A)D.{{a}}cP(A)设A={0},B=P(P(A)),下列选项错误的是()A.0gBB.{0}gBll.幕集P(P(P(0)))为()A.{{0},{0,{0}}}C.{0,{0,{0}},{{0}},{0}}*12•空集0的幕集P(0)的基数是13.集合A={l,2,・・・，10上的关系R={vx,y>lx+y=lO,XGA,yGA},则R的性质为（）A.自反的B.对称的C.传递的，对称的D.反自反的，传递的14•设A={a,b,c}上的关系如下，有传递性的有（）Pl={,,,}P2={va,c>,vc,a>}P3={,,,}P4={}设R和S是集合A上的任意关系，则下列命题为真的是（）若R和S是自反的，则ROS也是自反的若R和S是反自反的，则ROS也是反自反的若R和S是对称的，则ROS也是对称的若R和S是传递的，则ROS也是传递的16•若R和S是集合A上的两个关系，则下述结论正确的是（）若R和S是自反的，则RHS也是自反的若R和S是对称的，则ROS也是对称的若R和S是反对称的，则ROS也是反对称的若R和S是传递的，则RUS也是传递的°17•设A={l,2,3,4,5},P={vi,j>livj,i,jwA},则p的性质是（）A.对称的B.自反的C.反对称的D.反自反、反对称、传递的设集合A={a,b,c},R是A上的二元关系，R={va,a>,va,b>,va,c>,vc,a>},那么R是（）A.反自反的B.反对称的C.可传递的D.不可传递的设R和S是集合A上的等价关系，则RUS的对称性（）A.一定成立B.—定不成立C.不一定成立D.不可能成立20•设R和S是非空集合A上的等价关系，下述各式是等价关系的为（）A.（AXA）-RB.R2C.R-SD.r（R-S）21.集合A上的关系R是相容关系的必要条件是（）A.自反、反对称的B.反自反、对称的C.传递、自反的D.自反、对称的22•设R是集合A上的偏序关系，R是R的逆关系，则RUR是（）A.偏序关系B.等价关系C.相容关系D.都不是设集合A中有4个元素，则A上的不同的等价关系的个数为（）A.11个B.14个C.15个D.17个、填空题设M={1WxW12,x被2整除，xWZ},N={xl1WxW12,x被3整除，x^Z},贝VMUN=①，MAN②。设全集U={1,2,...,7}的子集为A={偶数},B={奇数},C={3的倍数},则AAB=①，AAC=②，AUC=③，bnc=④。3.设集合A={x|Yx<3,xeZ},B={xlx=2k,keZ},C={1,2,3,4,5}。(1).A©C=①(2).(A㊉B)AC=②(3).BffiB=③(4).A㊉(C-B)=④4.设I为整数集合,A={xlx2<30,xeI},B={xlx是素数，x<20},C={1,3,5}。.(AAB)UC=①.(B-A)UC=②.(C-A)n(B-A)=③(4).(BAC)-A=④5.设全集U={1,2,3,.,20},A、B、C是其子集，且A={xNx<4},B={xlx2-6x-7=0}C={xlx2<100}。(1).(A-B)AC=①(2).AABAC=②(3).(AAB)-C=③6.设A、B是集合，求A与B之间的关系。⑴•如果A={1},B={1,{1,2}}，则①⑵.如果A=0,B={0},则②⑶.如果A={a},B={0,a,{0}}，则.③⑷.如果A={0},B={0,{0}},则④供选择项：A.AeB且AcBB.AeB且A#BC.AgB但AcBD.AgB且A#B7.设A={{x,y},0,x,y}，求下列各式的结果：A-{x,y}=①;A-{0}=②；{{x,y}}-A=③;TOC\o"1-5"\h\z0-A=④:A的幕集P(A)=⑤。集合A={0,{a}}的幕集P(A)=。集合A={{1,2},{3}},B={{1},{2},{3}}，试写出AUB=①,AHB=②,P(A)=③。设A={xl100vxv200,x=7n+3,nwZ,xGZ}，贝VlAI=。若集合A的基数IAI=10，则其幕集的基数IP(A)I=。确定以下各式：(!).0n{0}=①(2).{0,{0}}-0=②(3).{0,{0}}-{0}=__③某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数。某学校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，且其中只有3人同时参加3种球队，那么仅仅参加两种球队得队员人数是设A={a,b,c},则集合S]={{a,b},{b,c}},S2={{a},{a,b},{a,c}},S3={{a},{b,c}},S4={{a,b,c}},S5={{a},{b},{c}}和S6={{a},{a,c}}中是A的完全覆盖的有①,是A的划分的有②。设D为同一平面上直线的集合，并且〃表示两直线间的平行关系，丄表示两直线间的垂直关系，贝y〃2=①，丄2=②，丄3=③。关系R是反自反的，当且仅当在关系矩阵中—①，在关系图上—②。关系R是对称的，当且仅当关系矩阵是①，在关系图上②。关系R是反对称的，当且仅当关系矩阵—①，在关系图—②。设A={1,2,3}上的关系R={v1,1>,v1,2>,v1,3>,v3,3>},则关系R具备①性,不具备②性。设A={1,2,3,4}上关系R={v1,2>,v2,4>,v3,3>,v1,3>},则r(R)=①，s(R)=②。设集合A仅含有3个元素，那么.在A上可定义.种不同的二元关系。.在A上可定种不同的自反关系。.在A上可定种不同的反自反关系。.在A上可定种不同的对称关系。•在A上可定种不同的反对称关系。如果R1和R2是A上的对称关系，有下列观点：.r1ur2是对称的.R1nR2是对称的.R1OR2是对称的其中是正确的。如果R1和R2是A上的反对称关系，有下列观点：.r1ur2是反对称的.R1nR2是反对称的⑶鸟滾?是反对称的其中是正确的。如果R1和R2是A上的传递关系，有下列观点：.R1UR2是传递关系.R1nR2是传递关系⑶鸟滾?是传递关系.R12是传递关系其中是正确的。R是A的二元关系，那么有下列观点：(1).当R是自反关系时，R的传递闭包也是自反关系(2).当R是反自反关系时，R的传递闭包也是反自反关系其中是正确的。R是A的二元关系，那么有下列观点：.当R是对称关系时，R的传递闭包也是对称关系.当R是反对称关系时，R的传递闭包也是反对称关系其中是正确的。集合A={a,b,c,d,e,f,g},A上的一个划分n={{a,b},{c,d,e},{f,g}}，那么n所对应的等价关系R应有个有序对。设R是集合{1,2,・・・，1(上的模7同余关系，贝9[2]r=。设比和R2是A的相容关系，那么对于下列观点：.R]UR2是相容关系.RXHR2是相容关系.R]OR2是相容关系其中是正确的。*31.整数集上的小于关系“V”具有①，②和③关系。设A={a,b,c}上偏序关系(P(A)c),则P(A)的子集B={0,{a},{b},{a,b},{b,c}}的极大兀是①，最大元是，上界是，下确界是④。TOC\o"1-5"\h\zHYPERLINK\l"bookmark68"A={2,3,4,5,6,8,10,12,24},R是A上的整除关系。那么A的极大元是①，极小元是②。A={1,2,3,4,5,6,7,8,9,10,11,12},R是A上的整除关系。子集B={2,4,6}，那么B的最大元是，B的最小元是，B的上界是，B的下界是④。A={1,2,3,4,5,6,8,10,24,36},R是A上的整除关系。子集B={1,2,3,4},那么B的上界是①，B的下界是②,B的上确界是③,B的下确界是④。三、判断题若A㊉B=A㊉C,贝9B=C。()若PUQ=Q,PHQ=0，贝P=0O(){0}g{0,{0}}且{0}匸{0,{0}}。()设A={0},B=P(P(A)),则有{0}gB，且{0}cBo()A,B是集合，则命题AcB和AgB可能同时成立。()设A，B为任意集合，贝P(A-B)=P(A)-P(B)O()若A-BcB，贝9BcAo()对每个集合A,有{A}cP(A)o()设A与B是任意两个集合，若{AHB,B-A}是AUB的一个划分，则有A-B=0。()若{A-B,B-A}是集合AUB的一个划分，则有AHB=0，其中Ah0,Bh0。()设A,B是两个任意的集合，若{AnB,A-B,B-A}是AUB的一个划分，则有AHB=0,A-B=0，B-A=0O()若{AnB}是AUB的一个划分，则有A-B=B-A=0o()若R是集合A上的传递关系，则R2也是集合A上的传递关系。()若集合A上的关系R是对称的，则°也是对称的。()一个不是自反的关系，一定是反自反的。()集合A={1,2,3}的任何关系R都不可能既是对称的，又是反对称的。()集合A={a,b,c}上的关系R={va,b>,va,c>}是不可传递的。()若R和S是集合A上的任意两个自反关系，则ROS也是自反的。()若R和S是集合A上的任意两个反自反关系，则ROS也是反自反的。()若R和S是集合A上的任意两个对称关系，则ROS也是对称的。()若R和S是集合A上的任意两个传递关系，则ROS也是传递的。()若R为集合A上的反对称关系，则t(R)—定是反对称的。()设R和S是集合A上的关系，则有：r(RUS)=r(R)Ur(S)；()s(RUS)=s(R)Us(S)；()t(RUS)匸t(R)Ut(S)；()设R和S是集合A上的等价关系，则RUS—定是等价的。()设R和S是集合A上的两个相容关系，则ROS和RHS都是相容关系。()平面上直线间的平行关系是等价关系。()设人的集合A上的朋友关系为R,则R是A上的相容关系。()四、综合题举出集合A，B，C的例子，使其满足AeB，BeC，但AgC。判断以下命题的真假：(1).ae{{a}}(2).{a}e{{a}}.xe{x}-{{x}}.{x}匸{x}-{{x}}.A-B=AoB=0.A-B=0oA=B.A㊉A=A.A-(BUC)=(A-B)n(A-C).如果AnB=B，则A=B.A={x}Ux，贝9xeA且xcA设A，B，C，D是Z的子集，其中：A={1,2,7,8}B={x2lx2<50且xeZ}C={xlxeZ且0WxW30且x可以被3整除}D={xlx=2k且keZ且0WkW6}用描述法表示下面集合并计算：.AUBUCUD.AnBnCnD.B-(AUC).(AnB)UD设全集U={1,2,・・・，12}A={1,3,5,7,9,11},B={2,3,5,7,11}，C={2,3,6,12}，D={2,4,8}。确定下面的集合：(1)AUB(2)AnC(3)(AUB)nCA-B(5)C-D(6)B㊉DA={{0},{0,1},{1,1,0}},B={{0,1},{1}}。计算AUB，AnB，A-B，P(A)。化简((AU(B-C))nA)U(B-(B-A))O第四章第五章、选择题*1.设S={a,b},则S上总共可定义的二元运算的个数是()A.4B.8C.16D.322.设集合A={1,2,3,・・・，10}下面定义的哪种运算关于集合A是不封闭的？()x*y=max{x,y}x*y=min{x,y}x*y=GCD(x,y)，即x,y的最大公约数x*y=LCM(x,y)，即x,y的最小公倍数在自然数集N上，下列哪种运算是可结合的？()A.a*b=a-bB.a*b=max{a,b}C.a*b=a+2bD.a*b=|a-b|对自然数集N,下列哪种运算不是可结合的？()D.a*b=a・b(mod3)A.a*b=a+b+3B.a*b=min{a,b}C.a*b=a+2b下列运算中，哪种运算关于整数集不能构成半群？()A.aob=max{a,b}B.aob=bA3.C.DQ是有理数，(Q,*)(其中*为普通乘法)不能构成()A.群B.独异点C.半群D.交换半群R为实数集，运算*定义为：a,bwR,a*b=a・lbl，贝M弋数系统(R,*)是()A.半群B.独异点C.群D.阿贝尔群*9.下列代数系统(S,*)中，哪个是群？()S={0,1,3,5}，*是模7的加法S=Q(有理数集合)，*是一般乘法S=Z(整数集合)，*是一般乘法S={1,3,4,5,9}，*是模11的乘法具有如下定义的代数系统(G,*)，哪个不够成群？()G={1,10}，*是模11的乘法G={1,3,4,5,9}，*是模11的乘法G=Q，*是普通加法G=Q，*是普通乘法*11.设x,y是群(G,*)的任意两个元素，n是大于0的整数，xn表示n个x进行乘法运算，则下述等式中哪个不成立？()(x*y)n=xn*yn(x*y)n+1=x*(y*x)n*yy*(x*y)n*y=(y*x)n*y(x*y)n*x=x*(y*x)n*12.任何一个有限群在同构的意义下可以看作是()A.循环群B.置换群C.交换群D.阿贝尔群设H,K是群(G,。)的子群，下面哪个代数系统仍是(G,。)的子群？()A.(HK,o)B.(HHK,o)C.(K-H,o)D.(H-K,o)任意一个具有多个等幂元的半群，它()。A.不能构成群B.不一定能构成群C.必能构成群D.能构成交换群*15.设Z是整数集合，+是一般加法，贝9下述函数中哪一个不是群(Z,+)的自同态？()A.f(x)=2xB.f(x)=1000xC.f(x)=|x|D.f(x)=0群(R,+)与(R-{O},X)之间的关系是()A.同态B.同构C.后者是前者的子群D.B,C均正确若(H,*)是(G,*)的真子群，且IHI=n,IGI=m,则有()A.n整除mB.m整除nC.n整除m且m整除nD.n不整除m且m不整除n*18.6阶群的任何非平凡子群一定不是()A.2阶B.3阶C.4阶D.6阶设z是整数集，+,•,分别是普通加法和乘法，贝y(z,+,・)是()A.域B.整环和域C.整环D.含零因子环下面哪个集合关于指定的运算构成环？(){a+b32|a,beZ},关于数的加法和