离散数学期末复习题

淮海工学院2011-2012-2离散数学期末复习题答案

一、选择题〔每题3分)

1、以下句子中哪个不是命题？(C)

A、你通过了离散数学考试B、我俩五百年前是一家

C、我说的是真话D、淮海工学院是一座工厂

2、以下联接词运算不可交换的是(C)

A、ABvC>-

3、命题公式「尸fQ不能表述为(B)

A、P或QB、非P每当QC、非P仅当QD、除非P,否则Q

4、以下公式中为永真式的是(C)

A、尸—(产AQ)B、-nP-»(PA2)C.(尸八。)7QD、(PvQ)fQ

5、以下公式中为非永真式的是(B)

A、(尸V「P)->QC、PA(「P->Q)D、尸Q)

6、设个体域A={〃力},那么谓词公式大(尸(x)八G(x))消去量词后，可表示为为(C)

A、(尸(。)A/(〃))v(G(。)AGS))B、(F(a)vF(h))A(G(«)VG(b))

C、(F(a)AG(。))v(F(b)AG(。))D、(F(tz)vG(〃))A(F(b)vG(b))

7、设个体域4={。,〃},那么谓词公式V灯)火(.)，)去掉量词后，可表示为(D)

A、a)AR(ayb)AR(b,a)AR(b,b)B>R(a,a)vR(a、b)\/R(b,a)\/R(b,b)

C、A/?(«,/?))a)A/?(/?,£?))(7?(a,a)vR(a,b》/\(R(b,a)vA(〃㈤)

8、设。：全总个体域，H(x)：x是人，P(x)：x犯错误，

那么命题“没有不犯错误的人”的逻辑符号化为(D)

A、3x(//(x)AP(x))B>Bx(H(x)—>P(x))C>\/x(H(x)AP(X))D、VX(H(X)—>P(x))

9、设。：全总个体域，产(x)：工是花，A/(x)：x是人，H(x,y)：x喜欢y,

那么命题“有的人喜欢所有的花”的逻辑符号化为(D)

A、Vx(M(x)/\》/(y)f"5,y))B、Vx("(x)八V)，(尸(y)f”(x,y))

C、3x(M(x)A3y(F(y)->H(x,y))D、3x(M(x)AV)，(b(J)->H(x,y))

10、设。为空集，那么以下为假命题的是(A)

A、0G0B、0O0C>0G{0)D、0C{0}

11、设。*各不相同，那么下述等式为真的是(D)

Ax[a,b]={{a},{b}}B、{a,Z?}={{〃,/?}}

C.({a}U{b}}={a,b}D.=

12、设集合A={O,0},。为空集，p(A)为A的募集，那么以下为假命题的是(B)

A、0Gp(A)B、OGp(A)C、{0}Gp(A)D、{0}Gp(A)

13、设集合A={0,0},。为空集，p(4)为A的募集，那么以下为假命题的是(B)

A、0ap(A)B、{0}qp(A)C、{0}ap(A)D、{{0}}=p(4)

14、非空集合X上的空关系。不具备的性质是(A)

A、自反性B、反自反性C、对称性D、传递性

10、设4={1,2,3}上的关系R的关系图如下，那么R不具备的性质为(A)

A、自反性B、反自反性C、反对称性D、传递性

15、4={1,2,3,4}上的嫁/?={<1,3>,<1,4>,<2,3〉,<2,4〉,<3,4>}只不具备(C)

A、反自反性B、反对称性C、对称性D、传递性

16、设尺为4={1,2,3}上的关系，其关系图如下，那么以下为真命题的是(C)

A、H对称，但不反对称B、R反对称，但不对称

C、R对称，又反对称D、R不对称，也不反对称

17、设氏为4={1,2,3,4}上的关系，其关系图如下，那么以下为假命题的是(C)

A、R不自反，也不反自反B、R不对称，也不反对称

C、K传递D、R不传递

18、设4={1,2,3},那么A上不同等价关系的个数为(C)

A、3B、4C、5D、6

19、设4={1,2,3,4},那么A上不同等价关系的个数为(C)

A、13B、14C、15D、16

20、设A、Z分别为实数集、整数集，那么以下函数为满射而非单射的是(C)

A、f:R—R,/(x)=x+6B、fR,/(x)=(x+6)2

C、/:/?->Z,/(x)=[x]D、f:RTR,f(x)=x6+6x

21、设R、斤、Z+分别为实数集、非负实数集、正整数集，以下函数为单射而非满射的是(B)

A、f:RTR,/(x)=-x2+7x-lB.f:Z'TR,/(A)=Inx；

C、—冗/(X)=WD、于：RTR、f(x)=7x+\

22、设|x|=3,|y|=4,那么从X到y可以生成不同的单射个数为(B).

A、12B、24C、64D、81

23、设|X|=3,|y|=2,那么从X到y可以生成不同的满射个数为(B).

A、6B、8C、9D、64

24、设集合A的哥集为p(A),r、U、—、x为集合的交、并、差、笛卡尔乘积运算，那么以下系统中是

代数系统的为(D)

A、〈夕(A),。)B、(夕(A),J〉C、(p(A),-)D、(夕(A),x)

25、在自然数集上定义的以下四种运算，其中满足结合律的是(C)

A、a*b=a-bB、a*b=\a-b\C、=max{a,〃}D、a^h=a+2b

26、设为前AN2个自然数集，+«表示模及加法，对代数系统A=(N«,+J,有[A)

A、0是么元，无零元B、1是么元，无零元C、无么元，0是零元D、无么元，无么元

27、设M.为前A22个自然数集，x氏表示模左乘法，对代数系统A=(NQXJ,有(B)

A、1是么元，无零元B、1是么元，()是零元C、无么元，0是零元D、无零元，无么元

28、设非空有限集S的密集为夕(S),对代数系统A=(p(S),Q”有(B)

A、①是么元，S是零元B、①是零元，S是么元C、唯一等甯元D、无等耗元

29、设非空有限集S的密集为1(S),对代数系统A=(2(S),J〉，有(A)

A、中是么元，S是零元B、(D是零元，S是么元C、唯一等哥元D、无等耗元

30、设Z是由所有整数组成的集合，对于以下*运算，代数系统<Z,*>为独异点的是(B)

A、a*b=aC>a*b=a+abD、”*/>=max(a,/?)

31、任意具有多个等察元的半群，它(A)

A、不能构成群B、不一定能构成群C、能构成群D、能构成阿贝尔群

32、以下命题正确的选项是(B)

A、简单回路必为根本回路B、根本回路必为简单回路

C、简单回路必不是根本回路D、根本回路必不是简单回路

33、欧拉回路是(B)

A、路径B、简单回路C、既是根本回路也是简单回路D、既非根本回路也非简单回路

34、哈密尔顿回路是(C)

A、路径B、简单回路C、既是根本回路也是简单回路D、既非根本回路也非简单回路

35、在任何有向图中，以下命题正确的选项是(C)

A、任意顶点的入度与出度都相等B、任意顶点的入度与出度都不相等

C、所有顶点的入度之和与出度之和都相等D、所有顶点的入度之和与出度之和都不相等

36、设有向线图G的顶点集丫={匕,匕，…，匕}，邻接矩阵4=(他)称”，那么deg-(»)=(D)

〃〃〃

A、%B、£%C、Z&D、Z%

i=l>1J=1

37、设有向线图G的顶点集1/一{4，为，…，匕}，邻接矩阵4-(％)…，那么deg+(q)=(C)

A、%B、2%C、Z%D、2%

J=ij=i

38、在有n个结点的简单无向图中，其边数(C)

A、最多有n-1条B、至少有n-1条C、最多有皿二。条D、至少有此二。条

22

39、在有n个结点的简单有向图中，其边数(C)

A、最多有n-1条B、至少有n-1条C、最多有条D、至少有条

40、在有n个结点的连通图中，其边数(B)

A、最多有U-1条B、至少有ii-l条C、最多有n条D、至少有n条

41、设/={0,{1},{1,3},{1,2,3}},那么设上包含关系“口”的哈斯图为(C)

42、集合A={1,2,3,4}上的偏序关系图为

那么它的哈斯图为(A)

43、以下哪一种图不一定是树(C)

A、无简单回路的连通图B、有n个顶点n-1条边的连通图

C、每对顶点间都有通路的图D、连通但删去一条边便不连通的图

44、设G是有5个结点的无向完全图，那么从G中删去(C)条边可以得到树

A、4B、5C、6D、10

二、填充题〔每题4分)

1、当赋予极小项足标相同的指派时，该极小项的真值为L当赋予极大项足标相同的指派时，该极大项

的真值为。

2、任意两个不同极小项的合取式的真值为。，而全体极小项的析取式的真值为1.

3、任意两个不同极大项的析取式的真值为L而全体极大项的合取式的真值为Q.

4、〃个命题变元可构造包括F的不同的主析取范式类别为二.

5、〃个命题变元可构造包括7的不同的主合取范式类别为三.

6、假设已证土iA(x)为真，那么可假设某一确定的个体)”记［(y)为真，此推理规则被称为竺.

7、令「是公理与前提的合取，「中无x的自由出现，假设从「可推出4工)，那么从「也可推出可/*

)，此推理规则被称为四.

8、p(0)={0),丽0))={0,{0}},2(夕({中}))={0,{0},{{0}},{0,{0}}}.

9.p(0)-0^{0}>p(/9(0))-/9(0)={{0}}.

1()、设/4={〃},那么/9(4)xp(A)={<0,0>,<0,a>,vA,0>,<A,A>}.

11、设集合分别含有〃〃个不同元素，那么4x5的基数为丝，夕(Ax8)的基数为经，

12、Ax0(8)的基数为④2”,p(A)x8的基数为〃2'",夕(4)xp(8)的基数为？二.

13、设4={1,2,3,4,6,近24},“〈”为A上函获系，那么偏序集vA,金>而最小元为上最小元

为「极大元为2生、最大元为斑."

14：设A={2,3,4,6,8,12},三”为A上整除关系，那么偏序集vA,W>的极小元为2,3,最小元为

&极大元为8,12,最大元为工，既非极小元也非极大元的是4,6.

15、设囚卜加,|片="，那么从x到y有空种不同的二元关系，有巴二种不同的函数.

16、在一个有〃个元素的集合上，可以有2)种不同的二元美系，有种不同的函数，

有里种不同的双射.

17、设A二{2,4,6},A上*为:a*b=max{a,b},那么在代数系统<A,*>中,么元是2，零元为§・

18、设人={3,6,9},A上*为：a*b=min{a,b},那么在代数系统<A,*>中,么元是2,零元为

19、设〈G*〉是一个群，那么

(1)假设a,b,x£G,a*x=b,那么x=a'*b；(2)假设a,b,x£G,a*x=a*b,那么x=b.

20、群<G*>的等基元是么无，有_L个，零元有9个.

21、设。是12阶群的生成元，那么/是金阶元素，/是生阶元素.

22、设〃是10阶群的生成元，那么,是,阶元素，疗是此阶元素.

23、在一个群〈Q*〉中，假设G中的元索•。的阶是k,那么才|的阶是

24、n阶无向完全图Kn的边数是业5,每个结点的度数是〃-1.

2----

9101、

1011

25、设有向图6=〈丫，E>,V={匕-2/3,匕}的邻接矩阵A=]]o0，

J000;

那么匕的入度deg-(匕)=3,匕的出度deg+(匕)=1.

26、设无向图G有18条边且每个顶点的度数都是3,那么图G有旦个顶点.

27、一棵无向树的顶点数为n,那么其边数为注1,其结点度数之和是2kz.

28、设T=<V,E>是一棵树，假设那么T中至少存在2片树叶.

三、问答题〔每题6分)

1、假设个体域。={—1,3,6},S(x)：x>3,Q(x)：x=5«：3,P：5>3,

那么谓词公式3x(S(x)t0(a))AP为真吗？为什么？

答：为真；

<^>((0->0)V(0->0)V(1->0))A1<^>(1V1V0)A1»1.

2、谓词公式由VxP(x,y)为真吗？为什么？

答：不为真；设个体域。：实教域，P(x,y)：x+y=0,

那么V灯)，P(x,y)—寺，VxP(x,y)=1->0o0.

3、设4={1,2,3},问A上存在一个既不是自反又不是反自反的关系吗？为什么？

答：存在；如R={vl,l>,vl,2>}.

4、设4={1,2,3},问4上存在一个既不是对称又不是反对称的关系吗？为什么？

答：存在；如/?={<1,2>,<1,3>,<2/>}.

5,设A={1,2,3},问A上存在一个既是对称又是反对称的关系吗？为什么？

答：存在；如A={vl,l>,v2,2>,<3,3>}.

6、设4二{2,3,4},B={2,4,7,10,12),从A到8的关系

K={va,〃>|a£A,〃e8,且。整除圻，试给出R的关系图和关系矩阵，并说明此关系R及其

逆关系是否为函数？为什么？

解：/?={<2,2>,<2,4>,<2,10>,<2,12>,<3,12>,<4,4>,<4,12>},那么R的关

系图为：

R的关系矩阵为

关系A不是A到3的函数,

因为元素2,4的象不唯一

12

逆关系R"也不是B到A的函数

因为元素7的象不存在.

7、设Z为整数集，函数/：ZxZ-Z,且/(x,y)=x+y,问/是单射还是满射？

为什么？并求/(x,x),/(x,-x).

解：Vx£ZJ<O,x>wZxZ,总有/(O,x)=x,那么/是满射；

对于<1,2>,<2,1>WZXZ,,有/(1,2)=3=/(2,1),而vl,2>wv2/>,那么/非单射；

/(x,x)=2xJ(x,—x)=0.

8、设Z为整数集合，定义为：。助二/，问其在Z上封闭吗？可交换吗？可结合吗？

答：①取”=2,b=T,a*〃=2"任Z,其在Z上不封闭；

②取a=2,〃=1时，a*〃=q"=2,b*a=ba=],其在Z上不可交换；

③取a=2,b=\,c=2,(a*b)*c=4,a*(b*c)=2,(a*份*cWa*(b*c),其在Z上不可结合.

9、设Z为整数集合，“*”定义为：。祐=2必，问其在Z上封闭吗？可交换吗？可结合吗？

答：①整数乘法运算在Z上封闭，

②Va,/?eZ,a*b=2ab=2ba=b*a,其在Z上可交换；

@Vfl,b,ceZ»(a*b)*c=2(2ab)*c'=4abc-2aX2bc=2a(b*c)=a*(b*c),其在Z上可结合.

10、设无向图G=〈匕£)有12条边，有6个3度顶点，其余顶点的度数均小于3,问G中至少有多

少个顶点？

答：设G中度数小于3的顶点有％个，那么由欧拉定理工deg(u)=24知，

veV

度数小于3的顶点度数之和为6,故当其余的顶点度数都为2时，G的顶点最少，

即G中至少有9个顶点.

11、〃取怎样的值，无向完全图K”有一条欧拉回路？

答：〃为奇数，VvGV,deg⑴=〃T为偶数，

所以，当〃是大于或等于3的奇数时，K“有欧拉回路.

12、判断以下无向图是否存在欧拉路径？是否为欧拉图？说明理由.

答:d(A)=2,d(B)=d(0=d(D)=4d(E)=d(F)=3

只有两个奇数度的结点，有欧拉路径，如EDBEFCABCDF；

由于每个结点的次数不均为偶数，所以不是欧拉图.

13、判断以下图是否为欧拉图？说明理由，是否存在哈密尔顿回路？

答：一个无向图D是欧拉图OD是连通的，且所有顶点的度等于偶数，

所以是欧拉图，但无哈密尔顿叵路.

14、判断以下图是否存在欧拉路径？是否为欧拉图？说明理由.

答：一个有向图D是欧拉图U>D是连通的，且所有顶点的入度等于出度，

所以是欧拉图，存在欧拉路径.

四、填表计算题〔每题10分)

1、对命题公式A=Tpiq)Mp7q),要求

(1)用0或1填补其真值表的空格处；(2)求该命题公式的主析取范式与主合取范式.

解：

PqpfqTp->g)A

001000

01i010

100111

11i010

主析取范式A=Z(2)；主合取范式Aon(0,L3).

2、对命题公式A=(prq)cr,要求

II）用0或1填补其直值表的空格处：（2）求该命题公式的本析取范式与主合取范式.

PqrpiqA

000i0

001i1

010i0

011i1

10001

10100

110i0

111i1

主析取范式AU>Z（1，3,4,7）；主合取范式4。11（0,2,5,6）.

3、设代数系统<A*>,其中*是A上的二元运算，由以下表给出，试列表分别讨论交换性、

某等性、么元和逆元.

*abc

aabc

bbca

ccab

解:

交换律耳等律次元逆元

有无ac_,=a,bx=c,c_,=b

4、设代数系统vA,*>,其中A=a力,c>,*是人上的二元运算，由以下表给出，试列表分别讨论交换性、

冢等性、么元和逆元.

*abc

aahc

babc

cabc

解:

交换律幕等律么元逆元

有无aa~l=a,h

五、计算问答题〔每题10分）

1、集合A={1,2,3,4}上的关系

/?={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>（,写出关系矩阵

A/，画出关系图并讨论R的王种性质.

因MR对角元皆为1,故R是自反的，不是反自反的；因例.为对称矩阵，故R是对称的;

因故R不是反对称的；

又因vl,3>,v3,4>wR,但<1,4>走R,故R无传递性.

2、设尺是集合4二{1,2,3,4}上的二元关系，

/?={<!,1>,<1,2>,<1,3>,<3,1>,v3,2>,v3,3>,<4,1>,v4,2>,<4,3>},

写出关系矩阵MR,画出关系图并讨论A的五种性质.42

」110、

0000

解：R的关系矩阵为]]]0,R的关系图为

J110>

四用犬对角元不全为1，也不全为0,故农不是自反的，也不是反自反的;

因“K为非对称矩阵，故R是反对称的，不是对称的；因=故R是传递的.

3、有向图G如图9.27所示,

⑴求G的邻接矩阵；

⑵根据邻接矩阵求各结点的出度和入度；

⑶求G中长度为3的路的总数，其中有多少条回路;

⑷求G的可达性矩阵.

「0110、

A1000

解:⑴株二0101；

J)00()…

\/4x4

⑵deg+“i)=2,deg—(也)=1,deg"(V2)=l>deg-(V2)=2,

deg'9)=2，deg-(V3)=1，dcg(m=0,dcg-(V4)=l：

[i0r'1110

、011o1101

⑶储二]

00o0110

<000、0000

长度为3的路有8条，其中回路3条;

「332n(\11I、

231ii111

⑷C3=A°+K+A2+AJCC

1Ti片i

122111

V4X4'0

,00000b

4、有向图。=<匕£>,其中结点集丫=｛匕,6,匕有向边集E可表示为:

(I)求。的邻接矩阵A；(2)求。的可达性矩阵P；

(3)说明必到匕长度为4的路径有几条?(4)%到其它各顶点长度为3的路径有几条?

000

000

解：⑴A=

1101

1100

001011011210

1101I2221

⑵A2=A3=

121012422

01101111J|_23

242r-111f

35421111

R=A+A2++A4=P=

46954

46321111

(3)v2到v3长度为4的路径有2条；

(4)也到其它各顶点长度为3的路径有2条.

5、有向图O=vV,E>,其中结点集V=｛匕，为，匕,匕｝，

有向边集七=｛<匕，匕>»<vpv3>,<vpv4>,<v2,Vj>,<v4,v2>,<v4,v3>)

⑴求。的邻接矩阵A；(2)求。的可达性矩阵P；

⑶说明D中经过v,长度为3的回路有几条？

(4)说明。中匕到匕长度为4的路径有几条？

⑸

说明。中匕到v3所有的路径有几条？

011

1000

解：⑴A=

0000

0110

11011221

01111101111

⑵A2=A}=>A4=

000000000000

10000111110

3553

33321111

P=A-FA2+A-+A4=P=

400000000

233111

⑶。中经过匕长度为3的回路有1条；(4)。中匕到匕长度为4的路径有2条;

(5)。中匕到匕所有的路径有5条.

四、证明计算题〔每题10分)

1、设4={1,2,3,4},在4乂4上定义7?:<<〃,〃>,〈°,〃》£/?0。+4=匕+。，

“十”为普通加法，证明：R是AxA上的等价关系，并求出[<2,4>]R,4XA/R.

证明：(1)V<a,b>eAxA,-a+b=b+a,;.«a,b>,<a,b»wR,即A自反；

(2)V«a,b>,<c,d»eR,则〃+d=h+cy,\c+h=d+ay

那么<vc,c/>,va,/?»wR,即R对称；

⑶V«a,b>,<c,d»e/?,«c,d>,<e,f»GR,

有a+/=〃+e,/.v<e,/>>eR,即R传递；

综上得出，R是AxA上的等价关系，

E[<2,4>]R={<atb>|<a,/?>GAxA,a=Z?-2}={<l,3>,<2,4>},

AxA//?={W,l>k，W,2>k，K2,l>k，[<1,3>]RA<3,11,4>]Ry[<4,1>]R}.

2、设A={1,2,3,4},在4乂4上定义/?:<<。,〃>,<。,〃》£/?。々・1=/?・。，

“・”为普通乘法，证明：R是AxA上的等价关系，并求出[<2,4>k，AxA/R.

证明：(1)V<a,b>eAxAj.〃・Z?=b・aR,即R自反；

(2)V«a.b>y<cyd»eR,则=b・c,：.c・b=iba,

那么<<c,d>,<〃/>>£火，即R对称;

⑶V«a,b>,<c,d»G/?,«c,d>,ve,fR、

则a・d=b・c,c・f=d・eaTef=b・c・d•e,

有a*f=b»e,vv>,v即及传递：

综上得出，R是AxA上的等价关系，

巨[v2,4>]R={<a,b>|<a,b>GAxA,2々=Z?}={v1,22,4>},

3、设R是实数集，R上的二元运算*定义为：a*b=a+b+ab,

证明：</?,*>是独异点，并写出其么元和零元.

证明：⑴由于实数经加法和乘法运算后，其运算结果仍为实数，所以运算*对于R是封闭的：

由于a*b=a+b+ab=a(b+1)+(/?+1)-1=(a+1)(/?+!)-!

从而有3祐)*c=((a+1)(8+1)T)*c=(((a+\)(b+1)T)+1)(c+1)H=(«+1)0+l)(c+l)-l

a*(b*c)=a*((b+l)(c+1)T)=3+1)(((/?+1)(c+1)-1)+1)-1=(a+1)0+1)(c+1)T

于是(a*b)*c=a*(b*c),所以*是可结合运算；

在<R,*>中，对J-任何实数4,都有0*4=4*0=()+〃+()•〃=4

故。是</?,*>中的么兀，VR*>是独异点；

对<凡*>中任何实数小都有(T)*a=a*(T)=(T)+a+(T>a=T,T是<R,*>中的零元.

4、某无向连通图G中有10条边，二个2度顶点，二个3度顶点，一个4度顶点，其余顶点的度数都是

1,求G的顶点个数，并证明G为树.

解：设G中度数为1的顶点个数为x

由握手定理知x+2x2+2x3+4=2x10

解得x=6

于是G中的顶点个数为1+2+2+1=11

因G为迷通图，且G中的边数比其顶点个数少1-故G为树.

五、证明题〔每题10分)

1、用逻辑推理规则证明：­9)一>T~s)，(qtp)7f,r=p-q.

证明：(1)rP

②(qfp)7Tp

(3)q.〃7(1),(2)(析取三段论)

(4)rv57(1)(加法式)

(5)Tp一幻-T，，vs)P

(6)〃­47(4),(5)(拒取式)

(7)(p—>q)人(q—>p):⑶,(6)(合取式)

(8)peqT(7)(等值表达式).

2、用逻辑推理规则证明：(pvq)f(r八s),(rvs)->/=>〃->/.

证明：U)pP(附加前提)

(2)/?v^T(l)(加法式)

⑶(pvg)f(I•人s)P

(4)rA57(2),⑶(假言推理)

(5"7⑷(简化式)

(6)rvjT(5)(加法式)

⑺"vs)—>rP

(8)rT(6),(7)(假言推理)

(9)pitCP.

3、用逻辑推理规则证明：X/x(F(x)vG(x)),X/x(G(x)f「R(x)),WxR(x)nDxF(x).

证明：(DVxR(x)P

⑵R(c)Td)(US)

⑶Vx(G(x)->Y(x))P

⑷G(c)->「R(c)丁⑶(US)

(5)-1G(c)7(2),⑷(拒取式)

⑹Vx(尸(x)vG(x))P

(7)F(c)vG(c)7(6)(US)

(8)F(c)T(5),⑺(析取三段论)

⑼Vx厂(x)丁⑻(UG).

4、用逻辑推理规则证明：BxF(x)Vy(F(y)vG(y)R(y)\BxF(x)BxR(x).

证明:(D3xF(x)P

⑵产(c)7⑴(ES)

(3)3xF(x)T\/y(F(y)\;G(y)—>R(y))P

⑷Vy(F(y)vG(y)fK(y))T⑴,⑶(假言推理)

⑸F(c)vG(c)->R(c)7(4)(US)

⑹产(c)vG(c)7⑵(加法式)

⑺R(c)7(5),⑹(假言推理)

⑻务贝*)777)(£G).

5、用逻辑推理规则证明：VA(P(X)FQ(x))=BxP{x}f3xg(x).

证明：(DHxP(x)P(附加前提)

⑵P(a)7⑴(£5)

⑶Vx(P(x)fQ(x))P

(4)P(a)->Q(a)7⑶(US)

⑸Q(a)丁⑵，⑷(假言准理)

⑹*Q(x)775)(EG)

⑺*P(x)—*Q(x)CP.

6、设R为集合A上的二元关系，如果R是反自反的和可传递的，那么R一定是反对称的.

证明：假设R不是反对称的，那么<y,x>eR9y

由R的传递性知，<X,X>GR,此与R反自反矛盾，故R反对称.

7,设R是A上的对称和传递关系，

证明：假设那么R是A上的等价关系.

证明：VtzeA,3beA,d<a,b>eR,因R是对称的，有<b,a>wR,

乂因H是传递的，所以那么R在4上自反，故R是A上的等价关系.

8、设R,S是A上的偏序关系，证明：RflS是A上的偏序关系.

证明：11)因R,S在A上的自反性，那么<x,x>wR「S,有R”S在A上自反；

(2)设S,而x/y,那么<x,yR,<x,)>eS,因R,S在A上的反对称性，有

<y,x>任R,<y,x>eS,那么<y,x>任RflS,于是，HflS在A上是反对称的；

(3)设<x,y>e/?S,<y,z>eR\S,

那么vx,y>GR,vy,z>eR,<x,y>GS,<y,z>GS,因RS在人上的传递性，

有vx,z>£R,<x,z>£S,那么<x,z>£/?S,于是，RS在A上是传递的：

综上所述，可证APIS是A上的偏序关系.

9、设R是S上的等价关系，证明：A”是S上的等价关系.

证明：(1)因R在5上的自反性，有IsJR，那么八二/；GR"，有R"在S上自反；

(2)因R在S上的对称性，有内=R,那么(/r，T=R=RT,有Qi在S上对称；

(3)因宠在S上的传递性，有R2qR,那么(R7)2=