《离散数学》习题集

《离散数学》习题集目录第一章数理逻辑2第二章集合14第三章二元关系22第三章二元关系36第五章无限集合50第1页共53页第一章数理逻辑1.1命题设P是命题“天下雪”；Q是命题“我去镇上”；R是命题“我有时间”。用逻辑符号写出以下命题：如天不下雨和我有时间，那么我去镇上；我去镇上，仅当我有时间；天不下雪；天正在下雪，我也没去镇上。对下述命题用中文写出语句：(i)Q(RP)；RQ；(QR)(RQ)；(RQ)。否定下列命题：上海处处清洁；每一个自然数都是偶数。说出下述每一命题的逆命题和逆反命题：如果天下雨，我将不去；仅当你去我将逗留；(c)如果n是大于2的正整数，则方程xnynzn无正整数解（费尔马最后定理）；如果我不获得更多帮助，我不能完成这个任务。给P和Q指派真值T，给R和S真值F，求下列命题的真值：(a)PQR((PQ)(RS))；(b)(PQ)R((QP)RS)；(c)P(QRP)Qs。构成下列公式的真值表：Q(PQ)P；第2页共53页(b)(PQQR)PR。证明下列公式的真值与它们的变元值无关：(a)P(PQ)Q；(b)(PQ)(QR)(PR)。7.对P和Q的所有值，证明PQ与PQ有同样的真值。证明(PQ)(PQ)总是真的。8.设是具有两个运算对象的逻辑运算符，如果(xy)z与x(yz)逻辑等价，那么运算符是可以结合的，确定逻辑运算符、、、哪些是可结合的；用真值表证明你的断言。指出一下各式哪些不是命题公式，如果是命题公式，请说明理由：(a)(((P)(PQ))R)；(b)((Q(PQ))P)。1.2重言式10．指出下列那些命题是重言式、偶然式和矛盾式：(a)PP；(b)PP；P(P)；(d)（PQ)(QP)；(e)（PQ)(PQ)；(f)（PQ)(QP)；(g)P(QR)(PQPR)；(h)（PQP)(PQ)；(i)(（PQ)(RS))((PR)(QS))。11.对下述每一表达式，找出仅用和的等价表达式，并尽可能简单：(a)PQR；(b)P(QRP)；(c)P(QP)。第3页共53页对下述每一表达式，找出仅用和的等价表达式，并尽可能简单：(a)PQP；(b)(P(QR))PQ；(c)PQ(RP)。12.用化简联结词的左边成右边的方法，证明以下是重言式：(a)((PQ)P)T；(b)(QP)（PQ)(QQ)P。证明下列等价关系：(a)P（QP)P(PQ)；(b)(PQ)(RQ)(PRQ)；(c)（PQ)(PQ)(PQ)(PQ)(PQ)；(d)（PQ)PQ。求出下列公式的最简等价式：(a)((PQ)(QP))R；(b)PP(QQ)；(c)（P（QS))(P(QS))。证明下列蕴含式：(a)PQ(PQ)；(b)P(QP)；(c)（P（QR))(PQ)(PR)；(d)（PQ)QPQ；(e)（(PP)Q)（(PP)R)(QR)。16.(a)与非运算符（又叫悉菲（Sheffer）记号）用下述真值表定义，可以看出PQ（PQ)，试证明（i）PPP；（ii）；(PP)(QQ)PQ；（iii）（PQ）(PQ)PQ。第4页共53页(b)或非运算符（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与（PQ)逻辑等价。对下述每一式，找出仅用表示的等价式。（i）P；（ii）PQ；（iii）PQ。PQPQPQPQ00100101101010110011011017.(a)用真值表证明和互相可分配；(b)、和对自己可分配吗？求出下列各式的代入实例：(a)(((PQ)P)P)：用PQ代P，用((PQ)R)代Q；(b)((PQ)(QP))；用Q代P，用PP代Q。1.3范式19.对任一指派，ij时，为什么mi和mj不能同时为真？为什么Mi和Mj不能同时为假？求下列各式的主合取范式：(a)PQRPQRPQR；(b)PQPQPQ；PQPQR。求下列各式的主析取范式和主合取范式：(a)（PQ）（PQ）；(b)P(P(Q(QR)))；(c)（PQR)(P(QR))；(d)PQSPQR。1.4联结词的扩充与归约第5页共53页22.仅用表达PQ；再用表达它。23.仅用表达PQ；仅用表达PQ。24.试证明等价式：(PQ)PQ和(PQ)PQ。25.写出一个仅含且等价于P(QR)的公式来。证明{},{},{,}都不是全功能联结词集合。27.证明{,}，{,T}是全功能联结词集合。28.证明联结词可交换，可结合，且在上可分配。29.证明联结词可交换，可结合，且在上可分配。1.5推理规则和证明方法用真值表证明下列推理规则的重言式形式都是重言式：拒取式；析取三段论；构造性二难定理；破坏性二难推理。H1,H2,是前提，C是结论，用真值表判断下列结论是否有效：H1:PQ，H2:Q，C:P；(b)H1:PQ，H2:PR，H3:QR，C:R；(c)H1:P(QR)，H2:PQ，C:R；(d)H1:P，H2:PQ，C:PQ。给出一个指派，证明以下结论是非有效的：(a)前提是AB,B(CD),C(AE),AE，结论是AE。(b)前提是A(BC),B(AC),C(AB),B，结论是AC。对下列每一个前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。如果我跑，我喘气。我没有喘气。天气是晴朗或阴暗，天气晴朗使我愉快而天气阴暗使我烦恼。如果考试及格了，那么我很高兴。如果我很高兴，那么我的饭量增加。我的饭量减少。第6页共53页对下述每一论证构造一个证明，给出所有必须增加的断言，指出用于每一步的推理规则。从语句“今天下雨或明天后天都下雨”和“明天不下雨或后天不下雨而今天下雨”可推出“今天下雨”。如果李敏来通信工程学院，若王军不生病，则王军一定去看望李敏。如果李敏出差到南京，那么李敏一定来通信工程学院。王军没有生病。所以，如果李敏出差到南京，王军一定去看望李敏。确定下列论证哪些是有效的论证，为有效论证构造证明，对非有效论证，表明为什么结论不能从前提得出。ABABAB(a)AC；(b)AC；(c)AC。CBCBCB36.仅用E4,E5,E8,E18,E21,I2证明P(PQ)Q。证明下列论证的有效性：(a)(AB)(AC)，(BC)，DA推得D；(b)PQR，RS，S推得PQ；(c)(PQ)R，RS，QT推得R。证明下列结论“(a)PQ，QR，RSPS；(b)PQRPQR；(c)PQPPQ；(d)PQR，Q(RS)，P(QS)。试说明“从假的前提出发，能证明任何命题”。证明下列各式的有效性：(a)RQ，RS，SQ，PQ推得P；(b)SQ，SR，R，RQ推得P；(c)(PQ)(RS)，((QP)R)，R推得PQ。1.6谓词和量词第7页共53页下列表达式哪些是命题？(a)x(P(x)Q(x))R；(b)x(P(x)Q(x))S(x)。42.设谓词S(x,y,z)表示“xyz”，谓词M(x,y,z)表示“xyz”，论述域是整数，用以上谓词表示下述断言：(a)对每一x和y，有一z，使xyz；(b)对每一x和y，有一z，使xzy；从任何整数减去0，其结果是原整数；(d)对所有x，对所有y，xyy。43.论述域是整数，对下列每一个断言找出谓词P使蕴含式是假。(a)x!yP(x,y)!yxP(x,y)；(b)!yxP(x,y)x!yP(x,y)。指定一个论述域使下列命题是真。要使指定得论述域是尽可能大的整数的一个子集。(a)x(x0)；x(x＝5)；yx(xy＝3)；(d)yx(xy0)。45.设论述域是自然数，P(x,y,z)表示“x＋yz”，Lxy(,)表示“xy”，用逻辑符表示下列断言：(a)对每一x和y，有一z，使x＋yz；(b)(b)没有x小于0；(c)4加3得7。将苏格拉底论证符号化。47.设P(x,y,z)表示xyz，E(x,y)表示x＝y，G(x,y)表示xy，论述域是整数，将下列断言译成逻辑符。（提示：要注意数学上习惯写法和逻辑符表示的差异，例如加法交换律在数学中写成：x＋yyx，翻译成逻辑符时，要按照实际意义翻译成：xy(xyyx)），即要自动加上全称量词，使整个式子成为命题。）(a)如果xy0，那么x＝0，或y＝0；(b)如果xy0，那么x并且y0；0，(c)xz是xy并且yz的必要条件；第8页共53页x＝y和xy不能同时出现；(e)存在一x，对每一y和z，使xyxz。将下列断言译为逻辑符号，选用的谓词应使逻辑符号中至少含有一个量词：有一个且仅有一个偶数是质数；没有一个奇数是偶数；某些卡车慢于所有火车，但是至少有一辆火车，快于每一卡车；所有步行的，骑马的或乘车的人，凡是口渴的都喝泉水。设E(x)表示“x是偶数”，O(x)表示“x是奇数”，P(x)表示“x是质数”，N(x)表示“x是负数”，I(x)表示“x是整数”和一些中缀表示的谓词诸如yx21等，将下列各句翻译成逻辑符。一个整数是奇数，如果它的平方是奇数；有两个奇数它们的和是偶数；不存在一个整数x使x21是负数；任何两个质数之和是质数；对任何整数，如果它的平方是负的，那么1＝1。如果论述域是{a,b,c}，试消去下列公式中的量词：(a)xR(x)xS(x)；(b)x(P(x)Q(x))。试说明下列公式是合式公式：(a)(x(F(x)Q(x))；(F(x,y)(xG(x,y)))。1.7谓词演算的永真公式证明永真公式Q14,Q15,Q16,Q17,Q19。53.下列断言如果是真的证明它们，如果是假的，找出P和Q的解释以证明公式是假。(a)x(P(x)Q(x))(xP(x)xQ(x))；(b)(xP(x)xQ(x))x(P(x)Q(x))；(c)(x(P(x)xQ(x))x(P(x)Q(x))；(d)x(P(x)Q(x))(xP(x)xQ(x))。第9页共53页设论述域是{a0,a1,a2,,an}，试证明下列关系式：(a)xA(x)Px(A(x)P)；(b)x(A(x)B(x))xA(x)xB(x)。55.对一个仅含元素0和1的论述域，试证明：x(P(x)Q(x))(xP(x)xQ(x))，并证明蕴含式之逆不是有效的。1.8谓词演算的推理规则对下列每一前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。所有三角形函数都是周期函数，而所有周期函数都是连续函数；所有偶数都被2除尽。整数4是偶数，但3不是；对汽车工业的好事就是对国家的好事，对国家的好事就是对你的好事。你去买一辆高价卡车是对汽车工业的好事。下列推导步骤为什么是错误的？(a)(i)xP(x)Q(x)P(ii)P(x)Q(x)T，1，US(b)(i)x（P(x)Q(x))P(ii)P(a)Q(b)T，1，US(c)(i)xP(x)x(Q(x)R(x))P(ii)P(a)x(Q(x)R(x)）T，1，US证明下列各断言：(a)(xP(x)Q(a))推得xP(x)Q(a))；(b)x(P(x)Q(x)),xP(x)，推得xQ(x)。59.考虑蕴含式x(P(x)Q(x))xP(x)xQ(x)证明它不是有效的。下面是一个论证，企图证明上式有效，试找出不正确的地方。x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))(xP(x)xQ(x))xP(x)xQ(x)xP(x)xQ(x)判断下列结论C能否有效的从给定的前提得出：(a)x(P(x)Q(x)),yP(y)C:zQ(z)；第10页共53页(b)xP(x),xQ(x)C:x(P(x)Q(x))。补充习题：判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100⑻我正在说谎。将下列命题符号化：2008年将在北京举办奥运会并且中国是世界四大文明古国之一。⑵如果小王努力学习，那么他的学习成绩就优秀。⑶张华是三好学生当且仅当德、智、体全优秀。⑷他或者骑自行车去学校，或者乘公共汽车去学校。构造命题公式?p∨q，(p∧q)∨(?p∧?q)的真值表。4根据等价的定义，用真值表证明p→(q→p)?p→(p→?q)。5用真值表证明德摩根律?(A∨B)?A∧?B。6用等价演算法证明p?q(p∧q)∨(?p∧?q)。用等价演算法判断下列公式的类型。q∨?((?p∨q)∧p)(p∨?p)→((q∨?q)∧r)(p→q)∧?p利用代入规则证明((p∨q)∧r)∨?((p∨q)∧r)为重言式。求命题公式(p∨q)?p的合取范式和析取范式。用真值表法，求(p→q)→r的主析取范式。用等价演算法求(p∧q)∨(?p∧r)∨(q∧r)的主析取范式。第11页共53页12用真值表法求(p→q)→r的主合取范式。13用等价演算法求(p→q)→r的主合取范式。证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。15推证?p∧(p∨q)q。分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。用直接推理法证明(p→q)∧(q→r)∧pr。18用CP规则证明：p→(q→r)，?t∨p，qt→r。19用间接法（反证法）证明：(p∧q)→r，?r∨s，?s，p?q。将下列命题符号化，并讨论它们的真值。2与3都是偶数。⑵如果5大于3，则2大于6。个体域是人类集合，对下列命题符号化。⑴凡人要死。⑵有的人是研究生。对下列命题符号化，并在①，②，③三个个体域中考察命题的真值。命题：⑴所有数小于5。至少有一个数小于5。个体域：{-1，0，1，2，4}{3，-2，7，8}{15，20，24}对下列命题在①，②两个个体域中符号化。命题：⑴所有老虎是要吃人。存在一个老虎要吃人。个体域：①所有老虎组成的集合。②全总个体域。用谓词公式表达下列自然语言中的命题：第12页共53页⑴并非每个实数都是有理数。⑵没有不犯错误的人。⑶并不是所有的兔子都比所有的乌龟跑得快。说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)→Q(y)⑵(x)(P(x)∧(y)Q(x,y))⑶(x)P(x)∧(y)Q(x,y)⑷(x)(y)(P(x,y)∧Q(y,z))?(x)R(x,y)⑸(x)P(x)∨R(x,y)26对(x)(y)(P(x,y)∧Q(y,z))?(x)R(x,y)中的约束变元y换名。27对(x)(P(y)∧R(x,y))→(y)Q(y)中的自由变元y进行代入。证明：⑴(x)(A(x)→B)(x)A(x)→B⑵(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)⑶(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)29求公式(x)F(x)→(x)G(x)的前束范式。30将((x)F(x)∨(x)G(x))→(x)(F(x)∨G(x))化为与其等价的前束合取范式。证明：苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。32证明：(x)(H(x)→M(x))，(x)H(x)(x)M(x)。33证明：(x)(A(x)∨B(x))，(x)?A(x)(x)B(x)。34用CP规则证明：(x)(F(x)∨G(x))(x)F(x)∨(x)G(x)。设个体域为全总个体域。证明推理：学术会的成员都是工人并且是专家。有些成员是青年人。所以有的成员是青年专家。第13页共53页第二章集合2.1集合论的基本概念用列举法表示下列集合：小于20的质数集合；构成evening的字母集合；(c){x|x2x60}。列出下列集合的成员：{x|x是36的因子}；(b){x|xaxb}。3.证明：若a,b,c,d是任意客体，则{{a},{a,b}}{{c},{c,d}}当且仅当ac和bd。4.列举下列集合的全部子集：(a){}；(b){,{}}；(c){{,a},{a}}；(d){{a,b},{a,a,b},{b,a,b}}。5.设A,B,C是集合，证明或否定以下断言：(a)[ABBC]AC；(b)[ABBC]AC；(c)[ABBC]AC。确定下列各命题的真和假：(a)；；(c){a,b}{a,b,c,{a,b,c}}；(d){a,b}{a,b,{{a,b}}}。2.2集合上的运算7.给定自然数集合N的下列子集：第14页共53页A{1,2,7,8}B{i|i250}C{i|i可被整除30}D{i|i2kkI0k6}求出下列集合A(B(CD))；A(B(CD))；B(AC)。8.设x和y是实数，定义运算xy是xy（x的y次幂）证明运算既非可交换的也非可结合的。设代表乘法运算，确定下列分配律哪些是成立的：(i)x(yz)(xy)(xz)；(ii)（yz)x(yx)(zx)。设A,B,C是任意集合，把ABC表示成不相交集合之并。10.(a)证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使ABBA；ABBA可能吗？刻画此式出现的全部条件；“相对补”是一个可结合的运算吗？证明你的断言。设A,B,C是论述域U的任意子集，证明下列各式：(a)A(BA)；(b)A(BC)(AB)(AC)；(c)A(BC)(AB)(AC)。12.证明AB，AB，AB三者是等价的。13.在下列命题中找出S和S：SCSCC{}；C{,{}}；(c)C{{i}|iI}。14.设C是一非空的某论述域U的子集的搜集，B是U的子集，证明下列分配律的推广：___(a)＝S；SSCSC第15页共53页(b)___SS。SCSC指出下列集合的幂集合：(a){a,b,c}；(b){{a,b},{c}}。证明下列各式：(a)AABB；(b)(AB)BAB；(c)C(AB)(CA)(CB)。2.1归纳法和自然数对下列集合给出归纳定义：(a)十进制无符号整数集合，定义集合将包含6，235，0045等等；(b)十进制的以小数部分为结束的实数集合，定义的集合包含5.3，453.，01.2700，0.480；(c)二进制形式的不以0开头的正偶数和0组成的集合，定义的集合包含0,110,1010等；把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串。例如[],[[]],[][],[[[]][]]等都是成形括号串（例中用[]代（）是为了明晰），试定义成形括号串集合。18.用{a}代替N的定义中的，但仍用这一定义，可否生成自然数集合？有何不同？证明成形括号串的左右括号个数相等。20.我们有3分和5分两种不同票值的邮票，试证明用这两种邮票就足以组成8分或者更多的任意邮资。21.用归纳法证明：对一切nI，(12n)21323n3。22.对所有nN，证明下列每一关系式：ni2(a)n(n1)(2n1)/6；i0n(n1)2；(b)(2i1)i0n(c)i(i!)(n1)!1；i0第16页共53页n(n1)r1n2(d)irinrn2r；i0(n1)rn1(r1)2r112n3n。如果每根直线连接多边形的两个点，且位于多边形上，那么这个多边形叫凸的，证明对一切n3，n边的凸多边形内角之和等于(n2)180。（提示：多边形能用连结两个非邻接的顶角划分为两部分。）24.找出自然域上的两个谓词P和Q一证明归纳证明的基础步骤和归纳步骤是独立的，也就是没有一个逻辑地蕴含另一个。特别，要找出一谓词P使P(0)是真而n(P(n)P(n1))是假，和一谓词Q，使Q(0)是假，而n(Q(n)Q(n1))是真。25.我们意欲证明，对一切n和一切S，如果S是n个人的集合，那么在S中的所有人都有同样的身材。下面“所有人都有同样的身材”的证明错在那里？(a)（基础）设S是一空集合，那么对所有的x和y，如果xS和yS，那么x和y有同样的身材。(b)（归纳）假定对所有包含n个人的集合断言是真。我们证明对包含n1个人的集合也真。任何由n1个人组成的集合包含两个n个人组成的不同的但交搭的子集合。用S和S表示这两个子集合。那么根据归纳前提，在S中的所有人有相同的身材，在S中的所有人有相同的身材，因为S和S是交搭的，所以，所有在SSS中的人都有相同的身材。26.设{A1,A2,,An}是集合的非空搜集，对n作归纳证明下述推广的德摩根定律：nn(a)AiAi；i1i1nn(b)AiAi。i1i1证明对所有大于1的整数n都能写成若干个质数之积。28.如果a(bc)(ab)c，那么二元运算称为可结合的。从它可推出更强的结果，即在任何仅含运算的表达式中，括号的位置不影响结果，就是，仅仅出现于表达式中的运算对象和次序是重要的。为了证明这个“推广的结合律”，我们定义“表达式集合”如下：（基础）单个运算对象a1是表达式；（归纳）设e1和e2是表达式，那么(e1,e2)是表达式；第17页共53页(c)（极小性）只有有限次应用（a）和（b）构成的式子才是表达式。设e是一个表达式，它有a1,a2,,an个运算对象，且此次序出现于表达式中，那么e(a1(a2(a3((an1an)))))证明这个推广的结合律。（提示：用数学归纳法第二原理。）2.5集合的笛卡儿乘积如果A{a,b}和B{c}，试确定下列集合：A{0,1}B；B2A；(c)(AB)2。30.设A{0,1}，构成集合(A)A。设A,B,C和D是任意集合，试证明：(AB)(CD)(AC)(BD)。32.试证明：ABBAABAB。指出下列各式是否成立：(a)(AB)(CD)(AC)(BD)；(b)(AB)(CD)(AC)(BD)(c)(AB)(CD)(AC)(BD)；(d)(AB)C(AC)(BC)；(e)(AB)C(AC)(BC)。补充习题：1令A{1,2}，B{1,2,O}，C{2,2,1}，D{2,O,O,1}，E{x|x33x20}。试指出哪些集合是相等的？哪些集合是不相等的？2设S{2,a,{3},4}，R{{a},3,4,1}，判断下列各命题真或假：（）{a}S；（）{3}S；（）{O}S；（）O{{3},4}；1234（5）O{{a}}R；（6）OR；（7）OR；（8）{{a},1,3,4}R第18页共53页试指出下列命题哪些为真？哪些为假？（1）OO；（2）O{O}；（3）O{{O}}；（4）O{O,{O}}；（5）OO；（6）O{O}；（7）O{{O}}；（8）O{O,{O}}4设A={a,b,c}，A是空集，试求P(A)，P(P(A))。求下列集合的幂集：（1）O；（2）{O}；（3）{O,{O}}；（4）{O,1,{2}}；（5）{{1},{O,1}}；（6）{{1,2},{1,1,2},{2,1,2}}6设A,B,C是集合，试回答下列问题：（1）若ABAC，是否必须BC？（2）若ABAC，是否必须BC？（3）若ABAC，是否必须BC？7设A,B是任意的集合，求证:A-B=A∩(~B)。8设A,B是任意的集合，求证:AB=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。9设集合E{1,2,3,4,5}，A，B和C是E的子集，A{1,3},B{2,3,5}，C{2,4}，试求：1）A~B（2）AB~C3）~AC（4）AB（5）CC10设A，B，C是任意集合，证明：(AB)CA(BC)CA。11设A，B是集合，证明：（1）若AB，则AB（2）(AB)(A)(B)（3）若AB且(C)(CA)，则BA第19页共53页4）AA12设A，B，C是任意集合，证明：ABCABAAC13某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为优的有多少人？14用命题定律中的吸收律A∨(A∧B)A和A∧(A∨B)A，证明集合恒等式：A∩(A∪B)=AA∪(A∩B)=A15用命题定律中的德摩根律?(A∨B)?A∧?B，?(A∧B)?A∨?B，证明集合恒等式：~(A∪B)=~A∩~B~(A∩B)=~A∪~B16设A，B是任意集合，用已知的集合恒等式证明：A-B=A-(A∩B)。17设A={a,b,c}，以下是A的子集构成的集合：S={{a,b},{b,c}}Q={{a},{a,b},{a,c}}D={{a},{b,c}}G={{a,b,cE={{a},{b},{c}}F={{a},{a,c}}试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？18设A={1,2,3}，试确定A的所有划分。19设A={a,b}，B={1,2,3}，⑴试求A×B和B×A⑵验证|A×B|=|A||B|和|B×A|=|B||A|20设A={1,2}，B={a,b}，A={x,y}，求：A×B×C，A×(B×C)。21设A{a,b},B{c}，求下列各集合：1）A{0,1}B2）B2A3）(AB)2第20页共53页22设A{a,b}，求P(A)A。23证明：若AABB，则AB。24证明：若ABAC，且AO，则BC。第21页共53页第三章二元关系3.1基本概念用列举法表示下列AB上的二元关系S：(a)A{0,1,2}，B{0,2,4}，S{x,y|x,yAB}；(b)A{1,2,3,4,5}，B{1,2,3}，S{x,y|xy2xAyB}。2.设A{0,1,2,3,4}，试用列举法表达由下列谓词确定的A上的n元关系，如果是二元关系，画出其关系图。P(x)x1；(b)P(x)32；(c)P(x)23；(d)P(x,y)xy4；(e)P(x,y)k(xkyk2)；(f)P(x,y,z)x2yz。对下列关系R，求出关系矩阵MR：(a)A{1,2,3}，R{2,2,1,2,3,1}；(b)A{0,1,2,3}，R{x,y|x2y1}；(c)A{5,6,7,8}，B{1,2,3}，R{x,y|xAyB3xyy}；(d)A{0,1,2,3,4,5,6}，R{x,y|xyx是质数}。4.对下列每一个N上关系R给出一归纳定义，用你的定义证明xR。(a)R{a,b|ab}，x3,1；(b)R{a,b|a2b}，x6,3；(c)R{a,b,c|abc}，x1,1,2。第22页共53页5.设A{1,2,3,4}，R{1,2,2,4,3,3}，S{1,3,2,4,4,2}，(a)求出RS，RS，RS，R；(b)求出D(R)，R(R)，D(RS)，R(RS)。6.证明对任意集合A和A上的二元关系R和S，有D(RS)D(R)D(S)，R(RS)R(R)R(S)。设A是n个元素的集合，证明A上有2n个一元关系；2A上有2n个二元关系。8.设P1(x,y)xy0，P2(x,y)|xy|4，P3(x,y)xy10，P(1x,y)x整除y，试确定由这些谓词所定义的整数集合I上的二元关系是否具有以下特性，将结果用Y(yes)和N(no)填入下表。自反的反自反的对称的反对称的传递的P1P2P3P49.确定整数集合I上的相等关系、关系、关系、全域关系、空关系具有哪些特性？试将结果用类似于上题的表列出。10.设A{1,2,3,4}，A上的下列关系是否可传递？如果不是可传递的，举出反例证明它，然后找出一个具有最少序偶的关系R，使R包含原关系，并且是可传递的。(a)R{1,1}；(b)R{1,2,2,2}；(c)R{1,2,2,3,1,3,2,1}；第23页共53页(d)R{1,2,4,3,2,2,2,1,3,1}。(a)找出一个非空的最小集合，并在其上定义一个既不是自反的，也不是反自反的关系；找出一个非空的最小集合，并在其上定义一个既不是对称的，也不是反对称的关系；若(a)，(b)二题中允许用空集合，结果将怎样？考虑任意集合A上的二元关系的集合，如果某一集合运算施于关系后，所得关系仍具有相同的性质，那么说一个关系的性质在该运算下是保持的。例如自反性质在二元运算并之下是保持的，因为两个自反关系的并是自反的。然而，自反性质在集合的求补运算下是不保持的，因为非空集合上的一个自反关系的绝对补不是一个自反关系。按照在指定的集合运算下给出的性质是否保持，填充下表。对每一非(N)的回答，给出反例。并R1R2交R1R2相对补R1R2绝对补AAR1自反的反自反的对称的反对称的传递的在R2平面上画出下述关系的图，确定对每一关系成立哪些性质。(a){x,y|xy}；(b){x,y|x210y0}；(c){x,y||x|1|y|1}。3.2关系的合成设R1和R2是集合A{a,b,c,d}上的关系，这里R1{b,b,b,c,c,a}，R2{b,a,c,d,c,a,d,c}，求出R1R2，R2R1，R1R2R1，R12，R23。第24页共53页设R1和R2是集合A{0,1,2,3}上的关系，这里R1{i,j|ji1ji/2}，R2{i,j|ij2}，求出RR，RR，RRR，R2，R3。12211211216.证明：如果R是集合A上的空关系或全域关系，则R2R。17.设A{a,b,c,d,e,f,g}，R是如图3.3所示的A上的二元关系，试找出最小的整数m和n，使得mn，且RmRn。设R1和R2是集合A上的任意关系，证明或否定下列断言：(a)如果R1和R2是自反的，那么R1R2是自反的；(b)如果R1和R2是反自反的，那么R1R2是反自反的；(c)如果R和R2是对称的，那么RR是对称的；112(d)如果R1和R2是反对称的，那么R1R2是反对称的；(e)如果R1和R2是传递的，那么R1R2是反传递的。19.R1,R2,R3是集合A上的二元关系，试证明如果R1R2，那么R1R3R2R3；R3R1R3R2。20.设A{1,2,3,4,5}，R{1,2,3,4,2,2}，S{4,2,2,5,3,1}，试求出MRS。000121.设A{1,2,3,4}，MR0000N。110，求MRn，n000103.3关系上的闭包运算22.试证明如果关系R是自反的，那么R也是自反的；如果R是可传递的、反自反的、对称的或反对称的，则R亦然。第25页共53页如果关系R是反对称的，则在关系RR的关系矩阵中有多少个非零记入值。设A{a,b,c}，R和S是A上的二元关系，其关系矩阵是110110MR010，MS010，001011试求出MR,MS,MRS,MRR。设R是A{1,2,3,4}上的二元关系，其关系矩阵是1010MR0011101，01010试求出(a)Mr(R)；(b)Ms(R)；(c)MR2,MR3,MR4和Mt(R)。26.设R1和R2是集合A上的关系，且R1R2，证明下列各式(a)r(R1)r(R2)；s(R1)s(R2)；(c)t(R1)t(R2)。设R1和R2是集合A上的关系，证明下列各式(a)r(R1R2)r(R1)r(R2)；(b)s(R1R2)s(R1)s(R2)；(c)t(R1R2)t(R1)t(R2)；用反例证明t(R1R2)t(R1)t(R2)。28.找出n个元素的集合A和A上的二元关系R，使R,R2,,Rn,Rn1都是有区别的，这可能吗？如有可能，试举出例子。29.(a)用反例证明语句“如果R是传递的，那么s(R)也是传递的”为假；(b)举一实例证明即使R是一有限集，st(R)和ts(R)也可以不相等。第26页共53页设R是集合A上的关系，证明下列各式(R)R；(b)RRRRR；(R)R。3.4次序关系31.设集合A{a,b,c,d,e}上的关系R为{b,a,c,a,d,a,d,a,d,c,e,a,e,c}IA作出关系R的哈斯图和有向图；求出A的最小元素和最大元素，如果不存在，请指出；求出A的极小元素和极大元素；求出子集{b,c,d}，{c,d,e}和{a,b,c}的上界和下界，再指出这些子集的最小上界和最大下界，如果存在的话。对下述每一条件，构造有限集和无限集的例子各一个：非空偏序集合，其中某些子集没有最大元素；非空偏序集合，其中有一子集存在最大下界，但没有最小元素；非空偏序集合，其中有一子集存在上界，但没有最小下界。下述4个集合偏序集合、拟序集合、线序集合、良序集合？(N),；(N),；(c)({a}),；(),。对集合II分别构造一良序和一拟序。证明下列断言：如果R是拟序，那么R也是拟序；如果R是偏序，那么R也是偏序；第27页共53页(c)如果R是线序，那么R也是线序；(d)存在一集合S和S上的关系R，使S,R是良序集合，但S,R不是。36.设R是集合S上的关系，S是S的子集，定义S上的关系R如下：RR(SS)，确定下述每一断言是真还是假。(a)如果R在S上是传递的，那么R在S上是传递的；如果R是S的偏序，那么R是S上的偏序；如果R是S的拟序，那么R是S上的拟序；如果R是S的线序，那么R是S上的线序；如果R是S的良序，那么R是S上的良序。37.(a)证明R是一拟序当且仅当RR，且RR；(b)证明R是一偏序当且仅当RRE，且RR。证明下述断言：对任意线序集合，每一子集的极小元素是最小元素，每一极大元素是最大元素；一线序集合的每一非空有限子集有一最小和最大元素。39.设A,是非空有限线序集合，|A|2，R是AA上的关系，根据R的不同定义，指出AA,R是拟序集合、偏序集合、线序集合、良序集合，还是其他集合？对任意a1,b1,a2,b2AA，(a)a1,b1Ra2,b2a1a2b1b2；(b)a1,b1Ra2,b2a1a2a1a2b1b2；(c)a1,b1Ra2,b2a1a2；(d)a1,b1Ra2,b2a1a2。40.设{a,b,c}，规定abc，(a)求出,词典序中下列各串的直接后继者和直接前驱者，如果它们存在的话：(i)xabc；(ii)yabaa；(iii)zbb；第28页共53页对,标准序，重复上一题。3.5等价关系设R是A上的等价关系，将A的元素按R的等价类顺序排列，则等价关系的关系矩阵MR有何特征？证明集合A上的全域关系AA是等价关系。43.假设A是含n各元素的有限集合（nN），问有多少个元素在A上的最大等价关系中？A上的最大等价关系的秩是什么？有多少个元素在A上的最小等价关系中？A上的最小等价关系的秩是什么？设R和R是集合A上的等价关系，证明RR是集合A上的等价关系；(b)用例子证明RR不一定是集合A上的等价关系，要尽可能小地选取集合A。设R1和R2是非空集合A上的等价关系，确定下述各式，哪些是A上的等价关系，对不是的举例说明。AAR1；R1R2；R12；(d)r(R1R2)（R1R2的自反闭包）；R1R2。46.R是整数集合I上的等价关系，将R中的每一序偶x,y标在II笛卡儿平面上，所得图形有何特点？47.应用上题结论说明下述I集合上的二元关系是否是等价关系，对不是的说明为什么，并找出R诱导的等价关系。(a)R；(b)R{a,b|(a0b0)(a0b0)}；第29页共53页(c)R{a,b|(a0b0)(a0b0)}；(d)R{a,b|x(xI10xa10(x1)10xb10(x1))}；(e)R{a,b|a整除b}。48.R是集合A上的二元关系，对于所有的a,b,cA，如果aRb,bRc，则cRa，那么称R是循环的，试证明R是自反的和循环的当且仅当R是一等价关系。49.下述论证一位着每一对称的何传递的关系是一等价关系。设R是一对称的何传递关系，(i)因为R是对称的，如果x,yR，那么y,xR；(ii)因为R是传递的，如果y,xRx,yR，那么x,xR，所以R是自反的。这得出R是一等价关系。这个论证有什么错误？50.设A{a,b,c}，求出A的所有划分；设A的所有划分构成的集合是P，画出P,细分的哈斯图。51.设A{a,b,c,d}，1是A的划分，1{{a,b,c},{d}}。列出1诱导出的等价关系的序偶；(b)对划分2{{a},{b},{c},{d}}，2{{a,b,c,d}}，做同样工作；(c)画出偏序集合{1,2,3},细分的哈斯图。52.设1和2是非空集合A的划分，说明下列各式哪些是A的划分，哪些可能是A的划分，哪些不是A的划分？(a)(b)(c)12；12；12；(d)(1(21))2。53.设{A1,A2,,Am}是集合A的划分，若AiB，i1,2,,m，试证明第30页共53页{A1B,A2B,,AmB}是AB的划分。54.设A是n个元素的有限集，假设1,2,,k是A上划分序列，使i1真细分i，找出最大可能的序列长度。设AI，定义A上的R1,R2,R3如下：aRbab(mod3)，aRbab(mod5)，aRbab(mod6)，123(a)对偏序集合{A/R1,A/R2,A/R3},细分画出哈斯图；描述一下各式所诱导的等价关系，它们的秩是什么？A/R1A/R2，A/R1A/R3，A/R1A/R2，A/R1A/R3。设Rj表示I上模j等价，设Rk表示I上模k等价，证明I/Rk细分I/Rj当且仅当k是j的整数倍；(b)描述划分I/RkI/Rj；描述划分I/RkI/Rj。57.证明如果1细分2，那么121和122。58.设P表示非空集合A的所有划分的集合，考虑偏序集合P,细分，设1和2是P的成员，证明12是集合{1,2}的最大下界；(b)证明12是集合{1,2}的最小上界。59.设R是集合A上的二元关系，如果R是自反的和对称的，则称R是相容关系。设A{316,347,204,678}，R{x,y|xAyAx和y有相同的数字}，R是相容关系吗？画出R的关系图。所有等价关系都是相容关系吗？相容关系的关系图和等价关系的关系图有何不同？第31页共53页补充习题：1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：R={,,,,,,}写出R的关系矩阵。3设A={1,2,3,4}，R是A的二元关系，定义为：R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>}写出A上二元关系R的关系矩阵。4设X={1,2,3,4}，X上的二元关系H和S定义如下：H={|xy是整数}2S={|xy是正整数}3试求H∪S，H∩S，~H，S-H。5X={1,2,3,4,5}，X上的二元关系R和S定义如下：R={<1,2>,<3,4>,<2,2}S={<4,2>,<2,5>,<3,1>,<1,3>}试求R°S，S°R，R°(S°R)，(R°S)°R，R°R，S°S，R°R°R。6A={1,2,3,4}，A上的二元关系R定义如下：R={<1,2>,<2,1>,<2,3>,<3,4>}求二元关系R的各次幂。7A={1,2,3,4,5}，A上的二元关系R和S定义如下：R={<1,2>,<2,2>,<3,4>}S={<1,3>,<2,5>,<3,1>,<4,2>}试求MR°S和MR°MS，它们是否相等?8设X={1,2,3,4}，Y={a,b,c}，X到Y二元关系R={<1,a>,<2,b>,<4,c>}，⑴试求RC，写出MR和MC，验证MC=MRTRR⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。9设R是实数集合，第32页共53页={|xR∧yR∧x＞y}是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。10设A={1,2,3}，定义A上的二元关系如下：R={<1,1>,<2,2>,<3,3>,<1,3>}S={<1,3>}T={<1,1>}试说明R，S，T是否是A上的自反关系或反自反关系。11设A={1,3,5,7}，定义A上的二元关系如下：R={|(a－b)/2是整数}试证明R在A上是自反的和对称的。12设A={1,2,3}，定义A上的二元关系如下：R={<1,1>,<2,2>}S={<1,1>,<1,2>,<2,1>}T={<1,2>,<1,3>}U={<1,3>,<1,2>,<2,1>}试说明R，S，T，U是否是A上的对称关系和反对称关系。13设R是实数集合，S={|xR∧yR∧x=y}是实数集合上的等于关系。证明实数集合上的等于关系是传递的。设R，S是X上的二元关系，证明⑴若R，S是自反的，则R∪S和R∩S也是自反的。⑵若R，S是对称的，则R∪S和R∩S也是对称的。⑶若R，S是传递的，则R∩S也是传递的。15设A={1,2,3}，定义A上的二元关系R为：R={<1,2>,<2,3>,<3,1>}试求：r(R)，s(R)，t(R)。16设A={1,2,3}，定义A上的二元关系R为：R={<1,2>,<2,3>,<3,1>}试用关系矩阵求传递闭包t(R)。17设集合A{a,b,c,d}，A上的二元关系R{(a,a),(a,c),(b,d)}，求R2。第33页共53页18设A={1,2,3,4,5}，R是A上的二元关系，R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>}证明R是A上的等价关系。19设R={|xI∧yI∧x≡ymodk}是整数集合I上的二元关系。证明R是等价关系。20设X={1,2,3,4}，X的划分S={{1}，{2,3}，{4}}，试写出S导出的等价关系R。21设X={1,2,3}，写出集合X上的所有等价关系。22R是集合M{1,2,3,4,5,6}上的关系，其中：1,1,1,3,1,6,2,2,2,5,3,1,3,3,3,6,4,4,5,2,5,5,6,1,6,3,6,6，1）验证R是等价关系；2）给出R的关系图．23设A={316,347,204,678,770}，A上的二元关系R定义为：R={|xA∧yA∧x和y有相同数码}，证明R是A上的相容关系。写出关系矩阵和关系图。用关系矩阵和关系图验证R是A上的相容关系。24设X={1,2,3,4}，S1={{1,2,3},{3,4}}，S2={{1,2},{2,3},{1,3},{3,4}}是X的两个覆盖。试写出S1和S2导出的相容关系R1和R2。25设A是集合，P(A)是A的幂集合，P(A)上的包含关系定义如下：={|xP(A)∧yP(A)∧xy}试证明是P(A)上偏序关系。26设A={2,5,6,10,15,30}，A上的整除关系R定义如下：R={|xA∧yA∧x整除y}验证R是A上的偏序关系，分析哪些元素盖住了另一些元素，哪些元素没有盖住了另一些元素。27设A={a,b,c,d,e,f,g,h}，A上的二元关系R={,,,,,,,,}∪IA验证R是A上的偏序关系。写出盖住关系COVA，画出哈斯图。找出集合A的极大元和极小元。28设A={2,3,6,12,24,36}，其上的整除关系R={|aA∧bA∧a能整除b}是A上的偏序关系，试求盖住关系COVA，画出哈斯图，确定下列集合的上界和下界。第34页共53页B1={2,3,6}B2={12,24,36}29设N为自然数集合，N上的大于等于关系定义为R≥={|xN∧yN∧x≥y}证明R≥是全序关系。30设P={,{a},{a,b},{a,b,c}}，P上的包含关系R={|xP∧yP∧xy}验证R是全序关系。第35页共53页第三章二元关系3.1基本概念用列举法表示下列AB上的二元关系S：(a)A{0,1,2}，B{0,2,4}，S{x,y|x,yAB}；(b)A{1,2,3,4,5}，B{1,2,3}，S{x,y|xy2xAyB}。2.设A{0