离散数学习题集(24页).doc

-离散数学习题集-第 23 页离散数学课外习题集编者：金鹏时间：2008-5-6目录：第一章一、 选择题1. 由n个命题变元组成不等值的命题公式的个数为（）n2D.2. 设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）®®PC.P «QD.ØQÚØP3. 下列各组公式中，哪组是互为对偶的？（）A.P,PB.P, ØPC.A,(A*)*D.A,A（其中P为单独的命题变元，A为含有联结词的命题变元）4. 设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）A. ØpÙØQB. ØPÚØQC. Ø(P««ØQ5. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）A. 2是偶数或-3不是负数C. 2是奇数或-3不是负数C2不是偶数且-3不是负数D. 2是奇数且-3不是负数6. 设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件事”符号化为（）ÚÚØ«QD. Ø(ØPÚØQ)7. 下列语句中哪个是真命题？（）A.我正在说谎。B.严禁吸烟。C.如果1+2=3，那么雪是黑的。D.如果1+2=5，那么雪是黑的。8. 下面哪个联结词运算不可交换？（）A.ÙB.®C.ÚD.«9. 命题公式(PÙ (P®Q) ®Q是（）。A.矛盾式B.蕴含式C.重言式D.等值式10. 下面哪个命题公式是重言式？（）A.(P®Q)Ù(Q® P)B.(PÙQ)®PC.(ØPÚQ)ÙØ(ØPÙØQ)D.Ø(PÚQ)11. 下列哪一组命题公式是等值的？（）A. ØPÙØQ,PÚ®(B®A),ØA®(A®ØB)®(PÚQ),ØQÙ (PÚQ)D.ØAÚ (AÙB),B12. P®Q的逆反式是（）®ØPB. P ®Ø QC. ØQ®PD. ØQ®ØP13. ØP®Q的逆反式是（）®ØPB. P ®Ø QC. Q®ØPD.P ®Ø Q 14. 下列命题联结词集合中，哪一个是最小联结词组？（）A.Ø,«B.Ø,Ú,ÙC.­D.Ù,®15. 下列联结词集合中，哪一个不是最小联结词组？（）A.Ø,ÙB.Ø,®C.Ø,Ù,ÚD.­16. 已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（）A.充分条件B.必要条件C.充要条件、B、C都不对17. ØP ® Q的反换式是（）®ØPB.ØP®ØQC.ØQ®Ø®ØQ18. 下面哪一个命题公式是重言式？（）®(QÚR)B.(PÚR)Ù(P®Q)C.(PÚQ) « (QÚR)D.(P®(Q®R) ®(P®Q) ®(P®R)19. 下列哪个命题公式不是重言式？（）®(PÚQ)B.(PÙQ)®PC.Ø(PÙØQ) Ù(ØPÚQ)D.(P®Q)«(ØPÚQ)20. 重言式的否定式是（）A.重言式B.矛盾式C.可满足式D.蕴含式21.下面哪一个命题是假命题？（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一22.下面哪一组命题公式不是等值的？（）A.Ø(A®B),AÙØBB.Ø(A«B),(AÙØB)Ú(ØAÙB)®(BÚC),ØAÙ(BÚC)D. A®(BÚC),(AÙØB)®C23. 命题公式P®QÙR的对偶式为（）®(QÚR)B. PÚ (QÚR)C.ØPÚ (QÙR)D.ØPÙ (QÚR)24. 命题公式P®(Q¯R)是（）A.重言式B.可满足式C.矛盾式D.等值式25. P«ØQÛ（）A.ØP® (P®ØQ)B.(ØPÚQ)Ú (ØQÚP)C.(ØPÚØQ)Ù(ØQÚP)D.(ØPÚØQ)Ù(QÚP)26. 命题公式Ø(PÙQ)®R的主析取范式中含极小项的个数为（）27. 命题公式Ø(PÙQ)®R的主析取范式中含极大项的个数为（）28. 命题公式Ø(PÙQ)®R的成真赋值为（）A.000,001,110B.001,011,101,110,111C.全体赋值D.无29. 如果AÞB成立，则以下各种蕴含关系哪一个成立？（）ÞAB.ØAÞØBC.ØBÞØAD.ØAÞB二、 填空题1. 下列句子中，是命题的有 (1).我是教师。(2).禁止吸烟！(3).蚊子是鸟类动物。(4).上课去！(5).月亮比地球大。2. 设P：我生病，Q：我去学校(1).命题“我虽然生病但我仍去学校”符号化为 。(2).命题“只有在生病的时候，我才不去学校”符号化为 。(3).命题“如果我生病，那么我不去学校”符号化为 。3. 设P：我有钱，Q：我去看电影。(1).命题“如果我有钱，那么我就去看电影”符号化为 。(2).命题“虽然我有钱，但我不去看电影”符号化为 。(3).命题“当且仅当我有钱时，我才去看电影”符号化为 。4.对于下列各式，是永真式的有 。(1).(PÙ(P®Q)®Q(2).P®(PÚQ)(3).Q®(PÙQ)(4).(ØPÙ(PÚQ)®Q(5).(P®Q) ®Q5.(PÙ(PÚQ) ®RÛ 。6.P®(P®Q) 。7. 对于下列各式(1).(ØPÙQ)Ú(ØPÙØQ)可化简为 。(2).Q®(PÚ(PÙQ) 可化简为 。(3).(ØPÚQ)«(ØQ®ØP)ÙP可化简为 。8.命题公式PÚ(QÙØR)的成真赋值为 ，成假赋值为 。9.若 且 则称X是公式A的子公式。10. 写出表中各列所定义的命题联结词。PQP QP Q111010010101000111.由n个命题变元可组成 个不等值的命题公式。12.用两种形式写出P­Q的对偶式 ， 。13.两个重言式的析取是 ，一个重言式与一个矛盾式的析取是 。14.A、B为两个命题公式，AÛB当且仅当 ，AÞB当且仅当 。15.设P、Q为两个命题公式，德摩根律可表示为 ，吸收率可表示为 。16.设命题公式A中仅含有联结词Ø，Ù，Ú，若 得到公式A*，则A*称为A的对偶式。17.公式(PÚQ) ®R的只含联结词Ø，Ù，Ú的等值式为 ，它的对偶式为18.命题公式AÛ(PÙQÙR)­0，则其对偶式A*Û 。19.在命题演算中，一个蕴含式与它的 式是等值的，它的 式与它的 是不等值的。20.公式ØP®Q的反换式为 ，逆反式为 。21.任意两个不同极小项的合取为 式，全体极小项的析取式必为22.命题公式Ø(P®Q)的主析取范式为 ，主合取范式的编码表示为23.已知公式A(P,Q,R)的主合取范式为M0ÙM3ÙM5，它的主析取范式为（写成编码形式） 。24.命题公式Ø(P«Q)的主析取范式为 ，其编码表示为 ，主合取范式的编码表示为 。25.对于前提：S®ØQ，SÚR，ØR, ØP«Q，其有效结论为 。26.对于前提：(PÙQ) ®R，ØRÚS, ØS，其有效结论为 。三、 判断题1. “王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（）2. 凡陈述句都是命题。（）3. 语句3x+5y=0是一个命题。（）4. 命题“两个角相等当且仅当它们是对顶角“的值为1。（）5. 语句“x+y=4”是个命题。（）6. 命题“十减四等于五”是一个原子命题。（）7. 命题“如果1+2=3，那么雪是黑的”是真命题。（）8. (P®(QÙR)是一个命题演算的命题公式，其中P、Q、R是命题变元。（）9. (P®(QÙR®ØQ)是一个命题公式，其中P、Q、R是命题变元。（）10. 若A：张明和李红都是三好学生，则ØA：张明和李红都不是三好学生。（）11. 若A：张明和李红都是运动员，则ØA：张明和李红不都是运动员。（）12. 若P：每一个自然数都是偶数，则ØP：每一个自然数都不是偶数。（）13. 若P：每个自然数都是偶数，则ØP：每个自然数不都是偶数。（）14. 如果AÛB，则AÙCÛBÙC，AÚCÛBÚC。（）15. 如果AÙCÛBÙC，则AÛB。（）16. 联结词“¯”是可结合的。（）17. 联结词“­”是可结合的。（）18. 联结词“¯”是可交换的。（）19. 联结词“­”是可交换的。（）20. 联结词“®”是满足交换律。（）21. “学习有如逆水行舟，不进则退”。设P：学习如逆水行舟，Q：学习进步，R：学习退步。则命题符号化为PÙ(ØQ®R)。（）22. P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：P® (ØQ®R)。（）23. 设P、Q是两个命题，当且仅当P、Q的真值均为1时，P«Q的值为1。（）24. 命题公式(PÙ(P®Q)®Q是矛盾式。（）25. 命题公式(PÙ(P®Q)®Q是重言式。（）26. 联结词Ù与Ú不是相互可分配的。（）27. 在命题的演算中，每个最小联结词组至少有两个联结词。（）28. 命题联结词集Ø,«是最小联结词集。（）29. 命题联结词集Ø,Ù,Ú是最小联结词集。（）30. 命题联结词集Ù,®是最小联结词集。（）31. 命题联结词集­和¯是最小联结词集。（）32. A是命题公式，A与(A*)*互为对偶式。（）33. A是命题公式，AÛ(A*)*。（）34. P是命题变元，P与P互为对偶式。（）35. 任一命题公式的主析取范式和它的主合取范式互为对偶式。（）36. 任一命题公式都可以表示成与其等值的若干极小项的析取式。（）四、 综合题1. 使用命题：P：这个材料有趣。Q：这些习题很难。R：这门课程让人喜欢。将下列句子用符号形式写出：(1). 这个材料有趣，并且这些习题很难。(2). 这个材料无趣，习题也不难，而且这门课程也不让人喜欢。(3). 如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。(4). 这个材料有趣，意味着这些习题很难，并且反之亦然。(5). 或者这个材料有趣，或者这些习题很难，并且两者恰具其一。2. 用符号形式写出下列命题：(1).假如上午不下雨，我去看电影，否则就在家里读书或者看报；(2).我今天进城，除非下雨；(3).仅当你走，我将留下；(4).一个数是素数当且仅当它只能被1和它自身整除。3. 判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。(1).是无理数。(2).5能被2整除。(3).现在开会吗？(4).x+5>0。(5).这朵花真好看呀！(6).2是素数当且仅当三角形有三条边。(7).雪是黑色的当且仅当太阳从东方升起。(8).2000年10月1日天气晴好。(9).太阳系以外的星球上有生物。(10).小李在宿舍。(11).全体起立！(12).4是2的倍数或是3的倍数。(13).4是偶数且是奇数。(14).李明与王华是同学。(15).蓝色和黄色可以调配成绿色。4. 确定下列命题的真值：(1).“如果太阳从西边出来，那么地球自转”；(2).“如果太阳从东边出来，那么地球自转停止”；(3).“如果8+9>30，那么三角形有三条边”；(4).“如果疑问句是命题，那么地球将停止转动”。5. 判断下面语句是否是命题，若是，确定其真值：(1).喜马拉雅山比华山高；(2).如果时间静止不动，你就可以长生不老；(3).如果时间流失不止，你就可以长生不老；(4).伦敦是英国首都；(5).这盆茉莉花好香阿！6. 给命题变元P、Q、R、S分别指派真值为1、1、0、0，求下列命题公式的真值：(1).(Ø(PÙQ)ÚØR)Ú(ØPÙQ)ÚØR)ÙS)(2).(PÚ(Q®(RÙØP)«(QÚØS)7. 设A*、B*分别是命题公式A和B的对偶式，判断下列各式是否成立，若不成立，请举例说明：(1).A*ÛA(2).AÛB则A*ÛB*(3).AÞB则A*ÞB*(4).(A*)*ÛA8. 命题联结词“¯”定义为P¯QÛØ(PÚQ)(1).构造P¯Q的真值表；(2).证明Ú、Ù、Ø可以用仅含联结词¯的等值公式表示。9. 化简下列命题公式：(1).AÚ(ØAÚ(BÙØB)(2).(AÙBÙC)Ú(ØAÙBÙC)(3).(P®Q)«(ØQ®ØP)ÙR(4).(A®B)«(ØB®ØA)ÚC10. 如果有AÙCÛBÙC，是否一定有AÛB?11. 如果有AÚCÛBÚC，是否一定有AÛB?12. 如果ØAÛØB是否有AÛB？13. 用真值表判断下列各式是否为重言式：(1).(ØPÚQ)Ù(Q®R)®Ø(PÙØR)(2).(PÙQ®R)®(PÙØRÙQ)14. 设命题公式A的真值表如表所示，试求出A的主析取范式和主合取范式（用编码表示和公式表示）：PQA11110101000115. 用等值演算法证明PÙ(P®Q) ®Q是重言式。16. 证明下列命题的等值关系：(1).(P®Q)Ù(R®Q)Û(PÚR)®Q(2).(PÙQÙA®C)Ù(A®PÚQÚC)Û(AÙ(P«Q)®C(3).P®(Q®P)ÛQ®(P®R)(4).(P®Q)Ù(P®R)ÛP®(QÙR)(5).(PÚQ)ÙØ(PÙQ)ÛØ(P«Q)17. 求证下面命题的蕴含关系：(1).PÙQÞP®Q(2).(P®(Q®R)Þ(P®Q)®(P®R)18. 求下面各式的主析取范式与主合取范式，并写出相应的为真赋值。(1).Ø(P®Q)«(P®ØQ)(2).(ØRÚ(Q®P)®(P®QÚR)(3).(P®Q)®Q)®(Q®P)®P)(4).(P®(Q®R)«(R®(Q®P)(5).Ø(P®Q)Ù(R®P)ÚØ(R®ØQ)®ØP19. 联结词f1，f2由表所示真值表定义，证明 f1，f2是最小联结词组。PQf1PP f1Q110110010110001120.设计一种简单的表决器，表决者每人座位旁边有一按钮，若同意则按下按钮，否则不按按钮，当表决结果超过半数时，会场电铃就会响，否则铃不响。试以表决人数为3人的情况设计表决器电路的逻辑关系。21. 证明­时最小联结词组。22. 设计一加法器，实现两自然数相加的功能。23. 某勘探队有3名队员。有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，时铁。经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。24. 观察下列推理过程，是否正确，结论是否有效，说明理由。(1).PÙQ®RP(2).P®RTI(3).PP(4).RTI所以PÙQ®R，PÞR。25. 下列证明过程是否正确，若正确补足每一步推理依据，否则指出错误。(1).ØDÚA(2).D(3).A(4).A®(C®B)(5).C®B(6).C(7).B(8).D®B26. 证明A®(B®C)，B®(C®D)ÞA®(B®D)。27.用CP规则证明ØPÚ(ØQÚR)，Q®(R®S)，PÞQ®S。28. 用推理规则说明A®B,Ø(BÚC)，AÙC是否能同时为真。29. 用推理规则说明(PÚQ)®R，ØSÚU，ØRÚS，U®W，ØWÞØPÙØQ。30. 用推理规则证明下列推理的正确性：如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。31. 用等值演算法证明ØPÙØ(P®Q)是矛盾式。32. 用CP规则证明A®(BÙC)，(E®ØF)®ØC，B®(AÙØS)ÞB®E。33. 用反证法证明(A®B)Ù(C®D)，(B®E)Ù(D®F)，Ø(EÙF)，A®CÞØA。34. 用反证法证明A®B，(ØBÚC)ÙØC，Ø(ØAÙD)ÞØD。第二章一、 选择题1. 谓词公式"x(P(x)Ú$yR(y)®Q(x)中量词"x的作用域是（）A. "x(P(x)Ú$yR(y)B.P(x)C. (P(x)Ú$yR(y)D.P(x)，Q(x)2. 谓词公式"x(P(x)Ú$yR(y)®Q(x)中变元x是（）A.自由变量B.约束变量C.既不是自由变量也不是约束变量D.既是自由变量也是约束变量3. 若个体域为整体域，下列公式中哪个值为真？（）A."x$y(x+y=0)B.$y"x(x+y=0)C."x"y(x+y=0)D.Ø$x$y(x+y=0)4. 设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式$x(P(x)ÙQ(x)在下面哪个论域中是可满足的？（）A.自然数集B.整数集C.实数集D.以上均不成立5. 设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可符号化为（）A.Ø"x(C(x)ÙØG(x)B.Ø"x(C(x)®ØG(x)C.Ø$x(C(x)ÙØG(x)D.Ø$x(C(x)®ØG(x)6. 设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为（）A."x(A(x)ÙB(x)B.Ø$x(A(x)®ØB(x)C.Ø$x(A(x)ÙB(x)D.Ø$x(A(x)ÙØB(x)7. 设Z(x)：x是整数，N(x)：x是负数，S(x,y)：y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式（）A."x"y(Z(x)ÙS(x,y)®ØN(y)B."x$y(Z(x)ÙS(x,y)®ØN(y)C."x"y(Z(x)®S(x,y)ÙØN(y)D."x(Z(x)ÙS(x,y)®ØN(y)8. 令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有的火车慢”可表示为（）A.$y(G(y)®"x(F(x)ÙH(x,y)B.$y(G(y)Ù"x(F(x)®H(x,y)C."x$y(G(y)®(F(x)ÙH(x,y)D.$y(G(y)®"x(F(x)®H(x,y)9. 设个体域A=a,b，公式"xP(x)Ù$xS(x)在A中消去量词后应为（）A.P(x)ÙS(x)B.P(a)ÙP(b)Ù(S(a)ÚS(b)C.P(a)ÙS(b)D.P(a)ÙP(b)ÙS(a)ÙS(b)10. 在谓词演算中，下列各式哪个是正确的？（）A.$x"yA(x,y)Û"y$xA(x,y)B.$x$yA(x,y)Û$y$xA(x,y)C.$x"yA(x,y)Û"x$yA(x,y)D."x"yA(x,y)Û"y"xA(x,y)11. 下列各式哪个不正确？（）A."x(P(x)ÚQ(x)Û"xP(x)Ú"xQ(x)B."x(P(x)ÙQ(x)Ü"xP(x)Ù"xQ(x)C.$x(P(x)ÚQ(x)Û$xP(x)Ú$xQ(x)D."xP(x)ÙQ)Û"xP(x)ÙQ12. 下面谓词公式哪个是前束范式？（）A."x"y$z(B(x,y)®A(z)B.Ø"x$yB(x,y)C.$x"y"x(A(x,y)ÙB(x,y)D."x(A(x,y)®$yB(y)13. 在谓词演算中：P(a)是"xP(x)的有效结论，其理论根据是（）A.全称规定规则(US)B.全称推广规则(UG)C.存在规定规则(ES)D.存在推广规则(EG)二、 填空题1. 令R(x)：x是实数，Q(x)：x是有理数。(1) 命题“并非每个实数都是有理数”。其符号化为 。(2) 命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可表示为 。2.设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。3.设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有智能工作都能由计算机来做”符号化为 。4. 设Q(x)：x是偶数，P(x)：x是素数，则命题“存在惟一一个偶素数”可符号化为 ，“至多存在一个偶素数”可符号化为 。5.设Q(x)：x是奇数，Z(x)：x是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为 。6.设个体域为自然数集，P(x)：x是奇数，Q(x)：x是偶数，则命题“不存在既是奇数又是偶数的自然数”可符号化为 。7.设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数担不是整数”符号化分别为 ， ， 。8."x"y(P(x,y)ÙQ(y,z)Ù$xP(x,y)中"x的作用域为 ，"y的作用域为 ，$x的作用域为 。9. 公式"x(P(x)®Q(x,y)Ú$R(y,z)®S(x)中自由变量为 ，约束变量为10. 取个体域为整数集，给定下列公式：(1)."x$y(x·y=0)(2)."x$y(x·y=1)(3)$x$y(x·y=2)(4)"x"y$z(x-y=z)(5).x-y=-y+x(5)."x"y(x·y=y)(7)"x(x·y=x)(8).$x"y(x+y=2y)上面公式中，真命题的有 ，假命题的有 。*11.下列谓词公式(1).Ø($xA(x)与"xØA(x)(2)."x(A(x)ÚB(x)与"xA(x)Ú"xB(x)(3)."x(A(x)ÙB(x)与"xA(x)Ù"xB(x)(4).$x"yD(x,y)与"y$xD(x,y)中 是等值的。12. 对公式"x(P(x)ÚQ(x)，其中P(x):x=1，Q(x):x=2，当论域为1,2时，其真值为 ，当论域为0,1,2时，其真值为 。13.设个体域为A=a,b,c，消去公式"xP(x)Ù$xQ(x)中的量词，可得 。14. 下列各式(1)."x(P(x)ÚQ(x)®("xP(x)Ú$xQ(x)(2).("x(A(x)®B(x)ÙA(c)®A(c)(3).("x(ØA(x)®B(x)Ù"xØB(x)®$xA(x)(4).($x(P(x)ÙQ(x)®$xP(x)®ØQ(x)其中 是永真式。15. 下列各式(1).$y"xA(x,y)(2).$x"yA(x,y)(3)."x$y A(x,y)(4).$x$yA(x,y)它们之间存在着 的推理关系。可供选择的项有：A.(1)Þ(2)；(2) Þ(3)B.(2) Þ(1)；(3) Þ(4)C.(1) Þ(3)；(4) Þ(3)D.(4) Þ(1)；(1) Þ(3)E.(1) Þ(3)；(2) Þ(4)16.填上联结词："xP(x)Ú"xQ(x) "x(P(x)ÚQ(x)*17.只用联结词Ø，"，®，表示以下的公式。(1).$x(P(x)ÙQ(x)= ；(2).$x(P(x)«"yQ(y)= ；(3)."y("xP(x)ÚØQ(y)= 。18. 给定下面谓词公式：(1)."x(ØF(x)®ØF(x)(2)."xF(x)®$xF(x)(3).Ø(F(x)®("yG(x,y)®F(x)(4)."x$yF(x,y)®$x"yF(x,y)(5).Ø"xF(x)«$xØF(x)(6)."x(F(x)ÙG(x)®("xF(x)Ú"xG(x)(7).$x$yF(x,y)®"x"yF(x,y)(8)."x(F(x)ÚG(x)®("xF(x)Ú"xG(x)(9).("xF(x)Ú"xG(x)®"x(F(x)ÚG(x)(10)."x"yF(x,y)«"y"xF(x,y)(11).Ø("xF(x)®"yG(y)Ù"yG(y)上面11个公式中，为重言式的有 ，为矛盾式的有 。19. 给定下列各公式：(1).(Ø$xF(x)Ú"yG(y)Ù(F(u)®"zH(z)(2).$xF(y,x)®"yG(y)(3)."x(F(x,y)®"yG(x,y)则 是(1)的前束范式， 是(2)的前束范式， 是(3)的前束范式。供选择的答案有$x"y"z(ØF(x)ÚG(y)Ù(F(u)®H(z)"x"y"z(ØF(x)ÚG(y)Ù(F(u)®H(z)$x"y(F(y,x)®G(y)"x"y(F(z,x)®G(y)"x"y(ØF(z,x)ÚG(y)"x$y(F(x,z)®G(x,y)"x"y(F(x,z)®G(x,y)"y"x(F(x,z)®G(x,y)"y"x(ØF(x,z)"G(y)20.谓词公式"xP(x)®"xQ(x)Ú$yR(y)的前束范式为 。21.谓词公式"x(P(x)®Q(x,y)Ú$zR(y,z)®S(x)的前束范式为 。*22.谓词公式Ø$x(Ø"yG(y,b)®H(x)的前束范式为 。23. 在谓词逻辑中给出四个推理：(1).前提："x(F(x)®G(x)，$yF(y)；结论：$yG(y)(2).前提：$x(F(x)ÙG(x)；结论："yF(y)(3).前提：$xF(x)，$xG(x)；结论：$y(F(y)ÙG(y)(4).前提："x(F(x)®H(x)，ØH(y)；结论："x(ØF(x)以上四个推理中正确的有 。24. 在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。命题符号化：F(x)：x喜欢步行；G(x)：x喜欢坐汽车；H(x)：x喜欢骑自行车。前提："x(F(x)®ØG(x)，"x(G(x)ÚH(x)，$x(ØH(x)；结论：$x(ØF(x)。三、 判断题1.在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（）2.公式"x(P(x)®Q(x)ÚR(y)中"x的作用域为P(x)。（）3.同一谓词公式，指定不同的论域，其真值不一定相同。（）4.谓词公式"xP(x)Ù$y(ØP(y)是矛盾式。（）*5."x(P(x)®Q(x)®($xP(x)®$xQ(x)为真。（）6.对公式$z(P(z)ÙQ(x,z)ÙM(z,y)ÚR(z)中自由变量代入后，有$z(P(z)ÙQ(a,z)ÙM(z,b)ÚR(z)（）7."x"y(P(x)®Q(y)Û$xP(x)®"yQ(y)（）*8.P(x)，Q(x)表示谓词，P表示命题，有"x(P(x)®P)Û$xP(x)®P（）*9."x(A(x)ÙB(x)Û"xA(x)Ù"xB(x)（）*10."x(A(x)®B(x)Þ$xA(x)Ù$xB(x)（）11.任意一个谓词公式都与一个前束范式等价。（）12.公式"xP(x)®$yQ(x,y)前束范式"x"y(P(x)®Q(x,y)为（）13.公式$x(Ø$yP(x,y)®($zQ(z)®R(x)的前束范式为$x$y$z(P(x,y)ÚØQ(z)ÚR(x)（）14. 下面的推理：条件："x(P(x)ÚQ(x)，根据全称规定（US）有：P(a)ÚQ(b)是正确的。（）15. 对公式$z(P(z)ÙQ(x,z)ÙM(z,y)ÚR(z)中约束变量z改名后，得到的等价公式为：$t(P9t)ÙQ(x,t)ÙM(t,y)ÚR(t)（）四、 综合题1. 用谓词和量词将下列命题符号化：(1).没有不犯错误的人；(2).尽管有人聪明，但未必一切人都很聪明；(3).每个计算机系的学生都学离散数学；(4).所有的人都学习和工作；(5).并非一切推理都能用计算机完成；(6).任何自然数都有惟一的一个后继数。*2.令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，L(x,y)表示“x<y”，其中个体域为自然数集，用以上符号表示下列命题：(1).没有x<0，且若x>0当且仅当有这样的y，使得xy。(2).并非对一切x，都存在y，使得xy。(3).对任意的x，若x+y=x，当且仅当y=0。3.用谓词公式表示命题“”，并写出该命题的否定命题。*4.设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化：(1).并不是外语学的好的都是三好学生。(2).有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。5. 指出下列公式中量词每次出现的作用域，并指出个体变量是约束变量还是自由变量。(1)."x"y(R(x,y)ÚL(y,z)Ù$xH(x,y)(2)."x(P(x)Ù$xQ(x)Ú("xP(x)®Q(x)6. 设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):x<y根据上面的解释，以下公式中哪些为真，哪些为假？(1).E(f(x,y),g(x,y)(2).E(f(x,x),h(x,a)(3).L(x,y)®L(y,x)(4).$xE(f(x,y),b)(5).ØE(x,a)ÙE(g(y,x),y)7. 在谓词逻辑中将命题(1)(2)(3)符号化，并指出各命题的真值。对应的个体域分别为：非负整数集N；实数集R；整数集Z。(1).对于任意的x，均有(x+1)2=x2+2x+1(2).存在x，使得x+1=0(3).存在x，使得5x=1*8.假设论域为自然数集N=1,2,3,，a为2，P为命题“2>1”；A(x)表示“x>1”；B(x)表示“x是某个自然数的平方”。请在此基础上，求下面公式的真值："x(A(x)®(A(a)®B(x)®(P®"xA(x)®B(a)9. 下列各式翻译成自然语言，然后在不同的个体域中确定它们的真值：(1)."x$y(x·y=0)(2).$x"y(x·y=0)(3)."x$y(x·y=1)(4).$x"y(x·y=1)(5)."x$y(x·y=x)(6).$x"y(x·y=x)(7)."x"y$z(x-y=z)个体域分别为：实数集整数集正整数集非负实数集10. 设解释T如下：个体域为实数集R，元素a=0，函数f(x,y)=x-y，特定谓词F(x,y)为x<y。根据解释T，下列哪些公式为真？哪些为假？(1)."xF(f(a,x),a)(2)."x"y(ØF(f(x,y),x)(3)."x"y"z(F(x,y)®F(f(x,z),f(y,z)(4)."x$yF(x,f(f(x,y),y)11. 求下面谓词公式$x(X(x)Ù"y(X(y)®(Y(x,z)ÙY(y,z)Ùp)®"t(X(t)®(Y(x,t)®Y(y,t)在赋值(z;p;X(x);Y(x,y)=(2;1;x是自然数;x<y)下的值。12. 设解释T为：个体域为D-2,3,6，谓词F(x)：x3，G(x)：x>5，R(x)：x7。根据解释T，求下列各式的真值：(1)."x(F(x)ÙG(x)(2)."x(R(x)®F(x)ÚG(5)(3).$x(F(x)ÚG(x)13. 设A(x)是一个含有个体变量x的谓词公式，证明下面等值式成立：Ø"xA(x)Û$x(ØA(x)14. 设A(x)，B(x)均为含有自由变量x的任意谓词公式，证明："x(A(x)®B(x)Þ"xA(x)®"xB(x)15.证明："x"y(G(x)«H(y)Þ"xG(x)«"xH(x)。16.设G(x)，