《离散数学》习题集

第1页共53页《离散数学》习题集目录第一章数理逻辑 2第二章集合 14第三章二元关系 22第三章二元关系 36第五章无限集合 50第一章数理逻辑1.1命题1.设是命题“天下雪”；是命题“我去镇上”；是命题“我有时间”。(a)用逻辑符号写出以下命题：(i)如天不下雨和我有时间，那么我去镇上；(ii)我去镇上，仅当我有时间；(iii)天不下雪；(iv)天正在下雪，我也没去镇上。(b)对下述命题用中文写出语句：(i)；(ii)；(iii)；(iv)。2.否定下列命题：(a)上海处处清洁；(b)每一个自然数都是偶数。3.说出下述每一命题的逆命题和逆反命题：(a)如果天下雨，我将不去；(b)仅当你去我将逗留；(c)如果是大于2的正整数，则方程无正整数解（费尔马最后定理）；(d)如果我不获得更多帮助，我不能完成这个任务。4.给和指派真值，给和真值，求下列命题的真值：(a)；(b)；(c)。5.构成下列公式的真值表：(a)；(b)。6.证明下列公式的真值与它们的变元值无关：(a)；(b)。7.对和的所有值，证明与有同样的真值。证明总是真的。8.设是具有两个运算对象的逻辑运算符，如果与逻辑等价，那么运算符是可以结合的，(a)确定逻辑运算符哪些是可结合的；(b)用真值表证明你的断言。9.指出一下各式哪些不是命题公式，如果是命题公式，请说明理由：(a)；(b)。1.2重言式10．指出下列那些命题是重言式、偶然式和矛盾式：(a)；(b)；(c)；(d)；(e)；(f)；(g)；(h)；(i)。11.对下述每一表达式，找出仅用和的等价表达式，并尽可能简单：(a)；(b)；(c)。对下述每一表达式，找出仅用和的等价表达式，并尽可能简单：(a)；(b)；(c)。12.用化简联结词的左边成右边的方法，证明以下是重言式：(a)；(b)。13.证明下列等价关系：(a)；(b)；(c)；(d)。14.求出下列公式的最简等价式：(a)；(b)；(c)。15.证明下列蕴含式：(a)；(b)；(c)；(d)；(e)。16.(a)与非运算符（又叫悉菲（Sheffer）记号）用下述真值表定义，可以看出，试证明（i）；（ii）；；（iii）。(b)或非运算符（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与逻辑等价。对下述每一式，找出仅用表示的等价式。（i）；（ii）；（iii）。00011011111000011011100017.(a)用真值表证明和互相可分配；(b)、和对自己可分配吗？18.求出下列各式的代入实例：(a)：用代，用代；(b)；用代，用代。1.3范式19.对任一指派，时，为什么和不能同时为真？为什么和不能同时为假？20.求下列各式的主合取范式：(a)；(b)；(c)。21.求下列各式的主析取范式和主合取范式：(a)；(b)；(c)；(d)。1.4联结词的扩充与归约22.仅用表达；再用表达它。23.仅用表达；仅用表达。24.试证明等价式：和。25.写出一个仅含且等价于的公式来。26.证明,,都不是全功能联结词集合。27.证明，是全功能联结词集合。28.证明联结词可交换，可结合，且在上可分配。29.证明联结词可交换，可结合，且在上可分配。1.5推理规则和证明方法30.用真值表证明下列推理规则的重言式形式都是重言式：(a)拒取式；(b)析取三段论；(c)构造性二难定理；(d)破坏性二难推理。31.是前提，是结论，用真值表判断下列结论是否有效：(a)，，；(b)，，，；(c)，，；(d)，，。32.给出一个指派，证明以下结论是非有效的：(a)前提是，结论是。(b)前提是，结论是。33.对下列每一个前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。(a)如果我跑，我喘气。我没有喘气。(b)天气是晴朗或阴暗，天气晴朗使我愉快而天气阴暗使我烦恼。(c)如果考试及格了，那么我很高兴。如果我很高兴，那么我的饭量增加。我的饭量减少。34.对下述每一论证构造一个证明，给出所有必须增加的断言，指出用于每一步的推理规则。(a)从语句“今天下雨或明天后天都下雨”和“明天不下雨或后天不下雨而今天下雨”可推出“今天下雨”。(b)如果李敏来通信工程学院，若王军不生病，则王军一定去看望李敏。如果李敏出差到南京，那么李敏一定来通信工程学院。王军没有生病。所以，如果李敏出差到南京，王军一定去看望李敏。35.确定下列论证哪些是有效的论证，为有效论证构造证明，对非有效论证，表明为什么结论不能从前提得出。(a)；(b)；(c)。36.仅用证明。37.证明下列论证的有效性：(a)，，推得；(b)，，推得；(c)，，推得。38.证明下列结论“(a)，，；(b)；(c)；(d)，，。39.试说明“从假的前提出发，能证明任何命题”。40.证明下列各式的有效性：(a)，，，推得；(b)，，，推得；(c)，，推得。1.6谓词和量词41.下列表达式哪些是命题？(a)；(b)。42.设谓词表示“”，谓词表示“”，论述域是整数，用以上谓词表示下述断言：(a)对每一和，有一，使；(b)对每一和，有一，使；(c)从任何整数减去0，其结果是原整数；(d)对所有，对所有，。43.论述域是整数，对下列每一个断言找出谓词使蕴含式是假。(a)；(b)。44.指定一个论述域使下列命题是真。要使指定得论述域是尽可能大的整数的一个子集。(a)；(b)；(c)；(d)。45.设论述域是自然数，表示“”，表示“”，用逻辑符表示下列断言：对每一和，有一，使；(b)没有小于0；(c)4加3得7。46.将苏格拉底论证符号化。47.设表示，表示，表示，论述域是整数，将下列断言译成逻辑符。（提示：要注意数学上习惯写法和逻辑符表示的差异，例如加法交换律在数学中写成：，翻译成逻辑符时，要按照实际意义翻译成：），即要自动加上全称量词，使整个式子成为命题。）(a)如果，那么或；(b)如果，那么并且；(c)是并且的必要条件；(d)和不能同时出现；(e)存在一，对每一和，使。48.将下列断言译为逻辑符号，选用的谓词应使逻辑符号中至少含有一个量词：(a)有一个且仅有一个偶数是质数；(b)没有一个奇数是偶数；(c)某些卡车慢于所有火车，但是至少有一辆火车，快于每一卡车；(d)所有步行的，骑马的或乘车的人，凡是口渴的都喝泉水。49.设表示“是偶数”，表示“是奇数”，表示“是质数”，表示“是负数”，表示“是整数”和一些中缀表示的谓词诸如等，将下列各句翻译成逻辑符。(a)一个整数是奇数，如果它的平方是奇数；(b)有两个奇数它们的和是偶数；(c)不存在一个整数使是负数；(d)任何两个质数之和是质数；(e)对任何整数，如果它的平方是负的，那么1＝1。50.如果论述域是，试消去下列公式中的量词：(a)；(b)。51.试说明下列公式是合式公式：(a)；(b)。1.7谓词演算的永真公式52.证明永真公式,,,,。53.下列断言如果是真的证明它们，如果是假的，找出和的解释以证明公式是假。(a)；(b)；(c)；(d)。54.设论述域是，试证明下列关系式：(a)；(b)。55.对一个仅含元素0和1的论述域，试证明：，并证明蕴含式之逆不是有效的。1.8谓词演算的推理规则56.对下列每一前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。(a)所有三角形函数都是周期函数，而所有周期函数都是连续函数；(b)所有偶数都被2除尽。整数4是偶数，但3不是；(c)对汽车工业的好事就是对国家的好事，对国家的好事就是对你的好事。你去买一辆高价卡车是对汽车工业的好事。57.下列推导步骤为什么是错误的？(a)(i)P(ii)T，1，US(b)(i)P(ii)T，1，US(c)(i)P(ii)T，1，US58.证明下列各断言：(a)推得；(b)，推得。59.考虑蕴含式(a)证明它不是有效的。(b)下面是一个论证，企图证明上式有效，试找出不正确的地方。60.判断下列结论能否有效的从给定的前提得出：(a)；(b)。补充习题：1判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100⑻我正在说谎。2将下列命题符号化：⑴2008年将在北京举办奥运会并且中国是世界四大文明古国之一。⑵如果小王努力学习，那么他的学习成绩就优秀。⑶张华是三好学生当且仅当德、智、体全优秀。⑷他或者骑自行车去学校，或者乘公共汽车去学校。3构造命题公式¬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)。7用等价演算法判断下列公式的类型。⑴q∨¬((¬p∨q)∧p)⑵(p∨¬p)→((q∨¬q)∧r)⑶(p→q)∧¬p8利用代入规则证明((p∨q)∧r)∨¬((p∨q)∧r)为重言式。9求命题公式(p∨q)↔p的合取范式和析取范式。10用真值表法，求(p→q)→r的主析取范式。11用等价演算法求(p∧q)∨(¬p∧r)∨(q∧r)的主析取范式。12用真值表法求(p→q)→r的主合取范式。13用等价演算法求(p→q)→r的主合取范式。14证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。15推证¬p∧(p∨q)q。16分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。17用直接推理法证明(p→q)∧(q→r)∧pr。18用CP规则证明：p→(q→r)，¬t∨p，qt→r。19用间接法（反证法）证明：(p∧q)→r，¬r∨s，¬s，p¬q。20将下列命题符号化，并讨论它们的真值。⑴2与3都是偶数。⑵如果5大于3，则2大于6。21个体域是人类集合，对下列命题符号化。⑴凡人要死。⑵有的人是研究生。22对下列命题符号化，并在①，②，③三个个体域中考察命题的真值。命题：⑴所有数小于5。⑵至少有一个数小于5。个体域：①{-1，0，1，2，4}②{3，-2，7，8}③{15，20，24}23对下列命题在①，②两个个体域中符号化。命题：⑴所有老虎是要吃人。⑵存在一个老虎要吃人。个体域：①所有老虎组成的集合。②全总个体域。24用谓词公式表达下列自然语言中的命题：⑴并非每个实数都是有理数。⑵没有不犯错误的人。⑶并不是所有的兔子都比所有的乌龟跑得快。25说明下列各式量词的辖域，找出约束变元和自由变元。⑴(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进行代入。28证明：⑴(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))化为与其等价的前束合取范式。31证明：苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。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)。35设个体域为全总个体域。证明推理：学术会的成员都是工人并且是专家。有些成员是青年人。所以有的成员是青年专家。第二章集合2.1集合论的基本概念1.用列举法表示下列集合：(a)小于20的质数集合；(b)构成evening的字母集合；(c)。2.列出下列集合的成员：(a)；(b)。3.证明：若是任意客体，则当且仅当和。4.列举下列集合的全部子集：(a)；(b)；(c)；(d)。5.设是集合，证明或否定以下断言：(a)；(b)；(c)。6.确定下列各命题的真和假：(a)；(b)；(c)；(d)。2.2集合上的运算7.给定自然数集合的下列子集：求出下列集合(a)；(b)；(c)。8.设和是实数，定义运算是（的次幂）(a)证明运算既非可交换的也非可结合的。(b)设代表乘法运算，确定下列分配律哪些是成立的：(i)；(ii)。9.设是任意集合，把表示成不相交集合之并。10.(a)证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合和，使；(b)可能吗？刻画此式出现的全部条件；(c)“相对补”是一个可结合的运算吗？证明你的断言。11.设是论述域的任意子集，证明下列各式：(a)；(b)；(c)。12.证明，，三者是等价的。13.在下列命题中找出和：(a)；(b)；(c)。14.设是一非空的某论述域的子集的搜集，是的子集，证明下列分配律的推广：(a)；(b)。15.指出下列集合的幂集合：(a)；(b)。16.证明下列各式：(a)；(b)；(c)。2.1归纳法和自然数17.对下列集合给出归纳定义：(a)十进制无符号整数集合，定义集合将包含6，235，0045等等；(b)十进制的以小数部分为结束的实数集合，定义的集合包含5.3，453.，01.2700，0.480；(c)二进制形式的不以0开头的正偶数和0组成的集合，定义的集合包含等；(d)把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串。例如[],[[]],[][],[[[]][]]等都是成形括号串（例中用[]代（）是为了明晰），试定义成形括号串集合。18.用代替的定义中的，但仍用这一定义，可否生成自然数集合？有何不同？19.证明成形括号串的左右括号个数相等。20.我们有3分和5分两种不同票值的邮票，试证明用这两种邮票就足以组成8分或者更多的任意邮资。21.用归纳法证明：对一切，。22.对所有，证明下列每一关系式：(a)；(b)；(c)；(d)；(e)。23.如果每根直线连接多边形的两个点，且位于多边形上，那么这个多边形叫凸的，证明对一切，边的凸多边形内角之和等于。（提示：多边形能用连结两个非邻接的顶角划分为两部分。）24.找出自然域上的两个谓词和一证明归纳证明的基础步骤和归纳步骤是独立的，也就是没有一个逻辑地蕴含另一个。特别，要找出一谓词使是真而是假，和一谓词，使是假，而是真。25.我们意欲证明，对一切和一切，如果是个人的集合，那么在中的所有人都有同样的身材。下面“所有人都有同样的身材”的证明错在那里？(a)（基础）设是一空集合，那么对所有的和，如果和，那么和有同样的身材。(b)（归纳）假定对所有包含个人的集合断言是真。我们证明对包含个人的集合也真。任何由个人组成的集合包含两个个人组成的不同的但交搭的子集合。用和表示这两个子集合。那么根据归纳前提，在中的所有人有相同的身材，在中的所有人有相同的身材，因为和是交搭的，所以，所有在中的人都有相同的身材。26.设是集合的非空搜集，对作归纳证明下述推广的德摩根定律：(a)；(b)。27.证明对所有大于1的整数都能写成若干个质数之积。28.如果，那么二元运算称为可结合的。从它可推出更强的结果，即在任何仅含运算的表达式中，括号的位置不影响结果，就是，仅仅出现于表达式中的运算对象和次序是重要的。为了证明这个“推广的结合律”，我们定义“表达式集合”如下：(a)（基础）单个运算对象是表达式；(b)（归纳）设和是表达式，那么是表达式；(c)（极小性）只有有限次应用（）和（）构成的式子才是表达式。设是一个表达式，它有个运算对象，且此次序出现于表达式中，那么证明这个推广的结合律。（提示：用数学归纳法第二原理。）2.5集合的笛卡儿乘积29.如果和，试确定下列集合：(a)；(b)；(c)。30.设，构成集合。31.设和是任意集合，试证明：。32.试证明：。33.指出下列各式是否成立：(a)；(b)(c)；(d)；(e)。补充习题：1令，，，，。试指出哪些集合是相等的？哪些集合是不相等的？2设，，判断下列各命题真或假：（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）3试指出下列命题哪些为真？哪些为假？（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）4设A={a,b,c}，A是空集，试求P(A)，P(P(A))。5求下列集合的幂集：（1）；（2）；（3）；（4）；（5）；（6）6设（1）若，是否必须？（2）若，是否必须？（3）若，是否必须？7设A,B是任意的集合，求证:A-B=A∩(~B)。8设A,B是任意的集合，求证:AB=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。9设集合，，和是的子集，,，，试求：（1）（2）（3）（4）（5）10设，，是任意集合，证明：。11设，是集合，证明：（1）若，则（2）（3）若且，则（4）12设，，是任意集合，证明：13某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为优的有多少人？14用命题定律中的吸收律A∨(A∧B)A和A∧(A∨B)A，证明集合恒等式：⑴A∩(A∪B)=A⑵A∪(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,c}}E={{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设，求下列各集合：（1）（2）（3）22设，求。23证明：若，则。24证明：若，且，则。第三章二元关系3.1基本概念1.用列举法表示下列上的二元关系：(a)，，；(b)，，。2.设，试用列举法表达由下列谓词确定的上的元关系，如果是二元关系，画出其关系图。(a)；(b)；(c)；(d)；(e)；(f)。3.对下列关系，求出关系矩阵：(a)，；(b)，；(c)，，；(d)，。4.对下列每一个上关系给出一归纳定义，用你的定义证明。(a)，；(b)，；(c)，。5.设，，，(a)求出，，，；(b)求出，，，。6.证明对任意集合和上的二元关系和，有，。7.设是个元素的集合，证明(a)上有个一元关系；(b)上有个二元关系。8.设，，，，试确定由这些谓词所定义的整数集合上的二元关系是否具有以下特性，将结果用Y(yes)和N(no)填入下表。自反的反自反的对称的反对称的传递的9.确定整数集合上的相等关系、关系、关系、全域关系、空关系具有哪些特性？试将结果用类似于上题的表列出。10.设，上的下列关系是否可传递？如果不是可传递的，举出反例证明它，然后找出一个具有最少序偶的关系，使包含原关系，并且是可传递的。(a)；(b)；(c)；(d)。11.(a)找出一个非空的最小集合，并在其上定义一个既不是自反的，也不是反自反的关系；(b)找出一个非空的最小集合，并在其上定义一个既不是对称的，也不是反对称的关系；(c)若(a)，(b)二题中允许用空集合，结果将怎样？12.考虑任意集合上的二元关系的集合，如果某一集合运算施于关系后，所得关系仍具有相同的性质，那么说一个关系的性质在该运算下是保持的。例如自反性质在二元运算并之下是保持的，因为两个自反关系的并是自反的。然而，自反性质在集合的求补运算下是不保持的，因为非空集合上的一个自反关系的绝对补不是一个自反关系。按照在指定的集合运算下给出的性质是否保持，填充下表。对每一非(N)的回答，给出反例。并交相对补绝对补自反的反自反的对称的反对称的传递的13.在平面上画出下述关系的图，确定对每一关系成立哪些性质。(a)；(b)；(c)。3.2关系的合成14.设和是集合上的关系，这里，，求出，，，，。15.设和是集合上的关系，这里，，求出，，，，。16.证明：如果是集合上的空关系或全域关系，则。17.设，是如图3.3所示的上的二元关系，试找出最小的整数和，使得，且。18.设和是集合上的任意关系，证明或否定下列断言：(a)如果和是自反的，那么是自反的；(b)如果和是反自反的，那么是反自反的；(c)如果和是对称的，那么是对称的；(d)如果和是反对称的，那么是反对称的；(e)如果和是传递的，那么是反传递的。19.是集合上的二元关系，试证明如果，那么(a)；(b)。20.设，，，试求出。21.设，，求，。3.3关系上的闭包运算22.试证明如果关系是自反的，那么也是自反的；如果是可传递的、反自反的、对称的或反对称的，则亦然。23.如果关系是反对称的，则在关系的关系矩阵中有多少个非零记入值。24.设，和是上的二元关系，其关系矩阵是，，试求出。25.设是上的二元关系，其关系矩阵是，试求出(a)；(b)；(c)和。26.设和是集合上的关系，且，证明下列各式(a)；(b)；(c)。27.设和是集合上的关系，证明下列各式(a)；(b)；(c)；(d)用反例证明。28.找出个元素的集合和上的二元关系，使都是有区别的，这可能吗？如有可能，试举出例子。29.(a)用反例证明语句“如果是传递的，那么也是传递的”为假；(b)举一实例证明即使是一有限集，和也可以不相等。30.设是集合上的关系，证明下列各式(a)；(b)；(c)。3.4次序关系31.设集合上的关系为(a)作出关系的哈斯图和有向图；(b)求出的最小元素和最大元素，如果不存在，请指出；(c)求出的极小元素和极大元素；(d)求出子集，和的上界和下界，再指出这些子集的最小上界和最大下界，如果存在的话。32.对下述每一条件，构造有限集和无限集的例子各一个：(a)非空偏序集合，其中某些子集没有最大元素；(b)非空偏序集合，其中有一子集存在最大下界，但没有最小元素；(c)非空偏序集合，其中有一子集存在上界，但没有最小下界。33.下述个集合偏序集合、拟序集合、线序集合、良序集合？(a)；(b)；(c)；(d)。34.对集合分别构造一良序和一拟序。35.证明下列断言：(a)如果是拟序，那么也是拟序；(b)如果是偏序，那么也是偏序；(c)如果是线序，那么也是线序；(d)存在一集合和上的关系，使是良序集合，但不是。36.设是集合上的关系，是的子集，定义上的关系如下：，确定下述每一断言是真还是假。(a)如果在上是传递的，那么在上是传递的；(b)如果是的偏序，那么是上的偏序；(c)如果是的拟序，那么是上的拟序；(d)如果是的线序，那么是上的线序；(e)如果是的良序，那么是上的良序。37.(a)证明是一拟序当且仅当，且；(b)证明是一偏序当且仅当，且。38.证明下述断言：(a)对任意线序集合，每一子集的极小元素是最小元素，每一极大元素是最大元素；(b)一线序集合的每一非空有限子集有一最小和最大元素。39.设是非空有限线序集合，，是上的关系，根据的不同定义，指出是拟序集合、偏序集合、线序集合、良序集合，还是其他集合？对任意，(a)；(b)；(c)；(d)。40.设，规定，(a)求出中下列各串的直接后继者和直接前驱者，如果它们存在的话：(i)；(ii)；(iii)；(b)对，重复上一题。3.5等价关系41.设是上的等价关系，将的元素按的等价类顺序排列，则等价关系的关系矩阵有何特征？42.证明集合上的全域关系是等价关系。43.假设是含各元素的有限集合（），问(a)有多少个元素在上的最大等价关系中？(b)上的最大等价关系的秩是什么？(c)有多少个元素在上的最小等价关系中？(d)上的最小等价关系的秩是什么？44.设和是集合上的等价关系，(a)证明是集合上的等价关系；(b)用例子证明不一定是集合上的等价关系，要尽可能小地选取集合。45.设和是非空集合上的等价关系，确定下述各式，哪些是上的等价关系，对不是的举例说明。(a)；(b)；(c)；(d)（的自反闭包）；(e)。46.是整数集合上的等价关系，将中的每一序偶标在笛卡儿平面上，所得图形有何特点？47.应用上题结论说明下述集合上的二元关系是否是等价关系，对不是的说明为什么，并找出诱导的等价关系。(a)；(b)；(c)；(d)；(e)。48.是集合上的二元关系，对于所有的，如果，则，那么称是循环的，试证明是自反的和循环的当且仅当是一等价关系。49.下述论证一位着每一对称的何传递的关系是一等价关系。设是一对称的何传递关系，(i)因为是对称的，如果，那么；(ii)因为是传递的，如果，那么，所以是自反的。这得出是一等价关系。这个论证有什么错误？50.设，求出的所有划分；设的所有划分构成的集合是，画出的哈斯图。51.设，是的划分，。(a)列出诱导出的等价关系的序偶；(b)对划分，，做同样工作；(c)画出偏序集合的哈斯图。52.设和是非空集合的划分，说明下列各式哪些是的划分，哪些可能是的划分，哪些不是的划分？(a)；(b)；(c)；(d)。53.设是集合的划分，若，，试证明是的划分。54.设是个元素的有限集，假设是上划分序列，使真细分，找出最大可能的序列长度。55.设，定义上的如下：，，，(a)对偏序集合画出哈斯图；(b)描述一下各式所诱导的等价关系，它们的秩是什么？，，，。56.设表示上模等价，设表示上模等价，(a)证明细分当且仅当是的整数倍；(b)描述划分；(c)描述划分。57.证明如果细分，那么和。58.设表示非空集合的所有划分的集合，考虑偏序集合，设和是的成员，(a)证明是集合的最大下界；(b)证明是集合的最小上界。59.设是集合上的二元关系，如果是自反的和对称的，则称是相容关系。设，，(a)是相容关系吗？(b)画出的关系图。(c)所有等价关系都是相容关系吗？(d)相容关系的关系图和等价关系的关系图有何不同？补充习题：1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。2设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：R={<a1,b1>,<a1,b3>,<a2,b2>,<a2,b3>,<a3,b1>,<a4,b1>,<a4,b2>}写出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={<x,y>|是整数}S={<x,y>|是正整数}试求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上的二元关系RR={<1,2>,<2,1>,<2,3>,<3,4>}求二元关系R的各次幂。7A={1,2,3,4,5}，A上的二元关系R和SR={<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和，验证=MRT⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。9设R是实数集合，＞={<x,y>|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>|(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={<x,y>|xR∧yR∧x=y}是实数集合上的等于关系。证明实数集合上的等于关系是传递的。14设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设集合，上的二元关系，求。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={<x,y>|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上的所有等价关系。22是集合上的关系，其中：，（1）验证是等价关系；（2）给出的关系图．23设A={316,347,204,678,770}，A上的二元关系R定义为：R={<x,y>|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)上的包含关系定义如下：={<x,y>|xP(A)∧yP(A)∧xy}试证明是P(A)上偏序关系。26设A={2,5,6,10,15,30}，A上的整除关系R定义如下：R={<x,y>|xA∧yA∧x整除y}验证R是A上的偏序关系，分析哪些元素盖住了另一些元素，哪些元素没有盖住了另一些元素。27设A={a,b,c,d,e,f,g,h}，A上的二元关系R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA验证R是A上的偏序关系。写出盖住关系COVA，画出哈斯图。找出集合A的极大元和极小元。28设A={2,3,6,12,24,36}，其上的整除关系R={<a,b>|aA∧bA∧a能整除b}是A上的偏序关系，试求盖住关系COVA，画出哈斯图，确定下列集合的上界和下界。⑴B1={2,3,6}⑵B2={12,24,36}29设N为自然数集合，N上的大于等于关系定义为R≥={<x,y>|xN∧yN∧x≥y}证明R≥是全序关系。30设P={,{a},{a,b},{a,b,c}}，P上的包含关系={<x,y>|xP∧yP∧xy}验证是全序关系。第三章二元关系3.1基本概念1.用列举法表示下列上的二元关系：(a)，，；(b)，，。2.设，试用列举法表达由下列谓词确定的上的元关系，如果是二元关系，画出其关系图。(a)；(b)；(c)；(d)；(e)；(f)。3.对下列关系，求出关系矩阵：(a)，；(b)，；(c)，，；(d)，。4.对下列每一个上关系给出一归纳定义，用你的定义证明。(a)，；(b)，；(c)，。5.设，，，(a)求出，，，；(b)求出，，，。6.证明对任意集合和上的二元关系和，有，。7.设是个元素的集合，证明(a)上有个一元关系；(b)上有个二元关系。8.设，，，，试确定由这些谓词所定义的整数集合上的二元关系是否具有以下特性，将结果用Y(yes)和N(no)填入下表。自反的反自反的对称的反对称的传递的9.确定整数集合上的相等关系、关系、关系、全域关系、空关系具有哪些特性？试将结果用类似于上题的表列出。10.设，上的下列关系是否可传递？如果不是可传递的，举出反例证明它，然后找出一个具有最少序偶的关系，使包含原关系，并且是可传递的。(a)；(b)；(c)；(d)。11.(a)找出一个非空的最小集合，并在其上定义一个既不是自反的，也不是反自反的关系；(b)找出一个非空的最小集合，并在其上定义一个既不是对称的，也不是反对称的关系；(c)若(a)，(b)二题中允许用空集合，结果将怎样？12.考虑任意集合上的二元关系的集合，如果某一集合运算施于关系后，所得关系仍具有相同的性质，那么说一个关系的性质在该运算下是保持的。例如自反性质在二元运算并之下是保持的，因为两个自反关系的并是自反的。然而，自反性质在集合的求补运算下是不保持的，因为非空集合上的一个自反关系的绝对补不是一个自反关系。按照在指定的集合运算下给出的性质是否保持，填充下表。对每一非(N)的回答，给出反例。并交相对补绝对补自反的反自反的对称的反对称的传递的13.在平面上画出下述关系的图，确定对每一关系成立哪些性质。(a)；(b)；(c)。3.2关系的合成14.设和是集合上的关系，这里，，求出，，，，。15.设和是集合上的关系，这里，，求出，，，，。16.证明：如果是集合上的空关系或全域关系，则。17.设，是如图3.3所示的上的二元关系，试找出最小的整数和，使得，且。18.设和是集合上的任意关系，证明或否定下列断言：(a)如果和是自反的，那么是自反的；(b)如果和是反自反的，那么是反自反的；(c)如果和是对称的，那么是对称的；(d)如果和是反对称的，那么是反对称的；(e)如果和是传递的，那么是反传递的。19.是集合上的二元关系，试证明如果，那么(a)；(b)。20.设，，，试求出。21.设，，求，。3.3关系上的闭包运算22.试证明如果关系是自反的，那么也是自反的；如果是可传递的、反自反的、对称的或反对称的，则亦然。23.如果关系是反对称的，则在关系的关系矩阵中有多少个非零记入值。24.设，和是上的二元关系，其关系矩阵是，，试求出。25.设是上的二元关系，其关系矩阵是，试求出(a)；(b)；(c)和。26.设和是集合上的关系，且，证明下列各式(a)；(b)；(c)。27.设和是集合上的关系，证明下列各式(a)；(b)；(c)；(d)用反例证明。28.找出个元素的集合和上的二元关系，使都是有区别的，这可能吗？如有可能，试举出例子。29.(a)用反例证明语句“如果是传递的，那么也是传递的”为假；(b)举一实例证明即使是一有限集，和也可以不相等。30.设是集合上的关系，证明下列各式(a)；(b)；(c)。3.4次序关系31.设集合上的关系为(a)作出关系的哈斯图和有向图；(b)求出的最小元素和最大元素，如果不存在，请指出；(c)求出的极小元素和极大元素；(d)求出子集，和的上界和下界，再指出这些子集的最小上界和最大下界，如果存在的话。32.对下述每一条件，构造有限集和无限集的例子各一个：(a)非空偏序集合，其中某些子集没有最大元素；(b)非空偏序集合，其中有一子集存在最大下界，但没有最小元素；(c)非空偏序集合，其中有一子集存在上界，但没有最小下界。33.下述个集合偏序集合、拟序集合、线序集合、良序集合？(a)；(b)；(c)；(d)。34.对集合分别构造一良序和一拟序。35.证明下列断言：(a)如果是拟序，那么也是拟序；(b)如果是偏序，那么也是偏序；(c)如果是线序，那么也是线序；(d)存在一集合和上的关系，使是良序集合，但不是。36.设是集合上的关系，是的子集，定义上的关系如下：，确定下述每一断言是真还是假。(a)如果在上是传递的，那么在上是传递的；(b)如果是的偏序，那么是上的偏序；(c)如果是的拟序，那么是上的拟序；(d)如果是的线序，那么是上的线序；(e)如果是的良序，那么是上的良序。37.(a)证明是一拟序当且仅当，且；(b)证明是一偏序当且仅当，且。38.证明下述断言：(a)对任意线序集合，每一子集的极小元素是最小元素，每一极大元素是最大元素；(b)一线序集合的每一非空有限子集有一最小和最大元素。39.设是非空有限线序集合，，是上的关系，根据的不同定义，指出是拟序集合、偏序集合、线序集合、良序集合，还是其他集合？对任意，(a)；(b)；(c)；(d)。40.设，规定，(a)求出中下列各串的直接后继者和直接前驱者，如果它们存在的话：(i)；(ii)；(iii)；(b)对，重复上一题。3.5等价关系41.设是上的等价关系，将的元素按的等价类顺序排列，则等价关系的关系矩阵有何特征？42.证明集合上的全域关系是等价关系。43.假设是含各元素的有限集合（），问(a)有多少个元素在上的最大等价关系中？(b)上的最大等价关系的秩是什么？(c)有多少个元素在上的最小等价关系中？(d)上的最小等价关系的秩是什么？44.设和是集合上的等价关系，(a)证明是集合上的等价关系；(b)用例子证明不一定是集合上的等价关系，要尽可能小地选取集合。45.设和是非空集合上的等价关系，确定下述各式，哪些是上的等价关系，对不是的举例说明。(a)；(b)；(c)；(d)（的自反闭包）；(e)。46.是整数集合上的等价关系，将中的每一序偶标在笛卡儿平面上，所得图形有何特点？47.应用上题结论说明下述集合上的二元关系是否是等价关系，对不是的说明为什么，并找出诱导的等价关系。(a)；(b)；(c)；(d)；(e)。48.是集合上的二元关系，对于所有的，如果，则，那么称是循环的，试证明是自反的和循环的当且仅当是一等价关系。49.下述论证一位着每一对称的何传递的关系是一等价关系。设是一对称的何传递关系，(i)因为是对称的，如果，那么；(ii)因为是传递的，如果，那么，所以是自反的。这得出是一等价关系。这个论证有什么错误？50.设，求出的所有划分；设的所有划分构成的集合是，画出的哈斯图。51.设，是的划分，。(a)列出诱导出的等价关系的序偶；(b)对划分，，做同样工作；(c)画出偏序集合的哈斯图。52.设和是非空集合的划分，说明下列各式哪些是的划分，哪些可能是的划分，哪些不是的划分？(a)；(b)；(c)；(d)。53.设是集合的划分，若，，试证明是的划分。54.设是个元素的有限集，假设是上划分序列，使真细分，找出最大可能的序列长度。55.设，定义上的如下：，，，(a)对偏序集合画出哈斯图；(b)描述一下各式所诱导的等价关系，它们的秩是什么？，，，。56.设表示上模等价，设表示上模等价，(a)证明细分当且仅当是的整数倍；(b)描述划分；(c)描述划分。57.证明如果细分，那么和。58.设表示非空集合的所有划分的集合，考虑偏序集合，设和是的成员，(a)证明是集合的最大下界；(b)证明是集合的最小上界。59.设是集合上的二元关系，如果是自反的和对称的，则称是相容关系。设，，(a)是相容关系吗？(b)画出的关系图。(c)所有等价关系都是相容关系吗？(d)相容关系的关系图和等价关系的关系图有何不同？补充习题：1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。2设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：R={<a1,b1>,<a1,b3>,<a2,b2>,<a2,b3>,<a3,b1>,<a4,b1>,<a4,b2>}写出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={<x,y>|是整数}S={<x,y>|是正整数}试求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上的二元关系RR={<1,2>,<2,1>,<2,3>,<3,4>}求二元关系R的各次幂。7A={1,2,3,4,5}，A上的二元关系R和SR={<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和，验证=MRT⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。9设R是实数集合，＞={<x,y>|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>|(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={<x,y>|xR∧yR∧x=y}是实数集合上的等于关系。证明实数集合上的等于关系是传递的。14设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设集合，上的二元关系，求。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={<x,y>|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上的所有等价关系。22是集合上的关系，其中：，