离散数学习题集

离散数学课外习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 集编者：金鹏时间：2008-5-6 目录 工贸企业有限空间作业目录特种设备作业人员作业种类与目录特种设备作业人员目录1类医疗器械目录高值医用耗材参考目录 ：第一章选择题由n个命题变元组成不等值的命题 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 的个数为（）A.2nB.2nC.n2D.设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）A.PQB.QPC.PQD.QP下列各组公式中，哪组是互为对偶的？（）A.P,PB.P,PC.A,(A*)*D.A,A（其中P为单独的命题变元，A为含有联结词的命题变元）设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）A.pQB.PQC.(PQ)D.PQ下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）A.2是偶数或-3不是负数C.2是奇数或-3不是负数C．2不是偶数且-3不是负数D.2是奇数且-3不是负数设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件事”符号化为（）A.PQB.PQC.PQD.(PQ)下列语句中哪个是真命题？（）A.我正在说谎。B.严禁吸烟。C.如果1+2=3，那么雪是黑的。D.如果1+2=5，那么雪是黑的。下面哪个联结词运算不可交换？（）A.B.C.D.命题公式(P(PQ))Q是（）。A.矛盾式B.蕴含式C.重言式D.等值式下面哪个命题公式是重言式？（）A.(PQ)(QP)B.(PQ)PC.(PQ)(PQ)D.(PQ)下列哪一组命题公式是等值的？（）A.PQ,PQB.A(BA),A(AB)C.Q(PQ),Q(PQ)D.A(AB),BPQ的逆反式是（）A.QPB.PQC.QPD.QPPQ的逆反式是（）A.QPB.PQC.QPD.PQ下列命题联结词集合中，哪一个是最小联结词组？（）A.{,}B.{,,}C.{}D.{,}下列联结词集合中，哪一个不是最小联结词组？（）A.{,}B.{,}C.{,,}D.{}已知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(QR)B.(PR)(PQ)C.(PQ)(QR)D.(P(QR))((PQ)(PR))下列哪个命题公式不是重言式？（）A.Q(PQ)B.(PQ)PC.(PQ)(PQ)D.(PQ)(PQ)重言式的否定式是（）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)C.A(BC),A(BC)D.A(BC),(AB)C命题公式PQR的对偶式为（）A.P(QR)B.P(QR)C.P(QR)D.P(QR)命题公式P(QR)是（）A.重言式B.可满足式C.矛盾式D.等值式PQ（）A.P(PQ)B.(PQ)(QP)C.(PQ)(QP)D.(PQ)(QP)命题公式(PQ)R的主析取范式中含极小项的个数为（）A.8B.3C.5D.0命题公式(PQ)R的主析取范式中含极大项的个数为（）A.0B.3C.5D.8命题公式(PQ)R的成真赋值为（）A.000,001,110B.001,011,101,110,111C.全体赋值D.无如果AB成立，则以下各种蕴含关系哪一个成立？（）A.BAB.ABC.BAD.AB填空题下列句子中，是命题的有(1).我是教师。(2).禁止吸烟！(3).蚊子是鸟类动物。(4).上课去！(5).月亮比地球大。设P：我生病，Q：我去学校(1).命题“我虽然生病但我仍去学校”符号化为。(2).命题“只有在生病的时候，我才不去学校”符号化为。(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)。对于下列各式(1).(PQ)(PQ)可化简为。(2).Q(P(PQ))可化简为。(3).(PQ)(QP)P可化简为。8.命题公式P(QR)的成真赋值为，成假赋值为。9.若且则称X是公式A的子公式。写出 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中各列所定义的命题联结词。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，其有效结论为。判断题“王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（）凡陈述句都是命题。（）语句3x+5y=0是一个命题。（）命题“两个角相等当且仅当它们是对顶角“的值为1。（）语句“x+y=4”是个命题。（）命题“十减四等于五”是一个原子命题。（）命题“如果1+2=3，那么雪是黑的”是真命题。（）(P(QR))是一个命题演算的命题公式，其中P、Q、R是命题变元。（）(P(QRQ))是一个命题公式，其中P、Q、R是命题变元。（）若A：张明和李红都是三好学生，则A：张明和李红都不是三好学生。（）若A：张明和李红都是运动员，则A：张明和李红不都是运动员。（）若P：每一个自然数都是偶数，则P：每一个自然数都不是偶数。（）若P：每个自然数都是偶数，则P：每个自然数不都是偶数。（）如果AB，则ACBC，ACBC。（）如果ACBC，则AB。（）联结词“”是可结合的。（）联结词“”是可结合的。（）联结词“”是可交换的。（）联结词“”是可交换的。（）联结词“”是满足交换律。（）“学习有如逆水行舟，不进则退”。设P：学习如逆水行舟，Q：学习进步，R：学习退步。则命题符号化为P(QR)。（）P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：P(QR)。（）设P、Q是两个命题，当且仅当P、Q的真值均为1时，PQ的值为1。（）命题公式(P(PQ))Q是矛盾式。（）命题公式(P(PQ))Q是重言式。（）联结词与不是相互可分配的。（）在命题的演算中，每个最小联结词组至少有两个联结词。（）命题联结词集{,}是最小联结词集。（）命题联结词集{,,}是最小联结词集。（）命题联结词集{,}是最小联结词集。（）命题联结词集{}和{}是最小联结词集。（）A是命题公式，A与(A*)*互为对偶式。（）A是命题公式，A(A*)*。（）P是命题变元，P与P互为对偶式。（）任一命题公式的主析取范式和它的主合取范式互为对偶式。（）任一命题公式都可以表示成与其等值的若干极小项的析取式。（）综合题使用命题：P：这个材料有趣。Q：这些习题很难。R：这门课程让人喜欢。将下列句子用符号形式写出：(1).这个材料有趣，并且这些习题很难。(2).这个材料无趣，习题也不难，而且这门课程也不让人喜欢。(3).如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。(4).这个材料有趣，意味着这些习题很难，并且反之亦然。(5).或者这个材料有趣，或者这些习题很难，并且两者恰具其一。用符号形式写出下列命题：(1).假如上午不下雨，我去看电影，否则就在家里读书或者看报；(2).我今天进城，除非下雨；(3).仅当你走，我将留下；(4).一个数是素数当且仅当它只能被1和它自身整除。判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。(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).蓝色和黄色可以调配成绿色。确定下列命题的真值：(1).“如果太阳从西边出来，那么地球自转”；(2).“如果太阳从东边出来，那么地球自转停止”；(3).“如果8+9>30，那么三角形有三条边”；(4).“如果疑问句是命题，那么地球将停止转动”。判断下面语句是否是命题，若是，确定其真值：(1).喜马拉雅山比华山高；(2).如果时间静止不动，你就可以长生不老；(3).如果时间流失不止，你就可以长生不老；(4).伦敦是英国首都；(5).这盆茉莉花好香阿！给命题变元P、Q、R、S分别指派真值为1、1、0、0，求下列命题公式的真值：(1).((PQ)R)(((PQ)R)S)(2).(P(Q(RP)))(QS)设A*、B*分别是命题公式A和B的对偶式，判断下列各式是否成立，若不成立，请举例说明：(1).A*A(2).AB则A*B*(3).AB则A*B*(4).(A*)*A命题联结词“”定义为PQ(PQ)(1).构造PQ的真值表；(2).证明、、可以用仅含联结词的等值公式表示。化简下列命题公式：(1).A(A(BB))(2).(ABC)(ABC)(3).((PQ)(QP))R(4).((AB)(BA)C如果有ACBC，是否一定有AB?如果有ACBC，是否一定有AB?如果AB是否有AB？用真值表判断下列各式是否为重言式：(1).((PQ)(QR))(PR)(2).(PQR)(PRQ)设命题公式A的真值表如表所示，试求出A的主析取范式和主合取范式（用编码表示和公式表示）：PQA111101010001用等值演算法证明P(PQ)Q是重言式。证明下列命题的等值关系：(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)求证下面命题的蕴含关系：(1).PQPQ(2).(P(QR))(PQ)(PR)求下面各式的主析取范式与主合取范式，并写出相应的为真赋值。(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)P联结词f1，f2由表所示真值表定义，证明{f1，f2}是最小联结词组。PQf1PPf1Q110110010110001120.设计一种简单的表决器，表决者每人座位旁边有一按钮，若同意则按下按钮，否则不按按钮，当表决结果超过半数时，会场电铃就会响，否则铃不响。试以表决人数为3人的情况设计表决器电路的逻辑关系。证明{}时最小联结词组。设计一加法器，实现两自然数相加的功能。某勘探队有3名队员。有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，时铁。经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。观察下列推理过程，是否正确，结论是否有效，说明理由。(1).①PQRP(2).②PRT①I(3).③PP(4).④RT②③I所以PQR，PR。下列证明过程是否正确，若正确补足每一步推理依据，否则指出错误。(1).①DA(2).②D(3).③A(4).④A(CB)(5).⑤CB(6).⑥C(7).⑦B(8).⑧DB证明A(BC)，B(CD)A(BD)。27.用CP规则证明P(QR)，Q(RS)，PQS。用推理规则说明AB,(BC)，AC是否能同时为真。用推理规则说明(PQ)R，SU，RS，UW，WPQ。用推理规则证明下列推理的正确性：如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。用等值演算法证明P(PQ)是矛盾式。用CP规则证明A(BC)，(EF)C，B(AS)BE。用反证法证明(AB)(CD)，(BE)(DF)，(EF)，ACA。用反证法证明AB，(BC)C，(AD)D。第二章选择题谓词公式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)谓词公式x(P(x)yR(y))Q(x)中变元x是（）A.自由变量B.约束变量C.既不是自由变量也不是约束变量D.既是自由变量也是约束变量若个体域为整体域，下列公式中哪个值为真？（）A.xy(x+y=0)B.yx(x+y=0)C.xy(x+y=0)D.xy(x+y=0)设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式x(P(x)Q(x))在下面哪个论域中是可满足的？（）A.自然数集B.整数集C.实数集D.以上均不成立设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))设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))设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))令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)))设个体域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)在谓词演算中，下列各式哪个是正确的？（）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)下列各式哪个不正确？（）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)Q下面谓词公式哪个是前束范式？（）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))在谓词演算中：P(a)是xP(x)的有效结论，其理论根据是（）A.全称规定规则(US)B.全称推广规则(UG)C.存在规定规则(ES)D.存在推广规则(EG)填空题令R(x)：x是实数，Q(x)：x是有理数。命题“并非每个实数都是有理数”。其符号化为①。命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可表示为②。2.设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化为。3.设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有智能工作都能由计算机来做”符号化为。设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的作用域为③。公式x(P(x)Q(x,y)R(y,z))S(x)中自由变量为①，约束变量为②。取个体域为整数集，给定下列公式：(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)中是等值的。对公式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)中的量词，可得。下列各式(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))其中是永真式。下列各式(1).yxA(x,y)(2).xyA(x,y)(3).xyA(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))=③。给定下面谓词公式：(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个公式中，为重言式的有①，为矛盾式的有②。给定下列各公式：(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)的前束范式。供选择的 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 有①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))的前束范式为。在谓词逻辑中给出四个推理：(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))以上四个推理中正确的有。在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。命题符号化：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))（）下面的推理：条件：x(P(x)Q(x))，根据全称规定（US）有：P(a)Q(b)是正确的。（）对公式z(P(z)Q(x,z)M(z,y))R(z)中约束变量z改名后，得到的等价公式为：t(P9t)Q(x,t)M(t,y))R(t)（）综合题用谓词和量词将下列命题符号化：(1).没有不犯错误的人；(2).尽管有人聪明，但未必一切人都很聪明；(3).每个计算机系的学生都学离散数学；(4).所有的人都学习和工作；(5).并非一切推理都能用计算机完成；(6).任何自然数都有惟一的一个后继数。*2.令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，L(x,y)表示“x0当且仅当有这样的y，使得x≥y。(2).并非对一切x，都存在y，使得x≤y。(3).对任意的x，若x+y=x，当且仅当y=0。3.用谓词公式表示命题“”，并写出该命题的否定命题。*4.设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化：(1).并不是外语学的好的都是三好学生。(2).有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。指出下列公式中量词每次出现的作用域，并指出个体变量是约束变量还是自由变量。(1).xy(R(x,y)L(y,z))xH(x,y)(2).x(P(x)xQ(x))(xP(x)Q(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是某个自然数的平方”。请在此基础上，求下面公式的真值：x(A(x)(A(a)B(x))((PxA(x))B(a))下列各式翻译成自然语言，然后在不同的个体域中确定它们的真值：(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)个体域分别为：①实数集②整数集③正整数集④非负实数集设解释T如下：个体域为实数集R，元素a=0，函数f(x,y)=x-y，特定谓词F(x,y)为x5，R(x)：x≤7。根据解释T，求下列各式的真值：(1).x(F(x)G(x))(2).x(R(x)F(x))G(5)(3).x(F(x)G(x))设A(x)是一个含有个体变量x的谓词公式，证明下面等值式成立：xA(x)x(A(x))设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)，H(x)分别是谓词公式，试证明xG(x)xH(x)x(G(x)H(x))17.下列公式是否成立，成立则证明，不成立，则举例说明之。(1).xyA(x,y)xyA(x,y)(2).xA(x)xB(x)x(A(x)B(x))18.下面公式是否是永真式？说明理由。(1).(AxB(x))x(AB(x))(2).x(A(x)B(x))(xA(x)xB(x))19.下面的公式是否是永真式？是则证明之，不是，请举出反例：(1).xyA(x,y)yxA(x,y)(2).(xA(x)xB(x))x(A(x)B(x))20.下面公式是否有效，对有效的公式加以证明，对无效的公式加以反驳。(1).x(P(x)Q(x))(xP(x)xQ(x))(2).(xP(x)xQ(x))x(P(x)Q(x))21.航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明：这个人一定不是航海家。22．指出下列推理中的错误：(1).①xF(x)G(x)前提引入②F(y)G(y)①US(2).①x(F(x)G(x))前提引入②F(a)G(b)①US(3).①F(x)G(x)前提引入②y(F(y)G(y))①EG(4).①F(x)G(c)前提引入②x(F(x)G(x))①EG(5).①F(a)G(b)前提引入②x(F(x)G(x))①EG(6).①x(F(x)G(x))前提引入②y(H(y)R(y))前提引入③F(c)G(c)①ES④F(c)③化简⑤H(c)R(c)②ES⑥H(c)⑤化简⑦F(c)H(c)④⑥合取⑧x(F(x)H(x))⑦EG23.试找出下列推理过程中的错误，写出正确的推导过程，说明理由：①x(P(x)Q(x))条件②P(y)Q(y)全称规定(US)③xP(x)条件④P(y)存在规定(ES)⑤Q(y)由条件②④⑥xQ(x)存在推广(EG)24.下面推理是否是一个有效的推理，为什么？①xyQ(x,y)条件②yQ(a,y)全称规定(US)③Q(a,b)存在规定(ES)④xQ(x,b)全称推广(UG)⑤yxQ(x,y)存在推广(EG)25.下面推广是否正确，若有错，请指出：x(A(x)B(x))x(A(x)B(x))①X(A(x)B(x))②x(A(x)B(x))③(xA(x)xB(x))④xA(x)x(B(x))⑤xA(x)xB(x)⑥xA(x)xB(x)⑦26.用谓词演算推理规则证明：x(P(x)(Q(y)R(x)))，xP(x)Q(y)x(P(x)R(x))27．改正下面证明中的错误：前提：x(y(S(x,y)M(y))z(P(z)R(x,z)))；结论：zP(z)xy(S(x,y)M(y))。证明过程：①x(y(S(x,y)M(y))z(P(z)R(x,z)))；P②y(S(b,y)M(y))z(P(z)R(b,z))①US③zP(z)P(附加前提)④z(P(z))③T,E⑤P(a)④US⑥P(a)R(b,a)T,⑤I⑦z(P(z)R(b,z))⑥UG⑧z(P(z)R(b,z))⑦T,E⑨y(S(b,y)M(y))②,⑧T,L⑩y(S(b,y)M(y))⑨T,E⑾y(S(b,y)M(y))⑩T,E⑿xy(S(x,y)M(y))⑾UG⒀zP(z)xy(S(x,y)M(y))CP第三章选择题对任意集合A、B、C，下述论断正确的是（）A.若AB，BC，则ACB.若AB，BC，则ACC.若AB，BC，则ACD.若AB，BC，则AC设A-B=，则有（）A.B=B.BC.ABD.AB设P={x|(x+1)2≤4}，Q={x|x2+16≥5x}，则下列选项正确的是（）A.PQB.PQC.QPD.Q=P设A={{1,2,3},{4,5},{6,7,8}}，下列选项正确的是（）A.1AB.{1,2,3}AC.{{4,5}}AD.A下列个选项错误的是（）A.B.C.{}D.{}设A={x|x3-x=0}，B={x|x2-4<0,xZ}，C={x|y=2x-1}，D={x|x+y=5,xy=6}，则有（）A.A=BB.A=CC.C=DD.C=A7.在0之间填上正确的符号。A.=B.C.D.设M={x|f1(x)=0}，N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（）A.M∩NB.M∪NC.M⊕ND.M-N设A={a,{a}}，下列选项错误的是（）A.{a}P(A)B.{a}P(A)C.{{a}}P(A)D.{{a}}P(A)设A={}，B=P(P(A))，下列选项错误的是（）A.BB.{}BC.{{}}BD.{,{}}P(A)幂集P(P(P()))为（）A.{{},{,{}}}B.{,{,{}},{}}C.{,{,{}},{{}},{}}D.{,{,{}}}*12.空集的幂集P()的基数是（）A.0B.1C.3D.413.集合A={1,2,…,10}上的关系R={|x+y=10,xA,yA}，则R的性质为（）A.自反的B.对称的C.传递的，对称的D.反自反的，传递的14.设A={a,b,c}上的关系如下，有传递性的有（）A.ρ1={,,,}B.ρ2={,}C.ρ3={,,,}D.ρ4={}15.设R和S是集合A上的任意关系，则下列命题为真的是（）A.若R和S是自反的，则RS也是自反的B.若R和S是反自反的，则RS也是反自反的C.若R和S是对称的，则RS也是对称的D.若R和S是传递的，则RS也是传递的16.若R和S是集合A上的两个关系，则下述结论正确的是（）A.若R和S是自反的，则R∩S也是自反的B.若R和S是对称的，则RS也是对称的C.若R和S是反对称的，则RS也是反对称的D.若R和S是传递的，则R∪S也是传递的17.设A={1,2,3,4,5}，ρ={|i,,,}，那么R是（）A.反自反的B.反对称的C.可传递的D.不可传递的19.设R和S是集合A上的等价关系，则R∪S的对称性（）A.一定成立B.一定不成立C.不一定成立D.不可能成立20.设R和S是非空集合A上的等价关系，下述各式是等价关系的为（）A.(A×A)-RB.R2C.R-SD.r(R-S)21.集合A上的关系R是相容关系的必要条件是（）A.自反、反对称的B.反自反、对称的C.传递、自反的D.自反、对称的22.设R是集合A上的偏序关系，是R的逆关系，则R∪是（）A.偏序关系B.等价关系C.相容关系D.都不是23.设集合A中有4个元素，则A上的不同的等价关系的个数为（）A.11个B.14个C.15个D.17个填空题1.设M={1≤x≤12，x被2整除，x∈Z}，N={x|1≤x≤12，x被3整除，x∈Z}，则M∪N=①，M∩N②。设全集U={1,2,…,7}的子集为A={偶数}，B={奇数}，C={3的倍数}，则A∩B=①，∩=②，=③,B∩C=④。设集合A={x|<3，xZ}，B={x|x=2k，kZ}，C={1,2,3,4,5}。(1).AC=①(2).(AB)∩C=②(3).BB=③(4).A(C-B)=④设I为整数集合，A={x|x2<30，xI}，B={x|x是素数，x<20}，C={1,3,5}。(1).(A∩B)∪C=①(2).(B-A)∪C=②(3).(C-A)∩(B-A)=③(4).(B∩C)-A=④设全集U={1,2,3,…,20}，A、B、C是其子集，且A={x|<4}，B={x|x2-6x-7=0}，C={x|x2<100}。(1).(A-B)∩=①(2).∩∩C=②(3).(A∩)-C=③设A、B是集合，求A与B之间的关系。(1).如果A={1}，B={1,{1,2}}，则①(2).如果A=，B={}，则②(3).如果A={a}，B={,a,{}}，则③(4).如果A={}，B={,{}}，则④供选择项：AB且ABB.AB且ABC.AB但ABD.AB且AB7.设A={{x,y},,x,y}，求下列各式的结果：A-{x,y}=①；A-{}=②；{{x,y}}-A=③；-A=④；A的幂集P(A)=⑤。8.集合A={,{a}}的幂集P(A)=。9.集合A={{1,2},{3}},B={{1},{2},{3}}，试写出A∪B=①，A∩B=②，P(A)=③。10.设A={x|100,<1,2>,<1,3>,<3,3>}，则关系R具备①性，不具备②性。21.设A={1,2,3,4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则r(R)=①，s(R)=②。设集合A仅含有3个元素，那么(1).在A上可定义.种不同的二元关系。(2).在A上可定义种不同的自反关系。(3).在A上可定义种不同的反自反关系。(4).在A上可定义种不同的对称关系。(5).在A上可定义种不同的反对称关系。如果R1和R2是A上的对称关系，有下列观点：(1).R1∪R2是对称的(2).R1∩R2是对称的(3).R1R2是对称的其中是正确的。如果R1和R2是A上的反对称关系，有下列观点：(1).R1∪R2是反对称的(2).R1∩R2是反对称的(3).R1R2是反对称的其中是正确的。如果R1和R2是A上的传递关系，有下列观点：(1).R1∪R2是传递关系(2).R1∩R2是传递关系(3).R1R2是传递关系(4).R12是传递关系其中是正确的。R是A的二元关系，那么有下列观点：(1).当R是自反关系时，R的传递闭包也是自反关系(2).当R是反自反关系时，R的传递闭包也是反自反关系其中是正确的。R是A的二元关系，那么有下列观点：(1).当R是对称关系时，R的传递闭包也是对称关系(2).当R是反对称关系时，R的传递闭包也是反对称关系其中是正确的。28.集合A={a,b,c,d,e,f,g}，A上的一个划分π={{a,b},{c,d,e},{f,g}}，那么π所对应的等价关系R应有个有序对。29.设R是集合{1,2,…,10}上的模7同余关系，则[2]R=。30.设R1和R2是A的相容关系，那么对于下列观点：(1).R1∪R2是相容关系(2).R1∩R2是相容关系(3).R1R2是相容关系其中是正确的。*31.整数集上的小于关系“<”具有①，②和③关系。32.设A={a,b,c}上偏序关系(P(A),)，则P(A)的子集B={,{a},{b},{a,b},{b,c}}的极大元是①，最大元是②，上界是③，下确界是④。33.A={2,3,4,5,6,8,10,12,24}，R是A上的整除关系。那么A的极大元是①，极小元是②。34.A={1,2,3,4,5,6,7,8,9,10,11,12}，R是A上的整除关系。子集B={2,4,6}，那么B的最大元是①，B的最小元是②，B的上界是③，B的下界是④。35.A={1,2,3,4,5,6,8,10,24,36}，R是A上的整除关系。子集B={1,2,3,4}，那么B的上界是①，B的下界是②，B的上确界是③，B的下确界是④。判断题1.若AB=AC，则B=C。（）2.若P∪Q=Q，P∩Q=，则P=。（）3.{}{,{}}且{}{,{}}。（）4.设A={}，B=P(P(A))，则有{}B，且{}B。（）5.A，B是集合，则命题AB和AB可能同时成立。（）6.设A，B为任意集合，则P(A-B)=P(A)-P(B)。（）7.若A-BB，则BA。（）8.对每个集合A，有{A}P(A)。（）9.设A与B是任意两个集合，若{A∩B,B-A}是A∪B的一个划分，则有A-B=。（）10.若{A-B,B-A}是集合A∪B的一个划分，则有A∩B=，其中A，B。（）11.设A，B是两个任意的集合，若{A∩B,A-B,B-A}是A∪B的一个划分，则有A∩B=，A-B=，B-A=。（）12.若{A∩B}是A∪B的一个划分，则有A-B=B-A=。（）13.若R是集合A上的传递关系，则R2也是集合A上的传递关系。（）14.若集合A上的关系R是对称的，则也是对称的。（）15.一个不是自反的关系，一定是反自反的。（）16.集合A={1,2,3}的任何关系R都不可能既是对称的，又是反对称的。（）17.集合A={a,b,c}上的关系R={,}是不可传递的。（）18.若R和S是集合A上的任意两个自反关系，则RS也是自反的。（）19.若R和S是集合A上的任意两个反自反关系，则RS也是反自反的。（）20.若R和S是集合A上的任意两个对称关系，则RS也是对称的。（）21.若R和S是集合A上的任意两个传递关系，则RS也是传递的。（）22.若R为集合A上的反对称关系，则t(R)一定是反对称的。（）设R和S是集合A上的关系，则有：r(R∪S)=r(R)∪r(S)；（）s(R∪S)=s(R)∪s(S)；（）t(R∪S)t(R)∪t(S)；（）24.设R和S是集合A上的等价关系，则R∪S一定是等价的。（）25.设R和S是集合A上的两个相容关系，则RS和R∩S都是相容关系。（）26.平面上直线间的平行关系是等价关系。（）27.设人的集合A上的朋友关系为R，则R是A上的相容关系。（）综合题举出集合A，B，C的例子，使其满足AB，BC，但AC。判断以下命题的真假：(1).a{{a}}(2).{a}{{a}}(3).x{x}-{{x}}(4).{x}{x}-{{x}}(5).A-B=AB=(6).A-B=A=B(7).AA=A(8).A-(B∪C)=(A-B)∩(A-C)(9).如果A∩B=B，则A=B(10).A={x}∪x，则xA且xA设A，B，C，D是Z的子集，其中：A={1,2,7,8}B={x2|x2<50且xZ}C={x|xZ且0≤x≤30且x可以被3整除}D={x|x=2k且kZ且0≤k≤6}用描述法表示下面集合并计算：(1).A∪B∪C∪D(2).A∩B∩C∩D(3).B-(A∪C)(4).(A∩B)∪D设全集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)A∪B(2)A∩C(3)(A∪B)∩(4)A-B(5)C-D(6)BDA={{},{,1},{1,1,}}，B={{,1},{1}}。计算A∪B，A∩B，A-B，P(A)。化简((A∪(B-C))∩A)∪(B-(B-A))。第四章第五章选择题*1.设S={a,b}，则S上总共可定义的二元运算的个数是（）A.4B.8C.16D.32设集合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，下列哪种运算不是可结合的？（）A.a*b=a+b+3B.a*b=min{a,b}C.a*b=a+2bD.a*b=ab(mod3)下列运算中，哪种运算关于整数集不能构成半群？（）A.aοb=max{a,b}B.aοb=bC.aοb=2abD.aοb=|a-b|6.*运算如下表所示，哪个能使({a,b},*)成为独异点？（）Q是有理数，(Q,*)（其中*为普通乘法）不能构成（）A.群B.独异点C.半群D.交换半群R为实数集，运算*定义为：a,bR，a*b=a|b|，则代数系统(R,*)是（）A.半群B.独异点C.群D.阿贝尔群*9.下列代数系统(S,*)中，哪个是群？（）S={0,1,3,5}，*是模7的加法S=Q(有理数集合)，*是一般乘法S=Z(整数集合)，*是一般乘法S={1,3,4,5,9}，*是模11的乘法10.具有如下定义的代数系统(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进行乘法运算，则下述等式中哪个不成立？（）A.(x*y