为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

《离散数学》题库及答案

2011-12-11 50页 doc 7MB 212阅读

用户头像

is_413678

暂无简介

举报
《离散数学》题库及答案 《离散数学》题库与答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?(   ) (1) Q=>Q→P (2) Q=>P→Q (3)P=>P→Q (4) P (P Q)=> P 答:在第三章里面有公式(1)是附加律,(4)可以由第二章的蕴含等值式求出(注意与吸收律区别) 2、下列公式中哪些是永真式?( ) (1)(┐P Q)→(Q→ R) (2)P→(Q→Q) (3)(P Q)→P (4)P→(P Q) 答:(2),(3),(4) 可...
《离散数学》题库及答案
《离散数学》与答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?(   ) (1) Q=>Q→P (2) Q=>P→Q (3)P=>P→Q (4) P (P Q)=> P 答:在第三章里面有公式(1)是附加律,(4)可以由第二章的蕴含等值式求出(注意与吸收律区别) 2、下列公式中哪些是永真式?( ) (1)(┐P Q)→(Q→ R) (2)P→(Q→Q) (3)(P Q)→P (4)P→(P Q) 答:(2),(3),(4) 可用蕴含等值式 3、设有下列公式,请问哪几个是永真蕴涵式?( ) (1)P=>P Q (2) P Q=>P (3) P Q=>P Q (4)P (P→Q)=>Q (5) (P→Q)=>P (6) P (P Q)=> P 答:(2)是第三章的化简律,(3)类似附加律,(4)是假言推理,(3),(5),(6)都可以用蕴含等值式来证明出是永真蕴含式 4、公式(x((A(x)(B(y,x))( (z C(y,z))(D(x)中,自由变元是( ),约束变元是( )。 答:x,y, x,z(考察定义在公式(x A和(x A中,称x为指导变元,A为量词的辖域。在(x A和(x A的辖域中,x的所有出现都称为约束出现,即称x为约束变元,A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y,x)和(z C(y,z)中y为自由变元,x和z为约束变元,在D(x)中x为自由变元) 5、判断下列语句是不是命题。若是,给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。  (3) 你喜欢唱歌吗? (4) 若7+8>18,则三角形有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) (y(x(x+y=0) 答:(1)对任一整数x存在整数 y满足x+y=0 (2)存在整数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)   (  ) 答:(1) F (反证法:假若存在,则(x- 1)*y=0 对所有的x都成立,显然这个与前提条件相矛盾) (2) F (同理) (3)F (同理) (4)T(对任一整数x存在整数 y满足条件 y=2x 很明显是正确的) 10、设谓词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、公式( P Q) ( P EMBED Equation.3 Q)化简为( ),公式 Q (P (P Q))可化简为( )。 答: P ,Q P(考查分配率和蕴含等值式知识的掌握) 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) ({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) EMBED Equation.3 4且x R},Q={x|5 x +16且x R},则下列命题哪个正确( ) (1) Q P  (2) Q P (3) P Q (4) P=Q 答:(3)(Q是集合R,P只是R中的一部分,所以P是Q的真子集) 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 答:(4)(差集的定义) 22、判断下列命题哪个为真?( ) (1) A-B=B-A => A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一个元素属于B,则A=B 答:(1)(考查空集和差集的相关知识) 23、判断下列命题哪几个为正确?(   )  (1) {Ф}∈{Ф,{{Ф}}} (2) {Ф} {Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф {Ф} (5) {a,b}∈{a,b,{a},{b}} 答:(2),(4) 24、判断下列命题哪几个正确?(     ) (1) 所有空集都不相等 (2) {Ф} Ф (4) 若A为非空集,则A A成立。 答:(2) 25、设 A∩B=A∩C, ∩B= ∩C,则B( )C。 答:=(等于) 26、判断下列命题哪几个正确?(     ) (1) 若A∪B=A∪C,则B=C (2) {a,b}={b,a} (3) P(A∩B) P(A)∩P(B) (P(S)表示S的幂集) (4) 若A为非空集,则A A∪A成立。 答:(2) 27、A,B,C是三个集合,则下列哪几个推理正确: (1) A B,B C=> A C (2) A B,B C=> A∈B (3) A∈B,B∈C=> A∈C 答:(1) ((3)的反例 C为{{0,1},0} B为{0,1},A为1 很明显结论不对) (二元关系部分) 28、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2求(1)R (2) R-1 答:(1)R={<1,1>,<4,2>} (2) R ={<1,1>,<2,4>}(考查二元关系的定义,R 为R的逆关系,即R ={}| ∈R) 29、举出集合A上的既是等价关系又是偏序关系的一个例子。(    ) 答:A上的恒等关系 30、集合A上的等价关系的三个性质是什么?( ) 答:自反性、对称性和传递性 31、集合A上的偏序关系的三个性质是什么?( ) 答:自反性、反对称性和传递性(题29,30,31全是考查定义) 32、设S={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉} 求(1)R R (2) R-1 。 答:R R ={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉}(考查F G ={|(t(∈F(∈G)}) R-1 ={〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉} 33、设A={1,2,3,4,5,6},R是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、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=2y},求(1)R (2) R-1 。 答:(1)R={<1,1>,<4,2>,<6,3>} (2) R ={<1,1>,<2,4>,(36>} 35、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},求R和R-1的关系矩阵。 答:R的关系矩阵= R 的关系矩阵= 36、集合A={1,2,…,10}上的关系R={|x+y=10,x,y A},则R 的性质为( )。 (1) 自反的  (2) 对称的   (3) 传递的,对称的 (4) 传递的 答:(2)(考查自反 对称 传递的定义) (代数系统部分) 37、设A={2,4,6},A上的二元运算*定义为:a*b=max{a,b},则在独异点中,单位元是( ),零元是( )。 答:2,6(单位元和零元的定义,单位元:e。x=x 零元:θ。x=θ) 38、设A={3,6,9},A上的二元运算*定义为:a*b=min{a,b},则在独异点中,单位元是( ),零元是( ); 答:9,3 (半群与群部分) 39、设〈G,*〉是一个群,则 (1) 若a,b,x∈G,a x=b,则x=( ); (2) 若a,b,x∈G,a x=a b,则x=( )。 答: (1) a b (2) b (考查群的性质,即群满足消去律) 40、设a是12阶群的生成元, 则a2是( )阶元素,a3是( )阶元素。 答: 6,4 41、代数系统是一个群,则G的等幂元是(    )。 答:单位元(由a^2=a,用归纳法可证a^n=a*a^(n-1)=a*a=a,所以等幂元一定是幂等元,反之若a^n=a对一切N成立,则对n=2也成立,所以幂等元一定是等幂元,并且在群中,除幺元即单位元e外不可能有任何别的幂等元) 42、设a是10阶群的生成元, 则a4是( )阶元素,a3是( )阶元素 答:5,10(若一个群G的每一个元都是G的某一个固定元a的乘方,我们就把G叫做循环群;我们也说,G是由元a生成的,并且用符号G=表示,且称a为一个生成元。并且一元素的阶整除群的阶) 43、群的等幂元是(  ),有(   )个。 答:单位元,1 (在群中,除幺元即单位元e外不可能有任何别的幂等元) 44、素数阶群一定是( )群, 它的生成元是( )。 答:循环群,任一非单位元(证明如下:任一元素的阶整除群的阶。现在群的阶是素数p,所以元素的阶要么是1要么是p。G中只有一个单位元,其它元素的阶都不等于1,所以都是p。任取一个非单位元,它的阶等于p,所以它生成的G的循环子群的阶也是p,从而等于整个群G。所以G等于它的任一非单位元生成的循环群) 45、设〈G,*〉是一个群,a,b,c∈G,则 (1) 若c a=b,则c=( );(2) 若c a=b a,则c=( )。 答:(1) b (2) b(群的性质) 46、的子群的充分必要条件是( )。 答:是群 或 ( a,b G, a b H,a-1 H 或( a,b G,a b-1 H 47、群<A,*>的等幂元有(   )个,是(   ),零元有(   )个。 答:1,单位元,0 48、在一个群〈G,*〉中,若G中的元素a的阶是k,则a-1的阶是( )。 答:k 49、在自然数集N上,下列哪种运算是可结合的?( ) (1) a*b=a-b  (2) a*b=max{a,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) 不能确定 答:1 59、n阶无向完全图Kn 的边数是( ),每个结点的度数是( )。 答: , 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) 不能确定。 答:(3) 67、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( )片树叶。 答:2 68、任何连通无向图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、(P→Q) R  解:(P→Q) R ( P Q ) R ( P R) (Q R) (析取范式) ( P (Q EMBED Equation.3 Q) R) (( P P) Q R) ( P Q R) ( P EMBED Equation.3 Q R) ( P Q R) (P Q R) ( P Q R) ( P EMBED Equation.3 Q R) (P Q R)(主析取范式) ((P→Q) R) ( P EMBED Equation.3 Q EMBED Equation.3 R) ( P Q EMBED Equation.3 R) (P EMBED Equation.3 Q R) (P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q EMBED Equation.3 R)(原公式否定的主析取范式) (P→Q) R (P Q R) (P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P Q R)(主合取范式) 2、(P R) (Q R) EMBED Equation.3 P 解: (P R) (Q R) EMBED Equation.3 P(析取范式) (P (Q EMBED Equation.3 Q) R) ((P EMBED Equation.3 P) Q R) ( P (Q EMBED Equation.3 Q) (R EMBED Equation.3 R)) (P Q R) (P EMBED Equation.3 Q R) (P Q R) ( P Q R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R) (P EMBED Equation.3 Q R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R) (主析取范式) ((P R) (Q R) EMBED Equation.3 P) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q EMBED Equation.3 R)(原公式否定的主析取范式) (P R) (Q R) EMBED Equation.3 P ( P Q R) ( P EMBED Equation.3 Q R)(主合取范式) 3、( P→Q) (R P) 解:( P→Q) (R P)  (P Q) (R P)(合取范式) (P Q (R EMBED Equation.3 R)) (P (Q EMBED Equation.3 Q)) R) (P Q R) (P Q EMBED Equation.3 R) (P Q R) (P Q R) (P Q R) (P Q EMBED Equation.3 R) (P Q R)(主合取范式) (( P→Q) (R P)) (P Q R) ( P Q R) ( P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q EMBED Equation.3 R)(原公式否定的主合取范式) ( P→Q) (R P)  ( P Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q EMBED Equation.3 R) (P EMBED Equation.3 Q R) (P Q R) (主析取范式) 4、Q→(P EMBED Equation.3 R) 解:Q→(P EMBED Equation.3 R) EMBED Equation.3 Q P EMBED Equation.3 R(主合取范式) (Q→(P EMBED Equation.3 R)) ( P EMBED Equation.3 Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P Q R) (P EMBED Equation.3 Q R) (P Q EMBED Equation.3 R) (P Q R)(原公式否定的主合取范式) Q→(P EMBED Equation.3 R) (P Q R) (P Q EMBED Equation.3 R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R)(主析取范式) 5、P→(P (Q→P)) 解:P→(P (Q→P)) EMBED Equation.3 P (P ( Q P)) EMBED Equation.3 P P T (主合取范式) ( P EMBED Equation.3 Q) ( P Q) (P EMBED Equation.3 Q) (P Q)(主析取范式) 6、 (P→Q) (R P) 解: (P→Q) (R P) EMBED Equation.3 ( P Q) (R P) (P EMBED Equation.3 Q) (R P)(析取范式) (P EMBED Equation.3 Q (R EMBED Equation.3 R)) (P ( Q Q) R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P EMBED Equation.3 Q R) (P Q R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R)(主析取范式) ( (P→Q) (R P)) (P Q EMBED Equation.3 R) ( P Q R) ( P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R) ( P Q EMBED Equation.3 R)(原公式否定的主析取范式) (P→Q) (R P) ( P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q EMBED Equation.3 R) (P Q R) (P EMBED Equation.3 Q R)(主合取范式) 7、P (P→Q)      解:P (P→Q) P ( P Q) (P EMBED Equation.3 P) Q T(主合取范式) ( P EMBED Equation.3 Q) ( P Q) (P EMBED Equation.3 Q) (P Q)(主析取范式) 8、(R→Q) P 解:(R→Q) P ( R Q ) P ( R P) (Q P) (析取范式) ( R (Q EMBED Equation.3 Q) P) (( R R) Q P) ( R Q P) ( R EMBED Equation.3 Q P) ( R Q P) (R Q P) (P Q EMBED Equation.3 R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R)(主析取范式) ((R→Q) P) ( P EMBED Equation.3 Q EMBED Equation.3 R) ( P Q EMBED Equation.3 R) (P EMBED Equation.3 Q R) ( P Q R) ( P EMBED Equation.3 Q R)(原公式否定的主析取范式) (R→Q) P (P Q R) (P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q EMBED Equation.3 R)(主合取范式) 9、P→Q 解:P→Q EMBED Equation.3 P Q(主合取范式) ( P (Q EMBED Equation.3 Q)) (( P P) Q) ( P Q) ( P EMBED Equation.3 Q) ( P Q) (P Q) ( P Q) ( P EMBED Equation.3 Q) (P Q)(主析取范式) 10、 P EMBED Equation.3 Q  解: P EMBED Equation.3 Q (主合取范式) (P ( Q Q)) (( P P) EMBED Equation.3 Q) (P EMBED Equation.3 Q) (P Q) ( P EMBED Equation.3 Q) (P EMBED Equation.3 Q) (P EMBED Equation.3 Q) (P Q) ( P EMBED Equation.3 Q)(主析取范式) 11、P Q 解:P Q(主析取范式) (P (Q EMBED Equation.3 Q)) ((P EMBED Equation.3 P) Q) (P EMBED Equation.3 Q) (P Q) (P Q) ( P Q) (P EMBED Equation.3 Q) (P Q) ( P Q)(主合取范式) 12、(P R) Q 解:(P R) Q (P R) Q ( P EMBED Equation.3 R) Q ( P Q) ( R Q)(合取范式) ( P Q (R EMBED Equation.3 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)(主合取范式) (P R) Q ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (原公式否定的主析取范式) (P R) Q (P Q EMBED Equation.3 R) (P Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R) ( P Q EMBED Equation.3 R) ( P Q R)(主析取范式) 13、(P Q) R 解:(P Q) R ( P Q) R (P EMBED Equation.3 Q) R(析取范式) (P EMBED Equation.3 Q (R R)) ((P P) (Q Q) R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R) (P EMBED Equation.3 Q R) ( P Q R) ( P EMBED Equation.3 Q R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R) ( P Q R) ( P EMBED Equation.3 Q R)(主析取范式) (P Q) R ( P Q) R (P EMBED Equation.3 Q) R(析取范式) (P R) ( Q R)(合取范式) (P (Q EMBED Equation.3 Q) R) ((P EMBED Equation.3 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 EMBED Equation.3 R)) 解:(P (Q R)) ( P ( Q EMBED Equation.3 R)) ( P (Q R)) (P ( Q EMBED Equation.3 R)) ( P Q) ( P R) (P Q) (P R)(合取范式) ( P Q (R EMBED Equation.3 R)) ( P (Q EMBED Equation.3 Q) R) (P Q (R EMBED Equation.3 R)) (P (Q EMBED Equation.3 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 EMBED Equation.3 R)) ( P Q R) (P Q R)(原公式否定的主合取范式) (P (Q R)) ( P ( Q EMBED Equation.3 R)) (P Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R)(主析取范式) 15、P ( P (Q ( Q R))) 解:P ( P (Q ( Q R))) P (P (Q (Q R))) P Q R(主合取范式) (P Q R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q EMBED Equation.3 R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q EMBED Equation.3 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 EMBED Equation.3 R) ( P ( Q Q) R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P Q R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R)(主合取范式) (P Q) (P R) ( P Q) ( P R) EMBED Equation.3 P (Q R)(合取范式) ( P (Q EMBED Equation.3 Q) (R EMBED Equation.3 R)) (( P P) Q R) ( P Q R) ( P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P Q R) (P Q R) ( P Q R) ( P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) (P Q R) (主析取范式) 三、证明: 1、P→Q, Q R, R, S P=> S 证明: (1) R 前提 (2) Q R 前提 Q (1),(2) P→Q 前提 P (3),(4) S P 前提 (7) S (5),(6) 2、A→(B→C),C→( D E), F→(D EMBED Equation.3 E),A=>B→F 证明: (1) A 前提 (2) A→(B→C) 前提 (3) B→C (1),(2) (4) B 附加前提 C (3),(4) C→( D E) 前提 D E (5),(6) F→(D EMBED Equation.3 E) 前提 F (7),(8) B→F CP 3、P Q, P→R, Q→S => R S 证明: (1) R 附加前提 (2) P→R 前提 (3) P (1),(2) (4) P Q 前提 (5) Q (3),(4) (6) Q→S 前提 (7) S (5),(6) (8) R S CP,(1),(8) 4、(P→Q) (R→S),(Q→W) (S→X), (W X),P→R => P 证明: (1) P 假设前提 (2) P→R 前提 (3) R (1),(2) (4) (P→Q) (R→S) 前提 (5) P→Q (4) (6) R→S (5) (7) Q (1),(5) (8) S (3),(6) (9) (Q→W) (S→X) 前提 (10) Q→W (9) (11) S→X (10) (12) W (7),(10) (13) X (8),(11) (14) W X (12),(13) (15) (W X) 前提 (16) (W X) (W X) (14),(15) 5、(U V)→(M N), U P, P→(Q S), Q EMBED Equation.3 S =>M 证明: (1) Q EMBED Equation.3 S 附加前提 P→(Q S) 前提 P (1),(2) U P 前提 U (3),(4) U V (5) (U V)→(M N) 前提 M N (6),(7) M (8) 6、 B D,(E→ F)→ D, E=> B 证明: (1) B 附加前提 (2) B D 前提 (3) D (1),(2) (4) (E→ F)→ D 前提 (5) (E→ F) (3),(4) (6) E EMBED Equation.3 F (5) (7) E (6) (8) E 前提 (9) E EMBED Equation.3 E (7),(8) 7、P→(Q→R),R→(Q→S) => P→(Q→S) 证明: (1) P 附加前提 (2) Q 附加前提 (3) P→(Q→R) 前提 (4) Q→R (1),(3) (5) R (2),(4) (6) R→(Q→S) 前提 (7) Q→S (5),(6) (8) S (2),(7) (9) Q→S CP,(2),(8) (10) P→(Q→S) CP,(1),(9) 8、P→ Q, P→R,R→ S =>S→ 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)→(P→R) 证明: (1) P→Q 附加前提 (2) P 附加前提 (3) Q (1),(2) (4) P→(Q→R) 前提 (5) Q→R (2),(4) (6) R (3),(5) (7) P→R CP,(2),(6) (8) (P→Q) →(P→R) CP,(1),(7) 10、P→( Q→ R),Q→ P,S→R,P => S 证明: (1) P 前提 (2) P→( Q→ R) 前提 (3) Q→ R (1),(2) (4) Q→ P 前提 (5) Q (1),(4) (6) R (3),(5) (7) S→R 前提 (8) S (6),(7) 11、A,A→B, A→C, B→(D→ C) => D 证明: (1) A 前提 (2) A→B 前提 (3) B (1),(2) (4) A→C 前提 (5) C (1),(4) (6) B→(D→ C) 前提 (7) D→ C (3),(6) (8) D (5),(7) 12、A→(C B),B→ A,D→ C => A→ D 证明: (1) A 附加前提 (2) A→(C B) 前提 (3) C B (1),(2) B→ A 前提 B (1),(4) C (3),(5) D→ C 前提 D (6),(7) A→ D CP,(1),(8) 13、(P Q) (R Q) (P R) Q 证明、 (P Q) (R Q) ( P Q) ( R Q) ( P EMBED Equation.3 R) Q EMBED Equation.3 (P R) Q (P R) Q 14、P (Q P) EMBED Equation.3 P (P EMBED Equation.3 Q) 证明、 P (Q P) EMBED Equation.3 P ( Q P) EMBED Equation.3 ( P) ( P EMBED Equation.3 Q) EMBED Equation.3 P (P EMBED Equation.3 Q) 15、(P Q) (P R), (Q R),S P S 证明、 (1) (P Q) (P R) 前提 (2) P (Q R) (1) (3) (Q R) 前提 (4) P (2),(3) (5) S P 前提 (6) S (4),(5) 16、P EMBED Equation.3 Q,Q EMBED Equation.3 R,R EMBED Equation.3 S P 证明、 (1) P 附加前提 (2) P EMBED Equation.3 Q 前提 (3) Q (1),(2) (4) Q EMBED Equation.3 R 前提 (5) R (3),(4) (6 ) R EMBED Equation.3 S 前提 (7) R (6) (8) R EMBED Equation.3 R
/
本文档为【《离散数学》题库及答案】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索