离散数学题库

《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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），（5），（6） 4、公式(x((A(x)(B(y，x))( (z C(y，z))(D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (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 （2） F （3）F （4）T 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) 17、在0（ ） 之间写上正确的符号。 (1) =　(2) 　(3) 　(4) 答：(4) 18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。 答：32 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） 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、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确： (1) A B，B C=> A C (2) A B，B C=> A∈B (3) A∈B，B∈C=> A∈C 答：（1） （二元关系部分） 28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R (2) R-1 。 答：（1）R={<1,1>,<4,2>} (2) R ={<1,1>,<2,4>} 29、举出集合A上的既是等价关系又是偏序关系的一个例子。(　　　　) 答：A上的恒等关系 30、集合A上的等价关系的三个性质是什么？( ) 答：自反性、对称性和传递性 31、集合A上的偏序关系的三个性质是什么？( ) 答：自反性、反对称性和传递性 32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝ 求(1)R R (2) R-1 。 答：R R ={〈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 。 答：（1）R={<1,1>,<4,2>,<6,3>} (2) R ={<1,1>,<2,4>,(36>} 35、设Ａ＝｛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,y A}，则R 的性质为（ ）。 (1) 自反的　　(2) 对称的　　 (3) 传递的，对称的 (4) 传递的 答：（2） （代数结构部分） 37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是( )，零元是( )。 答：2，6 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的等幂元是(　　　　)。 答：单位元 42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。 答：5，10 43、群的等幂元是(　　)，有(　　　)个。 答：单位元，1 44、素数阶群一定是( )群, 它的生成元是( )。 答：循环群，任一非单位元 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) 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 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 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 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 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) P (Q R)(合取范式) ( P (Q EMBED Equation.3 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) (主析取范式) 三、证明： 1、P→Q， Q R， R， S P=> S 证明： (1) R 前提 (2) Q R 前提 (3) Q （1），（2） (4) P→Q 前提 (5) P （3），（4） (6) 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 附加前提 (5) C （3），（4） (6) C→( D E) 前提 (7) D E （5），（6） (8) F→(D E) 前提 (9) F （7），（8） (10) 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 附加前提 （2） P→(Q S) 前提 （3） P （1），（2） （4） U P 前提 （5） U （3），（4） （6） U V （5） （7） (U V)→(M N) 前提 （8） M N (6),(7) （9） 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） (4) B→ A 前提 (5) B （1），（4） (6) C （3），（5） (7) D→ C 前提 (8) D （6），（7） (9) 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 （5），（7） 17、用真值表法证明Ｐ Ｑ (Ｐ Ｑ) (Ｑ Ｐ) 证明、 列出两个公式的真值表： P Q P Q （P Q） （Q P） F F F T T F T T T T F F F F T T 由定义可知，这两个公式是等价的。 18、P→Q P→(P Q) 证明、 设P→(P Q)为F，则P为T，P Q为F。所以P为T，Q为F ，从而P→Q也为F。所以P→Q P→(P Q)。 19、用先求主范式的方法证明(P→Q) (P→R) (P→（Q 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) ( P Q EMBED Equation.3 R) ( P Q R) ( P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P Q R) ( P EMBED Equation.3 Q R) (P→（Q R）) ( P （Q R）) ( P Q) ( P R) ( 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 EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P Q R) ( P EMBED Equation.3 Q R) 它们有一样的主合取范式，所以它们等价。 20、(P→Q) EMBED Equation.3 (Q R) EMBED Equation.3 P 证明、 设(P→Q) EMBED Equation.3 (Q R)为T，则P→Q和 (Q R)都为T。即P→Q和 Q EMBED Equation.3 R都为T。故P→Q， Q和 R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即 P为T。从而(P→Q) EMBED Equation.3 (Q R) EMBED Equation.3 P 21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; (2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) A 队获第一; 结论: (5) D队不是亚军。 证明、 设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A （B C），C EMBED Equation.3 A，D EMBED Equation.3 B，A；结论符号化为 D。 本题即证明 A （B C），C EMBED Equation.3 A，D EMBED Equation.3 B，A EMBED Equation