《离散数学》题库大全及答案.doc

离散数学题库答案课程内容涉及1集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数 2图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用 3代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数 4组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理 5数理逻辑部分：命题逻辑、一阶谓词演算、消解原理 离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。教学方式以课堂讲授为主, 课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。 编辑本段相关文献【1】 耿素云，屈婉玲.离散数学（国家十五规划教材）.高教出版社，2004。 【2】 袁崇义，屈婉玲，王捍贫，刘田.离散数学及其应用（第4版，译著）.机械工业出版社，2002。 【3】 陆钟万.计算机科学中的数理逻辑.科学出版社，2002。 【4】 哈密尔顿，朱水林译.数理逻辑.华东师大出版社，1987。 【5】 耿素云.离散数学习题集-数理逻辑与集合论分册.北大出版社，1993。 【6】 张立昂.离散数学习题集-抽象代数分册.北大出版社，1990。 【7】 耿素云.离散数学习题集-图论分册.北大出版社，1990。 【8】 离散数学习题辅导软件 【9】 命题逻辑教学软件 【10】离散数学教程，耿素云，屈婉玲, 王捍贫，北京大学出版社，2002。 【11】discrete mathematics and its applications,sixth edition，kenneth h.rosen discrete mathematics and its applications此书的价值已经被全世界几百所大学所证实,作为离散数学领域的经典教材,全世界几乎所有知名的院校都曾经使用本书作为教材.以我个人观点看来,这本书可以称之为离散数学百科.书中不但介绍了离散数学的理论和方法,还有丰富的历史资料和相关学习网站资源.更为令人激动的便是这本书少有的将离散数学理论与应用结合得如此的好.你可以看到离散数学理论在逻辑电路,程序设计,商业和互联网等诸多领域的应用实例.本书的英文版(第六版)当中更增添了相当多的数学和计算机科学家的传记,是计算机科学历史不可多得的参考资料.作为教材这本书配有相当数量的练习.每一章后面还有一组课题,把学生已经学到的计算和离散数学的内容结合在一起进行训练.这本书也是我个人在学习离散数学时读的唯一的英文教材,实为一本值得推荐的好书。 离散数学题库答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)q=qp (2)q=pq (3)p=pq (4)p(pq)=p 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(pq)(qr) (2)p(qq) (3)(pq)p (4)p(pq)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)p=pq (2) pq=p (3) pq=pq (4)p(pq)=q (5) (pq)=p (6) p(pq)=p答：（2），（3），（4），（5），（6）4、公式x(a(x)b(y，x) $z c(y，z)d(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z5、判断下列语句是不是命题。若是，给出命题的真值。( )(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） （2） （3） （4）8、设个体域为整数集，则下列公式的意义是( )。(1) x$y(x+y=0) (2) $yx(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=09、设全体域d是正整数集合，确定下列命题的真值：(1) x$y (xy=y)()(2) $xy(x+y=y)()(3) $xy(x+y=x) ()(4) x$y(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是负数”的否定是（ ）。答：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) (3) (4) 答：(4)18、若集合s的基数|s|=5，则s的幂集的基数|p(s)|=（ ）。答：3219、设p=x|(x+1)4且xr,q=x|5x+16且xr,则下列命题哪个正确（ ） (1) qp(2) qp(3) pq(4) p=q答：（3）20、下列各集合中，哪几个分别相等( )。(1) a1=a,b (2) a2=b,a (3) a3=a,b,a (4) a4=a,b,c(5) a5=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=，则下列哪个结论不可能正确？( )(1) a= (2) b=(3) ab (4) ba答：（4）22、判断下列命题哪个为真?( )(1) a-b=b-a = a=b (2) 空集是任何集合的真子集(3) 空集只是非空集合的子集 (4) 若a的一个元素属于b，则a=b答：（1）23、判断下列命题哪几个为正确？()(1) , (2) , (3) (4) (5) a,ba,b,a,b答：（2），（4）24、判断下列命题哪几个正确？()(1) 所有空集都不相等 (2) (4) 若a为非空集，则aa成立。答：（2）25、设ab=ac，b=c，则b()c。答：=（等于）26、判断下列命题哪几个正确？()(1) 若abac，则bc (2) a,b=b,a (3) p(ab)p(a)p(b) （p(s)表示s的幂集）(4) 若a为非空集，则aaa成立。答：（2） 27、，是三个集合，则下列哪几个推理正确：(1) ab，bc= ac (2) ab，bc= ab (3) ab，bc= ac答：（1） （二元关系部分）28、设1,2,3,4,5,6，b=1,2,3，从到b的关系x,y|x=y2，求(1)r (2) r-1 。答：（1）r=, (2) r=,29、举出集合a上的既是等价关系又是偏序关系的一个例子。()答：a上的恒等关系30、集合a上的等价关系的三个性质是什么？( )答：自反性、对称性和传递性31、集合a上的偏序关系的三个性质是什么？( )答：自反性、反对称性和传递性32、设s=,，上的关系1,2，2,1，2,3，3,4求(1)rr (2) r-1 。答：rr =1,1，1,3，2,2，2,4r-1 =2,1，1,2，3,2，4,333、设1，2，3，4，5，6，是a上的整除关系，求r= ()。答：r=,34、设1,2,3,4,5,6，b=1,2,3，从到b的关系x,y|x=2y，求(1)r (2) r-1 。答：（1）r=, (2) r=,(3635、设1,2,3,4,5,6，b=1,2,3，从到b的关系x,y|x=y2，求r和r-1的关系矩阵。答：r的关系矩阵= r的关系矩阵=36、集合a=1,2,10上的关系r=|x+y=10,x,ya，则r 的性质为（ ）。(1) 自反的(2) 对称的 (3) 传递的，对称的 (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,xg，ax=b，则x=( )；(2) 若a,b,xg，ax=ab，则x=( )。答： （1） ab （2） b40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。答： 6,441、代数系统是一个群，则g的等幂元是()。答：单位元42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。答：5，1043、群的等幂元是()，有()个。答：单位元，144、素数阶群一定是( )群, 它的生成元是( )。答：循环群，任一非单位元45、设g,*是一个群，a,b,cg，则(1) 若ca=b，则c=( )；(2) 若ca=ba，则c=( )。答：（1） b (2) b46、是的子群的充分必要条件是( )。答：是群 或 a，b g， abh，a-1h 或 a,b g，ab-1h 47、群a,*的等幂元有()个，是()，零元有()个。答：1，单位元，048、在一个群g,*中，若g中的元素a的阶是k，则a-1的阶是( )。答：k49、在自然数集n上，下列哪种运算是可结合的？（ ） (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)（图论部分）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答：（2）56、一个图的哈密尔顿路是一条通过图中( )的路。答：所有结点一次且恰好一次57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。答：以v为起点的边的条数， 以v为终点的边的条数58、设g是一棵树，则g 的生成树有( )棵。(1) 0(2) 1(3) 2(4) 不能确定答：159、n阶无向完全图kn 的边数是( )，每个结点的度数是( )。答：, n-160、一棵无向树的顶点数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是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。答：（3）67、设t=v,e是一棵树，若|v|1，则t中至少存在( )片树叶。答：268、任何连通无向图g至少有( )棵生成树，当且仅当g 是( )，g的生成树只有一棵。答：1，树69、设g是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。答：（1）70、设t是一棵树，则t是一个连通且( )图。答：无简单回路71、设无向图g有16条边且每个顶点的度数都是2，则图g有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16答：（4）72、设无向图g有18条边且每个顶点的度数都是3，则图g有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12答：(4)73、设图g=，v=a，b，c，d，e，e=,则g是有向图还是无向图？答：有向图74、任一有向图中，度数为奇数的结点有()个。答：偶数75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由()条边围成？(1) 2(2) 4(3) 3(4) 5答：（3）76、在有n个顶点的连通图中，其边数（ ）。(1) 最多有n-1条(2) 至少有n-1 条(3) 最多有n条 (4) 至少有n 条答：（2）77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。(1) 5(2) 7 (3) 8 (4) 9答：（4）78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。(1) n(2) 2n (3) n-1 (4) 2答：（1）79、下列哪一种图不一定是树（ ）。(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图答：（3）80、连通图g是一棵树当且仅当g中（ ）。(1) 有些边是割边(2) 每条边都是割边(3) 所有边都不是割边 (4) 图中存在一条欧拉路径答：（2）（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式： 1、(pq)r 解：(pq)r(pq )r(pr)(qr) （析取范式）(p(qq)r)(pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)（主析取范式）(pq)r)(pqr)(pqr)(pqr) (pqr)( pqr)（原公式否定的主析取范式）(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)（主合取范式）2、(pr)(qr)p 解： (pr)(qr)p（析取范式）(p(qq)r)(pp)qr)(p(qq)(rr)(pqr)(pqr)(pqr)(pqr)( pqr)( pqr)(pqr)(pqr) (pqr)(pqr)(pqr)(pqr) (pqr)(pqr) (主析取范式)（(pr)(qr)p）(pqr)(pqr）（原公式否定的主析取范式）(pr)(qr)p (pqr)(pqr)（主合取范式）3、(pq)(rp)解：(pq)(rp)(pq)(rp)（合取范式）(pq(rr)(p(qq)r)(pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)（主合取范式） (pq)(rp)(pqr)(pqr)(pqr)(pqr)(pqr)（原公式否定的主合取范式）(pq)(rp)(pqr)(pqr)(pqr)(pqr)(pqr)（主析取范式）4、q(pr) 解：q(pr)qpr（主合取范式）（q(pr)）(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr）（原公式否定的主合取范式）q(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr）（主析取范式）5、p(p(qp) 解：p(p(qp)p(p(qp)pp t (主合取范式)(pq)(pq)(pq)(pq)（主析取范式）6、(pq)(rp)解： (pq)(rp)(pq)(rp)(pq)(rp)（析取范式）(pq(rr)(p(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)（主析取范式）(pq)(rp)(pqr)(pqr)(pqr)(pqr)(pqr)（原公式否定的主析取范式）(pq)(rp)(pqr)(pqr)(pqr)(pqr)(pqr)（主合取范式）7、p(pq) 解：p(pq)p(pq)(pp)qt(主合取范式)(pq)(pq)(pq)(pq)（主析取范式）8、(rq)p解：(rq)p(rq )p(rp)(qp) （析取范式）(r(qq)p)(rr)qp)(rqp)(rqp)(rqp)(rqp)(pqr)(pqr)(pqr)（主析取范式）(rq)p)(pqr)(pqr）(pqr) (pqr)(pqr)（原公式否定的主析取范式）(rq)p(pqr)(pqr)(pqr)(pqr)(pqr)（主合取范式）9、pq 解：pqpq（主合取范式）(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq)（主析取范式）10、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)q(pr)q(pq)(rq)（合取范式）(pq(rr)(pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)（主合取范式）（pr）q (pqr)(pqr)(pqr)(pqr)(pqr) （原公式否定的主析取范式）（pr）q(pqr)(pqr)(pqr)(pqr)(pqr)（主析取范式）13、（pq）r解：（pq）r(pq)r(pq)r(析取范式)(pq(rr)(pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式）（pq）r(pq)r(pq)r(析取范式)(pr)(qr)(合取范式)(p(qq)r)(pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主合取范式)14、(p(qr)(p(qr)解：(p(qr)(p(qr)(p(qr)(p(qr)(pq)(pr)(pq)(pr)（合取范式）(pq(rr)(p(qq)r)(pq(rr)(p(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主合取范式)(p(qr)(p(qr)(pqr)(pqr)(原公式否定的主合取范式)(p(qr)(p(qr)(pqr)(pqr)(主析取范式)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)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)三、证明：1、pq，qr，r，sp=s证明：(1) r 前提(2) qr 前提(3) q （1），（2）(4) pq 前提(5) p （3），（4）(6) sp 前提(7) s （5），（6）2、a(bc)，c(de)，f(de),a=bf证明： (1) a 前提(2) a(bc) 前提 (3) bc （1），（2）(4) b 附加前提(5) c （3），（4）(6) c(de) 前提(7) de （5），（6）(8) f(de) 前提(9) f （7），（8）(10) bf cp 3、pq， pr, qs = rs证明：(1) r 附加前提(2) pr 前提(3) p （1），（2）(4) pq 前提(5) q （3），（4）(6) qs 前提(7) s （5），（6）(8) rs cp，（1），（8）4、(pq)(rs)，(qw)(sx)，(wx)，pr = p证明： （1） p 假设前提（2） pr 前提（3） r （1），（2）（4） (pq)(rs) 前提（5） pq （4）（6） rs （5）（7） q （1），（5）（8） s （3），（6）（9） (qw)(sx) 前提（10） qw （9）（11） sx （10）（12） w （7），（10）（13） x （8），（11）（14） wx （12），（13）（15） (wx) 前提（16） (wx)(wx) （14），（15）5、(uv)(mn), up, p(qs)，qs =m 证明：(1) qs 附加前提（2） p(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，(ef)d，e=b证明：(1) b 附加前提(2) bd 前提 (3) d （1），（2）(4) (ef)d 前提(5) (ef) （3），（4）(6) ef （5）(7) e （6）(8) e 前提(9) ee （7），（8）7、p(qr)，r(qs) = p(qs)证明：（1） p 附加前提（2） q 附加前提（3） p(qr) 前提（4） qr （1），（3）（5） r （2），（4）（6） r(qs) 前提（7） qs （5），（6）（8） s （2），（7）（9） qs cp，（2），（8）（10） p(qs) cp，（1），（9）8、pq，pr，rs =sq 证明：（1） s 附加前提（2） rs 前提（3） r （1），（2）（4） pr 前提（5） p （3），（4）（6） pq 前提（7） q (5），（6）（8） sq cp，（1），（7）9、p(qr) = (pq)(pr)证明：(1) pq 附加前提(2) p 附加前提(3) q (1),(2)(4) p(qr) 前提(5) qr (2),(4)(6) r (3),(5)(7) pr cp,(2),(6)(8) (pq) (pr) cp,(1),(7)10、p(qr)，qp,sr,p =s证明：（1） p 前提（2） p(qr) 前提（3） qr (1)，(2)（4） qp 前提（5） q (1)，(4)（6） r (3),(5)（7） sr 前提（8） s (6)，(7)11、a，ab， ac， b(dc) = d证明：（1） a 前提（2） ab 前提（3） b (1)，(2)（4） ac 前提（5） c (1)，(4)（6） b(dc) 前提（7） dc (3)，(6)（8） d (5)，(7)12、a(cb)，ba，dc = ad证明：（1） a 附加前提(2) a(cb) 前提 (3) cb （1），（2）(4) ba 前提(5) b （1），（4）(6) c （3），（5）(7) dc 前提(8) d （6），（7）(9) ad cp，（1），（8）13、(pq)(rq) （pr）q证明、(pq)(rq) (pq)(rq)(pr)q （pr）q(pr)q14、p(qp)p(pq)证明、p(qp)p(qp)(p)(pq)p(pq)15、（pq）（pr），(qr)，sps证明、(1) （pq）（pr） 前提 （2） p (qr) (1) （3） (qr) 前提 （4） p （2），(3) (5) sp 前提 (6) s (4),(5)16、pq，qr，rs p证明、(1) p 附加前提 （2） pq 前提 （3） q （1），（2） （4） qr 前提 (5) r （3），（4） (6 ) rs 前提 （7） r （6） （8） rr （5），（7）17、用真值表法证明 ()()证明、列出两个公式的真值表：p q pq （pq）（qp） f ff tt ft tt tf ff ft t由定义可知，这两个公式是等价的。18、pqp(pq)证明、设p(pq)为f，则p为t，pq为f。所以p为t，q为f ，从而pq也为f。所以pqp(pq)。19、用先求主范式的方法证明(pq)(pr) (p（qr）证明、先求出左右两个公式 的主合取范式(pq)(pr) (pq)(pr) (pq(rr)(p(qq)r) (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr) (p（qr）) (p（qr）) (pq)(pr)(pq(rr)(p(qq)r) (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)它们有一样的主合取范式，所以它们等价。20、(pq)(qr) p证明、设(pq)(qr)为t，则pq和(qr)都为t。即pq和qr都为t。故pq，q和r)都为t，即pq为t，q和r都为f。从而p也为f，即p为t。从而(pq)(qr) p21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?前提: (1) 若a队得第一，则b队或c队获亚军;(2) 若c队获亚军，则a队不能获冠军;(3) 若d队获亚军，则b队不能获亚军;(4) a 队获第一;结论: (5) d队不是亚军。证明、设a：a队得第一;b: b队获亚军;c: c队获亚军;d: d队获亚军;则前提符号化为a（bc），ca，db，a；结论符号化为 d。 本题即证明 a（bc），ca，db，ad。（1） a 前提 （2） a（bc）前提 （3） bc （1），（2） （4） ca 前提 （5） c （1），（4） （6） b （3），（5） （7） db 前提 （8） d （6），（7）22、用推理规则证明pq, (qr),pr不能同时为真。证明、 (1) pr 前提 (2) p (1) (3) pq 前提 (4) q (2),(3) (5) (qr) 前提 (6) qr (5) (7) q (6) (8) qq (4),(7)(集合论部分)四、设，是三个集合，证明：1、a (bc)(ab)(ac) 证明：(ab)(ac)= (ab) =(ab) （）=(ab)(ab)= ab=a（b）=a（b-c）2、(ab)(ac)=a(bc)证明：(a-b)(a-c)=(a)(a) =a ()=a= a-(bc)3、ab=ac，b=c，则c=b证明：b=b(a)=(b) (ba)=(c) (ca)=c(a)=c 4、ab=a(b-a)证明： a(b-a)=a(b)=(ab)(a)=(ab)u= ab5、a=b ab= 证明：设a=b，则ab=（a-b）（b-a）=。设ab=，则ab=（a-b）（b-a）=。故a-b=，b-a=，从而ab，ba，故a=b。6、ab = ac，ab=ac，则c=b证明：b=b(ab)= b(ac)= (ba)(bc)= (ac)(bc)= c(ab)= c(ac)=c7、ab=ac，b=c，则c=b 证明：b=b(a)=(ba)(b)=(ca)(c)=c(a)=c8、a(bc)(ab)c证明：a(bc)= a=a()=(a)=(a-b)=(a-b)-c9、(ab)(ac)=a(bc)证明：(a-b)(ac)=(a)(a)=(aa)()=a=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) =(a)(a) =a()=a= a-(bc)，且a=(a-b)(a-c)， 所以a= a-(bc)，故abc=。 因为abc=，所以a-(bc)=a。而a-(bc)= (a-b)(a-c)， 所以a=(a-b)(a-c)。12、(a-b)(a-c)=abc证明： 因为(a-b)(a-c) =(a)(a) =a()=a= a-(bc)，且(a-b)(a-c)=， 所以= a-(bc)，故abc。 因为abc，所以a-(bc)=a。而a-(bc)= (a-b)(a-c)， 所以a=(a-b)(a-c)。13、(a-b)(b-a)=a b=证明： 因为(a-b)(b-a)=a，所以b-aa。但(b-a)a=，故b-a=。 即ba，从而b=（否则a-ba，从而与(a-b)(b-a)=a矛盾）。 因为b=，所以a-b=a且b-a=。从而(a-b)(b-a)=a。14、(a-b)-ca-(b-c)证明：x(a-b)-c，有a-b且xc，即a，xb且xc。从而a，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)。即p(a)p(b)p(ab)。sp(ab)，有sab，所以sa且sb。从而sp(a)且sp(b)，故sp(a)p(b)。即p(ab)p(a)p(b)。 故p(ab)=p(a)p(b)17、（a-b）b=（ab）-b当且仅当b=。证明：当b=时，因为（a-b）b=（a-）=a，（ab）-b=（a）- =a，所以（a-b）b=（ab）-b。用反证法证明。假设b，则存在bb。因为bb且b ab，所以b（ab）-b。而显然b（a-b）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，对任意自然数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=z。2、设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