2023年离散数学题库及答案.pdf

《2023年离散数学题库及答案.pdf》由会员分享，可在线阅读，更多相关《2023年离散数学题库及答案.pdf（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 离散数学题库答案一、选择或填空(数理逻辑部分)1、下列哪些公式为永真蕴含式？()Q=QT P Q=PT Q (3)P=PTQ P A(P v Q)=P答：(1),(4)2、下列公式中哪些是永真式？()(-1 P人Q)T(Q TR)(2)P T(QTQ)(PAQ)T P (4)P T(PVQ)答：(2),(3),(4)3、设有下列公式，请问哪几个是永真蕴涵式？()P=PAQ PAQ=P PAQ=PVQ(4)PA(P-Q)=Q(5)(PTQ)=P(6)PA(PVQ)=P答：(2),(3),(4),，(6)4、公式X/x(A(x)-B(y,x)A 3Z C(y,z)-D(x)中，自由变元是(),约

2、束变元是()0答：x,y,x,z5、判断下列语句是不是命题。若是，给出命题的真值。()(1)北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗？(4)若7+8 1 8,则三角形有4条边。(5)前进！给我一杯水吧！答：(1)是，T (2)是，F(3)不是(4)是，T (5)不是 不 是6、命 题“存在一些人是大学生”的否认是(),而命题“所有的人都是要死的”的否认是()0答：所 有 人 都 不 是 大 学 生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()0(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校

3、(4)若我不生病，则我一定去学校答：(1)Qf P (2)P f Q(3)P c Q(4)P f Q8、设个体域为整数集，则下列公式的意义是()。(1)Vx3y(x+y=O)(2)3y Vx(x+y=O)答：(1)对 任 一 整 数x存 在 整 数y满 足x+y=O(2)存 在 整 数y对 任 一 整 数x满 足x+y=O9、设全体域D是正整数集合，拟定下列命题的真值：(1)Vx3y(xy=y)()(2)3xVy(x+y=y)()(3)3xVy(x+y=x)()(4)Vx3y(y=2x)()答：(1)F(2)F(3)F(4)T10、设 谓 词P(x)：x是奇数,Q(x):x是偶数，谓词公式3x

4、(P(x)vQ(x)在哪个个体域中为真？()(1)自然数 实数(3)复数 (1)(3)均成立答：(1)11、命 题”2是偶数或-3是负数”的 否 认 是()0答：2不是偶数且-3不 是 负 数。12、永真式的否认是()(1)永真式 永 假 式(3)可满足式 (1)一(3)均有也许答：(2)13、公式(PAQ)V(PAQ)化 简 为()，公 式Q f(P v(P人Q)可化简为()。答：P ,Q-P14、谓词公式Vx(P(x)v R R(y)-Q(x)中量词V x的 辖 域 是()。答：P(x)v ByR(y)15、令R(x)：x是实数，Q(x)：x是有理数。则命题“并非每个实数都是有理数”的符号

5、化表达为()o答：-iVx(R(x)-Q(x)(集合论部分)16、设庆=匕，a,下列命题错误的是()0(1)a/(A)(2)aP(A)(3)a“(A)(4)aP(A)答：17、在0()之间写上对的的符号。(1)=(2)o(3)e(4)生答：(4)18、若集合S的基数|S|=5,则S的森集的基数|P(S)|=()o答：3219、设P=x&+1)2 4且)(咫，0=仪|54*2+16且)(3)AuB(4)Bc=A答：22、判断下列命题哪个为真？()(1)A-B=B-A=A=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一个元素属于B,则A=B答：(1)23、判断下列命题哪几

6、个为对的？()(1)(，(3)(4)之 (5)a,bG a,b,a,b答：(2),(4)24、判断下列命题哪几个对的？()(1)所有空集都不相等(2)甸 力(4)若A为非空集，则A u A成立。答：25、设 AAB=AAC,A AB=A A C,则8()C。答：=(等于)26、判断下列命题哪几个对的？()(1)若 A U B=A U C,则 B=C(2)a,b=b,a(3)P(AAB)”(A)flP(B)(P(S)表达 S 的赛集)(4)若A为非空集，则 AHAUA成立。答：27、A,B,C是三个集合，则下列哪几个推理对的：(1)AcB,BqC=AcC(2)AeB,BC=AGB(3)AeB,B

7、C=AeC答：(1)(二元关系部分)28、设 A=1,2,3,4,5,6,B=1,2,3,从A 到 B 的关系 R=x,y|x=y?,求 R (2)R-1 o答:(1)R=,(2)RT=K1,1,29、举 出 集 合A上的既是等价关系又是偏序关系的一个例子。()答：A上的恒等关系30、集 合A上的等价关系的三个性质是什么？()答：自反性、对称性和传递性31、集 合A上的偏序关系的三个性质是什么？()答：自反性、反对称性和传递性32、设5=1,2,3,4,A上 的 关 系 !=1,2，2,1，2,3，求 RR R1 o答：RoR=,b=2,1，,33、设 庆=1,2,3,4,5,6,R是A上的整

8、除关系，求R=()。答：R=,34、设 庆=1,2,3,4,5,6,B=1,2,3,从 A到 B 的关系 R=x,y|x=2y,求 R (2)I T。答：(1)R=,(2)R-=,(36J35、设 A =1,2,3,4,5,6 ,B=1,2,3,从 A 到 B 的关系 R =x,y|x=y?,lo0oooR T的关系矩阵=ooo10求 R和 R-的关系矩阵。1 0 0 0 0 00 0 0 1 0 00 0 0 0 0 00 0 036、集合 A=1,2,，1 0 上的关系 R=|x+y=1 0,x,y e A ,则 R 的性质为（）。（1）自反的（2）对称的（3）传递的，对 称 的（4）传递

9、的答：（代数结构部分）37、设人=2,4,6 ,A上的二元运算*定义为：a*b=m ax a,b,则在独异点 中，单位元是（）,零元是（）。答：2,638、设 4=3,6,9 ,A上的二元运算*定义为：a*b=m i n 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=（）0答：（1）a-|*b（2）b40、设a是12阶群的生成元，则2?是（）阶元素，才是（）阶元素。答：6,441、代数系统 G,*是一个群，则G的等幕元是（）0答：单位元

10、42、设a是10阶群的生成元，则2“是（）阶元素，才是（）阶元素。答：5,1043、群4,*的等暴元是（），有（）个。答：单 位 元，144、素数阶群一定是（）群，它的生成元是（）0答：循 环 群，任一非单位元45、设 G,*是一个群，a,b,cGG,则（1）若 c*a=b,则 c=（）;（2）若 c*a=b*a,则 c=（）。答：（1）b*-1（2）b46、比，*是4,，*的子群的充足必要条件是（）0答：H,*是 群 或 V a,b eG,a*be H,a e H 或 V a,b eG,a*b 1 e H47、群VA,*的等森元有（）个，是（）,零元有（）个。答：1,单 位 元，048、在一

11、个群G,*中，若G中的元素a的阶是k,则aT的阶是（）。答：k49、在自然数集N上，下列哪种运算是可结合的？（）（1）a*b-a-b（2）a*b-max a,b（3）a*b-a+2b（4）a*b-1 a-b|答：50、任意一个具有2个或以上元的半群，它（）。(1)不也许是群(2)不一定是群(3)一定是群(4)是互换群答：51、6阶有限群的任何子群一定不是()(1)2阶(2)3阶(3)4阶 答：(格与布尔代数部分)52、下列哪个偏序集构成有界格()(1)(N,。(2)(Z,)(3)(2,3,4,6,12(整除关系)(z答:(4)53、有限布尔代数的元素的个数一定等于(1)偶 数(2)奇 数(3)

12、4的倍数答：(4)(图论部分)54、设G是一个哈密尔顿图，则G一定是(1)欧 拉 图 树 (3)平面图 答：(4)55、下面给出的集合中，哪一个是前缀码？(1)(0,10,110,101111(2)01,(3)b,c,aa,ab,aba(4)1,16阶D(P(A)v)o(4)2的正整数次赛)o连通图)001,000,11,101,001,0011答：56、一个图的哈密尔顿路是一条通过图中（）的路。答：所有结点一次且恰好一次57、在有向图中，结点v的出度deg+（v）表达（），入度deg-（v）表达（）。答：以v为 起 点 的边的条数，以v为终点的边的条数58、设G是一棵树，则G的生成树有（）棵

13、。（1）0（2）1 （3）2（4）不能拟定答：159、n阶无向完全图（的边数是（），每个结点的度数是（）0答：迎口，n-1260、一棵无向树的顶点数n与边数m关系是（）。答：m=n-161、一1个图的欧拉回路是一1条通过图中（）的回路。答：所有边一次且恰好一次62、有n个结点的树，其结点度数之和是（）0答：2n-263、下面给出的集合中，哪一个不是前缀码（）0（1）a,ab,110,a1b11（2）01,001,000,1（3）1,2,00,01,0210）（4）12,11,101,002,0011答：64、n个结点的有向完全图边数是（）,每个结点的度数是（）0答：n（n-1）,2n-265、

14、一个无向图有生成树的充足必要条件是（）0答：它是连通图66、设G是一棵树，n,m分别表达顶点数和边数，则(1)n=m(2)m=n+1(3)n=m+1(4)不能拟定。答：67、设1=V,E是一棵树，若|V|1,则T中至少存在()片树叶。答：268、任何连通无向图G至少有()棵生成树，当且仅当6是(),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有()个 顶

15、点。(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个顶点的连通图中，其 边 数()0(1)最多有n-1条 至 少 有n-1条 最 多 有n条 至 少 有n条答：77、一棵树有2个2度顶点，1个3度顶点，3个4度顶点

16、，则 其1度顶点为()。(1)5 7(3)8(4)9答：(4)78、若一棵完全二元(叉)树有2n-1个顶点，则 它()片树叶。(1)n(2)2n(3)n-1(4)2答：(1)79、下列哪一种图不一定是树()0(1)无简朴回路的连通图(2)有n个顶点n T条边的连通图(3)每对顶点间都有通路的图(4)连通但删去一条边便不连通的图答：80、连通图G是一棵树当且仅当G中()0(1)有些边是割边(2)每条边都是割边(3)所有边都不是割边(4)图中存在一条欧拉途径答：(数理逻辑部分)二、求下列各公式的主析取范式和主合取范式：1、(P T Q)AR解：(PTQ)AROJ PVQ)AR(-,PAR)v (Q

17、AR)(析取范式)O (iP A(Q v iQ)AR)v (,P v P)AQAR)o(iP AQAR)v (iPA i QAR)v (iPAQ AR)v (PAQAR)(-HPAQAR)v (PA-,QAR)v (PAQAR)(主析取范式)i(P-*Q)AR)(PA QAIR)V(IPAQA R)V(PA QAR)v (PAQA IR)v (PAQAR)(原公式否认的主析取范式)(PTQ)AR(PvQ v R)A(Pv iQvR)A(PVQV R)A(-nP v Q vR)A(iP v Q v R)(主合取范式)2、(PAR)v (QAR)v-,P解：(P人R)v (Q人R)v -1P(析取

18、范式)O (PA(QV IQ)AR)v (P v iP)AQAR)v (iPA(QV ,Q)A(RV 1R)O (PAQAR)v (PA IQAR)V(PAQAR)V(IPAQAR)v (-1 P A Q A R)v (-IPAQA-R)v (-1P A Q A R)v (-1P A Q A R)(PAQAR)V(P A IQAR)V(P A Q A R)v (-IPAQA-1 R)v(PAQAR)v (RP/KQAR)(主析取范式)(PAR)v (QAR)VP)O (PAQAR)v (PAQAR)(原公式否认的主析取范式)(PAR)v (QAR)V-,P O(PVQVR)入(PVQVR)(主

19、合取范式)3、(P T Q)A(RVP)解：(P T Q)A(RvP)(PvQ)A(R v P)(合取范式)O (P v Q v (RA ,R)A(P v(Q A-n Q)v R)(PvQ vR)A(P vQ v R)A(PvQ vR)A(PV ,QVR)o(PvQ vR)A(P v Q vR)A(P vQ v R)(主合取范式)-(PTQ)A(R vP)(P v ,Q v 1R)A(iP vQ vR)A(,Pv iQv R)A(,PVQV ,R)A(PVQVR)(原公式否认的主合取范式)J P T Q)A(RvP)(PAQAR)v (PA ,QA ,R)v (PAQA R)v (PA QAR

20、)V(PAQAR)(主析取范式)4、Q T(PVR)解：Q T(P vR)-Qv Pv-R(主合取范式)(Q T(P vR)(1Pv iQ v iR)A(nPv QvR)A(iP vQ v iR)A(PVQVR)A(P vQvR)A(P v Q vR)A(P v Q v R)(原公式否认的主合取范式)QT(P vR)(PAQAR)V(PAQA R)V(PAIQAR)V(PAIQA iR)v(IPAQA iR)v (PAQAR)v (PAQ/R)(主析取范式)5、P T(PA(Q TP)解：P T(PA(Q TP)o Pv(PA(,Q vP)o-.P vPO T(主合取范式)O(PAQ)v (-

21、,PAQ)v (PAQ)V(PAQ)(主析取范式)6、(P-Q)v (RAP)解：(PTQ)v (RAP)(P v Q)v (RAP)O(P/Q)V(RAP)(析取范式)O (PA IQA(Rv iR)v (PA(iQvQ)AR)(PA nQAR)v (PA iQA 1R)v (PA !QAR)v (PAQAR)O (PAQAR)v (PA-,QAR)V(PAQAR)(主析取范式)i(i(PTQ)v (RAP)(PAQA iR)v (iPAQAR)V(,PA ,QAR)v (-.PAQAR)v (PAQAR)(原公式否认的主析取范式)(PTQ)v(R A P)(-1 P v iQ v R)A(

22、P v -)Q v 1R)A(P V QV IR)A(PvQ vR)A(P v Q v R)(主合取范式)7、Pv(PTQ)解：Pv(PTQ)o P V (P v Q)。(P VP)vQo T (主合取范式)(-,PAQ)v (PAQ)v (PAQ)V(PAQ)(主析取范式)8、(R T Q)AP解：(R-Q)AP(RvQ)A P=(RAP)v (QAP)(析取范式)o(iRA(Qv iQ)AP)v (iRvR)AQAP)O (iR AQ AP)v (IRA IQAP)v (iR A Q A P)v (R A Q A P)(PAQA-,R)v (PAQAR)V(PAQAR)(主析取范式)i(R

23、 T Q)A P)(-,PAIQA iR)v (i P A Q A i R)v (PA Q A R)v (-.PAQAR)V(-,PA QAR)(原公式否认的主析取范式)(RTQ)APO(P vQ vR)A(Pv ,QvR)A(,PVQV R)A(P vQ vR)(P v Q vR)(主合取范式)9、PTQ解：P T Q oPvQ(主合取范式)O(-)PA(Qv ,Q)v (-iP v P)AQ)(I P A Q)v(i P A i Q)v(i P A Q)V(P A Q)(IPAQ)V(-nPA-.Q)v(PAQ)(主析取范式)10、PvQ解：P vQ (主合取范式)(PA(,QvQ)v(,

24、PvP)A iQ)O (PAQ)v(PAQ)v(-iPA 1Q)v(PA Q)(PA-,Q)v(PAQ)v(-,PA-,Q)(主析取范式)11、PAQ解：PAQ(主 析 取 范 式)(Pv(QA-nQ)A(PA-,P)VQ)O (P v iQ)A(P v Q)A(P v Q)A(,P v Q)(Pv Q)A(PvQ)A(-,P v Q)(主合取范式)12、(PvR).Q解：(PvR)-Q i(P v R)v Qo(,P 人一1R)vQo J P v Q)入(R v Q)(合取范式)O(,PvQ v(RA ,R)A(,PAP)VQV R)(,PvQvR)A(iPvQ v-nR)A(iP vQ v

25、 IR)A(PVQV-nR)O (nPvQvR)A(nPvQ v iR)A(1PvQ v iR)A(PVQV IR)O (P vQ vR)八(P v Q vR)A(P v Q vR)(主合取范式)(PvR)-Q(-1P v-1 Q v R)A(P v Q v-1R)A(P v Q v R)A(P V-iQvR)A(P V-1Q v-1R)(原公式否认的主析取范式)(PvR)-QO(PAQA R)v(PAQAR)v(iPA QA ,R)v(,PAQA R)v(-HPAQAR)(主析取范式)13、(P-Q)-R解：(P-Q)-RO i(P v Q)v RO(PAQ)v R(析取范式)(P A iQ

26、 A(R v R)v(P v-i P)A(Qv Q)AR)O (PA iQAR)v(PA iQA)R)v (PAQAR)V(PA-IQAR)V(IPAQAR)v(iPA)QAR)(PA IQAR)v(PA-IQA-1R)v(PAQAR)v(IPAQAR)V(PAQAR)(主析取范式)(P f Q)-RO-i(iPvQ)vRO(PAQ)v R(析取范式)O(PvR)A(Q vR)(合取范式)(P v(Q A Q)vR)A(P A-i P)v Q v R)O (P vQ vR)A(P v iQ v R)A(P v Qv R)A(IP V IQ VR)O (PvQvR)A(Pv Q vR)A(P v

27、Q vR)(主合取范式)14、(P.(QAR)A(P.(Q/R)解：(P f(Q/R)(P(Q/R)o J P v (Q A R)A(P v(-iQ A iR)O (-.PvQ)A(PvR)A(P vQ)A(P vR)(合取范式)o(-iP v Q v (RA-iR)A(-iP v (QA iQ)vR)A(PV IQV(RA R)A(P V(Q A)Q)V-1R)O (iPvQ vR)A(-nP vQ v-nR)A(i P V Q V R)A(iP v iQvR)A(P v Q v R)A(P v Q v R)A(P v Q v-R)A(P V-Q v-iR)(-1P v Q v R)A(-P

28、 v Q v-R)A(P v-1Q v R)A(P V-Q v R)A(PvQ v-iR)A(P vQ vR)(主合取范式)(P f (QAR)人(P f (Q八R)o(P vQ vR)A(P vQ vR)(原公式否认的主合取范式)(P-(QAR)A(P f (QAR)O (PAQAR)v(-,PA-,QAR)(主析取范式)15、Pv(P-(Qv(1 Q-R)解：Pv(P f (Qv(Q -R)O Pv(Pv(Qv(QvR)=P vQ vR(主合取范式)i(PvQvR)(Pv)QvR)A(Pv Qv iR)A(PvQ v IR)A(,PVQVR)A(iP vQ v ,R)A(iPv iQvR)

29、A(,Pv ,Qv 1R)(原公式否认的主合取范式)(PvQvR)(PAQAiR)v(PAQAR)V(IPAIQAR)V(PA-1QA-IR)v(PAQAR)V(PAQAR)V(PAQAR)(主析取范式)16、(P.Q)A(P-R)解、(P Q)A(P-R)O(P v Q)A(P v R)(合取范式)(PvQv(RA R)A(-1Pv(-!QAQ)vR)(iPvQvR)A P v Q v -iR)A(iP v-nQvR)A(-nPvQvR)o (PvQvR)A(P v Q vR)(P vQ vR)(主合取范式)(P f Q)A(P-R)o(iPvQ)A(,PvR)(QAR)(合取范式)O (I

30、PA(Qv iQ)A(Rv iR)v(iPvP)AQAR)(i P A Q A R)V(i P A i Q A R)V(i P A Q A i R)V(i P A i Q i R)v(iPAQAR)v(PAQAR)(i P A Q A R)V(-i P A -i Q A R)V (-i P A Q A-i R)v (i P A i Q -iv(PAQAR)（主析取范式）三、证明*1、PTQ,Q v R,R,S vP-)S证明：(1)R前提(2)Q v R前提(3)Q，（2）(4)PTQ前提(5)P(3),(4)(6)-nSvP前提(7)S(5),(6)2、A T（BT C),C T(D v E

31、),F T (D.E),A=BTF证明：(1)A前提(2)AT(BTC)前提(3)BTC(1),(2)(4)B附加前提(5)C，（4）(6)CT(iDv E）前提(7)-,DvE(5),(6)(8)FT(DAE）前提(9)F(7),(8)(10)BTFCP3、Pv Q,PTR,Q-S=Rv S证 明：(1)R附加前提(2)PTR前提(3)P(1),(2)(4)PvQ前提(5)Q(3),(4)(6)QTS前提(7)S(5),(6)(8)RvSCP,(1),(8)4、(PTQ)A(RTS)，(Q T W)A(S T X),证 明：(1)p假设前提(2)PTR前提(3)R(1),(2)(4)(PTQ

32、)A(R T S)前提(5)PTQ(4)(6)RTS(5)(7)Q(1),(5)(8)S(3),(6)(9)(QTW)A(STX)前提(10)QTW(9)(11)STX(10)(12)w(7),(10)(13)X(8),(11)(WAX),P T R=P(14)WAX(12),(13)(15)(WAX)前提(16)(WAX)A(WAX)(14),(15)5、(UvV)-(MAN),UVP,PT(QVS),Q八s=M证明：(1)-Q A S附加前提(2)PT(QvS)前提(3)P(1),(2)(4)UvP前提(5)U，（4）(6)UvV(5)(7)(UvV)T(MAN)前提(8)MAN(6),(

33、7)(9)M(8)6、.BvD,(E TF)TD,E=B证明：(1)B附加前提(2)iB v D前提(3)D(1),(2)(4)(E-F)fD前提(5)（E-F）(3),(4)(6)EAF(5)(7)E(6)(8)E前提(9)EA IE(7),(8)7、PT(Q TR),RT(QTS)=PT(QTS)证明:证明:(1)p附加前提(2)Q附加前提(3)PT(QTR)前提(4)QTR(1),(3)(5)R(2),(4)(6)RT(QTS)前提(7)QTS(5),(6)(8)S(2),(7)(9)QTSCP,(2),(8)(10)PT(QTS)CP,(1),(9)8、P TQ,PTR,R-S=ST-

34、Q证 明：(1)S附加前提(2)R TS前提(3)(1),(2)(4)PTR前提(5)P(3),(4)(6)P TQ前提(7)-Q(5),(6)(8)S TQCP,(1),(7)9、P T(Q T R)=(P T Q)T(P T R)(1)PTQ附加前提P附加前提Q(1),(2)(4)PT(QTR)前提(5)QTR(2),(4)(6)R (3),(5)(7)PTR CP,(2),(6)(8)(PTQ)T(PTR)CP,(1),(7)10、P T(QTR),QTP,STR,P=S证明:11、A,证明:=D(1)P前提(2)P T Q T R）前提(3)i QT i R(1),(2)(4)Q TP

35、前提(5)Q(1),(4)(6)R(3),(5)(7)STR前提(8)(6),(7)ATB,A-C,BT(DTC)(1)A前提(2)ATB前提(3)B(1),(2)(4)ATC前提(5)C(1),(4)(6)BT(DTC)前提(7)D TC(3),(6)(8)2(5),(7)12、AT(CvB),B TA,D TC =A TD证明:(1)A附加前提(2)AT(CvB)前提(3)CvB(1),(2)(4)B T-1A前提(5)B(1),(4)(6)C(3),(5)(7)D TC前提(8)D(6),(7)(9)A TDCP,(1),(8)13、(P-Q)A(R-Q)o (P v R)Q证 明、(P

36、 fQ)A(R f Q)(-1 P v Q)A(R v Q)(iP A iR)v Qo-(PvR)vQ(P v R)-Q14、P-(Q-P)=-,P-(P.1Q)证 明、P-(Q f P)i P v(i Q v P)(iP)v(Pv iQ)P-(P-1 Q)15、(P.Q)A(P.R),(QAR),S vP=S证 明、(1)(P-Q)A(P-R)前提(2)P-(QAR)(3)(QAR)前提(4)P(2),(3)(5)SvP前提(6)S(4),(5)16、P-Q,Q v R,R A-1 S=证 明、(1)P附加前提(2)P-前提(3)Q(1),(2)(4)Q v-1 R前提(5)R(3),(4)

37、(6)R A-i S前提(7)R(6)(8)R A-i R(5),(7)17、用真值表法证明P c QO(PFQ)A(Q-P)证 明、列 出 两 个 公 式 的 真 值 表：PQPcQ(P f Q)A(Q f P)FFTTFTFFTFFFTTTT由 定义可知，这 两 个 公 式 是 等 价 的。18、PTQnPT(P八Q)证 明、设PT(PAQ)为F,则P为T,PAQ为F o所 以P为T,Q为F,从 而PQ也 为F。所以 P T Q n P T (PAQ)O19、用先求主范式的方法证明(PTQ)A(PTR)=(PT(QAR)证明、先求出左右两个公式的主合取范式(PTQ)A(PTR)o J P

38、v Q)A(PvR)(iP vQ v(R A iR)A(Pv(Q A iQ)vR)O (iPvQ vR)A(iP vQ v iR)A(iP v 0 vR)A(PV ,QVR)O (,P v Q v R)A(iPvQ vR)A(iP v iQvR)(PT(QAR)o J P v (QAR)(iP v Q)A(P v R)O (iP vQ v(R A iR)A(iP v(Q A Q)vR)(-1PvQvR)A(PvQ v R)A(PvQvR)A(Pv iQvR)O (iP vQ v iR)A(iPvQ vR)A(iP v iQvR)它们有同样的主合取范式，所以它们等价。20、(PTQ)/x(QvR

39、)证明、设(PTQ)八(Q vR)为T,则P T Q和(Q vR)都 为T。即P T Q和 Q/R都 为T。故P T Q,Q和 R)都为T,即P T Q为T,Q和R都 为F。从 而P也 为F,即P为T。从而(PTQ)A-1 (QvR)21、为庆祝九七杳港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效？前 提：(1)若 A 队得第一，则 B 队 或 C 队获亚军；(2)若 C 队获亚军，则 A 队不能获冠军；(3)若 D 队获亚军，则 B 队不能获亚军；(4)A队获第一；结论：(5)D队不是亚军。证明、设 A:A 队得第一；B:B 队获亚军；C:C 队获亚军；D:D 队获亚军；则前提

40、符号化为A f (BvC),C f A,D-B,A;结论符号化为D。本题即证明 A f (BvC),C-A,D f B,A=D。(1)A 前提(2)A f (B v C)前提(3)BvC(1),(4)C A 前 提(5)-iC(1),(6)B(3),(5)(7)D f B 前提(8)-iD(6),(7)22、用推理规则证明P f Q,(QVR),PAR不能同时为真。证明、(1)PAR前提(2)P(1)(3)P f Q前提(4)Q(2),(3)(5)(QvR)前提(6)-Q A-1 R(5)(7)Q(6)(8)-nQ AQ(4),(7)(集合论部分)四、设A,B,C是三个集合，证明：1、A c

41、(B-C)=(A n B)-(A n C)证 明：(Ac B)(Ac C)=(An B)c A c C=(Ac B)c (A u C)=(A nB n A)u (An Bn C)=An Bn C=Ac(B e C)=Ac(B-C)2、(A-B)u (A C)-A(B n C)证 明：(A-B)u (A-C)=(Ac 后)u (Ac 3)=Ac(B u C)=Ac B c C=A-(BnC)3、A u B=A u C,A UC,则 C=B证 明：B=B u (A c A)=(B u A)c (Bu A)=(C u A)c (CuA)=Cu(A c A)=C4、A u B=A u (B-A)证 明

42、：Au(B-A)=Au(Be A)=(Au B)n (Au A)=(AuB)cU=AuB5、A=B 6 A B=o证 明：=设人=8,贝i)AB=(A-B)o (B-A)=(D u =。u设 AB=,则 A a B=(A-B)u (B-A)=。故 A-B=d ,B-A=O ,从而 A q B,B q A,故 A-Bo6、A n B =A c C,A u B=A u C,则 C=B证明:B=Bc(AuB)=B e(AuC)=(B c A)u(B c C)二(AnC)u (BAC)=C c(AuB)=C c(AuC)二 C7、A cB二AcC,A nB=7 n C,则 C=B证 明：B=Bc (A

43、o A)=(Bc A)u (Be A)=(CcA)u (C c A)=C c(Au A)二 C8、A-(B u C)=(A-B)-C证 明：A(BuC)=A c BVJC=Ac(B c C)=(A c B)c C=(A-B)c C=(A-B)-C9、(A-B)n (AC)=A(Bu C)证 明：(A-B)n (A-C)二 (A c B)c (A c C)二 (AcA)c (8 c C)=Ac BJC=K(BU C)10、A-B=B,则 A=B=。从 而 A=A-B=B=o11、A=(A-B)u (A-C)oA cB cC=0 证 明：=由 于(A-B)u (A-C)=(A c B)=(A c

44、C)=A c(B u C)=Ac finC=A-(Bc C),且 A=(A-B)u (A-C),所以 A=A-(B c C),故 AcBcC=(!)。=由于 AcBcC=由 于(A-B)c (A-C)=(An B)n (An C)=A c(8c C)=An B u C=A-(BuC),且(A-B)c (A-C)=，所以二 A-(BuC),故 A q B u C。由 于(A-B)u (B-A)=A,所以 B-A=A。但(B-A)cA=(I,故 B-A=!)。即 B A,从而 B=(D(否贝 A-B u A,从 而 与(A-B)u (B-A)=A 矛 盾)。=由于 B=，所以 A-B=A 且 B-

45、A=。从 而(A-B)u (B-A)=A。14、(A-B)-CoA-(B-C)证 明：V X e(A-B)-C,有xeA-B 且 x纪C,xeB 且 xe C。从而 xeA,x史B-C,故 xeA-(B-C)。从 而(A-B)-CqA-(B-C)15、P(A)uP(B)cP(AuB)(P(S)表达 S 的幕集)证 明：VSeP(A)oP(B),有 SeP(A)或 SeP(B),所以 S 1 A 或 S q B。从而 SqAuB,故 S e P(A u B)。即 P (A)u P (B)q P (A u B)16、P(A)nP(B)=P(AnB)(P(S)表达 S 的赛集)证 明：V S e P

46、(A)c P(B),有 SGP(A)且 S e P(B),所以 S q A 且 S q B。从而 SqAcB,故 S e P(A c B)。即 P (A)c P (B)q P (A c B)。V S e P(A n B),有 S =AcB,所以 S q A 且 S B。从而 S e P(A)且 S e P(B),故 S e P(A)c P(B)。即 P(A c B)q P(A)c P(B)。故 P(A c B)=P(A)c P(B)17、(A-B)uB二(AuB)-B 当且仅当 B二中。证 明：u 当 B=1)时，由 于(A-B)u B=(A-)u O=A,(A u B)-B=(A u )-二

47、A,所 以(A-B)u B=(A u B)-Bon 用反证法证 明。假 设BH D,则 存 在b e B。由 于beB且b e AuB,所以(A u B)-B o 而显然 b e (A-B)u B o 故 这 与 已 知(A-B)u B=(A u B)-B 矛盾。五、证明或解答：（数理逻辑、集合论与二元关系部分）1、设个体域是自然数，将下列各式翻译成自然语言:(1)3xVy(xy=1);(3)Vx3y(xy=0);(5)Vx3y(xy=x);(7)vxvy3z(x-y二 z)Vx3y(xy=1);(4)3xVy(xy=0);(6)3xVy(xy=x);答:(1)存在自然数X,对任意自然数y满足

48、xy=1；(2)对每个自然数x,存在自然数y满 足xy=1；(3)对每个自然数x,存在自然数y满足xy=O;(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,个体域为自然数。将下列命题符号化：(1)没有小于0的自然数；(2)x z是x y且y z的必要条件；(3)若乂 丫，则存在某些z,使z yz;(4)存在x,对任意v使 得xv二V；(5)对任意x,存在y

49、使x+y=x。答：(1)Vx(G(x,0)vM (0,0,x)或-ax L(x,0)(2)VxVy Vz(L(x,y)AL(y,z)-L(x,z)(3)VxVy(L(x,y)-3z(L(z,0)AG(X Z,yz)(4)Bx VyM (x,y,y)(5)Vx3yA(x,y,x)3、列出下列二元关系的所有元素：(1)A=0,1,2,B=0,2,4,R=|x,yeAnB;(2)A=1,2,3,4,5,B=1,2,R=12 x+y 4 J L x e J L y e B;(3)A=1,2,3,B=-3,-2,-1,0,1),R=|x|=|y|且 xw A且 yeB;解:(1)R=,(2)R=,；(3

50、)R=,o4、对任意集合A,B,证明：若AxA=BxB,则B=B。证明：若8=，则 BxB=(D。从而 AxA=!)。故 A=(D。从而 B=A。若 则 从而 AxA=。对 Vx e B,e Bx Bo 由于 Ax A=BxB,则 eAxA。从而 xeA。故 B屋A。同理可证，AoBo故 B=A。5、对任意集合A,B,证明：若A#，AxB=AxC,则B=C。证明：若8=，则 AxB=!)。从而 AxC=d)。由于 Aw。即 B=C。若 则 AXBH。从而 AXCH(!。对X/xeB,由 于A。，所 以 存 在y e A,使 eAxB。由 于AxB=AxC,则G AxCo 从而 xeC。故 Bq