《离散数学》题库及答案

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 为永真蕴含式(　　A　)(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)?B(y，x))??zC(y，z))?D(x)中，自由变元是()，约束变元是()。答：x,y,x,z（考察定义在公式?xA和?xA中，称x为指导变元，A为量词的辖域。在?xA和?xA的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?zC(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）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=09、设全体域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、公式(PQ)(PEMBEDEquation.3Q)化简为（），公式Q(P(PQ))可化简为（）。答：P，QP（考查分配率和蕴含等值式知识的掌握）14、谓词公式?x(P(x)??yR(y))Q(x)中量词?x的辖域是（）。答：P(x)??yR(y)（一对括号就是一个辖域）15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为（）。答：?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)EMBEDEquation.34且xR},Q={x|5x+16且xR},则下列命题哪个正确（）(1)QP　　(2)QP　(3)PQ　(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)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,b}∈{a,b,{a},{b}}答：（2），（4）24、判断下列命题哪几个正确(　　　　　)(1)所有空集都不相等(2){Ф}Ф(4)若A为非空集，则AA成立。答：（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为非空集，则AA∪A成立。答：（2）27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：(1)AB，BC=>AC(2)AB，BC=>A∈B(3)A∈B，B∈C=>A∈C答：（1）（（3）的反例C为{｛0，1｝，0｝B为｛0，1｝，A为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>}（考查二元关系的定义，R为R的逆关系，即R=｛<x,y>｝|<y,x>∈R）29、举出集合A上的既是等价关系又是偏序关系的一个例子。(　　　　)答：A上的恒等关系30、集合A上的等价关系的三个性质是什么()答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么()答：自反性、反对称性和传递性(题29，30，31全是考查定义)32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)RR(2)R-1。答：RR={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}（考查FG={<x,y>|?t(<x,t>∈F?<t,y>∈G)}）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>|x+y=10,x,yA}，则R的性质为（）。(1)自反的　　(2)对称的　　(3)传递的，对称的(4)传递的答：（2）（考查自反对称传递的定义）（代数系统部分）37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点<A,*>中，单位元是()，零元是()。答：2，6（单位元和零元的定义，单位元：e。x=x零元：θ。x=θ）38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点<A,*>中，单位元是()，零元是()；答：9，3（半群与群部分）39、设〈G,*〉是一个群，则(1)若a,b,x∈G，ax=b，则x=()；(2)若a,b,x∈G，ax=ab，则x=()。答：（1）ab（2）b（考查群的性质，即群满足消去律）40、设a是12阶群的生成元，则a2是()阶元素，a3是()阶元素。答：6,441、代数系统<G,*>是一个群，则G的等幂元是(　　　　)。答：单位元（由a^2=a,用归纳法可证a^n=a*a^(n-1)=a*a=a，所以等幂元一定是幂等元，反之若a^n=a对一切N成立，则对n=2也成立，所以幂等元一定是等幂元，并且在群<G,*>中，除幺元即单位元e外不可能有任何别的幂等元）42、设a是10阶群的生成元，则a4是()阶元素，a3是()阶元素答：5，10（若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=<a>表示，且称a为一个生成元。并且一元素的阶整除群的阶）43、群<G,*>的等幂元是(　　)，有(　　　)个。答：单位元，1（在群<G,*>中，除幺元即单位元e外不可能有任何别的幂等元）44、素数阶群一定是()群,它的生成元是()。答：循环群，任一非单位元（证明如下：任一元素的阶整除群的阶。现在群的阶是素数p，所以元素的阶要么是1要么是p。G中只有一个单位元，其它元素的阶都不等于1，所以都是p。任取一个非单位元，它的阶等于p，所以它生成的G的循环子群的阶也是p，从而等于整个群G。所以G等于它的任一非单位元生成的循环群）45、设〈G,*〉是一个群，a,b,c∈G，则(1)若ca=b，则c=()；(2)若ca=ba，则c=()。答：（1）b(2)b（群的性质）46、<H,,>是<G,,>的子群的充分必要条件是()。答：<H,,>是群或?a，bG，abH，a-1H或?a,bG，ab-1H47、群＜A,*＞的等幂元有(　　　)个，是(　　　)，零元有(　　　)个。答：1，单位元，048、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是()。答：k49、在自然数集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)不能确定答：159、n阶无向完全图Kn的边数是()，每个结点的度数是()。答：,n-160、一棵无向树的顶点数n与边数m关系是(　　　　)。答：m=n-161、一个图的欧拉回路是一条通过图中()的回路。答：所有边一次且恰好一次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-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，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答：（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(PQ)R(PR)(QR)（析取范式）(P(QEMBEDEquation.3Q)R)((PP)QR)(PQR)(PEMBEDEquation.3QR)(PQR)(PQR)(PQR)(PEMBEDEquation.3QR)(PQR)（主析取范式）((P→Q)R)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QEMBEDEquation.3R)（原公式否定的主析取范式）(P→Q)R(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQR)（主合取范式）2、(PR)(QR)EMBEDEquation.3P解：(PR)(QR)EMBEDEquation.3P（析取范式）(P(QEMBEDEquation.3Q)R)((PEMBEDEquation.3P)QR)(P(QEMBEDEquation.3Q)(REMBEDEquation.3R))(PQR)(PEMBEDEquation.3QR)(PQR)(PQR)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(主析取范式)（(PR)(QR)EMBEDEquation.3P）(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R）（原公式否定的主析取范式）(PR)(QR)EMBEDEquation.3P(PQR)(PEMBEDEquation.3QR)（主合取范式）3、(P→Q)(RP)解：(P→Q)(RP)　(PQ)(RP)（合取范式）(PQ(REMBEDEquation.3R))(P(QEMBEDEquation.3Q))R)(PQR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)（主合取范式）((P→Q)(RP))(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QEMBEDEquation.3R)（原公式否定的主合取范式）(P→Q)(RP)　(PQR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQR)（主析取范式）4、Q→(PEMBEDEquation.3R)解：Q→(PEMBEDEquation.3R)EMBEDEquation.3QPEMBEDEquation.3R（主合取范式）（Q→(PEMBEDEquation.3R)）(PEMBEDEquation.3QEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PQR）（原公式否定的主合取范式）Q→(PEMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R）（主析取范式）5、P→(P(Q→P))解：P→(P(Q→P))EMBEDEquation.3P(P(QP))EMBEDEquation.3 ppt 关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt (主合取范式)(PEMBEDEquation.3Q)(PQ)(PEMBEDEquation.3Q)(PQ)（主析取范式）6、(P→Q)(RP)解：(P→Q)(RP)EMBEDEquation.3(PQ)(RP)(PEMBEDEquation.3Q)(RP)（析取范式）(PEMBEDEquation.3Q(REMBEDEquation.3R))(P(QQ)R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)（主析取范式）((P→Q)(RP))(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)（原公式否定的主析取范式）(P→Q)(RP)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)（主合取范式）7、P(P→Q)　　　　解：P(P→Q)P(PQ)(PEMBEDEquation.3P)QT(主合取范式)(PEMBEDEquation.3Q)(PQ)(PEMBEDEquation.3Q)(PQ)（主析取范式）8、(R→Q)P解：(R→Q)P(RQ)P(RP)(QP)（析取范式）(R(QEMBEDEquation.3Q)P)((RR)QP)(RQP)(REMBEDEquation.3QP)(RQP)(RQP)(PQEMBEDEquation.3R)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)（主析取范式）((R→Q)P)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R）(PEMBEDEquation.3QR)(PQR)(PEMBEDEquation.3QR)（原公式否定的主析取范式）(R→Q)P(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)（主合取范式）9、P→Q解：P→QEMBEDEquation.3PQ（主合取范式）(P(QEMBEDEquation.3Q))((PP)Q)(PQ)(PEMBEDEquation.3Q)(PQ)(PQ)(PQ)(PEMBEDEquation.3Q)(PQ)（主析取范式）10、　PEMBEDEquation.3Q　解：PEMBEDEquation.3Q（主合取范式）(P(QQ))((PP)EMBEDEquation.3Q）(PEMBEDEquation.3Q)(PQ)(PEMBEDEquation.3Q)(PEMBEDEquation.3Q）(PEMBEDEquation.3Q)(PQ)(PEMBEDEquation.3Q)（主析取范式）11、PQ解：PQ（主析取范式）(P(QEMBEDEquation.3Q))((PEMBEDEquation.3P)Q)(PEMBEDEquation.3Q)(PQ)(PQ)(PQ)(PEMBEDEquation.3Q)(PQ)(PQ)（主合取范式）12、（PR）Q解：（PR）QEMBEDEquation.3(PR)Q(PEMBEDEquation.3R)Q(PQ)(RQ)（合取范式）(PQ(REMBEDEquation.3R))((PP)QEMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PQEMBEDEquation.3R)（主合取范式）（PR）Q(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)（原公式否定的主析取范式）（PR）Q(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQR)（主析取范式）13、（PQ）R解：（PQ）REMBEDEquation.3(PQ)R(PEMBEDEquation.3Q)R(析取范式)(PEMBEDEquation.3Q(RR))((PP)(QQ)R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(PQR)(PEMBEDEquation.3QR)(主析取范式）（PQ）REMBEDEquation.3(PQ)R(PEMBEDEquation.3Q)R(析取范式)(PR)(QR)(合取范式)(P(QEMBEDEquation.3Q)R)((PEMBEDEquation.3P)EMBEDEquation.3QR)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QR)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QR)(主合取范式)14、(P(QR))(P(QEMBEDEquation.3R))解：(P(QR))(P(QEMBEDEquation.3R))(P(QR))(P(QEMBEDEquation.3R))(PQ)(PR)(PEMBEDEquation.3Q)(PEMBEDEquation.3R)（合取范式）(PQ(REMBEDEquation.3R))(P(QEMBEDEquation.3Q)R)(PEMBEDEquation.3Q(REMBEDEquation.3R))(P(QEMBEDEquation.3Q)EMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QEMBEDEquation.3R)(主合取范式)(P(QR))(P(QEMBEDEquation.3R))(PEMBEDEquation.3QEMBEDEquation.3R)(PQR)(原公式否定的主合取范式)(P(QR))(P(QEMBEDEquation.3R))(PQR)(PEMBEDEquation.3QEMBEDEquation.3R)(主析取范式)15、P(P(Q(QR)))解：P(P(Q(QR)))P(P(Q(QR)))PQR(主合取范式)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PQEMBEDEquation.3R)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(原公式否定的主合取范式)(PQR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PEMBEDEquation.3QEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PQR)(主析取范式)16、(PQ)(PR)解、(PQ)(PR)(PQ)(PR)(合取范式)(PQ(REMBEDEquation.3R)(P(QQ)R)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQR)(PQR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(主合取范式)(PQ)(PR)(PQ)(PR)EMBEDEquation.3P(QR)(合取范式)(P(QEMBEDEquation.3Q)(REMBEDEquation.3R))((PP)QR)(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQR)(PQR)(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PEMBEDEquation.3QR)(PQR)(主析取范式)三、证明：1、P→Q，QR，R，SP=>S证明：(1)R前提(2)QR前提(3)Q（1），（2）(4)P→Q前提(5)P（3），（4）(6)SP前提(7)S（5），（6）2、A→(B→C)，C→(DE)，F→(DEMBEDEquation.3E),A=>B→F证明：(1)A前提(2)A→(B→C)前提(3)B→C（1），（2）(4)B附加前提(5)C（3），（4）(6)C→(DE)前提(7)DE（5），（6）(8)F→(DEMBEDEquation.3E)前提(9)F（7），（8）(10)B→FCP3、PQ，P→R,Q→S=>RS证明：(1)R附加前提(2)P→R前提(3)P（1），（2）(4)PQ前提(5)Q（3），（4）(6)Q→S前提(7)S（5），（6）(8)RSCP，（1），（8）4、(P→Q)(R→S)，(Q→W)(S→X)，(WX)，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）WX（12），（13）（15）(WX)前提（16）(WX)(WX)（14），（15）5、(UV)→(MN),UP,P→(QS)，QEMBEDEquation.3S=>M证明：(1)QEMBEDEquation.3S附加前提（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，(E→F)→D，E=>B证明：(1)B附加前提(2)BD前提(3)D（1），（2）(4)(E→F)→D前提(5)(E→F)（3），（4）(6)EEMBEDEquation.3F（5）(7)E（6）(8)E前提(9)EEMBEDEquation.3E（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→SCP，（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→QCP，（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→RCP,(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→(CB)，B→A，D→C=>A→D证明：（1）A附加前提(2)A→(CB)前提(3)CB（1），（2）(4)B→A前提(5)B（1），（4）(6)C（3），（5）(7)D→C前提(8)D（6），（7）(9)A→DCP，（1），（8）13、(PQ)(RQ)（PR）Q证明、(PQ)(RQ)(PQ)(RQ)(PEMBEDEquation.3R)QEMBEDEquation.3（PR）Q(PR)Q14、P(QP)EMBEDEquation.3P(PEMBEDEquation.3Q)证明、P(QP)EMBEDEquation.3P(QP)EMBEDEquation.3(P)(PEMBEDEquation.3Q)EMBEDEquation.3P(PEMBEDEquation.3Q)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、PEMBEDEquation.3Q，QEMBEDEquation.3R，REMBEDEquation.3SP证明、(1)P附加前提（2）PEMBEDEquation.3Q前提（3）Q（1），（2）（4）QEMBEDEquation.3R前提(5)R（3），（4）(6)REMBEDEquation.3S前提（7）R（6）（8）REMBEDEquation.3R（5），（7）17、用真值表法证明ＰＱ(ＰＱ)(ＱＰ)证明、列出两个公式的真值表： PQ PQ（PQ）（QP） FFFTTFTT TTFFFFTT由定义可知，这两个公式是等价的。18、P→QP→(PQ)证明：设P→(PQ)为F，则P为T，PQ为F。所以P为T，Q为F，从而P→Q也为F。所以P→QP→(PQ)。19、用先求主范式的方法证明(P→Q)(P→R)(P→（QR）证明：先求出左右两个公式的主合取范式(P→Q)(P→R)(PQ)(PR)(PQ(REMBEDEquation.3R)))(P(QEMBEDEquation.3Q)R)(PQR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(P→（QR）)(P（QR）)(PQ)(PR)(PQ(REMBEDEquation.3R))(P(QEMBEDEquation.3Q)R)(PQR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)(PQEMBEDEquation.3R)(PQR)(PEMBEDEquation.3QR)它们有一样的主合取范式，所以它们等价。20、(P→Q)EMBEDEquation.3(QR)EMBEDEquation.3P证明：设(P→Q)EMBEDEquation.3(QR)为T，则P→Q和(QR)都为T。即P→Q和QEMBEDEquation.3R都为T。故P→Q，Q和R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即P为T。从而(P→Q)EMBEDEquation.3(QR)EMBEDEquation.3P21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效前提:(1)若A队得第一，则B队或C队获亚军;(2)若C队获亚军，则A队不能获冠军;(3)若D队获亚军，则B队不能获亚军;(4)A队获第一;结论:(5)D队不是亚军。证明：设A：A队得第一;B:B队获亚军;C:C队获亚军;D:D队获亚军;则前提符号化为A（BC），CEMBEDEquation.3A，DEMBEDEquation.3B，A；结论符号化为D。本题即证明A（BC），CEMBEDEquation.3A，DEMBEDEquation.3B，AEMBEDEquation.3D（1）A前提（2）A（BC）前提（3）BC（1），（2）（4）CEMBEDEquation.3A前提（5）C（1），（4）（6）B（3），（5）（7）DEMBEDEquation.3B前提（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(B－C)＝(AB)－(AC)证明：(AB)－(AC)=(AB)EMBEDEquation.3=(AB)（EMBEDEquation.3EMBEDEquation.3）=(ABEMBEDEquation.3)(ABEMBEDEquation.3)=ABEMBEDEquation.3=A（BEMBEDEquation.3）=A（B-C）2、(A－B)(A－C)=A－(BC)证明：(A-B)(A-C)=(AEMBEDEquation.3)(AEMBEDEquation.3)=A(EMBEDEquation.3EMBEDEquation.3)=AEMBEDEquation.3=A-(BC)3、AB=AC，EMBEDEquation.3B=EMBEDEquation.3C，则C=B　　证明：B=B(EMBEDEquation.3A)=(BEMBEDEquation.3)(BA)=(CEMBEDEquation.3)(CA)=C(EMBEDEquation.3A)=C4、AB=A(B-A)证明：A(B-A)=A(BEMBEDEquation.3)=(AB)(AEMBEDEquation.3)=(AB)U=AB5、A=B?AB=　　证明：设A=B，则AB=（A-B）（B-A）=EMBEDEquation.3EMBEDEquation.3=。设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)(B∩C)=C(AB)=C(AC)=C7、AB=AC，EMBEDEquation.3B=EMBEDEquation.3C，则C=B证明：B=B(AEMBEDEquation.3)=(BA)(BEMBEDEquation.3)=(CA)(CEMBEDEquation.3)=C(AEMBEDEquation.3)=C8、A－(BC)＝(A－B)－C　　证明：A－(BC)=AEMBEDEquation.3=A(EMBEDEquation.3EMBEDEquation.3)=(AEMBEDEquation.3)EMBEDEquation.3=(A-B)EMBEDEquation.3=(A-B)-C9、(A－B)(A－C)=A－(BC)　证明：(A-B)(A－C)=(AEMBEDEquation.3)(AEMBEDEquation.3)=(AA)(EMBEDEquation.3EMBEDEquation.3)=AEMBEDEquation.3=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)=(AEMBEDEquation.3)(AEMBEDEquation.3)=A(EMBEDEquation.3EMBEDEquation.3)=AEMBEDEquation.3=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)=EMBEDEquation.3ABC证明：因为(A-B)(A-C)=(AEMBEDEquation.3)(AEMBEDEquation.3)=A(EMBEDEquation.3EMBEDEquation.3)=AEMBEDEquation.3=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)=AB=证明：因为(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-）EMBEDEquation.3=A，（AB）-B=（AEMBEDEquation.3）-=A，所以（A-B）B=（AB）-B。用反证法证明。假设B，则存在bB。因为bB且bAB，所以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):x<y,G(x,y):x>y，个体域为自然数。将下列命题符号化：（1）没有小于0的自然数;（2）x<z是x<y且y<z的必要条件;（3）若x<y，则存在某些z，使z<0,xz>yz;（4）存在x，对任意y使得xy=y;（5）对任意x，存在y使x+y=x。答：（1）x（G(x,0)M（0,0,x））或xL(x,0)（2）xyz((L(x,y)L(y,z))L(x,z))（3）xy((L(x,y)z(L(z,0)G(xz,yz)))