2023年山东大学离散数学题库及答案计本

《离散数学》题库答案

一、选挎或填空

(数理逻辑部分)

1、下列哪些公式为永真蕴含式？()

(1)-»Q=>Q-P(2)->Q=>PfQ(3)P=>P-Q(4)-1PA(PVQ)=>-IP

答：(1).(4)

2、下列公式中哪些是永真式？()

(1)(-1PAQ)-*(Q---iR)(2)Pf(Q-*Q)(3)(PAQ)-P(4)P-*(PvQ)

答：(2).(3),(4)

3、设有卜.列公式，请问哪几种是永真蕴涵式？()

(1)P=>PAQ(2)P/\Q=>P(3)PAQ=>PVQ

⑷PA(P-Q)=>Q(5)-n(P-Q)=>P(6)-iPA(PVQ)=>iP

答：(2).(3),(4),<5),(G)

4、公式Bx((A(x)rB(y,X))A3ZC(y,z))fD(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、设匕我生病，Q：我去学校，则下列命题可苻号化为()o

(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校

(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校

答：(1)-1QfP(2)Pf-iQ(3)P—->Q⑷-1PfQ

8、设个体域为整数集，则下列公式的意义是()。

3)Vx3y(x+y=0)(2)3yVx(x+y=0)

答：(1)对任一•整数x存在整数y满足x+y=O(2)存在整数y对任一•整数x满足x+y=O

9、设全体域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)T

10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式孔(P(x)vQ(x))在哪个个体域中为真？()

(1)自然数(2)实数(3)夏数(4)(1)一(3)均成立

答：(1)

11、命题”2是偶数或-3是负数”的否认是()o

答：2不是偶数且-3不是负数。

12、永真式的否认是()

(1)永真式(2)永假式(3)可满足式(4)(1)一(3)均有也许

答：(2)

13、公式(一।PAQ)V(―।PA―।Q)化简为()，公式Q->(Pv(P八Q))可化简为()»

答：，Q->P

14、谓词公式Vx(P(x)v力R(y))fQ(x)中量词Vx的辖域是()。

答：P(x)v3yR(y)

15、令K(x):x是实数，Q(x):x是有理数。则命题”并非每个实数都是有理数”的符号化表达为().

答：-nVx(R(x)->Q(x))

(集合论部分)

16、设A={a,{a}},下列命题错误的是(

⑴{a}GP(A)(2){a}CP(A)(3){{a}}GP(A)(4){{a}}CP(A)

答：⑵

17.在C()①之间写上对的的符号.

(1)=(2)1(3)e⑷生

答：(4)

18、若集合S的基数|S|=5,则SII勺恭集H勺基数P(S)|=(

答：32

19、设「二a|«+1)244且x£R),Q={x|5«x2+16且x£R},则下列命题哪个对的()

(1)QUP(2)QCP(3)PUQ⑷P=Q

答：(3)

20.下歹J各集合中，哪几种分别相等(晨

(1)Al={a,b}(2)A2={b,a)(3)A3={a,b,a}(4)A4={a,b,c}

(5)?\5={x|(x-a)(x-b)(x-c)=0}(6)A6={x|x'-(a+b)x+ab=0}

答：A1=A2=A3=A6,A4=A5

21、若A-B=6,则下列哪个结论不也许对H勺？()

(1)A=e(2)B=O>⑶AUB(4)BCA

答：(4)

22、判断下列命题哪个为真？()

(I)A-B=B-A=>A=B(2)空集是任何集合的真子集

(3)空集只是非空集合附子集(4)若人的一种元素属于B,则A=B

答：(1)

23、判断下列命题哪几种为对I向？()

⑴[①，{{中}}}⑵{①}q{①：{{6}}}⑶<l>e{{0}}

(4)中q{6}(5){a,b}G{a,b,{a},{b：}

答：(2),(4)

24、判断下列命题哪几种对的？()

(1)所有空集都不相等(2)(4)若A为非空集，则AUA成立。

答：(2)

25、设AnB=Anc,AnB=Anc,贝]B()C。

答：=(等于)

26、判断下列命题哪儿种对的？()

(1)若AUB=AUC,则B=C(2){a,b}={b,a}

(3)P(AAB)NP(A)nP(B)(P(S)表达SI内吊集)

(4)若A为非空集，则A。AUA成立。

答：(2)

27、A,B,C是三个集合，则下列哪几种推理对的：

(1)ACB,BCC=>ACC(2)ACB,BCC=>AeB(3)AeB,BGC=>AGC

答：⑴

(二元关系部分)

28.设4={1,2,3,4,5,6),B=(l,2,3),从人到已的关系R={<x,y)|x=y}求(1)R(2)Rl

答：(1)R={<1,1〉,〈4,2»(2)R-I=K1,1>,<2,4>}

29、举出集合A上的既是等价关系又是偏序关系的一种例子。()

答：A上的恒等关系

30、集合A上的等价关系的三个性质是什么？()

答：自反性、对称性和传递性

31、集合A上的偏序关系的三个性质是什么？()

答：自反性、反对称性和传递性

32、设S={1,2,3,4},A上啊关系R={{1,2〉，《2,1〉，〈2,3〉,<3,4>)

求⑴RoR(2)求。

答：RoR={<1,1),〈1,3〉，〈2,2〉，〈2,4)}

R"={(2,1),(1,2),(3,2),(4,3))

33、设4={1,2,3,4,5,6},R是A上的整除关系，求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、设4={1,2,3,4,5,6},B={1,2,3},从A到Bl内关系R={<x,y>|x=2y：s求⑴R(2)Rl,

答：(1)R=f<l,1\<4,2>,<6,3>}(2)R-，=f<l,1>,<2,4>,(36>1

2

35、设八=11,2,3,4,5,6},B=(l,2t3),从A到Bl向关系R={<x,y)|x=y],求R和R”的关系矩阵。

loo

ooo

OOO100000

答：R的关系矩阵=R的关系矩阵=000100

010

000000

000

000

36、集合A={1,2,…,10}上的关系1^={＜%丫＞/+丫=10,%丫£后,则R的性质为()。

(1)自反的(2)对称的(3)传递的，对称的(4)传递的

答：(2)

(代数构造部分)

37、设4={2,4,6),A上的二兀运算*定义为：a*b=max{a,b},则在独异点＜A,*)中，单位兀是()，零兀是()»

答:2,6

38、设4={3,6,9},A上的二元运算*定义为:a*b=min{a,b},则在独异点＜A,*＞中，单位元是（）,零元是（）;

答：9,3

（半群与群部分）

39、设（G,*）是一种群，则

（1）若a,b,xWG,a*x=b»则x=（）；

（2）若a,b,x£G,a*x=a*b,则x=（）（.

答：（I）a-，*b（2）b

40、设a是12阶群的J生成元，则求是（）阶元素，@'是（）阶元素。

答：6,4

41、代数系统《,*》是一种群，则G的等基元是（）,,

答：单位元

42、设a是10阶群的生成元，则1是（）阶元素，£是（）阶元素。

答：5,10

43、群倔*〉11勺等第元是（），有（）个。

答：单位元，1

44、素数阶群一定是（）群，它的生成元是（）。

答：循环群，任一非单位元

45、设（G,*）是一种群，a,b,cGG,则

（1）若c*a=b,则c=（）：（2）若c*a=b*a,则c=（）。

答：（1）b*rz-1（2）b

46、＜H,：*〉是＜。，*〉/、J子群口勺充足必要条件是（）o

1

答：＜H＞:*＞是群或Va,bEG,a*bGH,aGH或Da,bEG,a*b'GH

47、群＜A,*＞的等帮元々（）个，是（），零元杓（）个。

答：1,单位元，0

48、在一种群〈G,*〉中，若G中的元素a时阶是k,则小的阶是（）.

答：k

49、在白然数集N上，下列哪种运算是可结合的？（）

（1）a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=Ia-bI

答:(2)

50、任意一种具有2个或以上元的半群，它()。

(1)不也许是群(2)不一定是群

(3)一定是群(4)是互换群

答：⑴

51、6阶有限群的任何子群一定不是()。

(D2阶(2)3阶(3)4阶(4)6阶

答：⑶

(格与布尔代数部分)

52、下列哪个偏序集构成有界格()

(1)(N：<)(2)(Z,>)

(3)({2,3,4,6,12}/(整除关系))(4)(P(A),C)

答：⑷

53、有限布尔代数的元素的个数一定等于(

(1)偶数⑵奇数(3)4的倍数⑷2的正整多次事

答：(4)

(图论部分)

54、设G是种哈密尔顿图，则G定是().

⑴欧亚图⑵树⑶平面图⑷连通图

答：⑷

55、下而给出的集合中，哪一种是前缀码？()

(1)(0,10,110,101111)(2){01,001,000,1)

(3){b,c,aa,ab,aba}(4){1,11,101,00L0011}

答：(2)

56、一和图的哈密尔顿路是一条通过图中()1向路。

答：所有结点一次且恰好一次

57、在有向图中，结点v的出度deg.(v)表达(),入度deg(v)表达()。

答：以Y为起点的边的条数，以v为终点的边的条数

58、设G是一棵树，则G的生成树和()保。

(1)0(2)1(3)2(4)不能确定

答：1

59.n阶无向完全图K,H勺边数是()，每个给点的度数是(晨

少〃(〃T)

答：--------,n-l

2

60、一根无向树的顶点数n与边数m关系是()o

答：m=n-l

61、一和图的欧拉回路是一条通过图中()1向回路。

答：所有边一次且恰好一次

62、有n个结点H勺树，其结点度数之和是()o

答:2n-2

63、下面给出的集合中，哪一种不是前缀码()。

(1){a,ab,110,albll}(2){01,001,000,1}

(3){1,2,00,01,0210}(4){12,11,101,002,0011)

答：⑴

64、n个结点的有向完全图边数是(),每个结点的度数是()。

答:n(n-l),2n-2

65、一和无向图有生成树的充足必要条件是()。

答：它是连通图

66、设G是一棵树，n,m分别表达顶点数和边数，则

(1)n=m(2)m=n+l(3)n=m+l(4)不能确定。

答:(3)

67、设1=<V,E>是一棵树，若则T中至少存在()片树叶。

答：2

68、仟何连通无向图G至少有()棵生成树，当且仅当G是(),G的牛成树只有一棵。

答：1,树

69、设C是有n个结点m条边的连通平面图，且有k个面，则k等于：

(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。

答：(1)

70、设I是一棵树，则T是一种连通且()图。

答：无简朴回路

71、设无向图G有16条边且每个顶点的度数都是2,则图6有()个顶点。

(1)10(2)4(3)8(4)16

答：(4)

72、设无向图G有18条边且每个顶点的度数都是3,则图6有()个顶点。

(1)10(2)4(3)8(4)12

答：⑷

73、设图G=<V,E>,V={a,b,c,d,e),片{<&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)最多有nT条⑵至少有n-1条

(3)最多有n条(4)至少有n条

答:(2)

77、一枳树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为：)。

(1)5(2)7(3)8(4)9

答：⑷

78、若一棵完全二元(又)树有2nT个顶点，则它()片树叶。

(1)n(2)2n(3)n-1(4)2

答：⑴

79、下到哪一种图不一定是树()o

(1)无同朴回路的连通图(2)ffn个顶点n-1条边的连通图

(3)每对顶点间均有通路的图(4)连通但删去•条边便不连通的图

答：(3)

80、连通图G是一棵树当且仅当G中()0

(1)有些边是割边(2)每条边都是割边

(3)所有边都不是割边(4)图中存在一条欧拉途径

答:(2)

(数理逻辑部分)

二、求下列各公式的主析取范式和主合取范式：

1、(P-*Q)AR

解：(P-Q)AROJPVQ)/\R

<z>(-iPAR)V(QAR)(析取范式)

<z>(-!PA(V)AR)V((-1PVP)AQAR)

<z>(-iPAQAR)V(-iPA-1QAR)V(-IPAQAR)V(PAQ,\R)

^(-IPAQARJVC-IPA^QA^VCPAQAR)(主析取范式)

-1((P-Q)AR)<=>(-IPA-1QA-IR)V(-1PAQA-IR)V(PA-IQAR)

V(PAQA-IR)V(PA—IQA—IR)(原公式否认的主析取范式)

(P—Q)AR<z>(PVQVR)A(PV—IQVR)A(—IPVQV—IR)

A(-,PVIQVR)A(-1PVQVR)(主合取范式)

2、(PAR)V(QAR)V-nP

解：(PAR)V(QAR)V-1P(析取范式)

O(P/UV-I)AR)V((PV->P)AQAR)V(->PA(V->)A(RV-1R))

»(PAQAR)V(PA-IQAR)V(PAQAR)V(-IPAQAR)

V(-1PAQAR)v(-lPAQA-iK)V(-)PA-1QAR)V(-)PAIQA-)R)

(PAQAR)V(PA-IQARJV(-IPAQAR)V(-IPAQA-IR)V(-IPA—IQAR)V(—IPA—IQA—IR)(主

析取范式)

-i((PAR)V(QAR)V-«P)

O(P八」QA-(R)v(PAQA-IR)(原公式否认的主析取范式)

(PAR)V(QAR)V->P<=>(-1PVQVR)A(-.PV-1QVR)(主合取范式)

3、(-1P-Q)A(RVP)

解：(-1P-*Q)A(RVP)

<=>(PVQ)A(RVP)(合取范式)

»(PVQV(RA-(R))A(pv(A-|))VR)

<z>(PVQVR)A(PVQV-1R)A(PVQVR)A(PV-!QVR)

<^>(PVQVR)A(PVQV—1R)A(PV->QVR)(主合取范式)

((ffQ)A(RVP))

<^>(PV-|QV—1R)A(-«PVQVR)A(-|PV—|QVR)A(—)PVQV—)R)

A(-,PV-,QV-,R)(原公式否认的主合取范式)

(「P-Q)A(RVP)

O(-1PAQAR)V(F?A-1QA-1R)V(PAQA—»R)V(PA-1QAR)V(PAQAR)

(主析取范式)

4、Q-*(PV-nR)

解：Q-(PV-iR)

<=>-.QVPV->R(主合取范式)

-n(Q-(PV-nR))

-iPV-1QV—।R)A(-1PV—।QVR)A(~iPVQV-iR)A(-1PVQVR)

A(PV-iQVR)A(PVQV-nR)A(PVQVR)(原公式否认的主合取范式)

Q-(PV-iR)

(PAQAR)v(PAQA-iR)v(PA—iQAR)v(PA-iQA-iR)v(—iPAQA-iR)

V(—iPA—iQAR)V(―iPA-iQA-iR)(主析取范式)

5、P-*(P八(Q-P))

解：P-(PA(Q-P))

<=>-iPV(PA(-iQVP))

<=>-iPVP

<=>T(主合取范式)

<=>(-«PA-iQ)V(->PAQ)V(P/X-iQ)V(PAQ)(主析取范式)

6,-I(P-Q)V(RAP)

解：-AP-Q)V(RAP)<=>-i(-iPVQ)V(RAP)

<z>(PA-)Q)v(RAP)(析取范式)

(PA-iQA(KV—>R))V(PA(—iV)AR)

<^>(PA—iQAR)V(PA-iQA-iR)V(PA—iQAR)V(PAQAR)

<=>(PA-1QAR)V(PA->QA-(R)V(PAQAR)(主析取范式1

—i(―।(P-Q)V(RAP))U>(PAQA―।R)V(—iPAQAR)V(—iP/\—iQAR)

V(—IPA—>QA-IR)V(—IPAQA-IR)(原公式否认向主析取范式)

―।(P-*0)V(RAP)(-1PV—।0VR)A(PV—10V—।R)A(PVQv―।R)

A(PVQVR)A(PViQVR)(主合取范式)

7、PV(P-Q)

解：PV(P-Q)OPV(—1PVQ)O(PV->P)VQ

<=>T(主合取范式)

<=>(-IPA-nQ)V(IPAQ)V(PA-IQ)V(PAQ)(主析取范式)

8、(RfQ)AP

解：(R-Q)AP<=>(-iRVQ)AP

<=>(-1RAP)V(QAP)(析取范式)

<=>(-1RA(V-I)AF)V((-IRVR)AQAP)

<2>(-IRAQAP)V(-1RA->QAP)V(-1RAQAP)V(RAQAP)

<z>(PAQA-nR)V(PA-IQA-1R)V(PAQAR)(主析取范式)

-1((K-Q)AP)<=>(-1PA-1QA-1R)V(-1PAQA-1R)V(PA-1QAR)V(IP/\QAR)V(「PA-1QAR)(原公式否认

的主析取范式)

(R-*Q)AP<=>(PVQVK)A(PV-iQVR)A(「PVQV-iR)

A(PV-|QV-.R)A(PVQV-.R)(主合取范式)

9、P-Q

解：PfQO-1PVQ(主合取范式)

<z>(-iPA(V->))V((-iPVP)AQ)

<=>(-I?AQ)V(-)PA-IQ)V(-iPAQ)V(PAQ)

<=>(-iPAQ)V(iPA-iQ)V(PAQ)(主析取范式)

10、PV-nQ

解：PV-.Q(主合取范式)

<=>(PA(->V))V((-)PVP)A-.Q)

O(PA-iQ)V(PAQ)V(-iPA-iQ)V(PA-iQ)

O(PA-iQ)V(PAQ)V(-iPA-iQ)(主析取范式)

11、PAQ

解：PAQ(主析取范式)<=>(PV(A-I))A((PA-)P)VQ)

<=>(PV-iQ)A(PVQ)A(PVQ)A(-iPVQ)

<=>(PViQ)A(PVQ)A(-.PVQ)(主合取范式)

12、(PVR)->Q

解：(PVR)-Q

=(PVR)VQ

OjP人-iR)VQ

<=>(-iPVQ)A(-.RVQ)(合取范式)

=(->PVQV(RArR))A((-)PAP)VQV-nR)

<=>(->PVQVR)A(-»PVQV-IE)A(-)PVQV-)R)A(PVQV-iR)

O(-iPVQVR)A(iPVQV-nE)A(iBVQViR)A(PVQV-iK)

O(-1PVQVR)A(-iPVQV-nE)A(PvQVR)(主合取范式)

-i(PVR)fQ

<=X-IPV-1QVR)A(-1PV-IQV-IR)A(PVQVR)A(PV-1QVR)A(PV-IQV-1R)(原公式否认的主析取范式)

(PVR)->Q

OCPAQA-nRjvCPAQA^VC^PA-iQA-i^VC-nPAQA-nR)

V(-iPAQAR)(主析取范式)

13、(P->Q)->R

解：(P->Q)->R

<z>-i(-iPVQ)VR

<=>(PA-iQ)VR(析取范式)

<z>(PA-iQA(RV-(R))V((PV-.P)A(V-i)AK)

<=>(PA—iQAR)V(PA—iQA—iR)V(PAQAR)V(PA—«QAR)V(—)PAQAR)

V(—।PA—।QAR)

<z>(PA-iQAR)V(PA-«QA-1R)V(PAQAR)V(-1rAQAR)

V(—iPA—«QAR)(主析取范式)

(P->Q)->R

—i(―iPVQ)VK

<z>(PA」Q)VR(析取范式)

<=>(PVR)A(「QVR)(合取范式)

O(PV(A-!)VR)A((PA-IP)V-!QVR)

<=>(PVQVR)A(PV-iQVR)A(PV-iQVR)A(-iPV-iQVR)

<z>(PVQVR)△(PV-iQVR)△(-1PV「QVR)(主合取范式)

14、(P—>(QAR))A(—iP—>(—iQA—iR))

解：(P->(QAR))A(IP->-iR))

<=>(-.Pv(QAR))A(PV(-1QA-«R))

<=>(-,PVQ)A(-,PVR)A(PV-,Q)A(PV-,R)(合取范式)

O(-1PVQV(R/\rR))八(一|PV(A-))VR)A(PV->QV(RA-)R))

A(PV(A—i)V—iR)

<=>(-1PVQVR)A(-iPVQV-IR)A(-IPVQVR)A(—)PV-iQVR)

A(PV-iQVR)A(PV-nQV-iR)A(PVQV-iR)A(PV-iQV-nR)

<=>(—>PVQVR)A(-iPVQV—1R)A(-)PV—(QVR)A(PV—iQVR)

A(PVQV-iR)A(PV-iQV「R)(主合取范式)

—।(P—>(QAR))A(—।P—>(―।QA—।R)J

0(-1PV-.QV-.R)八(PVQVR)(原公式否认的主合取范式)

(P->(QAR))A(「P->(-IQA-IR))

<=>(PAQAR)V(「PA-nQA」iO(主析取范式)

15、PV(f(QV(「QfR)))

解：PV(-iPf(QV(」QfR)))

<=>pv(PV(Qv(QvR)))

<=>PVQVRC主合取范式)

-i(PVQVR)

O(PV-iQVR)A(PV-iQV->E)A(PVQV-«R)A(-iPVQVR)

A(―iPVQV-iR)A(—iPV—।QVR)A(—iPV—iQV-iR)

(原公式否认IKJ主合取范式)

(PVQVR)

O(-nPAQ八一!R)V(-IPAQAE)V(-1PA-iQAlOx/TA-nQ八1R)

V(P△-iQ八R)V(PAQ△rR)V(P△QAR)(主析取范式)

16、(PfQ)A(P->R)

解、(PfQ)A(PfR)

<=>(-.PVQ)A(-iPVR)(合取范式)

(―IPVQV(RA-iR)A(—iPV(―iA)VR)

<=>(-1PVQVR)A(-1PVQViR)A(-iPViQVR)A(-1PVQVR)

Q(「PVQVR)人(一1PVQV-!4)人(-1PVrQVR)(主合取范式)

(PfQ)/\(PfR)

<=>(-«P\/Q)入(「PVR)

a-1PV(Q人R)(合取范式)

<=>(-1PA(V-I)A(RV-|R))V((-)PVP)AQAR)

<=>(-)PAQAR)V(-iPA-1QAR)V(-1PAQA-,R)V(-iPA-1Q-1R)

V(-iPAQAR)V(PAQAR)

O(-.PAQAR)V(->PA-iQAR)V(-iPAQA-IR)V(-IPA-1Q-1R)V(PAQAR)

(主析取范式)

三、证明：

1、P—Q,-1QVR,―iR,-nSVP^-nS

证明：

(li-iR前提

(2)->QVR前提

•3)—iQ(1),(2)

14)P~Q前提

•5)-iP⑶，(4)

(6)->SVP前提

(7)―।s(5),(6)

2、A-*(B-*C),C-*(-iDvE),-nF-*(DAiE),A=>B-*F

证明:

(I)A前提

•2)A7B-C)前提

⑶B-C(1),(2)

(4iB附加前提

i：5)C(3),(4)

•6)C-*(-.DVE)前提

i：7)-iDvE(5),(6)

•8)—iF-*(DA—IE)前提

(9)F(7),(8)

(10)BTCP

3、PVQ,P-*R,QT=>RVS

证明:

⑴-1R附加前提

⑵I」R前提

⑶-1P(1),(2)

⑷PVQ前提

⑸Q(3),(4)

(6)Q-*S前提

⑺S(5),(6)

⑻RVSCP,(1),(8)

4、(P-Q)A(RfS),(Q-*W)A(S-*X),(WAX),P-*R=>-1P

证明：

(1)P假设前提

(2)P-*R前提

(3)R⑴，(2)

(4)(P-*Q)A(R-S)前提

(5)P-Q(4)

(6)R-S(5)

(7)Q(1),(5)

(8)S(3),(6)

⑼(QfW)A(S-X)前提

(10)Q-W<9)

(11)s-*x(10)

U2)w⑺，(1C)

(13)X(8),(11)

(14)WAX(12),(13)

(15)-1(WAX)前提

(16)-1(WAX)A(WAX)(14),(15)

5、(UW)-*(MAN),UVP,P-*(QVS),-nQA-)S=>M

证明:

(1.1-1QA—।S附加前提

⑵P-(QVS)前提

(3)-1P(1),(2)

(4)UVP前提

(5)U(3),(4)

(6)UVV(5)

(7)(UVV)-*(MAN)前提

(8)MAN(6),(7)

(9)M⑻

6、一।BVD(E-*-iF)-*-iD,E=>->B

证明：

•1)B附加前提

•2)—iBVD前提

⑶D(1),(2)

⑷(E-*—iF)-*—«D前提

⑸—i(E—•—iF)(3),(4)

•6)EA-nF(5)

•7)E(6)

•8)-iE前提

•9)EA-iE(7),(3)

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)Rf(QfS)前提

(7)Q-S(5),(6)

(8)S(2),(7)

(9)Q-SCP,(2),(8)

(10)P~(QT)CP,⑴，(9)

8、P-----!Q,IP~R,K-----1s=>S----->Q

证明：

(1)S附加前提

(2)R-*―।S前提

⑶-iR(1),(2)

(4)-iP~R前提

(5)P(3),(4)

•6)P--IQ前提

(7)—iQ(5),(6)

(8)S-----iQCP,(1),(7)

9、P►(Q-R)=>(r-Q)►(P-R)

证明:

(1)P-Q附加前提

(2)P附加前提

(3)Q(1),(2)

(4)P-*(QfR)前提

(5)Q-R(2),(4)

(6)R(3),(5)

(7)P-RCP,⑵，⑹

(8)(P-Q)-YPfR)CP,(1),(7)

10、PT-nQ—iR),Q-->P,S-R,P=>-iS

证明：

(1)P前提

⑵前提

⑶-iQ-*—.R⑴，(2)

(4)Q-----iP前提

⑸—1Q⑴，(4)

⑹-iR(3),(5)

(7)S-R前提

(8)—।S⑹，⑺

11、A,A-B,A-*C»B-*(D-----iC)=>-iD

证明:

(1)A前提

(2)A-B前提

(3)B⑴，(2)

(4)A-C前提

(5)C⑴，(4)

•6)B-*(D-*—iC)前提

•7)D-----iC(3),(6)

(8)->D(5),(7)

12、A>(CVD),Ba-iA,I)»―iC=>A•-―।D

证明:

⑴A附加前提

(2)A-(CVB)前提

(3)CVB(1),(2)

(4)Bf->.A前提

(5)-nB(1),(4)

(6)C(3),(5)

(7)D--1C前提

(8)-iD(6),(7)

(9)A--1DCP,(1),(8)

13、(P->Q)A(RfQ)<=>(PVR)->Q

证明、

(P-»Q)A(RfQ)

<=>(-iPVQ)A(-iRVQ)

<z>(-iPA-iR)VQ

(PVR)VQ

<=>(PVR)fQ

14、PT(QfP)<=>「Pf(Pf-iQ)

证明，

Pf(QfP)

<=>-iPV(-iQVP)

<z>-i(-iP)V(iPV-iQ)

<=>-iP->(Pf-iQ)

15、(P->Q)A(PfR),-i(QAR),svp=>s

证明、

(1)(PfQ)A(P->R)前提

(2)P->(QAR)(1)

(3)-I(QAR)前提

(4)-iP(2),(3)

(5)SVP前提

(6)s(4),(5)

16、PT-iQ,QV「R,RA_1S=>「P

证明、

(1)P附加前提

(2)P->-iQ前提

(3)-iQ(1),(2)

(4)QV-iR前提

(5)-iR(3),(4)

(6)RA—)S前提

(7)R(6)

(8)RA-iR(5),(7)

17、用真值表法证明PCQO(PfQ)A(QfP)

证明、

列出两个公式的真值表：

PQp—q(PfQ)A(Q->P)

FFTT

FTFF

TFFF

TTTT

山定义可知，这两个公式是等介的。

18、P-QnP->(P/\Q)

证明、

设P-(PAQ)为F,则P为T,PAQ为F。因此P为T,Q为F,从而P-Q也为F。因此P-Q=>P-(P八Q)。

19、用先求主范式的措施证明(P-Q)A(P-R)<=>(P-*(QAR)

证明，

先求出左右两个公式的主合取范式

(P-Q)A(P-R)<Z>(-!PVQ)A(-)PVR)

(—।PVQV(RA―।R)))/\(―।PV(A—।)VR)

(­।PvQvR)/\(-1PvQv-1R)人(-1PvQvR)/\(-1Pv-1QvR)

<=>(—iPvQv-iR)A(—iPvQvR)A(—iPv—iQvR)

(P-*(QAR))<=>(-iPv(QAR)•

<z>(-1PVQ)A(「PVR)

OC^PVQV(RA-,R))A(-iPv(A-,)VR)

O(-1PVQVR)A(-1BVQV-1R)A(->PVQVR)A(->PV-1QVK)

O(「PVQV-)R)A(「PVQVR)入([PV-iQx/R)

它们有同样口勺主合取范式，因此它们等价。

20、(P-Q)A-I(QVR)=>-)P

证明、

设(P-*Q)△-1(QVR)为T,则P-Q和一i(QvR)都为T。即P-*Q和一iQA「R都为T。故P-*Q.~iQ和一iR)都为T,即P-*Q

为T,Q和R都为F。从而P也为F,即一iP为T。从而(P-Q)八一।(QvR)=>-iP

21.为庆祝九七吞港回归祖国，四支足球队进行比赛，已知状况如下，问给论4否有效？

前提：(I)若A队得第一，则B队或C队获亚军；

(2)若C队获亚军，则A队不能获冠军；

(3)若D队获亚军，则B队不能获亚军；

(4)A队获第一；

结论：(5)D队不是亚军。

证明、

设飞A队得第一;B:B队获亚军;C:C队获亚军;D:D队获亚军；则前提符号化为Af(BvC),Cf「A,Of->B,A；结论

符号化为「及

本题即i正明A—>(BVC)»C—>―।A»D—>—।B,=y>―iD。

(1)A前提

(2)Af(BVC)前提

(3)BVC(1),(2)

(4)C—>-iA前提

(5)-iC(1),(4)

(6)B(3),(5)

(7)D->-iB前提

(8)-iD(6),(7)

22、用推理规则证明P-Q,->(QVR),P八R不能同步为真。

证明、

(1)PAR前提

⑵P(1)

⑶P->Q前提

(4)Q⑵，⑶

⑸-i(QVR)前提

(6)―>QA-iR(5)

(7)->Q(6)

(8)-iA(4),(7)

(集合论部分)

四、设A,B,C是三个集合，证明：

1、AC(B-C)=(ACH)-(ACC)

证明：

(AnB)-(AAC)=(AC1B)CACC=(ACB)C(4UC)

=(ACBCA)u(AnBnC)=AHBnC=AC(BnC)

=AC(B-C)

2,(A-B)O(A-C)=A-(BnC)

证明:

(A-B)U(A-C)=(ACB)5ACC)=AC(BOC)

=ACBcC=A-(Bnc)

3、AUB=ADC,ADB=AUC,则C=B

证明：

B=BU(ACA)=(BDA)C(BUA)

=(cuA)n(cuA)=CU(A