《离散数学》题库及答案

1、离散数学题库与答案一、选择或填空(数理逻辑部分)1、下列哪些公式为永真蕴含式？()(1) q=qpp (2)q=pq p=p-q (4) -pa(pvq)=-p答：在第三章里面有公式(1)是附加律，(4)可以由第二章的蕴含等值式求出(注 意与吸收律区别)2、下列公式中哪些是永真式？()(1)( 1 pr、q)f(qfr) (2)p -(qfq) (3)(p aq)-p (4)p -(pq)答：(2), (3), (4)可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式 ?()p=p q p q=p p q=pqp a(p -q)=q (5)(p-q)=p (6) -pa(pvq)=-p

2、答：(2)是第三章的化简律，(3)类似附加律，(4)是假言推理，(3),(5),(6)都可以用蕴含等值式来证明出是永真蕴含式4、公式 vx(a(x) t b(y, x)八 3z c(y , z) t d(x)中，自由变元是()， 约束变元是()。答：x,y, x,z (考察定义在公式vx a和三x a中，称x为指导变元，a为量词的 辖域。在vx a和双a的辖域中，x的所有出现都称为约束出现，即称 x为 约束变元，a中不是约束出现的其他变项则称为自由变元。 于是a(x)、b(y, x)和三z c(y , z)中y为自由变元，x和z为约束变元，在 d(x)中x为自由 变元)5、判断下列语句是不是命

3、题。若是，给出命题的真值。 ()(1)北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗？(4) 若7+8 18,则三角形有4条边。 前进！ (6)给我一杯水吧！答：(1)是，t(2)是，f(3)不是(4)是，t (5)不是(6)不是(命题必须满足是陈述句，不能是疑问句或者祈使句。)6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都 是要死的”的否定是()。答：所有人都不是大学生，有些人不会死(命题的否定就是把命题前提中的量词“ v换 成存在工换成v”，然后将命题的结论否定，“且变或 或变且)7、设p:我生病，q:我去学校，则下列命题可符号化为()。(1)只有

4、在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：(1) qt p (注意只有才”和除非就”两者都是一个形式的)(2) pt -q(3) piq(4)pt q8、设个体域为整数集，则下列公式的意义是()。(1)-x y(x+y=0) (2)y-x(x+y=0)答：(1)对任一整数x存在整数y满足x+y=0(2)存在整数y对任一整数x满足x+y=09、设全体域d是正整数集合，确定下列命题的真值：(1) -x y (xy=y) ()(2)x-y(x+y=y)()(3) x - y(x+y=x) ()(4) - x y(y=2x

5、)()答：(1) f (反证法：假若存在，则(x-1 ) *y=0对所有的x都成立，显然这个与 前提条件相矛盾)(2) f (同理) (3) f (同理) (4) t (对任一整数x存在 整数y满足条件y=2x很明显是正确的)10、设谓词p(x) : x是奇数，q(x): x是偶数，谓词公式3x(p(x) vq(x) 在哪个个体域中为真?() 自然数 (2)实数 (3)复数 (4) (1)-(3) 均成立答：(1)(在某个体域中满足不是奇数就是偶数，在整数域中才满足条件，而自然数子整数的子集，当然满足条件了)11、命题“ 2是偶数或-3是负数”的否定是()。答：2不是偶数且-3不是负数。12、

6、永真式的否定是()永真式(2)永假式(3)可满足式(4) (1)-(3)均有可能答：(2)(这个记住就行了)13、公式(pnq)人paq)化简为()，公式qt (pv(paq)可化简为()。答：p , a p (考查分配率和蕴含等值式知识的掌握)14、谓词公式vx(p(x) 7三yr(y) t q(x)中量词vx的辖域是()。答：p(x) 7三yr(y)(一对括号就是一个辖域)15、令r(x):x是实数，q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为()。答：-x(r(x) q(x)(集合论部分)16、设人=依,但,下列命题错误的是()。(1) a p(a) (2) a

7、p(a) (3) a p(a) (4) a p(a) 答：(2) (a是p (a)的一个元素)17、在0 ()之间写上正确的符号。(1) =(2)(3)(4)答：(4)(空集没有任何元素，且是任何集合的子集)18、若集合s的基数|s|=5 ,则s的募集的基数|p(s)|=()。答：32 (2的5次方 考查募集的定义，即募集是集合 s的全体子集构成的集合)19、设p=x(x+1) %4且xwr,q=x|5 a=b (2)空集是任何集合的真子集(3)空集只是非空集合的子集(4) 若a的一个元素属于b,则a=b答：(1)(考查空集和差集的相关知识)23、判断下列命题哪几个为正确？(), (2) ,

8、(3) (4)三 (5) a,b6 a,b,a,b答：(2), (4)24、判断下列命题哪几个正确？() 所有空集都不相等(2) #(4) 若a为非空集，则a二a成立。答：(2)25、设 aa b=ah c, a a b=a a c,贝u b( )c。答：=(等于)26、判断下列命题哪几个正确？(1)若 au b= au c,则 b= c (2) a,b=b,a(3) p(a a b) # p(a) a p(b) (p(s)表示 s 的募集)(4)若a为非空集，则a#au a成立。答：(2)27、a, b, c是三个集合，则下列哪几个推理正确: (1) a 三 b, bc= a=c (2) a

9、 = b, bc= as b (3) a sb, b6 c= as c答：(1)(3)的反例c为 0, 1, 0 b为0, 1, a为1很明显结论不对)(二元关系部分)28、设人=1,2,3,4,5,6 ,b=1,2,3，从 a到 b 的关系 r= x,y|x=y2 求(1)r (2) r -1答：(1) r=, (2) r=,(考查二元关系的定义，r,为 r 的逆关系，即 r= | r)29、举出集合a上的既是等价关系又是偏序关系的一个例子。()答：a上的恒等关系30、集合a上的等价关系的三个性质是什么？()答：自反性、对称性和传递性31、集合a上的偏序关系的三个性质是什么？()答：自反性、

10、反对称性和传递性(题29, 30, 31全是考查定义)32、设 s= 1 , 2 , 3 , 4 , a上的关系区=1,2，2,1，2,3，3,4求(1)r *(2) r -1 。答：r*r =1,1，1,3，2,2，2,4(考查 f*g=| 三t( 6 fa6g)r1 = 2,1，1,2，3,2，4,333、设人=1, 2, 3, 4, 5, 6, r是a上的整除关系，求r=()r=,34、设人=1,2,3,4,5,6 ,b=1,2,3，从 a到 b 的关系 r= |x=2y ,求(1)r (2) r -1 。答：(1) r=, (2) r=,(3635、设人=1,2,3,4,5,6 ,b=

11、1,2,3，从a到 b的关系r= |x=y2, 求r和r1的关系矩阵。一1 00 0答：r的关系矩阵=0 00 10 00 00100000一1r的关系矩阵=0-00 0 0 0 00 0 10 00 0 0 0 036、集合 a=1,2, - -,10上的关系 r=|x+y=10,x,y wa,则 r 的性质 自反的 （2）对称的 （3）传递的，对称的（4）传递的答：（2）（考查自反对称传递的定义）（代数系统部分）37、设a=2,4,6 , a上的二元运算*定义为：a*b=maxa,b,则在独异点 a,*中，单位元是（），零元是（）。答：2,6 （单位元和零元的定义，单位元：e。x=x 零元

12、：0 o x= 0 ）38、设a=3,6,9 , a上的二元运算*定义为：a*b=mina,b,则在独异点 a,*中，单位元是（），零元是（）；答：9, 3（半群与群部分）39、设g,*是一个群，则（1） 若 a,b,x 6 g a*x=b,则 x=（）;（2） 若 a,b,x 6 g a*x=a*b,则 x=（）。答：（1） a-b（2） b （考查群的性质，即群满足消去律）40、设a是12阶群的生成元，则3是（）阶元素，/是（） 阶元素。答：6,441、代数系统g,*是一个群，则g的等哥元是（）。答：单位元（由aa2=a,用归纳法可证aan=a*aa（n-1）=a*a=a,所以等幕元一定是

13、嘉等元， 反之若aan=a对一切n成立，则对n=2也成立，所以幕等元一定是等幕元，并且在 群 g,*中，除幺元即单位元e外不可能有任何别的事等元）42、设a是10阶群的生成元， 则/是（）阶元素，了是（） 阶元素答：5, 10（若一个群g的每一个元都是 g的某一个固定元 a的乘方，我们就把g叫做循环群；我们也说， g是由元a生成的，并且用符号 g=a表示，且称a 为一个生成元。并且一元素的阶整除群的阶）43、群g,*的等哥元是（），有（）个。答：单位元，1 （在群g,*中，除幺元即单位元e外不可能有任何别的幕 等元）44、素数阶群一定是（） 群，它的生成元是（）。答：循环群，任一非单位元（证明

14、如下：任一元素的阶整除群的阶。现在群的阶是素数p,所以元素的阶要么是1要么是p。g中只有一个单位元，其它元素的阶都不等于1, 所以都是p。任取一个非单位元，它的阶等于 p,所以它生成的g的循环子群的阶也是 p,从而等于整个群go所以g等于它的任一非单位元生成的循环群）45、设g,*是一个群，a,b,c 6 g 则（1）若 c*a=b,则 c=（ ）; （2） 若 c*a=b*a,则 c=（）。答：（1） b*a，（2） b（群的性质）46、$*是6的子群的充分必要条件是（）。答：h, * 是群或 v a , b w g a * bw h, a-1 w h 或v a,b g g, a* b-1

15、w h47、群 a,* 的等哥元有（）个，是（），零元有（）个。答：1,单位元，048、在一个群g,*中，若g中的元素a的阶是k,则a1的阶是（）。答：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阶有限群的任何子群一定不是（）。2阶 （2） 3 阶（3） 4 阶 （4） 6 阶答：（3）（格与布尔代数部分）52、下列哪个偏序集构成有界格（）（n,

16、）（2）（z, ）（2,3,4,6,12,| （整除关系）（4） （p（a）,三）答：（4）（考查募集的定义）53、有限布尔代数的元素的个数一定等于（）。（1） 偶数（2） 奇数（3） 4 的倍数 （4） 2的正整数次募答：（4）（图论部分）54、设g是一个哈密尔顿图，则 g一定是（） 欧拉图（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、一个

17、图的哈密尔顿路是一条通过图中（） 的路。答：所有结点一次且恰好一次，入度deg（v）表示（）57、在有向图中，结点v的出度deg+（v）表示（）答：以v为起点的边的条数， 以v为终点的边的条数58、设g是一棵树，则g的生成树有（） 棵。0（2）1（3） 2（4）不能确定答：159、n阶无向完全图k的边数是（），每个结点的度数是（）答：n（ n-1 260、一棵无向树的顶点数n与边数m关系是（）。答：m=n-161、一个图的欧拉回路是一条通过图中（） 的回路。答：所有边一次且恰好一次62、有n个结点的树，其结点度数之和是（）。答：2n-2 （结点度数的定义）63、下面给出的集合中，哪一个不是前缀

18、码（）。（1） a , ab, 110, albll （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分别表示顶点数和边数，则 n=m m=n+1 （3） n=m +1 （4） 不能确定。答：（3）67、设丁=v,e是一棵树，若|v|1 ,则t中至少存在（） 片树叶。答：268、任何连通无向图g至少有（）棵生成树，当且仅当g

19、是（），g的生成树只有一棵。答：1,树69、设g是有n个结点m条边的连通平面图，且有k个面，则k等于：（1） m-n+2 n-m-2 n+m-2 m+n+2。答：（1）70、设 t 是一棵树，则 一棵树，则 t 是一个连通且(答：无简单回路71、设无向图g有16条边且每个顶点的度数都是2,则图6有()个顶点。(1) 10 (2) 4 (3) 8 (4) 16答： ( 4)72、设无向图g有18条边且每个顶点的度数都是3,则图6有()个顶点。(1) 10 (2) 4 (3) 8 (4) 12答： (4)73、 设图g=， v=a ， b， c ， d， e ， e=,则g是有向图还是无向图？答：

20、有向图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)

21、 n-1(4) 2答：（1）79、下列哪一种图不一定是树（）。（1）无简单回路的连通图 （2）有n个顶点n-1条边的连通图（3）每对顶点间都有通路的图（4）连通但删去一条边便不连通的图答：（3）80、连通图g是一棵树当且仅当6中（）。（1）有些边是割边（2）每条边都是割边（3）所有边都不是割边（4）图中存在一条欧拉路径答：（2）（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式：1、(p q)八 r解：(p-q) ar= (pvq ) aru ( -par) v(qar)(析取范式)二(-p (q -q) r) ( -p p) q r)二(- p q r) ( - p -q r) ( -

22、 p q r) (p q r)u ( -paqar) v( - paqar)v(paqa r)(主析取范式)(p-q、r)u ( -paqlr)v( -paqa-r) v(pa-qar)v(paqa-r) v( p aqar)(原公式否定的主析取范式)(pfq)aru (p vqvr) a(p v-qvr)a(pvq广r)a( -pv - qvr) a( -pvqvr)(主合取范式)2、(p ar)v(qar)v-p解：(p r) (q r) -p (析取范式)二(p (q - q) r) (p- p) q r) ( - p (q - q) (r - r)二(p q r) (p -q r) (

23、p q r) ( 一 p q r)(pqr) (pq r) (p qr) ( p q - r)=(p q r)(p - q r) ( 一 p q r) ( 一 p q - r)(pa-qar)v(paq,r)(主析取范式)(par) v(qar)v-p)=(p - q - r) (p q - r)(原公式否定的主析取范式)(p r)v(qar)mp u (pmqr)a(pmq“r)(主合取范式)3、(- q)a(rvp)解：(-4q) (r p)二(p vq)a(r vp)(合取范式)=(p q (r -r) (p (q -q) r)=(p q r) (p q -r) (p q r) (p -

24、q r)u (p vqvr) a(pvqv-r)a(p v-qvr)(主合取范式)-(- p- q) (r p)二(p -q -r) (-p q r) ( -p -q r) ( -p q -r)八(px/qvr)(原公式否定的主合取范式)(一 p一 q) (r p)=(一 p q r) (p -q - r) (p q - r) (p -q r) (p q r)(主析取范式)4、ch(p v-r)解：qh (p -r)=-q p -r (主合取范式)(qh(plr)二 (- p -q -r) ( -p -q r) ( - p q - r) ( - p q r)a(p v-qvr) a(p vqv

25、r) a(pvqvr)(原公式否定的主合取范式)qh (p -r)二(p q r) (p q -r) (p -q r) (p -q -r) ( - p q - r) v(paqar)paq.r)(主析取范式)5、pf (pa(qp)解：p- (p 八(q-p)u - p (p ( - q p)u -p pu t (主合取范式)二(p q) (p q) (p q) (p q)(主析取范式)6、-(pq)v(rap)解： -(pq)v(rap) (-pvq)v(rap)u (p a-q)v(rap)(析取范式)匕(p -q (r -r) (p ( -q q) r)二(p -q r) (p -q -

26、r) (p -q r) (p q r)u (paq八 r)v(paqar)m(p 八 q,、r)(主析取范式)-(-(pq)v(rap) u (paq、-r)v( -paqar)v(-paq,lr)v (paqar)v(paqar)(原公式否定的主析取范式)(p-q)(rap)u ( -pv -qv r) a(pv -qv-r)a(pvqv-r) a(puqvr)a(pqvr)(主合取范式)7、pv(pq)解：pv(pq) pv( -pvq) (p v-p) vq仁t(主合取范式)=(p -q) ( -p q) (p -q) (p q)(主析取范式)8、(rq)八 p解：(rq)ap ( -r

27、vq ) apu ( -rap) v(qap)(析取范式)二(一 r (q -q) p) ( -r r) q p)二(一 r q p) ( -r -q p) ( - r q p) (r q p)u (p aqa -r) v(p a - qa - r) v(p aqa r)(主析取范式)(r - q) a p) u ( - pa-qa-r)v(-paqa-r) v (p a qa r) v( ”2困(八9困(原公式否定的主析取范式)(rq)ap (p vqvr) a(p v-qvr)a(pmq 广 r)a (p v -qv - r) a(p vqv - r)(主合取范式)9、pf q解：p- q

28、= - p q (主合取范式)=(一 p (q - q) ( 一 p p) q)=(一 p q) ( 一 p 一 q) ( 一 p q) (p q)之(paq)v(paq)v(paq)(主析取范式)10、 p -q解：p v-q (主合取范式)二(p ( -q q) ( -p p) qq)(p (p - q) (p q) ( - p - q) (p -q二(p aq)m(p aq)v(paq)(主析取范式)11、p q解：p q (主析取范式)=(p (q -q) (p-p) q)=(p -q) (p q) (p q) ( - p q)二(p -q) (p q) ( -p q)(主合取范式)1

29、2、(pvr!) t q解：(pmr) t q匕一(pr)q=(-p -r) q=(pq)( -r q)(合取范式)：三(pq(r-r) (-pp)q-r)二(pqr)( pq-r)( -pq-r)(pq- r)二(pqr)( pq-r)( pq-r)(pq- r)二(-pvqvr)a( -pvqv-r)a(p vqv-r)(主合取范式)(pvr) t q=(-p -q r) ( p -q - r) (p q r) (p -q r) (p -q -r) (原公式否定的主析取范式)(pr) q二(p q -r) (p q r) ( p -q -r) ( - p q - r)v( -paqar)(

30、主析取范式)13、(pt q) t r解：(pt q t ru 一( 一 p q) ru (p aq),r(析取范式)二(p- q(r- r) (p-p)(q- q)r)=(p-qr)(p -q -r)(pqr)(p -qr)( -p q r)(-p -q r)二(p-qr)(p -q -r)(pqr)(-p qr)v( -paqar)(主析取范式)(p q r二一(p q) rv (p aq)vr(析取范式)u (p vr)h(qr)(合取范式)二(p (q q) r) (p-p) -q r)二(p q r) (p -q r) (p -q r) (- p -q r)仁(p vqvr)a(p

31、vqmr)a(pvqmr)(主合取范式)14、(p (q r) ( -p ( -q -r)解：(p (q r) ( -p ( -q -r)=(-p (q r) (p ( -q -r)u (pvq)a(pvr)a(pvq)a(pr)(合取范式)二(一 p q (r -r) ( - p (q -q) r) (p -q (r r)(p (q -q) - r)二(pq r) (一pq -r) (- pq r) (- p-qr)(p-q r) (p -q-r)(pq -r)(pqr)仁(一 pq r) (一 p q -r) (一 p-q r)(p-qr)八(p vqvr)a(p vq*r)(主合取范式)

32、-(p (q r) ( -p ( -q r)u (pvqvr)八(p vqr)(原公式否定的主合取范式)(p (q r) ( -p ( -q -r)二(p aqar)v(paqar)(主析取范式)15、p ( -p (q ( -q r)解：p ( -p (q ( -q r)=p (p (q (q r)u pyqvr(主合取范式)一(p q r)m(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 q -r) ( -p q r) ( -p -q r) (p -q -

33、 r)v(p a- q 八 r)v(p aqa-r) v (p a qa r)(主析取范式)16、(p q) (p r)解、(p q) (p r)仁(-pvq)a(-pvr)(合取范式)二(一 p q (r -r) ( - p ( - q q) r)二(p q r) ( -p q -r) ( -p -q r) (- p q r)u ( -pvqvr)a( -pvqv -r)a( -pvqvr)(主合取范式)(p q) (p r)二(一 p q) ( 一 p r)upm(qar)(合取范式)二(- p (q -q) (r r) ( - p p) q r)二(一 p q r) ( 一 p -q r

34、) ( 一 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 q r)(主析取范式)三、证明：1、p q,q%r,r, -svp=-s证明：(2) 一 q r 一 q(1)r前提前提(1),(4) p - q前提(5) p(3), (4)(6) -svp前提(7) s(5), (6)2、a (bc), c7 (dhe), f7 (dae),a=bf证明：(1) a前提(2) a - (bc)前提(3) b-c(1), (2)(4) b附加前提(5) c(3), (4)(6)

35、 c -(-dve)前提(7) dve(5), (6)(8) f-(dae)前提(9) f，(8)(10) b 一f cp3、pg p - r, q-s = r vs证明:(1) r附加前提p一 r前提p(1),(2)pvq前提(5) q(3),(4)(6) q- s前提s(5),(6)(8) r vs cp , (1), (8)4、(p - q)a(r-s), (q-w)a(s-x),(wx), pf r =p(1) p证明：假设前提(2) p-r前提(3) r(1), (2)(4) (p-q)a(r-s)前提(5) p-q(4)(6) r-s(5)(7) q(1), (5)(8) s(3)

36、, (6)(9) (q-w),、(sx)前提(10) q-w(9)(11) s-x(10)(12) w(7), (10)(13) x(8), (11)(14) w 八x(12), (13)(15) -(wax)前提(16) -(wax) a(wax)(14), (15)5、(u、v)(man), u vp, p-(qms), -qa-s =m证明：(1) -qa-s附加前提(2) p- (qvs)前提(3) p(1),(2)(4) u vp前提(5) u(3),(4)(6) u vv(5)(7) (u w)(man)前提(8) m n (6),(7)(9) m(8)6、bd, (e-f)-d,

37、e=b证明：(1) b附加前提(2) -bvd前提(3) d(1),(4) (e 一f) 一d前提(5) (e-f) (3), (4)(6) e a-f(5)(7) e(6)(8) e前提(9) e a-e，(8)7、p (qr), e(q-s) = p(qs)证明:(10) p附加前提(11) q附加前提(12) p - (qr)前提(13) q-r(1), (3)(14) r(2), (4)(15) r - (q-s)前提(16) q-s(5), (6)(17) s(2),(18) q-scp , (2), (8)(19) p一(qs)cp , (1), (9)8、p-q,r, es =s

38、-q 证明：(1) s附加前提(2) r 一s前提(3) r (1), (2)(4) p一 r前提(5) p(3),(4)(6) p 一q前提(7) q (5 ), (6)(8) s -q cp , (1), (7)9、p (q-r) = (p -q)(pr)证明：(1) p - q 附加前提(2) p附加前提(3) q(1),(2)(4) p - (qr)前提(5) q - r ,(4)(6) r,(5)(7) p -r cp,(2),(6)(8) (p -q) 一(p-r) cp,(1),(7)10、p-(chr), chp,s-r,p=s证明：(1) p前提(2) p 一(qhr)前提(

39、3) -qhr(1), (2)(4) q 一p 前提(5) q(1),(4)(6) r(3),(5)(7) s -r前提(8) s(6),(7)11、a, z b, ac, b (d-c)=d证明：(1) a前提(2) a-b前提(3) b(1), (2)(4) a -c前提(5) c(1), (4)(6) b 一(d-c)前提 d 一c (3), (6)(8) -d (5), (7)12、2 (c vb), b7a,八c = ad证明：(1) a附加前提(2) a一 (cvb)前提(3) c vb(1), (2)(4) b一a前提(5) b(1), (4)(6) c(3),(5)(7) d一

40、c前提(8) d(6), (7)(9) a -d cp , (1), (8)13、(ptq)a(rtq)=(pvr) tq证明、(p q) (r q)二(一 p q) ( -r q)二(一 p -r) q仁(pv r) vq二(p r) q14、p (q p)= -p (p -q)证明、p (q p)之-p ( -q p)二一(一 p) ( 一 p - q)二 一 p (p一. 1q)15、(ptq) a(4r),(qar), sps证明、(pt q) a (pt r)前提(2) p ，(q r) (1)(3) -(qar)前提(4) p(2), (3)(5) svp前提(6) s,(5)16

41、、p，q, q r, r -s-p证明、(1) p附加前提(2) p tq前提(3) q(1), (2)(4) q v -r前提(5) r(3), (4)(6 ) rls 前提(7) r(6)(8) r lr(5), (7)17、用真值表法证明p a q。( pt q) a(qt p)证明、列出两个公式的真值表：pqp修q(pt q)人(a p)ffttftfftffftttt由定义可知，这两个公式是等价的。18、 q pf (p q)证明：设p一(p八q)为f,则p为t, p/vq为f。所以p为t, q为f ,从而p- q也为f。所以 p一 g p一 (p q)。19、用先求主范式的方法证明

42、(p-q)a(p-r)匕(p- (qar)证明：先求出左右两个公式的主合取范式(pq)a(pr) - ( -pvq)a ( -pvr)=(-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 一(qar) ) u ( -pv (qa r)=(-p q) ( -p r)=(p q (r -r)( - p (q -q) r)= (-p q r) ( - p q - r) ( - p q r) ( - p - q r)=(-pq -r) (

43、 - p q r) ( -p -q r)它们有一样的主合取范式，所以它们等价。20、(pq)a-(qvr) =p证明：设(p一q)a1qvr)为t,则 4q和(qmr)都为t。即 4q和q八-1r者b为t 故 4qq和r)都为t,即 4q为t, q和r都为f。从而p也为f,即p为t。 从而(pq)a(qr) =p21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问 结论是否有效？前提：(1)若a队得第一，则b队或c队获亚军；(2)若c队获亚军，则a队不能获冠军；(3)若d队获亚军，则b队不能获亚军；(4) a队获第一；结论：d 队不是亚军。证明：设a: a队得第一；b: b队获亚

44、军;c: c队获亚军；d: d队获亚军；则前提符号化为 at (bvc), cta, ab, a；结论符号化为 d。本题即证明at (by。，ca, d-b, a=d(1) a前提(2) at (b,c)前提(3) b 7c (1), (2)(4) c ta前提(5) c (1), (4)(6) b(3), (5)(7) dtb 前提(8) d (6), (7)22、用推理规则证明ptq,(qvr),p ar不能同时为真。 证明：(1) par前提(2) p(1)(3) pt q前提q(2),(3)(5) -(qvr) 前提(6) -q -r(5)(7) q(6)(8) -q q(4),(7)

45、(集合论部分)四、设a, b, c是三个集合，证明：1、ac (b c)=(acb) (acc)证明：(acb) (acc尸(acb) c a-c =(acb) c (a=c) 二(ac be a) = (a c be c尸 a c bc c =a (b c ) =ac (b-c)2、(ab)=(a c尸a (bc)证明：(a-b)(a-c)=(a - b) (a _ c) =a ( b . c)=a - b - c = a-(b - c)3、a，jb=a c, aub=ac,贝 u c=b证明：b=b_. ( a - a)=(b a) (b 一 a)=(c a) - (c a)=c ( a

46、- a)=c4、a，jb=a (b-a)证明：a 一(b-a尸a 一(b - a)=(a b) - (a 一 a)=(a 一 b) - u= a_. b5、a=b a 学 bw证明：二设 a=b 贝uas)b= (a-b) u (b-a) =6 = 6=9。u 设 a$b=6 ,贝u a5 b= (a-b) = (b-a) =6。故 a-br , b-a=6 , 从而ab, ba,故a=b6、acb = acc, aub=a，c,贝 u c=b证明：b=b- (a b)= b (a c)= (b - a) 一(b - c)=(a c c) u (b n c尸 c c (au b)=c - (a

47、 一 c)=c7、acb=ac, acb=acc,贝 u c=b证明：b=b- (a - a)=(b - a) (b 一 a)=(c - a) 一 (c - a)=c - (a a)=c8、a- (bc)=(a-b)-c证明：a- (b . c)= a - b - c=a- ( b - c)=(a - b) - c=(a-b) - c=(a-b)-c9、(ab)c(a c尸a (b = c)证明：(a-b) c(ac)=(a - b) - (a - c)=(a - a) - ( b - c)=a - b 一 c=a (b - c)10、a-b=b,贝u a=b=证明：因为 b=a-b,所以 b

48、=b b= (a-b) c bw。从而 a=a-b=b=。11、a=(a-b) 一 (a-c)= a b - c=；，证明：二 因为(a-b) =(a-c) =(a c b)=(acc) =ac(b = c)=a，n b-c = a-(b c c),且 a=(a-b) u (a-c),所以 a= a-(b c c),故 ac be cn 0u 因为 ac be cr ,所以 a-(b c c尸a。而 a-(b c c)= (a-b) = (a-c), 所以 a=(a-b) 2 (a-c)。12、(a-b) - (a-c)= :，ma b_ c证明：二 因为(a-b) c(a-c) =(a c

49、b) c(ac c) =a c(bc c)=a，n b-c = a-(b uc),且(a-b) c (a-c尸 , 所以 g = a-(b =c),故 a1bc。u 因为 aj bj c,所以 a-(b = c尸a。而 a-(b= c)= (a-b) c (a-c), 所以 a=(a-b) c (a-c)。13、(a-b) - (b-a)=a = b= 证明：二因为(a-b) =(b-a尸a,所以 b-a = a。但(b-a) c a# ,故 b-a=6。即bja,从而br (否则a-b匚a,从而与(a-b) = (b-a)二a矛盾)。u 因为b=g ,所以 人6=人且b-a=g。从而(a-b) = (b-a)=a。14、(a-b)-c a-(b-c)证明：v xe(a-b)-c ,有 xwa-b 且 xc,即 xa, xb 且 xc。从而 xa, xb-c,故 xwa-(b-c)。从而(a-b)-c a-(b-c)15、p(a)up(b)=p(a=b) (p(s)表示 s 的募集) 证明：v s三 p(a) = p(b),有 s三 p(a)或 sw p(b),所以 s1 a或 sc