2023年离散数学题库及答案

《离散数学》题库答案

一、选择或填空

(数理逻辑部分)

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

⑴=>QTP(2)「Q=>PTQ(3)P=>PTQ(4)「P八(PvQ)二〉「P

答：⑴,(4)

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

⑴JP人Q)T(QT「R)(2)PT(QTQ)(3)(PAQ)-P⑷PT(PVQ)

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

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

⑴P=>PAQ(2)PAQ=>P(3)PAQ=>PVQ

⑷PA(PTQ)二>Q(5)「(PTQ)=>P(6)「PA(PVQ)=>「P

答：(2),(3),(4),(5),(6)

4、公式Vx((A(x)fB(y,x))A3ZC(y,z))fD(x)中，自由变元是(),

约束变元是()o

答：x,y,x,z

5、判断下列语句是不是命题。若是，给出命题的真值。()

(1)北京是中华人民共和国的首都。(2)陕西师大是一座工厂。

(3)你喜欢唱歌吗？⑷若7+8>18,则三角形有4条边。

(5)前进！(6)给我一杯水吧！

答：(1)是，T(2)是，F(3)不是

(4)是，T(5；不是⑹不是

6、命题”存在一些人是大学生”的否认是(),而命题“所有的人都

是要死的”的否认是()o

答：所有人都不是大学生，有些人不会死

7、设P：我生病，Q:我去学校，则下列命题可符号化为()o

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

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

答：(1)「QTP(2)PT「Q(3)(4)「PfQ

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

(1)Vx3y(x+y=O)(2)3yVx(x+y=O)

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

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是偶数,谓词公式3x(P(x)vQ(x))

在哪个个体域中为真？()

(1)自然数⑵实数(3)复数(4)(1)一(3)均成立

答：⑴

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

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

12、永真式的否认是()

(1)永真式⑵永假式⑶可满足式⑷(1)一(3)均有也许

答:(2)

13、公式([PAQ)v(「PA「Q)化简为(),公式Qf(Pv(P八Q))可化简

为()。

答：「P,QfP

14、谓词公式Vx(P(x)vRR(y))->Q(x)中量词X/x的辖域是()。

答：P(x)v3yR(y)

15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理

数”的符号化表达为()o

答：—«Vx(R(x)->Q(x))

(集合论部分)

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

(1){a}“(A)(2){a}cP(A)(3){{a}}eP(A)(4){{a}}cP(A)

答：⑵

17、在0()①之间写上对的的符号。

(1)=(2)e(3)e(4)任

答：(4)

18、若集合S的基数|S|二5,则S的幕集的基数|P(S)|二()0

答：32

19、设P={x|(x+1)2<4且XER},Q={x|5<x2+16且x$R},则下列命题哪个对

的()

(1)Q<=P(2)QcP(3)P(=Q(4)P二Q

答：⑶

20、下列各集合中，哪几个分别相等()o

答：(2)

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

(1)AcB,BcC=>AcC(2)AcB,BcC=>AEB(3)AEB,BEC=>AeC

答：⑴

(二元关系部分)

28、设人={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y?},

求⑴R(2)R-1o

答:(1)R={<1,1>,<4,2>](2)R-'=«1,1>,<2,4>}

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

答：A上的恒等关系

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

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

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

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

32、设S={1,2,3,4},A上的关系口={〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉}

求⑴RoR(2)R1o

答：RQR=(<1,1>,<1,3>,<2,2>,<2,4>)

K={〈2,1〉，<1,2>,<3,2>,<4,3>}

33、设八={1,2,3,4,5,6},R是A上的整除关系，求R={()}o

答：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},

求⑴R(2)R

答:(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},从A到B的关系R={〈x,y〉|x=y?},

求R和R7的关系矩阵。

IoO

ooO

ooO100000

答：R的美系矩阵二o1ORT的关系矩阵二000100

ooO000000

oo

一OJ

36、集合A={1,2,…，10}上的关系R={<x,y>|x+y=10,x,yeA},则R的性质

为（）o

（1）自反的（2）充■称的（3）传递的，对称的（4）传递的

答：（2）

（代数结构部分）

37、设A={2,4,6},A上的二元运算*定义为：a*b=max{a,b},则在独异点

<A,*>中，单位元是（）,零元是（)o

答：2,6

38、设A={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,xWG,a*x=a*b,则x=(）。

答：(1)a'*b(2;b

40、设a是12阶群的生成元，则2?是（）阶元素，2?是（）阶元素。

答：6,4

41、代数系统《,*＞是一个群，则G的等赛元是（）o

答：单位元

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

答：5,10

43、群4,*》的等赛元是（），有（）个。

答：单位元，1

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

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

45、设＜G,*＞是一个群,a,b,cEG,则

(1)若c*a=b,则c=();(2)若c*a二b*a,则c=()。

答：⑴b*/(2)b

46、＜H,,*＞是4,,*）的子群的充足必要条件是（）o

答：是群或XXa,bGG,a*beH,a'GH或XXa,bGG,a*b-1GH

47、群VA,*＞的等冢元有（）个，是（）,零元有（）个。

答：1,单位元，0

48、在一个群〈G,*〉中，若G中的元素a的阶是k,则aT的阶是（）。

答：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个或以上元的半群，它（）o

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

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

答：⑴

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

(1)2阶(2)3阶(3)4阶⑷6阶

答：(3)

(格与布尔代数部分)

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

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

(3)({2,3,4,6,12),|(整除关系))(4)(P(A),q)

答:(4)

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

(1)偶数(2)奇数(3)4的倍数(4)2的正整数次露

答：(4)

(图论部分)

54、设G是一个哈密尔顿图，则G一定是()o

(1)欧拉图⑵树(3)平面图⑷连通图

答：(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阶无向完全图的边数是（）,每个结点的度数是（）o

答：必”e

2

60、一棵无向树的顶点数n与边数m关系是（）o

答：m-n-1

61、一个图的欧拉回路是一条通过图中（）的回路。

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

62、有n个结点的树，其结点度数之和是（）o

答：2n-2

63、下面给出的集合中，哪一个不是前缀码（）o

（1）{a,ab,110,a1b11}（2）{01,001,000,1）

（3）{1,2,00,01,0210）（4）{12,11,101,002,0011}

答：⑴

64、n个结点的有向完全图边数是（）,每个结点的度数是（）o

答：n（n-1）,2n-2

65、一个无向图有生成树的充足必要条件是（）o

答：它是连通图

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

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

答：⑶

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

答：2

68、任何连通无向图G至少有()棵生成树，当且仅当6是(),

G的生成树只有一棵。

答：1,树

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

--

(1)mn+2(2)nm-2(3)n+m-2(4)m+n+2o

答：⑴

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

答：⑶

76、在有n个顶点的连通图中，其边数()o

(1)最多有rr1条(2)至少有n-1条

⑶最多有n条⑷至少有n条

答：(2)

77、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点

为()。

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

答：⑷

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

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

答：⑴

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

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

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

答：(3)

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

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

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

答：⑵

(数理逻辑部分)

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

1、(PTQ)AR

解：(PTQ)/\Ro(「PvQ)AR

<=>(IPAR)v(QAR)(析取范式)

<=>(-1PA(QV—1Q)AR)v((—1PvP)AQAR)

<=>(—IPAQAR)v(—IPA—IQAR)v(—)PAQAR)v(PAQAR)

<=>(IPAQAR)v(IPA->QAR)v(PAQAR)(主析取范式)

—i((PTQ)ARJ^C-IPA-HQA—iR)v(—IPAQA—IR)V(PA—IQAR)

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

(P->Q)AR<=>(PVQVR)A(Pv-iQvR)A(-IPVQV-nR)

△(「Pv「QvR)A(「PvQvR)(主合取范式)

2、(PAR)v(QAR)v-,P

解：(PAR)v(QAR)V「P(析取范式)

<=>(PA(Qv-iQ)AR)v((Pv-iP)AQAR)v(—iPA(QV-)Q)A(RV-IR))

<=>(PAQAR)v(PA—IQAR)V(PAQAR)V(IPAQAR)

v(~IPAQAR)v(~IPAQA-।R)v(-1PA—iQAR)v(-।PA―10A―।R)

<=>(PAQAR)V(PA—IQAR)V(—IPAQAR)V(—IPAQA-IR)V

(-IPA—IQAR)V(-IPA-lQA-lR)(主析取范式)

-n((PAR)V(QAR)V^P)

U>(PA-.QA「R)v(PAQA「R)(原公式否认的主析取范式)

(PAR)v(QAR)Vo(「PVQVR)八(「PVVR)(主合取范式)

3、(「PTQ)八(RvP)

解：（［PTQ）八（RvP）

<=>(PvQ)A(RvP)(合取范式)

=(PvQv(RA—iR))A(Pv(QA—iQ))vR)

<=>(PvQvR)A(PvQv—iR)A(PvQvR)A(PV-IQVR)

<=>(PvQvR)A(PvQv—1R)A(Pv-nQvR)(主合取范式)

((「PTQ)A(RvP))

<=>(Pv—iQv-iR)A(—।PvQvR)A(「Pv-iQvR)A(-nPVQV—)R)

A(_,Pv「Qv「R)(原公式否认的主合取范式)

(「PTQ)A(RvP)

<=>(-IPAQAR)V(PA-»QA—IR)v(PAQA-iR)v(PA—)QAR)V(PAQAR)

(主析取范式)

4、QT(Pv「R)

解：QT(Pv「R)

(主合取范式)

「(QT(Pv「R))

O(-1Pv-iQv-iR)A(—iPv-nQvR)A(-iPvQv-iR)A(—IPVQVR)

A(Pv-nQvR)A(PvQv-.R)A(PvQvR)(原公式否认的主合取范式)

QT(Pv-,R)

<=>(PAQAR)v(PAQA-nR)v(PA—!QAR)v(PA—IQA—IR)V(—«PAQA—)R)

v(^PAIQAR)V(-1PA-1QA-1R)(主析取范式)

5、PT"(QTP))

解：PT(PA(QTP))

<=>-iPv(PA(-iQvP))

<=>-iPvP

=T(主合取范式)

O(IPA-IQ)v(IPAQ)v(PA「Q)V(PAQ)(主析取范式)

6、「(PTQ)v(R八P)

解：［(PTQ)v(RAP)(［PvQ)v(RAP)

O(PA「Q)V(RAP)(析取范式)

=(PA—IQA(Rv—)R))v(PA(—IQVQ)AR)

<=>(PA—IQAR)v(PA—IQA—IR)V(PA—10AR)V(PAQAR)

O(PA-HQAR)v(PA「Q人［R)v(PAQAR)(主析取范式)

—i(-1(PTQ)v(RAP))<=>(PAQA—iR)v(—iPAQAR)v(—iPA—10AR)

v(「P/\」Q/\」R)V(「P/\QA「R)(原公式否认的主析取范式)

—।(PTQ)v(RAP)=(—iPv—nQvR)A(Pv—iQv—iR)A(PvQv—।R)

A(PvQvR)A(Pv^QvR)(主合取范式)

7、Pv(PTQ)

解：Pv(P->Q)«PV(iPvQ)<=>(PV-,P)vQ

=T(主合取范式)

u>(「P八］Q)v(-.PAQ)v(PA「Q)V(PAQ)(主析取范式)

8、(R->Q)AP

解：(RTQ)八Po(「RvQ)AP

O(^RAP)V(QAP)(析取范式)

<=>(-)RA(QV-IQ)AP)v((-iRvR)AQAP)

O(—IRAQAP)v(—IRA—IQAP)v(—iRAQAP)V(RAQAP)

<=>(PAQA-nR)v(PA-,QA「R)V(PAQAR)(主析取范式)

—i((RTQ)AP)<=>(-IPA—>QA-iR)V(—IPAQA—»R)V(PA-IQAR)

V(->P八Q/\R)V(-.PA八R)(原公式否认的主析取范式〉

(RTQ)AP<=>(PvQvR)A(Pv-nQvR)A(-nPVQV「R)

A(PviQviR)A(PvQviR)(主合取范式)

9、PTQ

解：PTQ=「PvQ(主合取范式)

O(,PzA(Qv.Q))v((.PvP)AQ)

<=>(-1PAQ)v(->PA-iQ)v(-1PAQ)v(PAG)

O(「PAQ)v(「PA「Q)v(P/\Q)(主析取拈式)

10、Pv「Q

解：Pv「Q(主合取范式)

=(P/\(^QvQ))v((^PvP)A-.Q)

<z>(PA-1Q)V(PAQ)V(-1PA-nQ)V(PA「Q)

<=>(P/\]Q)V(PAQ)v(「P八「Q)(主析取范式)

11、PAQ

解：PAQ(主析取范式)«(Pv(QA-nQ))A((PA^P)VQ)

O(PV—iQ)A(PVQ)A(PVQ)A(-1PvQ)

«(Pv-iQ)A(PvQ)A(^PvQ)(主合取范式)

12、(PvR).Q

解：(PvR)fQ

=-.(PvR)vQ

<=>(—।PA—iR)vQ

O([PvQ)A(「RvQ)(合取范式)

o(—iPvQv(RA—iR))A((—IPAP)VQV—IR)

(―।PvQvR)A(—।PvQv—।R)A(—।PvQv—।R)A(PVQV—।R)

<=>(—iPvQvR)A(-IpvQv—iR)A(-iPvQv—IR)A(PVQV—IR)

o(「PvQvR)A(「PvQv「R)A(PvQv「R)(主合取范式)

」(PvR)-Q

<=>(-iPv-iQvR)A(-1Pv-iQv-iR)A(PvQvR)A(PV—IQVR)A(PV-IQV—IR)

(原公式否认的主析取范式)

(PvR)-Q

<=>(PAQA-iR)v(PAQAR)v(-IPA-IQA—)R)V(—IPAQA-IR)

v(.PAQAR)(主析取范式)

13、(P.Q)->R

解：(P-Q)-R

O-i(-iPvQ)vR

O(PA->Q)vR(析取范式)

=(PA—IQA(Rv—IR))v((Pv—।P)A(QV—IQ)AR)

(PA―iQAR)V(PA―iQA—iR)V(PAQAR)V(PA—i0AR)V(―iPAQAR)

v(-1P八「QAR)

<^>(PA—»QAR)V(PA-1QA-1R)V(PAQAR)V(-1PAQAR)

V(-1PA「QAR)(主析取范式)

(P->Q)-R

O—i(—iPvQ)vR

U>(P/\]Q)vR(析取范式)

=(PvR)A(「QvR)(合取范式)

<=>(Pv(QA-iQ)vR)A((PAP)VQVR)

U>(PvQvR)A(Pv-iQvR)A(Pv-iQvR)AJPV-IQVR)

<_>(PvQvR)A(Pv-nQvR)A(->Pv「QvR)(主合取范式)

14、(PT(QAR))A(「P->(「QA「R))

解：(Pf(QAR))A(「Pf(「Q/\]R))

=(QAR))A(PV(「QA「R))

<=>(iPvQ)A(「PvR)A(Pv-nQ)A(Pv「R)(合取范式)

<=>(—iPvQv(RA—।R))A(―।Pv(QA—।Q)vR)A(PV―।Qv(RA―।R))

A(PV(QA-10)V-1R)

O(-1PvQvR)A(—IPvQv-iR)A(-1Px/QvR)A(-IPV-nQVR)

A(Pv—iQvR)A(Pv—)Qv—»R)A(PvQv—।R)A(PV—)QV—।R)

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

A(PvQv「R)A(Pv-.Qv「R)(主合取范式)

「(Pf(OAR))A(「Pf(-1QA-(R))

o(-.Pv-.Qv-.R)八(PvQvR)(原公式否认的主合取范式)

(P-(QAR))A(「P-(IQAIR))

<=>(PAQAR)v(「PA-IQA「R)(主析取范式)

15、pv(「p.(Qv(「Q-R)))

解：Pv(「Pf(Qv(「Q->R)))

<=>Pv(Pv(Qv(QvR)))

OPvQvR(主合取范式)

」(PvQvR)

«(Pv—)QvR)A(Pv—iQv—iR)A(PvQv—)R)A(—।PVQVR)

A(-iPvQv-iR)A(-iPv—«QvR)A(-iPv-nQv-!R)

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

(PvQvR)

<z>(—।PAQA―iR)V(—iPAQAR)V(—iPA—iQAR)V(PA—iQA―iR)

v(PA-IQAR)v(PAQA「R)V(PAQAR)(主析取范式)

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

解、(P->Q)A(P->R)

=(「PvQ)A(「PVR)(合取范式)

(—iPvQv(RA—।R)A(।Pv(—)QAQ)vR)

<=>(「PvQvR)A(-iPvQv-nR)A(-iPv-nQvR)A(-iPvQvR)

o(-.PvQvR)A(->PvQv[R)A(-.Pv->QvR)(主合取范式)

(PfQ)A(PfR)

=(-nPVQ)A(-iPVR)

O「Pv(QAR)(合取范式)

O(「PA(QV「Q)八(RV[R))V((「PVP)AQAR)

»(—IPAQAR)v(-IPA—>QAR)V(-IPAQA-.R)V(-)PA—IQ—IR)

v(—iPAQAR)v(PAQAR)

O(—)PAQAR)v(—IPA—IQAR)v(-IPAQA—)R)V(―1P八―1()V(PAQAR)

(主析取范式)

三、证明：

1、PTQ,-iQvR,-1R,-1SvP->S

证明：

(1)「R前提

(2)—।QvR前提

(3)(1),(2)

(4)PTQ前提

(5)「P(3),(4)

(6)-.SvP前提

(7)「S(5),(6)

2、AT(BTC),CT(「DvE),「FT(D八「E),A二)BTF

证明：

(1)A前提

(2)AT(BTC)前提

(3)BTC(1),(2)

(4)B附加前提

(5)C(3),(4)

(6)CT(—IDvE）前提

(7)-.DvE(5),(6)

(8)—iFT(DA「E）前提

(9)F(7),(8)

(10)BfFCP

3、PvQ,PTR,QTS二)RvS

证明：

(1)iR附加前提

(2)PTR前提

(3)「P(1),(2)

(4)PvQ前提

(5)Q(3),(4)

(6)QTS前提

(7)S(5),(6)

(8)RvSCP,(1),(8)

4、(PTQ)△(RTS),(QTW)A(STX)(WAX),PTR=>「P

证明：

(1)P假设前提

(2)PTR前提

(3)R(1),(2)

(4)(PTQ)A(RTS)前提

(5)PTQ(4)

(6)RTS(5)

(7)Q(1),(5)

(8)S(3),(6)

(9)(Q->W)A(STX)前提

(10)QTW(9)

(11)STX(10)

(12)W(7),(10)

(13)X(8),(11)

(14)WAX(12),(13)

(15)「(W/xX)前提

(16)「(WAX)A(WAX)(14),(15)

5、(UvV)->(MAN),UVP,PT(QVS),-,0AIS=>M

证明：

(1)—iQA—iS附加前提

(2)PT(QvS)前提

(3)「P(1),(2)

(4)UvP前提

(5)U(3),(4)

(6)UvV(5)

(7)(UvV)->(MAN)前提

(8)MAN(6),(7)

(9)M(8)

6^—(BvD,(ET「F)T「D,「E二》」B

证明：

(1)B附加前提

(2)->BvD前提

(3)D(1),(2)

(4)(Ef前提

(5)「（E-*「F）(3),(4)

(6)EA-.F(5)

(7)E(6)

(8)-.E前提

(9)EA—iE(7),(8)

7、PT(QTR),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、PT-)Q,「PTR,RT「S二)ST「Q

证明：

(1)S附加前提

(2)RT—IS前提

(3)「R(1),(2)

(4)「PTR前提

(5)P(3),(4)

(6)PT「Q前提

(7)iQ(5),(6)

(8)ST「QCP,(1),(7)

9、PT(QTR)=>(PTQ)T(PTR)

证明：

(1)PTQ附加前提

(2)P附加前提

(3)Q(1),(2)

(4)PT(QTR)前提

(5)QTR(2),(4)

(6)R(3),(5)

(7)PTRCP,(2),(6)

(8)(PTQ)T(PTR)CP,(1),(7)

10、PTjQTiR),QT「p,STR,P=＞「S

证明:

(1)P前提

(2)PT（「QT「R）前提

(3)「QT-.R(1),(2)

(4)QT「P前提

(5)iQ(1),(4)

(6)「R(3),(5)

(7)STR前提

(8)—iS(6),(7)

11、A,ATB,ATC,BT(DT-)C)=＞「D

证明:

(1)A前提

(2)ATB前提

(3)B(1),(2)

(4)ATC前提

(5)C(1),(4)

(6)BT(DT「C)前提

(7)DT-1c(3),(6)

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

12、AT(CvB),BT「A,DT「C二)AT「D

证明：

(1)A附加前提

(2)AT(CvB)前提

(3)CvB(1),(2)

(4)BT「A前提

(5)「B(1),(4)

(6)C(3),(5)

(7)DT「C前提

(8)「D(6),(7)

(9)AT—)DCP,(1),(8)

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

证明、

(PfQ)A(RfQ)

=(—iPvQ)A(—।RvQ)

<Z>(-)PA-IR)VQ

<=>-i(PvR)vQ

<_>(PvR)—>Q

14、p_>(Q->P)=[P->(P->]Q)

证明、

Pf(QfP)

<=>-iPv(iQvP)

<=>—i(—«P)v(—।Px/—iQ)

(Pf「Q)

15、(P-Q)A(P-R),-I(QAR),SVP=S

证明、

(1)(PfQ)A(PfR)前提

(2)P>(QAR)⑴

(3)-1IQAR)前提

(4)iP(2),(3)

(5)SvP前提

(6)S⑷，⑸

16、P.「Q,Qv-iR,RA-1Sn-iP

证明、

(1)P附加前提

(2)Pf-nQ前提

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

(4)Qv—।R前提

(5)-1R(3),(4)

(6)RA-1S前提

(7)R(6)

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

17、用真值表法证明P.Q=(P-Q)A(Q-P)

证明、

列出两个公式的真值表：

PQP6Q(PfQ)A(Q-P)

FFTT

FTFF

TFFF

TTTT

由定义可知，这两个公式是等价的。

18、PTQ=PT"Q)

证明、

设PT(PAQ)为F,则P为T,PAQ为F。所以P为T,Q为F,从而PTQ也为F。

所以PTQnPT(PAQ)O

19、用先求主范式的方法证明(PTQ)△(PTR)o(PT(QAR)

证明、

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

(PTQ)A(PTR)o(「PvQ)A(「PvR)

<=>(—iPvQv(RA「R)))A(—iPv(QA—iQ)vR)

<=>(—iPvQvR)A(-iPvQv—iR)A(—iPvQvR)A(—)PV—IQVR)

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

(PT(QAR))=(「Pv(QAR))

<=>(—IPvQ)A(—1PvR)

O(-iPvQv(RA-iR))A(-iPv(QA-iQ)vR)

o(—)PvQvR)A(—)PvQv—iR)A(—iPvQvR)A(—IPV—iQvR)

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

它们有同样的主合取范式，所以它们等价。

20、(PTQ)A[(QVR)=>IP

证明、

设(PTQ)A[(QVR)为T,则PTQ和「(QvR)都为T。即PTQ和A「R都为T。

故PTQ,和「R)都为T,即PTQ为T,Q和R都为F。从而P也为F,即「P为T。

从而(PTQ)△—।(QvR)=>—1P

21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问

结论是否有效？

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

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

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

(4)A队获第一;

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

证明、

设A:A队得第一；B:B队获亚军；C：C队获亚军；D:D队获亚军；则前提符号化为

Af(BvC),Cf「A,Df「B,A：结论符号化为「D。

本题即证明A->(BvC),C->「A,D->[B,A=>iDo

(1)A前提

(2)Af(BvC)前提

⑶BvC(1),⑵

(4)Cf-1A前提

⑸~nC(1),(4)

(6)B(3),(5)

(7)Df「B前提

(8)「D(6;,(7)

22、用推理规则证明P->Q,「(QVR),PAR不能同时为真。

证明、

(1)PAR前提

(2)P(1)

(3)PfQ前提

(4)Q(2),(3)

(5)「(QvR)前提

(6)—«QA->R(5)

(7)「Q(6)

(8)-iQAQ(4),(7)

(集合论部分)

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

1、An(B-C)=(AnB)-(AnC)

证明：

(AnB)—(AnC)=(AnB)cAcC=(AcB)c(AuC)

二(AcBcA)u(AcBcC)二AcBcC=Ac(BnC)

二Ac(B-C)

2、(A—B)u(A—C)二A—(BnC)

证明：

(A-B)(A-C)=(AnB)(AnC)=Ac(BkjC)

二AcBcC=A-(BnC)

3、AuB=AuC,7uB=AuC,则C二B

证明：

B二Bu(AnA)=(BuA)n(BuA)

=(CuA)n(CvA)=Cu(AcA)二C

4、AoB—Au(B-A)

证明：

Au(B-A)=AD(BnA)=(AuB)n(AuA)

二(AuB)cU=AuB

5、A=B<=>A㊉B=6

证明：

n设A=B,贝IAaB二(A-B)o(B-A)二①u(D二①。

<=设A㊉B=①，则A㊉B二(A-B)u(B-A)二①。故A-B二①，B-A二①,

从而AqB,BcA,故A二B。

6、AcB—AcC,AB—AuC,则C—B

证明:

B二Be(AuB)=Be(A=C)二(BcA)u(BcC)

=(AnC)=(BDC)=Cn(AoB)

=Cn(A=C)

二C

7、AcB=AcC,7nB=7nC,则C二B

证明：

B二Be(AuA)=(BnA)(BnA)

二(CcA)u(CnA”Cc(AuA)

=C

8、A-(BuC)=(A-B)-C

证明：

A—(BuC)=AcBuC

=An(BnC)=(AnB)cC

=(A-B)cC=(A-B)-C

9、(A—B)n(A—C)=A一(BuC)

证明：

(A-B)n(A-C)

=(AnB)n(AnC)

二(AcA)c(BcC)

=An8DC二A一(BuC)

10、A-B=B,则A二B二①

证明：

由于B=A-B,所以B二BeB二(A-B)cB=①。从而A二A-B二B二中。

11、A二(A-B)U(A—C)OACBCC=(D

证明：

n由于(A—B)u(A—C)=(AnB)(AnC)=An(BuC)

二AcBcC=A-(BcC),且A=(A-B)u(A-C),

所以A二A-(BnC),故AcBcC二①。

U由于AcBcC=①，所以A-(BcC)=A。而A-(BcC)二(A-B)u(A-C),

所以A=(A-B)u(A-C)o

12、(A-B)c(A-C)二中=AqBuC

证明：

=由于(A—B)c(A-C)=(AnB)n(AnC)=An(BnC)

=AnBuC=A-(BUC),且(A—B)c(A-C)二①，

所以①二A-(BuC),故AqBuC。

<=由于AqBuC,