山东大学离散数学题库及答案.docx

山东大学离散数学题库及答案 离散数学题库答案 一、选择或填空 1、下列哪些公式为永真蕴含式？( ) (1)ØQ=>QP (2)ØQ=>PQ (3)P=>PQ (4)ØPÙ(PÚQ)=>ØP 答：， 2、下列公式中哪些是永真式？( ) (1)(PÙQ)(QØR) (2)P(QQ) (3)(PÙQ)P (4)P(PÚQ) 答：， 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>PÙQ (2) PÙQ=>P (3) PÙQ=>PÚQ (4)PÙ(PQ)=>Q (5) Ø(PQ)=>P (6) ØPÙ(PÚQ)=>ØP 答：， 4、公式"x(A(x)®B(y，x)Ù $z C(y，z)®D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答： 是，T 是，F 不是 是，T 不是 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答： ØQ®P P®ØQ P«ØQ ØP®Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) "x$y(x+y=0) (2) $y"x(x+y=0) 答：对任一整数x存在整数 y满足x+y=0存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) "x$y (xy=y) ( ) (2) $x"y(x+y=y) ( ) (3) $x"y(x+y=x) ( ) (4) "x$y(y=2x) ( ) 答： F F F T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)ÚQ(x)在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)-(3)均成立 答： 11、命题“2是偶数或-3是负数”的否定是。 答：2不是偶数且-3不是负数。 12、永真式的否定是 (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)-(3)均有可能 答： 1 。 13、公式(ØPÙQ)Ú(ØPÙ答：ØP ，Q®P ，公式 Q®(PÚ(PÙQ)可化简为。 ØQ)化简为14、谓词公式"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) aÎP(A) (2) aÍP(A) (3) aÎP(A) (4) aÍP(A) 答：(2) 17、在0F之间写上正确的符号。 (1) = (2) Í (3) Î (4) Ï 答：(4) 18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=。 答：32 19、设P=x|(x+1)2£4且xÎR,Q=x|5£x2+16且xÎR,则下列命题哪个正确 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=A5 21、若A-B=，则下列哪个结论不可能正确？( ) (1) A= (2) B= (3) AÌB (4) BÌA 答： 22、判断下列命题哪个为真?( ) (1) A-B=B-A => A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一个元素属于B，则A=B 答： 23、判断下列命题哪几个为正确？( ) (1) , (2) Í, (3) (4) Í (5) a,ba,b,a,b 答：， 24、判断下列命题哪几个正确？( ) (1) 所有空集都不相等 (2) ¹ (4) 若A为非空集，则AÌA成立。 答： 25、设AB=AC，AB=AC，则B( )C。 答：= 26、判断下列命题哪几个正确？( ) (1) 若ABAC，则BC (2) a,b=b,a 2 ）(3) P(AB)¹P(A)P(B) (4) 若A为非空集，则A¹AA成立。 答： 27、，是三个集合，则下列哪几个推理正确： (1) AÍB，BÍC=> AÍC (2) AÍB，BÍC=> AB (3) AB，BC=> AC 答： 28、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求(1)R (2) R-1 。 答：R=<1,1>,<4,2> (2) R-1=<1,1>,<2,4> 29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上的恒等关系 30、集合A上的等价关系的三个性质是什么？( ) 答：自反性、对称性和传递性 31、集合A上的偏序关系的三个性质是什么？( ) 答：自反性、反对称性和传递性 32、设S=,，上的关系1,2，2,1，2,3，3,4 求(1)RoR (2) R-1 。 答：RoR =1,1，1,3，2,2，2,4 R-1 =2,1，1,2，3,2，4,3 33、设1，2，3，4，5，6，是A上的整除关系，求R= ( )。 答：R=<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>, <1,5>,<1,6>,<2,4>,<2,6>,<3,6> 34、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=2y，求(1)R (2) R-1 。 答：R=<1,1>,<4,2>,<6,3> (2) R-1=<1,1>,<2,4>,(36> 35、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求R和R-1的关系矩阵。 éê100ùê000ú答：R的关系矩阵=ê000úé100000êúù10ú R-1的关系矩阵=ê000100ú ê0ê000úêêúë000000úûêë000úúû36、集合A=1,2,10上的关系R=<x,y>|x+y=10,x,yÎA，则R 的性质为。 (1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的 答： 37、设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，则在独异点<A,*>中，单位元是( )，零元是( )答：2，6 38、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，则在独异点<A,*>中，单位元是( )，零元是( )答：9，3 3 。； 39、设G,*是一个群，则 (1) 若a,b,xG，a*x=b，则x=( )； (2) 若a,b,xG，a*x=a*b，则x=( )。 答： a-1*b b 2340、设a是12阶群的生成元， 则a是( )阶元素，a是( )阶元素。 答： 6,4 41、代数系统<G,*>是一个群，则G的等幂元是( )。 答：单位元 42、设a是10阶群的生成元， 则a是( )阶元素，a是( )阶元素。 答：5，10 43、群<G,*>的等幂元是( )，有( )个。 答：单位元，1 44、素数阶群一定是( )群, 它的生成元是( )。 答：循环群，任一非单位元 45、设G,*是一个群，a,b,cG，则 (1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。 答： b*a-143 (2) b 46、<H,*>是<G,*>的子群的充分必要条件是( )。 答：<H,*>是群 或 " a，b ÎG， a*bÎH，a-1ÎH 或" a,b ÎG，a*bÎH -147、群A,*的等幂元有( )个，是( )，零元有( )个。 答：1，单位元，0 48、在一个群G,*中，若G中的元素a的阶是k，则a的阶是( )。 答：k 49、在自然数集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) (2) (3) ） (4) (P(A),Í) 答：(4) 53、有限布尔代数的元素的个数一定等于。 (1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂 4 -1答：(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 答： 56、一个图的哈密尔顿路是一条通过图中( )的路。 答：所有结点一次且恰好一次 57、在有向图中，结点v的出度deg(v)表示( )，入度deg(v)表示( )。 答：以v为起点的边的条数， 以v为终点的边的条数 58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定 答：1 59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 答：+-n(n-1)2, n-1 60、一棵无向树的顶点数n与边数m关系是( )。 答：m=n-1 61、一个图的欧拉回路是一条通过图中( )的回路。 答：所有边一次且恰好一次 62、有n个结点的树，其结点度数之和是( )。 答：2n-2 63、下面给出的集合中，哪一个不是前缀码( )。 (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-2 65、一个无向图有生成树的充分必要条件是( )。 答：它是连通图 66、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 答： 67、设T=V,E是一棵树，若|V|>1，则T中至少存在( )片树叶。 答：2 68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 答：1，树 69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: 5 (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 答： 70、设T是一棵树，则T是一个连通且( )图。 答：无简单回路 71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 答： 72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 答：(4) 73、设图G=<V，E>，V=a，b，c，d，e，E=<a,b>,<a,c>,<b,c>,<c,d>,<d,e>,则G是有向图还是无向图？ 答：有向图 74、任一有向图中，度数为奇数的结点有( )个。 答：偶数 75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？ (1) 2 (2) 4 (3) 3 (4) 5 答： 76、在有n个顶点的连通图中，其边数。 (1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条 答： 77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为。 (1) 5 (2) 7 (3) 8 (4) 9 答： 78、若一棵完全二元树有2n-1个顶点，则它片树叶。 (1) n (2) 2n (3) n-1 (4) 2 答： 79、下列哪一种图不一定是树。 (1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 答： 80、连通图G是一棵树当且仅当G中。 (1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割边 (4) 图中存在一条欧拉路径 答： 二、求下列各公式的主析取范式和主合取范式： 1、(PQ)ÙR 解：(PQ)ÙRÛ(ØPÚQ )ÙR Û(ØPÙR)Ú(QÙR) 6 Û(ØPÙ(QÚØQ)ÙR)Ú(ØPÚP)ÙQÙR) Û(ØPÙQÙR)Ú(ØPÙØQÙR)Ú(ØPÙQÙR)Ú(PÙQÙR) Û(ØPÙQÙR)Ú(ØPÙØQÙR)Ú(PÙQÙR) Ø(PQ)ÙR)Û(ØPÙØQÙØR)Ú(ØPÙQÙØR)Ú(PÙØQÙR) Ú(PÙQÙØR)Ú( PÙØQÙØR) (PQ)ÙRÛ(PÚQÚR)Ù(PÚØQÚR)Ù(ØPÚQÚØR) Ù(ØPÚØQÚR)Ù(ØPÚQÚR) 2、(PÙR)Ú(QÙR)ÚØ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)Ú(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ÙØR) (主析取范式) Ø Û(PÙØQÙØR)Ú(PÙQÙØR）(PÙR)Ú(QÙR)ÚØP Û(ØPÚQÚR)Ù(ØPÚØQÚR) 3、(ØPQ)Ù(RÚP) 解：(ØPQ)Ù(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) Ø(ØPQ)Ù(RÚP) Û(PÚØQÚØR)Ù(ØPÚQÚR)Ù(ØPÚØQÚR)Ù(ØPÚQÚØR) Ù(ØPÚØQÚØR) (ØPQ)Ù(RÚP) Û(ØPÙQÙR)Ú(PÙØQÙØR)Ú(PÙQÙØR)Ú(PÙØQÙR)Ú(PÙQÙR) ØR) 解：Q(PÚØR) ÛØQÚPÚØR Ø Û(ØPÚØQÚØR)Ù(ØPÚØQÚR)Ù(ØPÚQÚØR)Ù(ØPÚQÚR) Ù(PÚØQÚR)Ù(PÚQÚØR)Ù(PÚQÚR） Q(PÚØR) Û(PÙQÙR)Ú(PÙQÙØR)Ú(PÙØQÙR)Ú(PÙØQÙØR)Ú(ØPÙQÙØR) Ú(ØPÙØQÙR)Ú(ØPÙØQÙØR） 5、P(PÙ(QP) 解：P(PÙ(QP) ÛØPÚ(PÙ(ØQÚP) ÛØPÚP 4、Q(PÚ 7 Û T (主合取范式) Û(ØPÙØQ)Ú(ØPÙQ)Ú(PÙØQ)Ú(PÙQ) 6、Ø(PQ)Ú(RÙP) 解： Ø(PQ)Ú(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) Ø(Ø(PQ)Ú(RÙP)Û(PÙQÙØR)Ú(ØPÙQÙR)Ú(ØPÙØQÙR) Ú (ØPÙØQÙØR)Ú(ØPÙQÙØR) Ø(PQ)Ú(RÙP)Û(ØPÚØQÚR)Ù(PÚØQÚØR)Ù(PÚQÚØR) Ù(PÚQÚR)Ù(PÚØQÚR) 7、PÚ(PQ) 解：PÚ(PQ)ÛPÚ(ØPÚQ)Û(PÚØP)ÚQ ÛT(主合取范式) Û(ØPÙØQ)Ú(ØPÙQ)Ú(PÙØQ)Ú(PÙQ) 8、(RQ)ÙP 解：(RQ)ÙPÛ(ØRÚQ )ÙP Û (ØRÙP)Ú(QÙP) Û (ØRÙ(QÚØQ)ÙP)Ú(ØRÚR)ÙQÙP) Û(ØRÙQÙP)Ú(ØRÙØQÙP)Ú(ØRÙQÙP)Ú(RÙQÙP) Û(PÙQÙØR)Ú(PÙØQÙØR)Ú(PÙQÙR) Ø(RQ)ÙP)Û(ØPÙØQÙØR)Ú(ØPÙQÙØR）Ú(PÙØQÙR) Ú(ØPÙQÙR)Ú(ØPÙØQÙR) (RQ)ÙPÛ(PÚQÚR)Ù(PÚØQÚR)Ù(ØPÚQÚØR) Ù(PÚØQÚØR)Ù(PÚQÚØR) 9、PQ 解：PQÛØPÚQ Û(ØPÙ(QÚØQ)Ú(ØPÚP)ÙQ) Û(ØPÙQ)Ú(ØPÙØQ)Ú(ØPÙQ)Ú(PÙQ) Û(ØPÙQ)Ú(ØPÙØQ)Ú(PÙQ) 10、 PÚØQ 解： PÚØQ Û(PÙ(ØQÚQ)Ú(ØPÚP)ÙØQ） Û(PÙØQ)Ú(PÙQ)Ú(ØPÙØQ)Ú(PÙØQ） Û(PÙØQ)Ú(PÙQ)Ú(ØPÙØQ) 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) 12、®Q 解：®Q 8 ÛØ(PÚR)ÚQ Û(ØPÙØR)ÚQ Û(ØPÚQ)Ù(ØRÚQ) Û(ØPÚQÚ(RÙØR)Ù(ØPÙ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ÚØR) Ø®Q Û(ØPÚØQÚR)Ù(ØPÚØQÚØR)Ù(PÚQÚR)Ù(PÚØQÚR)Ù(PÚØQÚØR) ®Q Û(PÙQÙØR)Ú(PÙQÙR)Ú(ØPÙØQÙØR)Ú(ØPÙQÙØR) Ú(ØPÙQÙR) 13、®R 解：®R ÛØ(ØPÚQ)ÚR Û(PÙØQ)ÚR(析取范式) Û(PÙØQÙ(RÚØR)Ú(PÚØ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ÙQÙR)Ú(ØPÙQÙR) Ú(ØPÙØQÙR)(主析取范式） ®R ÛØ(ØPÚQ)ÚR Û(PÙØQ)ÚR(析取范式) Û(PÚR)Ù(ØQÚR)(合取范式) Û(PÚ(QÙØQ)ÚR)Ù(PÙØP)ÚØQÚR) Û(PÚQÚR)Ù(PÚØQÚR)Ù(PÚØQÚR)Ù(ØPÚØQÚR) Û(PÚQÚR)Ù(PÚØQÚR)Ù(ØPÚØQÚR)(主合取范式) 14、(P®(QÙR)Ù(ØP®(ØQÙØR) 解：(P®(QÙR)Ù(ØP®(ØQÙØR) Û(ØPÚ(QÙR)Ù(PÚ(ØQÙØR) Û(ØPÚQ)Ù(ØPÚR)Ù(PÚØQ)Ù(PÚØR) Û(ØPÚQÚ(RÙØR)Ù(ØPÚ(QÙØQ)ÚR)Ù(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Ú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ÙØR) Û(PÙQÙR)Ú(ØPÙØQÙØR)(主析取范式) 9 15、PÚ(ØP®(QÚ(ØQ®R) 解：PÚ(ØP®(QÚ(ØQ®R) Û PÚ(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ÚØ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)(主析取范式) 16、(P®Q)Ù(P®R) 解、(P®Q)Ù(P®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) Û(ØPÚQÚR)Ù(ØPÚQÚØR)Ù(ØPÚØQÚR)(主合取范式) (P®Q)Ù(P®R) Û(ØPÚQ)Ù(ØPÚR) ÛØPÚ(QÙR)(合取范式) Û(ØPÙ(QÚØQ)Ù(RÚØR)Ú(ØPÚ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ÙR) (主析取范式) 三、证明： 1、PQ，ØQÚR，ØR，ØSÚP=>ØS 证明： (1) ØR 前提 (2) ØQÚR 前提 (3) ØQ ， (4) PQ 前提 (5) ØP ， (6) ØSÚP 前提 (7) ØS ， 2、A(BC)，C(ØDÚE)，ØF(DÙ证明： (1) A 前提 (2) A(BC) 前提 (3) BC ， 10 ØE),A=>BF (4) B 附加前提 (5) C ， (6) C(ØDÚE) 前提 (7) ØDÚE ， (8) ØF(DÙØE) 前提 (9) F ， (10) BF CP 3、PÚQ， PR, QS => RÚS 证明： (1) ØR 附加前提 (2) PR 前提 (3) ØP ， (4) PÚQ 前提 (5) Q ， (6) QS 前提 (7) S ， (8) RÚS CP， 4、(PQ)Ù(RS)，(QW)Ù(SX)，Ø(WÙX)，PR => ØP 证明： P 假设前提 PR 前提 R ， (PQ)Ù(RS) 前提 PQ RS Q ， S ， (QW)Ù(SX) 前提 QW SX W ， X ， WÙX ， Ø(WÙX) 前提 Ø(WÙX)Ù(WÙX) ， 5、(UÚV)(MÙN), UÚP, P(QÚS)，ØQÙ证明： (1) ØQÙ ØS =>M ØS 附加前提 P(QÚS) 前提 ØP ， UÚP 前提 U ， 11 UÚV (UÚV)(MÙN) 前提 MÙN (6),(7) M 6、ØBÚD，(EØF)ØD，ØE=>ØB 证明： (1) B 附加前提 (2) ØBÚD 前提 (3) D ， (4) (EØF)ØD 前提 (5) Ø(EØF) ， (6) EÙØF (7) E (8) ØE 前提 (9) EÙØE ， 7、P(QR)，R(QS) => P(QS) 证明： P 附加前提 Q 附加前提 P(QR) 前提 QR ， R ， R(QS) 前提 QS ， S ， QS CP， P(QS) CP， 8、PØQ，ØPR，RØS =>SØQ 证明： S 附加前提 RØS 前提 ØR ， ØPR 前提 P ， PØQ 前提 ØQ (5）， SØQ CP， 9、P(QR) => (PQ)(PR) 证明： (1) PQ 附加前提 (2) P 附加前提 (3) Q (1),(2) 12 (4) P(QR) 前提 (5) QR (2),(4) (6) R (3),(5) (7) PR CP,(2),(6) (8) (PQ) (PR) CP,(1),(7) 10、P(ØQØR)，QØP,SR,P =>ØS 证明： P 前提 P(ØQØR) 前提 ØQØR (1)，(2) QØP 前提 ØQ (1)，(4) ØR (3),(5) SR 前提 ØS (6)，(7) 11、A，AB， AC， B(DØC) => ØD 证明： A 前提 AB 前提 B (1)，(2) AC 前提 C (1)，(4) B(DØC) 前提 DØC (3)，(6) ØD (5)，(7) 12、A(CÚB)，BØA，DØC => AØD 证明： A 附加前提 (2) A(CÚB) 前提 (3) CÚB ， (4) BØA 前提 (5) ØB ， (6) C ， (7) DØC 前提 (8) ØD ， (9) AØD CP，13、(P®Q)Ù(R®Q) Û®Q 证明、 (P®Q)Ù(R®Q) Û(ØPÚQ)Ù(ØRÚQ) Û(ØPÙØR)ÚQ ÛØÚQ 13 Û(PÚR)®Q 14、P®(Q®P)ÛØP®(P®ØQ) 证明、 P®(Q®P) ÛØPÚ(ØQÚP) ÛØ(ØP)Ú(ØPÚØQ) ÛØP®(P®ØQ) 15、Ù，证明、 (1) Ù 前提 P® (QÙR) (1) Ø(QÙR)，SÚPÞS Ø(QÙR) 前提 ØP ，(3) (5) SÚP 前提 (6) S (4),(5) 16、P®证明、 (1) P 附加前提 P® ØQ，QÚØR，RÙØSÞ ØP ØQ 前提 ØQ ， QÚØR 前提 (5) ØR ， (6 ) RÙØS 前提 R RÙØR ， 17、用真值表法证明«Û (®)Ù(®) 证明、 列出两个公式的真值表： P Q P«Q Ù F F F T T F T T T T F F F F T T 由定义可知，这两个公式是等价的。 18、PQÞP(PÙQ) 证明、 设P(PÙQ)为F，则P为T，PÙQ为F。所以P为T，Q为F ，从而PQ也为F。所以PQÞP(PÙQ)。 19、用先求主范式的方法证明(PQ)Ù(PR) Û (P 证明、 先求出左右两个公式 的主合取范式 (PQ)Ù(PR) Û(ØPÚQ)Ù(ØPÚR) 14 Ø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) Û(ØPÚ) Û(ØPÚQ)Ù(ØPÚR) Û(Ø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) 它们有一样的主合取范式，所以它们等价。 20、(PQ)Ù证明、 Û(ØPÚQÚ(RÙØ(QÚR) ÞØP Ø(QÚR)为T，则PQ和Ø(QÚR)都为T。即PQ和ØQÙØR都为T。故PQ，ØQ和ØR)都为T，即PQ为T，Q和R都为F。从而P也为F，即ØP为T。从而(PQ)ÙØ(QÚR) ÞØP 设(PQ)Ù21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; (2) (3) (4) 若C队获亚军，则A队不能获冠军; 若D队获亚军，则B队不能获亚军; A 队获第一; 结论: (5) D队不是亚军。 证明、 设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A®，C®符号化为 ØD。 本题即证明 A®，C® A 前提 A®前提 BÚC ， C® ØA，D®ØB，A；结论ØA，D®ØB，AÞØD。 ØA 前提 ØC ， ØB 前提 B ， D® ØD ，