山东大学离散数学题库及答案(计本)

1、离散数学题库答案一、选择或填空(数理逻辑部分)1、下列哪些公式为永真蕴含式()(1)Q=CHP(2)Q=8Q(3)P=AQ(4)P(PQ)=P答：(1)，(4)2、下列公式中哪些是永真式()(1)(nPQ尸(Q-R)(2)8(Q-Q)(3)(PQ)-P(4)八(PQ)答：(2)，(3)，(4)3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=PQ(2)PQ=P(3)PQ=PQ(4)P(P-Q)=Q(5)(PQ)=P(6)P(PQ)=P答：(2)，(3)，(4)，(5)，(6)4、公式x(A(x)B(y,x)zC(y,z)D(x)中，自由变元是()，约束变元是()答：x,y,x,z5、判断下

2、列语句是不是命题。若是，给出命题的真值。()(1)北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗(4)若7+818,则三角形有4条边(5)前进！(6)给我一杯水吧！答：(1)是，T(2)是，F(3)不是(4)是，T(5)不是(6)不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()答：所有人都不是大学生，有些人不会死7、设P:我生病，Q:我去学校，则下列命题可符号化为()。(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：(1)QP(2)PQ(3)PQ

3、(4)PQ8、设个体域为整数集，则下列公式的意义是()。(1)xy(x+y=0)(2)yx(x+y=0)答：(1)对任一整数x存在整数y满足x+y=0(2)存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)xy(xy=y)()(2)xy(x+y=y)()(3)xy(x+y=x)()(4)xy(y=2x)()答：(1)F(2)F(3)F(4)T10、设谓词P(x):x是奇数，Q(x):x是偶数，谓词公式x(P(x)Q(x)府哪个个体域中为真()(1)自然数(2)实数(3)复数(4)(1)-(3)均成立答：(1)11、命题“2是偶数或-3是负数”的否定是()

4、。答：2不是偶数且-3不是负数。12、永真式的否定是()(1)永真式(2)永假式(3)可满足式(4)(1)-(3)均有可能答：(2)13、公式(PQ)(PQ)化简为()，公式Q(P(PQ)可化简为()。答：P，QP14、谓词公式x(P(x)yR(y)Q(x)中量词x的辖域是()。答:P(x)yR(y)15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为(答：x(R(x)Q(x)(集合论部分)16、设A=a,a,下列命题错误的是()。(1)aP(A)(2)aP(A)(3)aP(A)(4)aP(A)答：(2)17、在0()之间写上正确的符号。(1)=(2

5、)(3)(4)答：(4)18、若集合S的基数|S|=5,则S的募集的基数|P(S)|=()。答：3219、设P=x|(x+1)24且xR,Q=x|5*2+16且*R,则下列命题哪个正确()(1)QP(2)QP(3)PQ(4)P=Q答：20、下列各集合中，哪几个分别相等()。A1=a,b(2)A2=b,a(3)A3=a,b,a(4)A4=a,b,cA5=x|(x-a)(x-b)(x-c)=0(6)A6=x|x2-(a+b)x+ab=0答：A1=A2=A3=A6,A4=A521、若A-B=O,则下列哪个结论不可能正确()(1)A=O(2)B=O(3)AB(4)BA答：(4)22、判断下列命题哪个为

6、真()(1)A-B=B-A=A=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一个元素属于B,则A=B答：(1)23、判断下列命题哪几个为正确()eg,(3)ea,bea,b,a,b答：,(4)24、判断下列命题哪几个正确()(1)所有空集都不相等(2)(4)若A为非空集，则AA成立。答：25、设Anb=ahc,Anb=Anc,贝Ub()c。答：=(等于)26、判断下列命题哪几个正确()(1)若AUB=AUC,则B=C(2)a,b=b,a(3)P(AHB)P(A)HP(B)(P(S表示S的募集)(4)若A为非空集，则AAUA成立。答：27、A,B,C是三个集合，则下列哪

7、几个推理正确：(1)AB,BC=AC(2)AB,BC=AGB(3)AGB,BGC=AC答：(1)(二元关系部分)28、设人=1,2,3,4,5,6,B=1,2,3,从A到B的关系R=|x=y2,求(1)R(2)R-1。答：(1)R=,(2)R1=,29、举出集合A上的既是等价关系又是偏序关系的一个例子。()答：A上的恒等关系30、集合A上的等价关系的三个性质是什么()答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么()答：自反性、反对称性和传递性32、设S=1,2,3,4,A上的关系R=1,2，2,1，2,3，3,4求(1)RR(2)R1o答：RR=1,1，1,3，2,2，2

8、,4R-1=2,1，1,2，3,2，4,333、设人=1,2,3,4,5,6,R是A上的整除关系，求R=()答：R=, |x=2y,求(1)R (2) R1 |x=y2,求R和R1的关系矩阵,34、设人=1,2,3,4,5,6,B=1,2,3,从A到B的关系R=答：(1)R=,(2)R1=,(3635、设人=1,2,3,4,5,6,B=1,2,3,从A到B的关系R=100000000答： R 的关系矩阵=010000000100R 1 的关系矩阵 = 0 0 000010000000036、集合A=1,2，,10上的关系R=|x+y=10,x,yA,则R的性质为()(1)自反的(2)对称的(3

9、)传递的，对称的(4)传递的答：(2)(代数结构部分)37、设A=2,4,6,A上的二元运算*定义为：a*b=maxa,b,则在独异点中，单位元是()，零元是()，答：2，638、设A=3,6,9,A上的二元运算*定义为：a*b=mina,b,则在独异点中，单位元是()，零元是()；答：9，3(半群与群部分)39、设G,*是一个群，则(1)若a,b,xGG,ax=b,则x=()；(2)若a,b,xGG,ax=ab,则x=()答：(1)a1b(2)b40、设a是12阶群的生成元，则22是()阶元素，23是()阶元素。答：6,441、代数系统G,*是一个群，则G的等募元是()。答：单位元42、设a

10、是10阶群的生成元，则24是()阶元素，23是()阶元素。答：5，1043、群G,*的等幂元是()，有()个。答：单位元，144、素数阶群一定是()群,它的生成元是()。答：循环群，任一非单位元45、设G,*是一个群，a,b,cGG,贝U(1)若ca=b,则c=()；(2)若ca=ba,则c=()。答：(1)ba1(2)b46、H,是6,的子群的充分必要条件是()。答：H,是群或a，bG，abH，a-1H或a,bG，ab-1H47、群A,*的等嘉元有()个，是()，零元有()个。答：1，单位元，048、在一个群G,*中，若G中的元素a的阶是k,则a-1的阶是()。答：k49、在自然数集N上，下

11、列哪种运算是可结合的()(1)a*b=a-b(2)a*b=maxa,b(3)a*b=a+2b(4)a*b=|a-b|答：(2)50、任意一个具有2个或以上元的半群，它()(1)不可能是群(2)不一定是群(3)一定是群(4)是交换群答：(1)51、6阶有限群的任何子群一定不是()。(1)2阶(2)3阶(3)4阶(4)6阶答：(3)(格与布尔代数部分)52、下列哪个偏序集构成有界格()(1)(N,)(2)(Z,)(3)(2,3,4,6,12,|(整除关系)(4)(P(A),)答：(4)53、有限布尔代数的元素的个数一定等于()(1)偶数(2)奇数(3)4的倍数(4)2的正整数次幂答：(4)(图论部

12、分)54、设G是一个哈密尔顿图，则G一定是()。(1)欧拉图(2)树(3)平面图(4)连通图答：(4)55、下面给出的集合中，哪一个是前缀码()(1)0,10,110,101111(2)01,001,000,1(3)b,c,aa,ab,aba(4)1,11,101,001,0011答：56、一个图的哈密尔顿路是一条通过图中()的路。答：所有结点一次且恰好一次57、在有向图中，结点v的出度deg+(v)表示()，入度deg-(v)表示()。答：以v为起点的边的条数，以v为终点的边的条数58、设G是一棵树，则G的生成树有()棵。0(2)1(3)2(4)不能确定答：159、n阶无向完全图Kn的边数是

13、()，每个结点的度数是()。穴n(n1)答：,n-1260、一棵无向树的顶点数n与边数m关系是()。答：m=n-161、一个图的欧拉回路是一条通过图中()的回路。答：所有边一次且恰好一次62、有n个结点的树，其结点度数之和是()。答：2n-263、下面给出的集合中，哪一个不是前缀码()。(1)a,ab,110,a1b11(2)01,001,000,1(3)1,2,00,01,0210(4)12,11,101,002,0011答：(1)64、n个结点的有向完全图边数是()，每个结点的度数是()。答：n(n-1),2n-265、一个无向图有生成树的充分必要条件是()。答：它是连通图66、设G是一棵

14、树，n,m分别表示顶点数和边数，则(1)n=m(2)m=n+1(3)n=m+1(4)不能确定。答：67、设T=VE是一棵树，若|V|1,则T中至少存在()片树叶。答：268、任何连通无向图G至少有()棵生成树，当且仅当G是()，G的生成树只有一棵。答：1,树69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于：m-n+2n-m-2n+m-2m+n+2。答：(1)70、设T是一棵树，则T是一个连通且()图。答：无简单回路71、设无向图G有16条边且每个顶点的度数都是2,则图6有()个顶点。(1)10(2)4(3)8(4)16答：(4)72、设无向图G有18条边且每个顶点的度数都是3,则

15、图G有()个顶点。(1)10(2)4(3)8(4)12答：(4)73、答：有向图设图G=,V=a,b,c,d,e,E=,BG是有向图还是无向图有向图74、，答：偶数（偶数）个。75、具有6个顶点，12条边的连通简单平面图中，每个面都是由（）条边围成(1)2(2)4(3)3(4)5答：3）76、在有n 个顶点的连通图中，其边数（1） 最多有 n-1 条其边数（）。（2） 至少有 n-1 条答：2）77、答：4）78、）答：79、（3） 最多有 n 条（4） 至少有 n2 个 2 度顶点，个 3 度顶点，3 个 4 度顶点，则其1 度顶点为（）。(1) 5(2) 7若一棵完全二元（叉）(1) n

16、(2) 2n1)(3) 8树有(4) 92n-1 个顶点，则它（则它（）片树叶。(3) n-1(4) 2下列哪一种图不一定是树（）。（1） 无简单回路的连通图（2） 有n个顶点n-1条边的连通图（4） 连通但删去一条边便不连通的图（3） 每对顶点间都有通路的图答：（3）80、连通图 G 是一棵树当且仅当G 中（ ） 。（1）有些边是割边（2）每条边都是割边（3）所有边都不是割边（4）图中存在一条欧拉路径答：（2）（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式：1、（P-Q）解：（P-Q）P R) (QR)（析取范式）(QQ)R)(P) Q R)R) (R) (PQR) (P Q R)

17、R) (R) (PQ R)（主析取范式）(P- Q)R)R)R) (PQ R)(P-Q)R(PR)(P QR)R）（原公式否定的主析取范式）(PQ R)R)R) (R)（主合取范式）2、 (P R)(QR)解： (P R) (Q R)（析取范式）(P (QQ)R) (P P)R)( P (Q Q) (R R)(PQR)(PQR)(PQR) (PQR)( P Q R) ( P Q R) ( P Q R) ( P Q R)(PQR)(PQR)(PQR)(PQR) ( P取范式 )( (P R) (QR)P)(P Q R) (P QR) (原公式否定的主析取范式)(P R) (Q R)P(P Q R

18、) ( P Q R)(主合取范式)3、(PfQ) (R P)解：(P-Q)(R P)(P Q) (R P)(合取范式)(P Q (R R) (P (Q Q) R)(P Q R) (P Q R) (P Q R) (P Q R)(P Q R) (P Q R) (P Q R)(主合取范式)(P- Q) (R P)(P Q R) ( P Q R) ( P Q R) ( P Q R)(P Q R)(原公式否定的主合取范式)(P-Q) (R P)( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)(主析取范式)Q R) ( PR) (主析4、Qf(PR)解：Q-(PR)Q P

19、R (主合取范式)(Q-(PR)( P Q R) ( P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) (P QR) (原公式否定的主合取范式)Q-(PR)(P Q R) (P Q R) (P Q R) (P Q R) ( P Q( P Q R) ( P QR) (主析取范式)R)5、八(P (QP)解：P-(P(Q-P)P (P ( Q P)PPT (主合取范式)(P Q) ( P Q) (P Q) (P Q)(主析取范式)6、(P-Q) (R P)解：(P-Q) (R P) ( P Q) (R P)(P Q) (R P)(析取范式)(P Q (R R) (P

20、(PQR)(PQ(PQR)(PQQ Q) R)R) (P Q R) (P Q R)R) (P Q R)(主析取范式)(P-Q) (R P) (P(P QQR)(PQR)(PQR)R)(PQR)(原公式否定的主析取范式)(P-Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)7、P(P-Q)解：P(P-Q)P(PQ)(PP)QT（主合取范式）(PQ)(PQ)(PQ）（PQ）（主析取范式）8、(RfQ)P解：(R-Q)P(RQ)P（RP）（QP）（析取范式）(R(QQ)P)(RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PR)(PQR）（主析取范式）(2

21、Q)P)(PR)(PQR)(PQR)(PQR)(PQR）（原公式否定的主析取范式）(R-Q)P(PQR)(PQR)(PQR)(PR)(PQR）（主合取范式）解：P-QPQ（主合取范式）10、P解：PP(QQ)(PP)Q)(PQ)(P(PQ)(PQ（主合取范式）Q)Q)(PQ)(PQ)（PQ）（主析取范式）(P(QQ)(PP)Q）(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ）（主析取范式）11、PQ解：PQ（主析取范式）(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(主合取范式)12、(PR)Q解：（PR）Q(PR)QR)QQ)(RQ)(合取范式)(R

22、R)(PP)QR)R)R)(PR)(PQR)R)R)(PR)(PQR)R)R)(PQR）（主合取范式）PR)(PQR)(PR)(PQR)(PR)(PR)（原公式否定的主析取范式）PR)Q(PQR)(PQR)(PR)(PQR)（PQR）（主析取范式）13、 ( P Q) R解：（PQ）(P(P(P(P(PPQ)RQ）R（析取范式）(RR)(PR)(PQR)R)(PQR）住析取范式）P)(QR)R)Q)(PQR)(PQR)R)(PR)(PQR)(PR)PQ)R(PQ)R(PQ） R（析取范式）(PR） （ QR）合取范式）(P(QQ) R) (PP)Q R)(PQ R) (P Q R) (PQ R

23、) ( PR)(PQ R) (P Q R) ( PQ R）（主合取范式）14、 (P (Q R) ( P ( QR)解： (P (Q R) ( P ( QR)P (Q R) (P ( QR)P Q) ( P R) (P Q) (PR）（合取范式）P Q (RR) ( P (QQ) R) (P(RR)(P (QQ)R)(P(P(P (Q R)(PQ R) ( PQ R) (PQ R) ( P(P QR)(P(P(QR)R) ( P Q R) ( PR) (P QR) ( PR)R) (PQ R) (PR）（主合取范式）R） （P QR）（原公式否定的主合取范式）(P (Q R) ( P ( QR

24、)(P Q R) ( PR）（主析取范式）R)R)15、 P(P(Q(QR)解：P(P(Q(QR)P(P(Q(QR)PQR(主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否定的主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)16、 (PQ)(PR)解、(PQ)(PR)(PQ)(PR)(合取范式)(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)合取范式)(P(QQ)(RR)(PP

25、)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)R)(PQR)(PQR)(PQR)(PQR)(PQ(主析取范式)三、证明：1、八Q,QR,R,SP=S证明：(1) R前提(2) QR前提(3) Q(1)，(2)(4) 八Q前提(5) P(3)，(4)(6) SP前提(7) S(5)，(6)2、Af(BfC),Cf(DE),Ff(DE),A=BHF证明：(1) A前提(2) A-(B-C)前提(3) B-C(1),(2)(4) B附加前提(5)C（3），（4）(6)C-(DE）前提(7)DE（5），（6）(8)Ff(DE）前提(9)F（7），（8）(10)BfFCP3、PQ,

26、八R,CKS=RS证明：(1)R附加前提(2)PfR前提(3)P（1），（2）(4)PQ前提(5)Q（3），（4）(6)QfS前提(7)S（5），（6）(8)RSCP，（1），（8）4、(P-Q)(R-S),(Q-W)(SfX),(WX),八R=证明：（1）P假设前提PfR前提（3）R（1），（2）(4)(P-Q)(R-S)前提(5)P-Q（4）(6)RS（5）（7）Q（1），（5）（8）S（3），（6）(9)(Q-W)(腔X)前提(10)QfW（9）(11)SX（10）(12)W（7），（10）(13)X（8），（11）(14)WX（12），（13）(15)(WX)前提(16)(WX)(WX

27、)(14)，(15)5、(UV)(MN),UP,h(QS),QS=M证明：(1)QS附加前提八(QS）前提（3）P（1），（2）(4)UP前提（5）U（3），（4）(6)UV（5）(7)(UV)-(MN)前提(8)MN(6),(7)（9）M（8）6、BD,年F户D，E=B证明：(1)B附加前提(2)BD前提(3)D（1），（2）(4)(E-F)-D前提(5)(EF)（3），（4）(6)EF（5）(7)E（6）(8)E前提(9)EE（7），（8）7、八(Q-R),Rf(Q-S)=P(QfS)证明：（1）P附加前提（2）Q附加前提P（3）Pf(QR)前提（4）QfR（1），（3）（5）R（2），（

28、4）（6）R(QfS)前提（7）QfS（5），（6）（8）S（2），（7）（9）QfSCP，（2），（8）（10）Pf(QS)CP，（1），（9）8、八Q,八R,RfS=SQ证明：（1）S附加前提（2）2S前提（3）R（1），（2）（4）PfR前提（5）P3），（4）（6）PfQ前提（7）Q（5），（6）（8）SfQCP，（1），（7）9、八(Q-R)=(4Q)f(PfR)证明：(1)八Q附加前提(2)P附加前提(3)Q(1),(2)八(Q-R)前提Q-R,(4)(6) R(3),(5)(7) P-RCP,(2),(6)(8) (P-Q)-(P-R)CR1),(7)10、Pf(QfR),QfP

29、,SR,P=S八(Q-QfRQf P证明：（ 1） P（ 2）（ 3）（ 4）（ 5） Q（ 6） R腔R（ 8） S11、A,A-B,AfC,证明：（1） A（2） AfB（3） 3）B（4） AfC前提R)前提(1)，(2)前提(1)，(4)(3),(5)前提(6) ，(7)Bf(D-C)=D前提前提(1)，(2)前提(5)(1),(4)(6)Bf(D-C）前提(7)DfC,(6)(8),12、Af(CB),B-A,D-证明:(2)A-(CB)前提CB(1),(2)(4) B-A前提(5) B(1),(4)(6) C(3),(5)(7) D-C前提(8) D(6),(7)(9) A-DCP

30、,(1),(8)13、(PQ)(RQ)(PR)Q证明、(PQ)(RQ)14、P(PQ)(RQ)(PR)Q(PR)Q(PR)Q(QP)P(PQ)证明、P(QP)15、（PP(QP)(P)(PQ)P(PQ)Q)(PR),(QR),SPS证明、(1)(PQ)(PR)前提(2)P(QR)(1)(3)(QR)前提(4)P,(5)SP前提(6)S(4),(5)16、PQ,QR,RSP证明、(1) P附加前提(2) PQ前提(3) Q(1),(2)(4) QR前提(5) R(3),(4)(6)RS前提附加前提(1)A(7) R(6)(8) RR(5),(7)17、用真值表法证明PQ(PQ)(QP)证明、列出

31、两个公式的真值表：由定义可知，这两个公式是等价的P QP Q(P Q)(QP)F FRRF RFFR FFFR RRR18、PfQPf(PQ)证明、设P-(PQ)为F,则P为T, P Q为F。所以P为T, Q为F ,从而PfQ也为Fo所以QPf(P19、用先求主范式的方法证明(P-Q)(P-R)(P- ( QR)证明、先求出左右两个公式的主合取范式(P-Q)(P-R)Q)(R)(RR)P (QQ)R)R)(R)R)R)R)R)R)(P一(QR)(QR)Q)R)(RR)(QQ)R)R)R)Q R)R)R)R)R)它们有一样的主合取范式,所以它们等价。20、(P-Q)(QR)证明、设(P-Q)(Q

32、R)为 R,则Q 和(QR)都为R即P-Q和R都为R。故P-Q,Q和R)都为R,即P-Q为R, Q和R都为F。从而P也为F,即 P为Ro从而(P- Q)(Q R)21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效前提：(1)若A队得第一，则B队或C队获亚军；若C队获亚军，则A队不能获冠军；若D队获亚军，则B队不能获亚军；A队获第一；结论：(5)D队不是亚军。证明、化为设A:A队得第一；B:B队获亚军；C:C队获亚军；D:D队获亚军；则前提符号化为A(BC),CA,DB,A;结论符号Do本题即证明A(BC),CA,DB,AD。(1)A前提(3)BC(1),(2)(4)

33、CA前提(5)C(1),(4)(6)B(3),(5)DB前提(8)D(6),(7)用推理规则证明PQ,(QJ、(1)PR前提(2)P(1)PQ前提Q,(3)(QR)前提(6)QR(5)Q(6)(8)QQ,(7)(BC)前提(2)AR),PR不能同时为真。22、(集合论部分)四、设A,B,C是三个集合，证明：1、A(B-C)=(AB)-(AC)证明：(A B)-(A C)= (A B)A C =(A B) (A C )=(A BA) (A BC )= A B C =A(B C )=A(B-C)2、(A-B)(A-C)=A-(BC)证明：(A-B)(A-C)=(AB)(AC)=A(BC)=ABC=

34、A-(BC)3、A B=A C, AB=A证明：C,贝 U C=BB=B(AA)=(BA)(BA)=(CA)(CA)=C(AA)=C4、AB=A(B-A)证明：A(B-A)=A(BA)=(AB)(AA)=(AB)U=AB5、A=BAB=证明：A=B,贝UAB=(A-B)(B-A)=设 A B=，则 A B= (A-B)(B-A)=o故A-B=,B-A=,从而AB,BA,故A=B=6、AB=AC,AB=AC,贝UC=B证明:B=B(AB)=B(AC)=(BA)(BC)=(AC)(BnC)=C(AB)=C(AC)=C7、AB=AC,AB=AC,则C=B证明:B=B(AA)=(BA)(BA)=(CA

35、)(CA)=C(AA)=C8、A-(BC)=(A-B)-C证明：A-(BC)=ABC=A(BC)=(AB)C=(A-B)C=(A-B)-C9、(A-B)(A-C)=A-(BC)证明：(A-B)(A-C)=(AB)(AC)=(AA)(BC)=ABC=A-(BC)10、A-B=B,则A=B=证明：因为B=A-B,所以B=BB=(A-B)B=。从而A=A-B=B=。11、A=(A-B)(A-C)ABC=证明：因为(A-B)(A-C)=(AB)(AC)=A(BC)=ABC=A-(BC),且A=(A-B)(A-C),所以A=A-(BC),故ABC=o因为ABC=，所以A-(BC)=A而A-(BC)=(A

36、-B)(A-C),所以A=(A-B)(A-C)o12、(A-B)(A-C)=ABC证明：因为(A-B)(A-C)=(AB)(AC)=A(BC)=ABC=A-(BC),且(A-B)(A-C)=,所以=A-(BC),故ABCo因为ABC,所以A-(BC)=A。而A-(BC)=(A-B)(A-C),所以A=(A-B)(A-C)o证明：因为(A-B)(B-A)=A,所以B-AA。但(B-A)A=,故B-A=。即BA,从而B=(否则A-BA,从而与(A-B)(8-川=庆矛盾)。因为B=，所以A-B=A且B-A=。从而(A-B)(B-A)=A。14、(A-B)-CA-(B-C)证明：x(A-B)-G有XA

37、-B且xC,即XA,xB且xC从而xA,xB-C,故xA-(B-C)。从而(A-B)-CA-(B-C)15、P(A)P(B)P(AB)(P(S表示S的募集)证明：SP(A)P(B),有SP(A)或SP(B),所以SA或SB。从而SAB,故SP(AB)。即P(A)P(B)P(AB)16、P(A)P(B)=P(AB)(P(S表示S的募集)证明：SP(A)P(B),有SP(A)且SP(B),所以SA且SB。从而SAB,故SP(AB)o即P(A)P(B)P(AB)。SP(AB),有SAB,所以SA且SB。从而SP(A)MSP(B),故SP(A)P(B)。即P(AB)P(A)P(B)。故P(AB)=P(

38、A)P(B)17、 (A-B)B=(AB)-B当且仅当B=。证明：B)B。当B=时，因为(A-B)B=(A-)=A,(AB)-B=(A)-=A,所以(A-B)B=(A-B。用反证法证明。假设B，则存在bB。因为bB且bAB，所以b(AB)-B。而显然b(A-B)故这与已知(A-B)B=(AB)-B矛盾。五、证明或解答：(数理逻辑、集合论与二元关系部分)答：1、设个体域是自然数，将下列各式翻译成自然语言：(1)xy(xy=1);(2)xy(xy=1);(3)xy(xy=0);(4)xy(xy=0)(5)xy(xy=x);(6)xy(xy=x)(7)xyz(x-y=z)(1)存在自然数x，对任意自

39、然数y满足xy=1;(2)对每个自然数x，存在自然数y满足xy=1;(3)对每个自然数x，存在自然数y满足xy=0;(4)存在自然数x,对任意自然数y满足xy=1;(5)对每个自然数x,存在自然数y满足xy=x;(6)存在自然数x，对任意自然数y满足xy=x;(7)对任意自然数x,y,存在自然数z满足x-y=zo2、设A(x,y,z):x+y=z,M(x,y,z):xy=z,L(x,y):xy，个体域为自然数。将下列命题符号化：1)没有小于0的自然数;2) xz是xy且yz的必要条件;(3)若xy,则存在某些z,使zyz;(4)存在x,对任意y使得xy=y;(5)对任意x，存在y使x+y=x。

40、答：( 1) x(G(x,0)M(0,0,x)或xL(x,0)( 2) xyz(L(x,y)L(y,z)L(x,z)( 3) xy(L(x,y)z(L(z,0)G(xz,yz)( 4) xyM(x,y,y)( 5) xyA(x,y,x)3、列出下列二元关系的所有元素：(1) A=0,1,2，B=0,2,4，R=|x,yAB;(2) A=1,2,3,4,5,B=1,2,R=|2x+y4且xA且yB;(3) A=1,2,3,B=-3,-2,-1,0,1,R=|x|=|y|且xA且yB;解：(1)R=,(2)R=,;(3)R=,。4、对任意集合A,B,证明：若AA=BB,则B=B。证明：若B=，则B

41、B=。从而AA=。故A=。从而B=A。若B，则BB。从而AA。对xB,BB。因为AA=BB,则AA。从而xA。故BA同理可证，AB。故B=A。5、对任意集合A,B,证明：若A,AB=AC,则B=C。证明：若B=，则AB=。从而AC=。因为A，所以C=。即B=C。若B，则AB。从而AC。对xB,因为A,所以存在yA,使AB。因为AB=AC,则AC。从而xC。故BC。同理可证，CB。故B=C。6、设A=a,b,B=c。求下列集合：(1) A0,1B；(2)B2A；(3) (AB)2;(4)P(A)A。解：( 1) A0,1B=,;( 2) B2A=,;( 3) (AB)2=,;( 4) P(A)A

42、=,。7、设全集U=a,b,c,d,e,A=a,d,B=a,b,c,C=b,d求下列各集合：(1) ABC;ABC;(3)(AB)C；(4) P(A)-P(B);(5)(A-B)(B-C);(6)(AB)C;解：(1) ABC=a;(2)ABC=a,b,c,d,e;(3) (AB)C=b,d；(4)P(A)-P(B)=d,a,d;(5) (A-B)(B-C)=d,c,a;(6)(AB)C=b,d。8、设A,B,C是任意集合，证明或否定下列断言：(1)若AB,且BC,则AC;(2)若AB,且BC,则AC;(3)若AB,且BC,则AC;(4)若AB,且BC,则AC;证明：(1)成立。对xA,因为A

43、B,所以xBo又因为BC,所以xC。即AC。(2)不成立。反例如下：A=a,B=a,b,C=a,b,c)虽然AB,且BC,0AC。(3)不成立。反例如下：A=a,B=a,b,C=a,b,c。虽然AB,且BC,但AC(4)成立。因为AB,且BC,所以ACo9、A上的任一良序关系一定是A上的全序关系。证明：a,bGA,则a,b是A的一个非空子集。0是A上的良序关系，a,b有最小元。若最小元为a,则ab；否则bao从而为A上的的全序关系。10、若R和S都是非空集A上的等价关系，则RS是A上的等价关系。证明：aGA,因为R和S都是A上的等价关系，所以xRx且xS为故xRSx,从而RS是自反的。a,bA

44、,aRSb,即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bRSa从而RS是对称的。a,b,cGA,aRSb且bRSc,即aRb,aSb,bRc且bSo因为R和S都是A上的等价关系，所以aRc且aSo故aRSo从而RS是传递的。故RS是A上的等价关系。11、设RAXA,则R自反IaRo证明：xA,R是自反的，xRxo即R,故IaR。xA,IaR,R。即xRx,故R是自反的。12、设A是集合，RAXA,则R是对称的R=Ri。证明：R,R是对称的，yRx。即R,故R-1。从而RR1。反之R-1,即RoR是对称的，yRXo即R,R-1R。故R=R1。x,yA,若R,即R1。R

45、=R1,R即yRx,故R是对称的。13、设A,B,C和D均是集合，RAXB,SBXC,TCXD,则(ST)=(RS)(RT)；(ST)(RS)(RT)；证明:(1)（ST）,则由合成关系的定义知yB,使得R!LSTo从而R且S或R且T,BPRSRTo故(RS)(RT)。从而R(ST)(RS)14、设证明:(RT)。同理可证（RS）故R(ST)=(R(2)R且T,即x,A,为偏序集,S)(Sz设15、设a,b都是B的最大元,的。A=1,2,3,写出下列图示关系的关系矩阵,1(1)(2)(3)16、(1)(2)(3)解:(RT),T)R(ST)o(RT)。则由合成关系的定义知yB,使得R且S从而R且SRS且RTo故(RS)(RT)从而R(ST)(RS)(RT)。BA,若B有最大（小）元、上（下）确界，则它们是惟一的。则由最大元的定义ab,ba。并讨论它们的性质:1是A上的偏序关系,a=bo即B如果有最大元则它是惟一R=,;Mr=1；它是反自反的、反对称的、传递的;R=,;MR=1；它是反自反的、对称的;R=,;Mr=1A=1,2-；10o下列哪个是A的划分若是划分,B=1,3,6,2,8,10,4,5,7;C=1,5,7,