《离散数学》第1—7章 习题详解.doc 15页

'第一章命题逻辑基本概念课后练习题答案1、是命题的为（1）、（2）、（3）、（6）、（7）、（10）、（11）、（12）、（13）是简单命题的为（1）、（2）、（7）、（10）、（13）是真命题的为（1）、（2）、（3）、（10）、（11）真值现在不知道的为（13）2、3略4 .将下列命题符号化，并指出真值：　　（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；　　（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；　　（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；　　（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；　　（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：　　（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；　　（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；　　（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；　　（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；　　（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；　　（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.8.设p:2<1，q:3<2(1)p→q，真值为1(2)p→┐q，真值为1(3)┐q→p，真值为0(4)┐q→p，真值为0(5)┐q→p，真值为0(6)p→q，真值为19.（2）、（6）真值为0，其余为110.（1）、（4）真值为0，其余为111、12略13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：　　（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；　　（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；　　（3）pq，真值为1；　　（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.14略15、p、q为真命题，r为假命题，（4）的真值为1，其余为016、（4）的真值为1，其余为017、真18、小王会唱歌，小李不会跳舞19、（1）（4）（6）为重言式，（3）为矛盾式，其余为非重言式的可满足式20、（1）01,10,11（2）00,10,11（3）00,01,10（4）01,10,1121、（1）011；（2）010,110,101,100；（3）100,101 22、无成真赋值23、无成假赋值24、均为重言式25、均为矛盾式26、前者为矛盾式，后者为重言式27略；28不能；29略；30不能返回第二章命题逻辑等值演算本章自测答案3、（1）矛盾式；（2）重言式；（3）可满足式5.(1)：∨∨,成真赋值为00、10、11；　(2)：0，矛盾式，无成真赋值；　(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；　(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；　(2)：∨⇔∨∨∨∨∨∨；　(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；　(2)：∨∨∨∨∨∨∨⇔1；　(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案 6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系　　(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确　　(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为　　　　(p→q)∧p→q(记作*1)　　在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.　　可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即　　　　(p→q)∧p→q⇒q　　(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为　　　　(p→q)∧p→q(记作*2)　　可以用多种方法证明*2 不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等　　　　(p→q)∧q→p　　⇔(┐p∨q)∧q→p　　⇔q→p　　⇔┐p∨┐q　　⇔⇔∨∨　　从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数　　推理的形式结构为　　　　(p→q┐)∧(r→q)→(r→┐p)(记为*)　　可以用多种方法证明*为重言式，下面用等值演算法证明：　　　　(p→┐q)∧(r→q)→(r→┐p)　　⇔(┐p∨┐q)∨(q∨┐r)→(┐q∨┐r)　　(使用了交换律)　　⇔(p∨q)∨(┐p∧r)∨┐q∨┐r　　⇔(┐p∨q)∨(┐q∧┐r)　　⇔┐p∨(q∨┐q)∧┐r　　⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.　　推理的形式结构为　　　　(p→q)∧┐p→(┐q∧┐r)　　⇔(┐p∨q)∧┐p→(┐q∧┐r)　　⇔┐p→(┐q∧┐r)　　(使用了吸收律)　　⇔p∨(┐q∧┐r)　　⇔∨∨∨　　由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明　　①p→(q→r)　　　　　前提引入　　②P　　　　　　　　　前提引入　　③q→r　　　　　　　①②假言推理　　④q　　　　　　　　　前提引入　　⑤r　　　　　　　　③④假言推理　　⑥r∨s　　　　　　　前提引入　（2）证明：　　①┐(p∧r)　　　　　前提引入　　②┐q∨┐r　　　　　①置换　　③r　　　　　　　　　前提引入　　④┐q　　　　　　　②③析取三段论　　⑤p→q　　　　　　　前提引入　　⑥┐p　　　　　　　　④⑤拒取式　（3）证明： 　　①p→q　　　　　　　前提引入　　②┐q∨q　　　　　　①置换　　③(┐p∨q)∧(┐p∨p)②置换　　④┐p∨(q∧p　　　　③置换　　⑤p→(p∨q)　　　　④置换15.(1)证明：　　①S　　　　　　　　结论否定引入　　②S→P　　　　　　前提引入　　③P　　　　　　　　①②假言推理　　④P→(q→r)　　　　前提引入　　⑤q→r　　　　　　③④假言推论　　⑥q　　　　　　　　前提引入　　⑦r　　　　　　　　⑤⑥假言推理　（2）证明：　　①p　　　　　　　　附加前提引入　　②p∨q　　　　　　①附加　　③(p∨q)→(r∧s)　前提引入　　④r∧s　　　　　　②③假言推理　　⑤s　　　　　　　　④化简　　⑥s∨t　　　　　　⑤附加　　⑦(s∨t)→u　　　　前提引入　　⑧u　　　　　　　　⑥⑦拒取式16.(1)证明：　　①p　　　　　　　　结论否定引入　　②p→┐q　　　　　前提引入　　③┐q①②　　　　假言推理　　④┐r∨q　　　　　前提引入　　⑤┐r　　　　　　　③④析取三段论　　⑥r∧┐s　　　　　前提引入　　⑦r　　　　　　　　⑥化简　　⑧┐r∧r　　　　　⑤⑦合取　（2）证明：　　①┐(r∨s)　　　　结论否定引入　　②┐r∨┐s　　　　①置换　　③┐r　　　　　　　②化简　　④┐s　　　　　　　②化简　　⑤p→r　　　　　　前提引入　　⑥┐p　　　　　　　③⑤拒取式　　⑦q→s　　　　　　前提引入　　⑧┐q　　　　　　　④⑦拒取式　　⑨┐p∧┐q　　　　⑥⑧合取　　⑩┐(p∨q)　　　　⑨置换 　　口p∨q　　　　　　前提引入　　⑾①口┐(p∨q)∧(p∨q)⑩口合取17．设p：A到过受害者房间，q:A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。　　前提：(p∧┐q)→r,p,q→s,┐s　　结论：r　　证明：　　　　①q→s前提引入　　　　②┐s前提引入　　　　③┐q①②拒取式　　　　④p前提引入　　　　⑤p∧┐q③④合取　　　　⑥（p∧┐q）→r前提引入　　　　⑦r⑤⑥假言推理18．（1）设p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。　　前提：p→(p∨r),s→┐q,p,s　　结论：r　　证明：　　　　①s→┐q　　　前提引入　　　　②s　　　　　　前提引入　　　　③┐q　　　　　①②假言推理　　　　④p　　　　　　前提引入　　　　⑤p→(q∨r)　　前提引入　　　　⑥q∨r　　　　④⑤假言推理　　　　⑦r　　　　　　③⑥析取三段论（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。　　前提：p→q,┐r→p,┐q　　结论：r　　证明：　　　　①p→q　　　　前提引入　　　　②┐q　　　　　前提引入　　　　③┐p　　　　　①②拒取式　　　　④┐r→p　　　前提引入　　　　⑤r　　　　　　③④拒取式返回第四章(一阶)谓词逻辑基本概念本章自测答案4.(1)┐x(F(x)∧┐G(x))⇔x(F(x)→G(x)),其中,F(x)：x是有理数,G(x)：x能表示成分数；　(2)┐x(F(x)→G(x))⇔x(F(x)∧┐G(x)),其中,F(x)：x在北京卖菜,G(x)：x是外地人；　(3)x(F(x)→G(x)),其中,F(x)：x是乌鸦,G(x)：x是黑色的；　(4)xF(x)∧G(x)),其中,F(x)：x是人,G(x)：x天天锻炼身体。因为本题中没有指明个体域,因而使用全总个体域。5.(1)xy(F(x)∧G(y)→H(x,y)),其中,F(x)：x是火车,G(y)：y是轮船,H(x,y)：x比y快； 　(2)xy(F(x)∧G(y)→H(x,y)),其中,F(x)：x是火车,G(y)：y是汽车,H(x,y)：x比y快；　(3)┐x(F(x)∧y(G(y)→H(x,y)))⇔x(F(x)→y(G(y)∧┐H(x,y))),其中,F(x)：x是汽车,G(y)：y是火车,H(x,y)：x比y快；　(4)┐x(F(x)→y(G(y)→H(x,y)))⇔xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽车,G(y)：y是火车,H(x,y)：x比y慢。6.各命题符号化形式如下：　(1)xy(x．y=0)；　(2)xy(x．y=0)；　(3)xy(y=x+1)　(4)xy(x．y=y．x)　(5)xy(x．y=x+y)　(6)xy(x+y＜0)9.(1)对任意数的实数x和y,若x＜y,则x≠y；　(2)对任意数的实数x和y,若x–y=0,则x＜y；　(3)对任意数的实数x和y,若x＜y,则x–y≠0；　(4)对任意数的实数x和y,若x–y＜0,则x=y.其中,(1)(3)真值为1(2)与(4)真值为0.11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。这里仅对(3)、(4)、(5)给出证明。　(3)取解释I为：个体域为自然数集合N,F(x,y)：x≤y,在下,xyF(x,y)为真,而xyF(x,y)也为真(只需取x=0即可),于是(3)中公式为真,取解释为：个体域仍为自然数集合N,而F(x,y)：x=y。此时,xyF(x,y)为真(取y为x即可),可是xyF(x,y)为假,于是(3)中公式在下为假,这说明(3)中公式为可满足式。　(4)设I为任意一个解释,若在I下,蕴涵式前件xyF(x,y)为假,则xyF(x,y)→yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常项x0,使yF(x0,y)为真,并且对于任意y∈,F(x0,y)为真,由于有x0∈,F(x0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以yxF(x,y)为真,由于I的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。　(5)取解释为：个体域为自然数集合,F(x,y)：x=y在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x＜y,(5)中公式就为假了,所以它为可满足式。13．（1）取解释为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在下，x（F（x）∨G（x））为真命题。　　取解释为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在下，x（F（x）∨G（x））为假命题。　　（2）与（3）可类似解答。14．提示：对每个公式分别找个成真的解释，一个成假的解释。返回第五章谓词逻辑等值演算与推理本章自测答案2.(1)(F(a)∧F(b)∧F(c))∧(G(a)∨G(b)∨G(c))　(2)(F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c))　(3)(F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c))　(4)(F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c))5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1.(1)的演算如下： 　　　xyF(x,y)　　⇔x(F(x,3)∨F(x,4))　　⇔(F(3,3)∨F(3,4))∧(F(4,3)∨F(4,4))　　⇔1∧1⇔16.乙说得对，甲错了。本题中，全称量词的指导变元为x，辖域为(F(x)→G(x,y)),其中F(x)与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“┐”。演算的第二步，在原错的基础上又用错了等值式，即　　(F(x)∧(G(y)→H(x,y)))≠(F(x)∧G(y)→H(x,y))12.公式的前束范式不唯一，下面每题各给出一个答案。　(1)xy(F(x)→G(z,y));　(2)xt(x,y)→G(x,t,z));　(3)x4((F(,y)→G(,y))∧(G(,y)→F(x4,y)));　(4)((F()→G(,))→(H()→L(,)));　(5)(F(,)→(F()→┐G(,))).13.(1)xy(F(x)∧G(y)∧H(x,y)),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快；　(2)xy(F(x)∧G(y)→H(x,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快；　(3)xy(F(x)∧G(y)∧┐H(x,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快；　(4)xy(F(x)∧G(y)→┐H(x,y)),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢；14.(1)对F(x)→xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式。　　　　　F(x)→xG(x)<=>x(F(y)→G(x))　　因为量词辖域(F(y)→G(x))中，除x外还有自由出现的y，所以不能使用EI规则。　(2)对xF(x)→yG(y)也应先化成前束范式才能消去量词，其前束范式为xy(F(x)→G(y)),要消去量词，既要使用UI规则，又要使用EI规则。　(3)在自然推理系统F中EG规则为　　　　　A(c)/∴x(x)　　其中c为特定的个体常项，这里A(y)=F(y)→G(y)不满足要求。　(4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，显然F(3)∧G(4)为真，但不存在使F(x)∧G(x)为真的个体。　(5)这里c为个体常项，不能对F(c)→G(c)引入全称量词。15.(1)证明：①xF(x)　　　　　　　　　　　前提引入　　②xF(x)→y((F(y)∨G(y))→R(y))　前提引入　　③y((F(y)∨G(y))→R(y)　　　　　　①②假言推理　　④F(c)　　　　　　　　　　　　　　　　①EI　　⑤(F(c)∨G(c))→R(c)　　　　　　　　③UI　　⑥F(c)∨G(c)　　　　　　　　　　　　　④附加　　⑦R(c)　　　　　　　　　　　　　　　　⑤⑥假言推理　　⑧xR(x)　　　　　　　　　　　　　　　⑦EG(2)证明①xF(x)　　　　　　　　　　　　　前提引入　　②x((F(x)→G(a)∧R(x)))　　　　　　前提引入　　③F(c)　　　　　　　　　　　　　　　　①EI　　④F(c)→G(a)∧R(a)　　　　　　　　　　②UI　　⑤G(a)∧R(c)　　　　　　　　　　　　　③④假言推理 　　⑥R(c)　　　　　　　　　　　　　　　　⑤化简　　⑦F(c)∧R(c)　　　　　　　　　　　　　③⑥合取　　⑧x(F(x)∧R(x))　　　　　　　　　　　⑦EG(3)证明：①┐xF(x)　　　　　　　　　　　前提引入　　②x┐F(x)　　　　　　　　　　　　　　①置换　　③┐F(c)　　　　　　　　　　　　　　　②UI　　④x(F(x)∨G(x))　　　　　　　　　　前提引入　　⑤F(c)∨G(c)　　　　　　　　　　　　　④UI　　⑥F(c)　　　　　　　　　　　　　　　　③⑤析取三段论　　⑦xF(x)　　　　　　　　　　　　　　　⑥EG(4)证明①x(F(x)∨G(x))　　　　　　　　　前提引入　　②F(y)∨G(y)　　　　　　　　　　　　　①UI　　③x(┐G(x)∨┐R(x))　　　　　　　　前提引入　　④┐G(y)┐R(y)　　　　　　　　　　　　③UI　　⑤xR(x)　　　　　　　　　　　　　　前提引入　　⑥R(y)　　　　　　　　　　　　　　　　⑤UI　　⑦┐G(y)　　　　　　　　　　　　　　　④⑥析取三段论　　⑧F（y）　　　　　　　　　　　　　　　②⑦析取三段论　　⑨xF(x)　　　　　　　　　　　　　　⑧UG17．本题不能用附加前提证明法.20.(1)与(2)均可用附加前提证明法。22.(1)设F(x)：x为偶数，G(x):x能被2整除。　　前提:x(F(x)→G(x))，F(6)　　结论：G(6)(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。　　前提:x(F(x)→G(x))，┐G(a)　　结论：┐F(a)23.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。　　前提:x(F(x)→G(x))，x(F(x)∧H(x))　　结论:x(G(x)∧H(x))　　证明提示：先消存在量词。(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。　　前提:x((F(x)∨G(x))→H(x))，x(I(x)→┐H(x))　　结论:x(I(x)→(┐F(x)∧┐G(x)))　　证明①x(I(x)→(┐H(x))　　　　　　　　　　前提引入　　　　②I(y)→H(y)　　　　　　　　　　　　　　①UI　　　　③x((F(x)∨G(x))→H(x))　　　　　　　前提引入　　　　④(F(y)∨G(y))→H(y)　　　　　　　　　　③UI　　　　⑤┐H(y)→(┐F(y)∧┐G(y))　　　　　　　④置换　　　　⑥I(y)→(┐F(y)∧┐G(y))　　　　　　　　②⑤假言三段论　　　　⑦x(I(x)→(┐F(x)∧┐G(x))　　　　　　⑧UG24.设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)　　证明①x┐H(x)　　　　　　　　　　　　　　　前提引入　　　　②┐H(c)　　　　　　　　　　　　　　　　　①UI　　　　③x(G(x)∨H(x))　　　　　　　　　　　　前提引入　　　　④G(c)∨H(c)　　　　　　　　　　　　　　　③UI　　　　⑤G(c)　　　　　　　　　　　　　　　　　　②④析取三段论　　　　⑥x(F(x)→G(x))　　　　　　　　　　　前提引入　　　　⑦F(c)→┐G(c)　　　　　　　　　　　　　　⑥UI　　　　⑧┐F(c)　　　　　　　　　　　　　　　　　⑤⑦拒取式　　　　⑨x┐F(x)　　　　　　　　　　　　　　　⑧UG25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。　　前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a)　　结论：I(a)　　证明①F(a)　　　　　　　　　　　　　　　　　　前提引入　　　　②x(F(x)→G(x))　　　　　　　　　　　　前提引入　　　　③F(a)→G(a)　　　　　　　　　　　　　　　②UI　　　　④G(a)　　　　　　　　　　　　　　　　　　①③假言推理　　　　⑤H(a)　　　　　　　　　　　　　　　　　　前提引入　　　　⑥x(G(x)∧H(x)→I(x))　　　　　　　　　前提引入　　　　⑦G(a)∧H(a)→I(a)　　　　　　　　　　　⑥UI　　　　⑧G(a)∧H(a)　　　　　　　　　　　　　　　④⑤合取　　　　⑨I(a)　　　　　　　　　　　　　　　　　　⑦⑧假言推理返回第六章集合代数本章自测答案4.(1)③(2)④(3)⑤(4)⑦(5)⑧6.只有(2)为真，其余为假。9.(1){4}；(2){1,3,5,6}；(3){2,3,4,5,6}；(4){,{1}}；(5){{4},{1,4}}.11.(1)；(2){1,4,5}.22.(2)、(3)、(4)、(8)、(10)为真，其余为假。24.(1)为真，其余为假，因为　　　　(P-Q)=P⇒(P-Q)∩Q=P∩Q⇒=P∩Q　　(2)(3)(4)的反例：P={1}，Q={2}26.(A–B)∪(B–A)=(A∩B)∪(B∩A)　　=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)　　=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)27.(1)(A-B)-C=A∩B∩C=A∩(B∪C)=A-(B∪C)　(2)(A-C)-(B-C)A∩C∩(B∩C)　　　=A∩C∩(B∪C)=(A∩C∩B)∪(A∩C∩C)　　　=A∩∩C=(A–B)- C　(3)(A–B-C=A∩B∩C=A∩C∩B=(A–C)–B28.(1)A∩(B∪A)=(A∩B)∪(A∩A)=(A∩B)∪　　　=A∩B=B∩A　(2)((A∪B)∩A)=(A∪B)∪A　　　=(A∩B)∪A=A29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A)=(A∪B)-(A∩B)=A∪B矛盾.30.AB⇔x(x∈A→x∈B)⇔x(xB→xA)　　　⇔x(x∈B→x∈A)⇔BA　　　AB⇒A∪AA∪B⇒EA∪B　　而A∪BE，因此AB⇒A∪B=E反之，　　　A∪B=E⇒A∩(A∪B)=A⇒A∩B=A⇒AB　　综合上述，AB⇔A∪B=E　　　AB⇒A-B=⇒A-BB　　反之A-BB⇒(A-B)∪BB⇒A∪BB⇒A∪B=B⇒AB　　综合上述AB⇔A-BB31.任取x,x∈A⇒{x}A=>{x}∈P(A)=>{x}∈P(B)=>{x}B⇒x∈B32.先证CA∧CB⇒CA∩B,任取x,x∈C⇒x∈C∧x∈C⇒x∈A∧x∈B⇒x∈A∪B,从而得到CA∪B.再证CA∩B⇒CA∧CB，这可以由CA∩BA,CA∩BB得到。33.PQ⇒P-Q=⇒P-QP，反之，P-QP⇒P∩(P-Q)P∩P⇒P-Q=⇒PQ34.令X=，则有∪Y=，即Y=.35.AB⇒A∪AB∪A⇒EB∪A因为E为全集,B∪AE综合上述B∪A=E.36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有：　(A∩C)∪(A-C)(B∩C)∪(B-C)　⇒(A∩C)∪(A∩C)(B∩C)∪(B∩C)　⇒(A∩(C∪C)(B∩(C∪C)⇒A∩EB∩E⇒AB37.恒等变形法　　B=B∩(B∪A)=B∩(AB)=B∩(AC)　　=(B∩A)∪(B∩C)=(A∩C)∪(B∩C)　　=(A∪B)∩C=(A∪C)∩C=C39.任取x，有x∈P(A)⇒xA⇒xB⇒x∈P(B)，因此P(A)P(B).40.(1)任取x有　　x∈P(A)∩P(B)⇔x∈P(A)∧x∈P(B)⇔xA∧xB　　　　　　　　　⇔xA∩B⇔x∈P(A∩B)(2)任取x有　　x∈P(A)∪P(B)⇔x∈P(A)∨x∈P(B)⇔xA∧xB　　　　　　　　　⇒xA∪B⇔x∈P(A∪B)　　注意与(1)的推理不同，上面的推理中有一步是“⇒”符号，而不是“⇔”符号。(3)反例如下：A={1}，B={2}，则　　P(A)∪P(B)={,{1},{2}}　　P(A∪B)={,{1},{2},{1,2}}返回 第七章二元关系本章自测答案3.(1)任取,有　　∈(A∩B)×(C∩D)<=>x∈A∩B∧y∈C∩D　⇔x∈A∧x∈B∧y∈C∧y∈D　⇔(x∈A∧y∈C)∧(x∈B∧y∈D)　⇔∈A×C∧∈B×D　⇔∈(A×C)∩(B×D)　(2)都为假,反例如下:　　A={1},B={1,2},C={2},D={3}4.(1)为假,反例如下:A={1},B=,C={2};　(2)为真,证明如下:任取有　　∈A×(B∩C)×(C∩D)⇔x∈A∩B∧y∈B∧y∈C　⇔(x∈A∧y∈B)∧(x∈A∧y∈C)　⇔∈A×B∧∈A×C⇔∈(A×B)∩(A×C)　(3)为真,令A=即可;　(4)为假,反例如下:A=7.={<2,2>,<3,3>,<4,4>}　={<2.3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>}∪　LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}　DA={<2,2>,<2,4>,<3,3>,<4,4>}9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4><2,6>,<4,1>,<4,2>,<4,4>,<4,6><6,1>,<6,2>,<6,4><6,6>}　(2){<1,2>,<2,1>};　(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>}　(4){<1,2>,<2,2>,<4,2>,<6,2>}12.（略）13.A∩B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>},A∩B={<2,4>}　　domA={1,2,3},domB={1,2,4},dom(A∪B)={1,2,3,4}　　ranA={2,3,4},ranB={2,3,4},ran(A∪B)={4},fld(A-B)={1,2,3}14.RR={<0,2>,<0,3>,<1,3>}　R={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}　R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}　R[{1,2}]={2,3}18.(1)F(G∪H)=FG∪FH　　任取,有　　　　∈F(G∪H)⇔t(∈F∧∈G∪H)　　⇔t(∈F∧(∈G∨∈H))　　⇔t((∈F∧∈G)∨(∈F∧∈H))　　⇔t(∈F∧∈G)∨t(∈F∧∈H))　　⇔∈FG∨∈FH⇔∈FG∪FH　(2)和(4)类似可证19.(2)任取y,有 　　y∈R[T∪W]⇔x(x∈T∪W∧∈R)　　　⇔x((x∈T∨x∈W)∧∈R　　　⇔x((x∈A∧∈R)∨(x∈W∧∈R))　　　⇔x(x∈T∧∈R)∨x(x∈W∧∈R)　　　⇔y∈R[T]∨y∈R[W]⇔y∈R[T]∩R[W](3)任取,有　　∈F(A∩B)⇔x∈A∩B∈F　　　⇔x∈A∧x∈B∧∈F　　　⇔(x∈A∧∈F)(x∈B∧∈F)　　　⇔∈FA∧∈FB　　　⇔∈FA∩FB20.(1)任取,有　　∈(∪)<=>∈∪　　　⇔∈∨∈　　　⇔∈∨∈　　　⇔∈∪　(2)和(1)类似可证.21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根据xRy⇔x+y=10=>yRx,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的,<1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的.22.(1)关系图如图7.15所示;(P148)　(2)具有反自反性、反对称性、传递性.26.(1)R={<3,3>,<3,1>,<3,5>},={<3,3>,<3,1>,<3,5>}　(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>}　　　s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>}　　　T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>}31.(1)R={<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪；(2)R；(3)R.32.(1)不是等价关系，因为<1,1>R，R不是自反的；　(2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2；　(3)不是等价关系，因为<2,2>R，R不是自反的；　(4)不是等价关系，因为R不是传递的。　(5)是等价关系。33．关系图如图7.17说示(P151)　[a]=[b]={a,b},[c]=[d]={c,d}　　38.现取x，有x∈A⇒∈R⇒∈R∧∈R　　⇒∈R∧∈⇒∈R∩R　任取,有∈R∩⇒∈R∧∈　　⇒∈∧∈R⇒∈R∩R　任取,,有 　　　∈R∩∧∈R∩　　⇒∈R∧∈∧∈R∧∈　　⇒(∈R∧∈R)∧(∈∧∈　　⇒∈R∧∈R⇒∈R∩R42.x,x∈A⇒∈R⇒∈R∧∈R⇒∈T,T是自反的。　　　x,y∈A,∈T⇔∈R∧∈R　⇔∈R∧∈R⇒∈T,T是对称的。　　　x,y,z∈A,∈T∧∈T　⇔∈R∧∈R∧∈R∧∈R　⇒∈R∧∈R∧∈R∧∈R　⇒∈R∧∈R⇒∈T　T是传递的。43．哈斯图如下图所示.　　44.(a)偏序集,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪　(b)偏序集,A={a,b,c,d,e,f},R={,,}∪　(c)偏序集,A={1,2,3,4,5},R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪45.(a)A={a,b,c,d,e,f,g},={,,,,,,,,,}∪　(b)A={a,b,c,d,e,f,g},R口={,,,,,,}∪46.哈斯图如图7.19所示（P153）　（1）极大元e,f；极小元a,f；没有最大与最小元。　（2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。返回5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、。　　解：由握手定理图G的度数之和为：　　　　3度与4度顶点各2个，这4个顶点的度数之和为14度。　　　　其余顶点的度数共有6度。　　　　其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,　　所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,. 7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求，,.解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.,,14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。(1)2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4解：(1)2+2+3+3+4+4+5=23是奇数，不可图化；(2)2＋2+2+2+3+3+4+4=16,是偶数，可图化；'