离散数学期末复习题

一、选择题

1、永真式的否定是（2）

(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)PQR (2)RPS (3)SQR (4) (PR)(QS)。

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑴ PQ ⑵PQ(3) PQ ⑷ PQ(PQ) 提示：R(PQ)PQ 4、下列表达式错误的有⑷

⑴P(PQ)P ⑵P(PQ)P

⑶P(PQ)PQ ⑷P(PQ)PQ 5、下列表达式正确的有⑷

⑴ PPQ ⑵ PQP ⑶ Q(PQ)⑷(PQ)Q 6、下列联接词运算不可交换的是(3)

⑴ ⑵ (3) ⑷  6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为⑷

⑴x(M(x)y(F(y)H(x,y)) ⑵x(M(x)y(F(y)H(x,y))

(3) x(M(x)y(F(y)H(x,y)) ⑷x(M(x)y(F(y)H(x,y))

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑴x(L(x)A(x,y)) ⑵x(L(x)y(J(y)A(x,y))) (3) xy(L(x)J(y)A(x,y)) ⑷xy(L(x)J(y)A(x,y))

8、谓词公式x(P(x)yR(y))Q(x)中的 x是⑶

⑴自由变元 ⑵约束变元 ⑶既是自由变元又是约束变元 ⑷既不是自由变元又不是约束变元 9、下列表达式错误的有⑴

⑴x(A(x)B(x))xA(x)xB(x) ⑵x(A(x)B(x))xA(x)xB(x) (3) x(A(x)B(x))xA(x)xB(x) ⑷x(A(x)B(x))xA(x)xB(x) 10、下列推导错在⑶

①xy(xy) P

②y(zy) ③(zCz)

US① ES②

④x(xx) UG③ ⑴② ⑵③ ⑶④ ⑷无 11、下列推理步骤错在⑶

①xyF(x,y) P

②yF(z,y) ③F(z,c) ④xF(x,c)

US① ES② UG③

⑤yxF(x,y) EG④

⑴①→② ⑵②→③ ⑶③→④ ⑷④→⑤

12、设个体域为{a,b}，则xyRx,y去掉量词后，可表示为⑷

⑴Ra,aRa,bRb,aRb,b ⑵Ra,aRa,bRb,aRb,b

- 1 -

(3) Ra,aRa,bRb,aRb,b ⑷Ra,aRa,bRb,aRb,b 提示：原式yRa,yyRb,yRa,aRa,bRb,aRb,b 二、填充题

1、一个命题含有n个原子命题，则对其所有可能赋值有2n 种。

2、n个命题变元可产生2n个互不等价的极小项，其中，任意两个不同极小项的合取式为矛盾式（永假式），而全体极小项的析取式为重言式（永真式），n个命题变元可构造包括F的不同的主析取范式类别为2。

3、n个命题变元可产生2n个互不等价的极大项，其中，任意两个不同极大项的析取式为重言式（永真式），而全体极小项的合取式为矛盾式（永假式），n个命题变元可构造包括T的不同的主合取范式类别为2。

5、公式(PQ)(P(QS))的对偶公式为(PQ)(P(QS))。 6、设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的逻辑符号可化为SPQR 。 7、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为PQ； “虽然你努力了，但还是失败了”的翻译为PQ。

8、令A(x)：x会叫，B(x)：x是狗，C(x)：x会咬人，则命题“会叫的狗未必会咬人” 的符号化为x(A(x)B(x)C(x))。

9、设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为xy(P(x)Q(y)R(x,y))。

10、令A（x）:x是自然数，B（x,y）：x 小于y，则命题“存在最小的自然数” 的符号化为x(A(x)y(A(y)B(y,x)。

三、计算题

1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式

（1）（PQ）（P∨Q）； （2）（PQ）∧Q； （3）（PQ）∧R；

解 （1）、（2）和（3）的真值表如表1、表2和表3所示：

表1 P Q PQ P∨Q （PQ）（P∨Q） 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 表2 P Q PQ （PQ） （PQ）∧Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 表3 P Q R PQ R （PQ）∧R 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0

- 2 -

2n2n

1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 由上述真值表可知，（1）为永真式，（2）为永假式，（3）为可满足式。 （3）的主析取范式为：(0,2,6)；其主合取范式为(1,3,4,5,7)。

2、给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式yxL(x,y)的真值。

解：yxL(x,y)y(L(2,y)L(3,y))(L(2,2)L(3,2))(L(2,3)L(3,3))

(10)(01)000。

3、个体域为{1，2}，求xy（x+y=4）的真值。 解：xy（x+y=4）x（（x+1=4）∨（x+2=4））

（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4）） （0∨0）∧（0∨1）0∧10。

四、证明题

1、证明下列逻辑恒等式：

（1）ＰＱ (ＰＱ)(ＱＰ) 证明、用真值表法证明

P Q PQ （PQ）（QP）

F F T T

F T F F

T F F F

T T T T

由定义可知，这两个公式是等价的。 （2）P(QP)P(PQ)

证明、P(QP)P(QP) P(PQ)

P(PQ) P(PQ) P(PQ)

（3） (PQ)(RQ)((PR)Q)

证明 ： 左((PQ)(RQ))((PR)Q)

((PR)Q)(PRQ)右

（4）求证：x(A(x)B(x)) xA(x)xB(x)

证明 ：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x) （5）求证：x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))

证明：左x((P(x)Q(x)∧P(x))x((P(x)∨Q(x))∧P(x))x(P(x)∧Q(x)) 右 （6）求证：xy(P(x)Q(y)) xP(x)yQ(y) 证明：xy(P(x)Q(y))xy(P(x)∨Q(y))

x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)xP(x)yQ(y)

证明：左x(FxGx)xFxGx(xFxxGx) xFxxGxxGxxFx右

（7）求证：xFxGxxGxxFx 2、用推理规则证明下列各结论是各前提的有效结论： （1）P→Q，QR，R，SP=>S 证明：(1) R P

(2) QR P

(3) Q T（1），（2）(析取三段论)

- 3 -

(4) P→Q P (5) P T（3），（4）(拒取式) (6) SP P (7) S T（5），（6）(析取三段论)

（2）A→(B→C)，C→(DE)，F→(DE),A=>B→F 证明： (1) A P (2) A→(B→C) P (3) B→C T（1），（2）(假言推理)

(4) B P（附加前提） (5) C T（3），（4）(假言推理) (6) C→(DE) 前提 (7) DE T（5），（6）(假言推理) (8) F→(DE) 前提 (9) F T（7），（8）(拒取式) (10) B→F CP

（3）(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R => P 证明：（1） P P （假设前提）

（2） P→R P

（3） R T（1），（2）(假言推理) （4） (P→Q)(R→S) P

（5） P→Q T（4）(化简律) （6） R→S T（4）(化简律) （7） Q T （1），（5）(假言推理) （8） S T（3），（6）(假言推理) （9） (Q→W)(S→X) P

（10） Q→W T（9）(化简律) （11） S→X T（9）(化简律) （12） W T（7），（10）(假言推理) （13） X T（8），（11）(假言推理) （14） WX T（12），（13）(合取引入) （15） (WX) P

（16） (WX)(WX) T（14），（15）(合取引入) 由（16）得出矛盾式，故P为原前提的有效结论

（4）x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))

证明(1)xP(x) P

(2)P(a) T(1)，ES (3)x(P(x)Q(y)∧R(x)) P

(4)P(a)Q(y)∧R(a) T(3)，US

(5)Q(y)∧R(a) T(2)(4) (假言推理) (6)Q(y) T(5) (化简律) (7)R(a) T(5) (化简律)

(8)P(a)∧R(a) T(2)(7) (合取引入) (9)x(P(x)∧R(x)) T(8)，EG

(10)Q(y)∧x(P(x)∧R(x)) T(6)(9) (合取引入) （5）(x)(P(x)Q(x))(x)P(x)(x)Q(x) 证明：①xP(x) P（ 附加前提）

②P(e)

T①ES ③(x)(P(x)Q(x))

P

- 4 -

④P(e)Q(e) ⑤Q(e) ⑥(x)Q(x)

⑦(x)P(x)(x)Q(x)

T③US

T②④(假言推理) T⑤EG CP

（6）xP(x)x(P(x)Q(x)R(x)),xP(x),xQ(x)xy(P(x)R(y)) 证明：⑴xP(x)x(P(x)Q(x)R(x))

⑵xP(x)

⑶x(P(x)Q(x)R(x)) ⑷P(e) ⑸xQ(x) ⑹Q(d)

⑺P(d)Q(d)R(d) ⑻Q(d)P(d) ⑼R(d) ⑽P(e)R(d) ⑾(y)(P(e)R(y)) ⑿(x)(y)(P(x)R(y))

（7）xP(x)Q(x)xP(x)xQ(x)证明：（1）(x)p(x)(x)Q(x) P （2）xP(x)xQ(x) T （3）xP(x) T （4）P(e) T （5）xP(x)Q(x) P （6）xP(x)Q(x) T （7）P(e)Q(e) T （8）Qe T (4). (7) ((9) xQx T (2) ((10)Qe T(9)US

P P

T⑴⑵(假言推理) T⑵ES P T⑸ES T⑶US T⑹（附加律） T⑺⑻(假言推理) T⑷⑼(合取引入) T⑽EG T⑾EG

（假设前提） （1） （2）(化简律) （3）ES （5） （6）US

假言推理)

化简律) - 5 -

(11)QeQe T (8) (10) (合取引入) 由（11）得出矛盾式，故xP(x)xQ(x)为原前提的有效结论

五、将下列命题形式化，并证明结论的有效性：

1、为庆祝九七回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军;

(2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) A 队获第一;

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

证明、设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军; 则前提符号化为A（BC），CA，DB，A；结论符号化为 D。 本题即证明 A（BC），CA，DB，AD。 （1） A P （2） A（BC） P

（3） BC T（1），（2）(假言推理) （4） CA P

（5） C T（1），（4）(拒取式) （6） B T（3），（5）(析取三段论) （7） DB P

（8） D T（6），（7）(拒取式) 故该结论有效

2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。

解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：PxA(x)，xA(x)QQP。

(1)PxA(x) P (2)PxA(x) T(1) (3)xA(x)P T(2) (4)xA(x)Q P (5)(xA(x)Q)∧(QxA(x)) T(4)

(6)QxA(x) T(5) (化简律)

(7)QP T(6)(3) （假言三段论） 3、所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。 解：设Q(x)：x是有理数，R(x)：x是实数，Z(x)：x是整数。

命题形式化：x(Q(x)R(x)),x(Q(x)Z(x)) x(R(x)Z(x))。

证明：（1）x(Q(x)Z(x)) P (2) Q(a)Z(a) T(1) ES (3) Q(a) T(2) (化简律) (4) x(Q(x)R(x)) P (5) Q(a)R(a) T(4)US

(6) R(a) T(3)(5) (假言推理) (7) Z(a) T(2) (化简律) (8) R(a)Z(a) T(6)(7) (合取引入) (9) x(R(x)Z(x)) T (8) EG

- 6 -

集合、关系、函数的重要知识

一、关系的集合运算法则

设R,R1,R2,R3AA，则有 1.(R)2.(R1111R11 R，1，(IA)1IA，(AA)1AA，(R1R2)1R21R2，(R1R2)1R11R2)1R111111R2，(R1R2)R1R2

3.R1(R2R3)(R1R2)R3 4.R1(R2R3)(R1R2)(R1R3)，R1(R2对称性 若x,yRR3)(R1R2)(R1R3)

非（反）对称性 若x,yR 传递性 若x,yR 且y,zR 则x,zR 二、关系特性的判断方法 自反性 非（反）自反性 定义 xA xA x,xRx,xR 则y,xR 且xy 则y,xR 集合IAR IAR R1R 运算 关系主对角线主对角线元对称矩阵 矩阵 元素全为1 素全为0 关系图中各顶图中各顶点若两顶点间图 点都有环 都无环 有边，必为双 向边 三、关系特性在各种运算下的遗传变异问题 设R,R1,R2AA，则有

RR1IA RRR2R 若aij1，且ij，若aij1，ajk1 则aji0 若两顶点间有边，必为单向边 则aik1 若两顶点通过中间点相联，则两顶点间必有直达边

四、函数的性质

设函数f:BC，g:AB， 若f,g是单射，则f若若若若若

g:AC也是单射；

f,g是满射，则fg:AC也是满射； f,g是双射，则fg:AC也是双射； fg:AC是单射，则g是单射； fg:AC是满射，则f是满射；

fg:AC是双射，则f是满射，g是单射

- 7 -

集合、关系、函数的重要习题

一、选择题

1、下列为真命题的是（B）

A、a{{a}} B、{a}{{a}} C、{a}{{a}} D、{a}{{a}} 2、下列结果错误的是（B）

A、{}{} B、{}{} C、{}{} D、{}{} 3、非空集合X上的空关系不具备的性质是（A）

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

4、设R为S={1，2，3}上的关系，其关系图如下，则下列为真命题的是（C）

A、R对称，但不反对称 B、R反对称，但不对称 C、R对称，又反对称 D、R不对称，也不反对称

5、设R为S={1，2，3，4}上的关系，其关系图如下，则下列为假命题的是（C）

A、R不自反，也不反自反 B、R不对称，也不反对称 C、R传递 D、R不传递 6、设R，S是集合A上的关系，则下列断言正确的是（A）

A、若R,S自反，则RS自反 B、若R,S对称，则RS对称； C、若R,S反自反，则RS反自反 D、若R,S反对称，则RS反对称 7、设Z为整数集，下面哪个序偶不够成偏序集（A）

A、Z,(：小于关系) B、Z,(：小于等于关系)

(：等于关系) D、Z,(：整除关系)

8、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（C ）

C、Z,

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

则它的哈斯图为（A）

- 8 -

10、下列关系中能构成函数的是（B）

A、{x,y|(x,yN)(xy10)}；B、{x,y|(x,yR)(yx)}； C、{x,y|(x,yR)(yx)}； D、{x,y|(x,yZ)(xymod3)} 11、下列函数是双射的为（A ）

A、f : ZE , f (x) = 2x B、f : NNN, f (n) = C、f : RZ , f (x) = 1 D、f : ZN, f (x) = | x | （注：Z—整数集，E—偶数集， N—自然数集，R—实数集） 12、下面函数为单射而非满射的是（B） A、f:RR,C、f:RZ,13、下列命题正确的有（C ）

A、若gf是双射，则f,g都是单射 B、若gf是双射，则f,g都是满射 C、若gf是双射，则f是单射, g是满射 D、若gf是双射，则f是满射, g是单射 二、填充题

1、设M{x1x12,x被2整除，xZ}，N{x1x12,x被3整除，xZ}， 则 MN{6，12} ，MN{2，4，8，10} ，MN{2，3，4，8，9，10} 2、集合A{{,2},{2}}的幂集(A)={,{{,2}},{{2}},{{,2},{2}}} 3、(()){,{}}， (({})){,{},{{}},{,{}}} 4、设Aa,b，则(A)A

,a,,b,{a},a,{a},b,{b},a,{b},b,A,a,A,b 5、设关系A={<1,2>,<2 , 4 >,<3 , 3 >} 与 B={<1,3>,<2,4>,<4,2>}, 则AB= {< 1 , 4 > , < 2 , 2 > }，(AB){ < 4 , 2 > } 6、设集合A={1，2，3，4，5}上偏序关系的Hass图为

122f(x)x22x1 B、f:ZR,f(x)lnx； f(x)[x] D、f:RR,f(x)2x1

则集合A上的最大元为1，最小元为无，极大元为1，极小元为4,5，lub为1，glb为无； 其子集B={2，3，4}上的最大元为无，最小元为4，；极大元为2,3，极小元为4 ，lub为1，glb为4

7、偏序集A,R的哈斯图为

则R= {,,,,,,,,,}IA 8、 设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，则由S导出的等价关系 R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > } 9、设|X|=m，|Y|=n，则从X到Y有2mn 种不同的关系，有n 种不同的函数

n2nm

10、在一个有n个元素的集合上，可以有2 种不同的关系，有n 种不同的函数，有n! 种 不同的双射

11、设 f，g是自然数集N上的函数xN,则ff(x)x1,g(x)2x，

g(x)2x1，gf(x)2(x1)

- 9 -

三、问答、计算、证明题

1、设R是X＝{1，2，3，4}上的二元关系，

R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}

(1)画出R的关系图． (2)写出R的关系矩阵．

(3)说明R是否是自反、反自反、对称、传递的？ 解 (1)R的关系图如图所示： (2) R的关系矩阵为：

10M(R)11110000

110110(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；

由于对角线上存在非0元，R不是反自反的； 由于矩阵不对称，R不是对称的；

从关系图看出，若两顶点通过中间点相联，则两顶点间必有直达边，所以R是传递的． 2、设X为集合，A＝(X)－{}－{X}，且A≠，若|X|＝n，问

(1)偏序集是否有最大元？ (2)偏序集是否有最小元？

(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。

解：考察(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X．

偏序集与偏序集<(X)，>相比，恰好缺少第0层和第n层． A≠，则偏序集不存在最大元和最小元

因此的极小元就是X的所有单元集，即{x}，x∈X； 而极大元恰好是比X少一个元素，即X－{x}，x∈X． 3、 R{1,1,1,3,2,2,3,3,3,1,3,4,4,3,4,4}是集合

A{1,2,3,4}上的关系，写出关系矩阵MR，画出关系图，问R是A上的等价关系吗？

解：

10MR10010100 R的关系图为

011011

R是自反、对称的，但不传递，故不是等价关系．

4、求S={1，2，3，4，5}上的等价关系R，使其诱导划分{{1，2}，{3}，{4，5}}， 画出关系图．

解：R1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>} R2={3}×{3}={<3,3>}

R3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>} R=R1R2R3

={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}．

- 10 -

5、设A{2，，34}，B{2，4，7，10,12}，从A到B的关系

试给出R的关系图和关系矩阵，并说明此关R{a,baA,bB,且a整除b}，

系R及其逆关系R1是否为函数？为什么？

解：R{2,2,2,4,2,10,2,12,3,12,4,4,4,12}则R的关系图为：

A B R的关系矩阵为

11011 MR00001 01001关系R不是A到B的函数，

因为元素2，4的象不唯一 逆关系R1也不是B到A的函数 因为元素7的象不存在．

2 3 4 2 4 7 10 12

6、设|A|8，R是A的等价关系且由R诱导的A的划分块数为4，则不同的R有多少种？ 解：我们知道一个集合上的等价关系数目与该集合的划分数目是一致的，因而，该题只需求出将8个元素的集合分成4份的划分种数即可。

如果4份中元素个数分别为5，1，1，1，则共有C8种， 如果4份中元素个数分别为4，2，1，1，则共有C8C4种， 如果4份中元素个数分别为3，3，1，1，则共有C8C5种， 如果4份中元素个数分别为3，2，2，1，则共有C8C5种， 如果4份中元素个数分别为2，2，2，2，则共有C8C6种，

542333222因此，A上秩为4的等价关系共有C8+C8C4+C8C5+C8C5+C8C6．

2232334257、设A{1,2,3,4}，在AA上定义关系R:a,b,c,dRadbc，证明：R是AA上的等价关系，并求出[2,3]R,AA/R． 证明：a,b,c,dR adbcabcd

abab,a,b,a,bR,即R自反．

2）a,b,c,dR,则abcd,从而c,d,a,bR，即R对称． 3）a,b,c,dR,c,d,e,fR,则abcdcf ， 从而a,b,e,fR,即 R传递．

综上得出，R是等价关系．

1）a,bAA,[2,3]R{a,ba,bAA,ab231}{1,2,2,3,3,4}，

AA/R{[1,1]R,[1,2]R,[1,3]R,[1,4]R,[2,1]R,[3,1]R,[4,1]R}． 8、设A={1，2，3，4}，在(A)上规定二元关系R{s,t|s,t(A)(|s||t|)}， 证明：R是(A)上的等价关系，并写出[{2,3}]R， 商集(A)/R．

证明：⑴s(A)，由于|s||s|，所以s,sR，即R自反的．

⑵s,t(A)，若s,tR，则|s||t||t||s|，t,sR，R是对称的． ⑶s,t,u(A)，若：s,tR且t,uR，即：|s||t||u| |s||u|,s,uR 所以R是传递的．

由⑴⑵⑶知，R是等价关系．

[{2,3}]R{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}，

(A)/R{[]R,[{1}]R,[{1,2}]R[{1,2,3}]R,[A]R}．

- 11 -

9、若R和S都是非空集A上的等价关系，则RS是A上的等价关系．

证明：a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xRSx。从而RS是自反的．

a,b∈A，aRSb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bRSa。从而RS是对称的．

a,b,c∈A，aRSb且bRSc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aRSc。从而RS是传递的．

故RS是A上的等价关系．

10、设R是A上一个二元关系， S{a,b|a,bAcA(a,cRc,bR)}，试证明：若R是A上一个等价关系，则S也是A上的一个等价关系． 证明：（1）aA，由R自反，则a,aRa,aR，a,aS，即S自反．

（2）a,bS,则a,b,cA，且a,cRc,bR 由R对称，知b,cRc,aR，于是b,aS，即S对称． （3）a,bS,b,cS，则a,b,c,d,eA，且

a,dR,d,bR,b,eR,e,cR

由R传递，知a,bRb,cR，于是a,cS，即S传递的．

由（1）、（2）、（3）得，S是等价关系．

AA

11、设A={1，2}，A上所有函数的集合记为A, 是函数的复合运算，试给出A上运算的

A

运算表，并指出A中是否有幺元，哪些元素有逆元？

A解：因为|A|=2，所以A上共有2=4个不同函数。令A{f1,f2,f3,f4}，其中：

2

f1(1)1,f1(2)2;f2(1)1,f2(2)1;f3(1)2,f3(2)2;f4(1)2,f4(2)1

 f1 f2 f3 f1 f1 f2 f3 f2 f2 f2 f3 f3f3 f4 f4 f2 f3 f2 f3f2 f1 f1为AA中的幺元，f1和f4有逆元．

设函数f：R×RR×R，f定义为：f()＝。

－1

(1)证明f是双射；(2) 求逆函数f；(3)求ff．

证明： (1)x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射；

f4 f3f3uwuw

，y＝，则∈R×R 22

uwuwuwuw且f()＝<＋，－>＝，所以f是满射，故为双射

2222uwuw－1

(2)f()＝<，>。

22∈R×R，令x＝

(3)ff()＝f()＝＝<2x，2y>．

12、设f是A到A的满射，且fff，证明fIA．

证明：因为f是满射，所以aA，存在a1A使得f(a1)a， 又因为f是函数，所以f(f(a1))f(a) 即ff(a1)f(a) 由 fff，知ff(a1)f(a1)，则f(a)f(a1)a，由a的任意性知fIA．

- 12 -

代数系统

一、选择题：

1、下列正整数集的子集在普通加法运算下封闭的是（ D ）

A、{xx30} B、{xx与30互质} C、{xx是30的因子} D、{xx是30的倍数} 2、设S={1，2，…，10 }，则下面定义的运算*关于S非封闭的有（ D ）

A、x*y=max(x ,y) B、x*y=min(x ,y) C、x*y=取其最大公约数D、x*y= 取其最小公倍数

3、设集合A的幂集为(A)，、、、为集合的交、并、差、笛卡尔乘积运算，则下列系统中是代数系统的为（ D ） A、

(A), B、(A), C、(A), D、(A),

4、在自然数集上定义的下列四种运算，其中满足结合律的是（C）

A、abab B、ab|ab| C、abmax{a,b}D、aba2b 5、设Z为正整数集，*表示求两数的最小公倍数，对代数系统AZ,*，有（ A ） A、1是么元，无零元 B、1是零元，无么元 C、无零元，无么元 D、无等幂元 6、设非空有限集S的幂集为(S)，对代数系统A(S),，有（ B ）

A、是么元，S是零元 B、是零元，S是么元 C、唯一等幂元 D、无等幂元 7、在有理数集Q上定义的二元运算*： x*yxyxy，则Q中元素满足（ C ） A、都有逆元 B、只有唯一逆元 C、x1时，有逆元 D、都无逆元 8、设R是实数集合，“”为普通乘法，则代数系统 一定不是（ D ） A、半群 B、独异点 C、可交换的独异点 D、循环独异点 9、设S={0，1}，*为普通乘法，则< S , * >（ B ）

A、是半群，但非独异点B、是独异点，但非群C、是群，但非阿贝尔群D、是阿贝尔群 10、任意具有多个等幂元的半群，它（A ）

A、不能构成群B、不一定能构成群 C、能构成群 D、能构成阿贝尔群 二、填充题：

1、下表中的运算均定义在实数集上，请在相应的空格中打“√”或填上具体实数（不满足或无该项者不填） ×   结合律 √ × √ 交换律 √ × √ 么元（含左、右么元） 0 0（右幺元） 1 零元（含左、右零元） × × 0 2、设A={2,4,6}，A上*为：a*b=max{a,b}，则在独异点中，么元是(2)，零元为(6)。 3、设A={3,6,9}，A上*为：a*b=min{a,b}，则在独异点中，么元是(9)，零元为(3) 。 4、代数系统中，|A|>1，若e和分别为的么元和零元，则e和的关系为e 。 5、设< {a,b,c}, * >为代数系统，* 运算如* a b c a a b c b b a c

c c c c

则它的么元为a ；零元为c； a、b、c的逆元分别为a、b、无。 6、设〈G,*〉是一个群，则

1下：

(1) 若a,b,x∈G，ax=b，则x=( ab)；(2) 若a,b,x∈G，ax=ab，则x=( b )。 7、群的等幂元是(么元)，有(1)个，零元有(0)个。

8、设a是12阶群的生成元， 则a是(6 )阶元素，a是(4)阶元素。 9、设a是10阶群的生成元， 则a是(5 )阶元素，a是(10)阶元素。

- 13 -

432310、在一个群〈G,*〉中，若G中的元素a的阶是k，则a的阶是(k)。 三、简答题：

AA

1、设A={1，2}，A上所有函数的集合记为A, 是函数的复合运算，试给出A上运算的

A

运算表，并指出A中是否有么元，哪些元素有逆元？

A答：因为|A|=2，所以A上共有2=4个不同函数。令A{f1,f2,f3,f4}，其中：

2

1f1(1)1,f1(2)2;

f2(1)1,f2(2)1;f3(1)2,f3(2)2;f4(1)2,f4(2)1 f1 f2 f3 f1 f1 f2 f3 f2 f2 f2 f3 f3f3 f4 f4 f2 f3 f2 f3f2 Af1为A中的么元，f1和f4有逆元。

2、已知定义在集合{a,b,c,d}上的运算*如下表： * a b

a a b

b b a

c c d

d d c

试问：1）{a,b,c,d},是否为代数系统？

2）{a,b,c,d},是否为子群？ 3）{a,b,c,d},是否为群？ 4）{a,b,c,d},是否有单位元？ 5）{a,b,c,d},是否满足交换律？ 题号 1 2 3 f4 f3f3f1 c c d b a d d c a b 4 5 答案 √ √ √ √ √ 3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下： [i]3[j][(ij)mod3]，试给出+3的运算表，并指出是否构成群？

答： +3 [0] [1] [2] [0] [0] [1] [2]

[1] [1] [2] [0]

[2] [2] [0] [1]

构成群。 四、计算题：

1、设S=QQ，Q为有理数集合，*为S上的二元运算：对任意(a,b)，(c,d)S,有 (a,b)*(c,d)=(ac,ad+b),求出S关于二元运算*的么元，以及当a0时，(a,b)关于*的逆元。 解：设S关于*的么元为(a,b)。根据*和么元的定义，对(x,y)S,有

(a,b)*(x,y)=(ax,ay+b)=(x,y), (x,y)*(a,b)=(ax,xb+y)=(x,y)。

即ax=x,ay+b=y,xb+y=y对x,yQ都成立。解得a=1,b=0，则S关于*的么元为(1,0)。 当a0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有 (a,b)*(c,d)= (ac,ad+b)=(1,0)，(c,d)*(a,b)= (ac,cb+d)=(1,0)

即ac=1,ad+b=0,cb+d=0。解得c=1/a,d=-b/a。 所以(a,b)关于*的逆元为(1/a, -b/a)。

- 14 -

2、试求中每个元素的阶。

解：0是中关于+6的么元。则|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。 五、证明题：

1、 设是一个代数系统，*是R上二元运算，a,bRa*babab， 则0是么元且是独异点。 证明：（1） aR,0*a0a0aa,a*0a0a0

即 0*aa*0a，0是么元

（2）由于+，·在R封闭，则*在R上封闭。 （3） a,b,cR

(a*b)*c(abab)*cababc(abab)cabcabacbcabca*(b*c)abcabacbcabc

因此 ， 〈R，*〉是独异点。

2、I上的二元运算*定义为：a,bI，a*b=a+b-2。试证：为群。 证明：（1）a,b,cI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c)

=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，从而*满足结合律。

（2）记e=2。对aI，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。 （3）对aI，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。综上所述，为群。

3、设*是集合A上可结合的二元运算，且a,bA,若a*b=b*a，则a=b。试证明： （1）aA,a*a=a，即a是等幂元；（2） a,bA,a*b*a=a。 证明：（1）aA,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。

（2）a,bA,因为由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),

(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，从而a*b*a=a。

222

4、设半群中消去律成立，则是可交换半群当且仅当a,bS，（a·b）=a·b。

2

证明： a,bS，（a·b）=(a·b)·(a·b)=((a·b)·a)·b=(a·(b·a))·b

22

=(a·(a·b))·b=((a·a)·b)·b=(a·a)·(b·b)=a·b;

 a,bS，因为（a·b）2=a2·b2，所以(a·b)·(a·b)=(a·a)·(b·b)。 故a·((b·a)·b)=a·(a·(b·b))。由于·满足消去律，所以(b·a)·b=a·(b·b)，即(b·a)·b=(a·b)·b。从而a·b=b·a。故·满足交换律。

5、若是可交换独异点，T为S中所有等幂元的集合，则是的子独异点。 证明：  ee=e，eT，即T是S的非空子集。

 a,bT, 是可交换独异点,(ab)(ab)=((ab)a)b =(a(ba))b=（a(ab)）b=((aa)b)b=(aa)(bb)=ab, 即abT。 故是的子独异点。 有么元且满足消去律的有限半群一定是群。

证明 设是一个有么元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。

所以(a*b)*ca*(b*c)aG，则akG，对a，a2，…，ak，…，因G只有有限个元素，所以存在k＞l，

使得a＝a。令m＝k－l，有a*e＝a*a，其中e是么元。由消去律得a＝e。

于是，当m＝1时，a＝e，而e是可逆的；

m-1m-1m-1

当m＞1时，a*a＝a*a＝e。从而a是可逆的，其逆元是a。 总之，a是可逆的。

6、对独异点，若A中每个元素都有右逆元，则必为群。

证明：设e为的么元， aA，记b是a的右逆元，c是b的右逆元，

则b*a(b*a)*e(b*a)*(b*c)b*(a*b)*cb*ce，则b是a的左逆元。

- 15 -

klllmm故aA，a有唯一逆元b，于是，必为群。

7、设群除单位元外每个元素的阶均为2，则是交换群。

-1

证明：对任一aG，由已知可得a*a=e，即a=a。

-1-1-1

对任一a,bG，因a*b=(a*b)=b*a=b*a，所以*满足交换律。 从而＜G,*＞是交换群。 8、证明：（1）有限群中阶大于2的元素的个数一定是偶数。 （2）偶数阶群中阶为2 的元素的个数一定是奇数。

-1-1

证明：（1）设是有限群，则aG，有|a|=|a|。且当a 阶大于2时，aa。故阶数大于2 的元素成对出现，从而其个数必为偶数。 证明：（2）设是偶数阶群，则由于群的元素中阶为1 的只有一个单位元，阶大于2 的元素是偶数个，剩下元素中都是阶为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。

－1

9、设是由g生成的循环群，则若G为无限循环群，则G只有两个生成元g和g。

i证明：因为g是群的生成元，所以对任意的a∈G，存在i∈Z使得a＝g。又a＝(g1)i，

－1

所以g也是群的生成元。

－1

再证G只有g和g这两个生成元。假设h也是G的生成元，对G的元素g，存在整数s，使得g＝hs。对于h来说，由g是G的生成元，存在整数t，使得h＝gt。于是，g＝hs＝gst。由G中的消去律得gst1＝e。因为G是无限群，必有st－1＝0。

－1

从而有s＝t＝1或s＝t＝－1，即h＝g或h＝g。

-1

10、是个群，u∈G，定义G中的运算“”为ab=a*u*b，对任意a，b∈G， 求证：也是个群。

-1

证明：1）a，b∈G，ab=a*u*b∈G，运算是封闭的。

-1-1-1-1

2）a，b，c∈G，（ab）c=（a*u*b）*u*c=a*u*（b*u*c）=a（bc），运算是可结合的。

-1

3）a∈G，设E为的单位元，则aE=a*u*E=a，得E=u，存在单位元u。

-1-1-1-1

4）a∈G，ax=a*u*x=E，x=u*a*u，则xa=u*a*u*u*a=u=E，各元素都有逆元。 所以也是个群。

-1

11、设是群，作f:GG,aa。证明：f是G的自同构G是交换群。 证明：  设f 是G的自同构。

-1-1-1-1-1-1-1

对a，bG，a·b=(b·a)=(f(b) ·f(a))=(f(b·a))=((b·a))=b·a。 故运算·满足交换律 ，即G是可交换群。

因为当ab时，a-1b-1，即f(a)f(b)，故f是G到G中的一个单射。

-1-1-1

又对aG，有f(a)=(a)=a。故f是G到G上的满射。从而f是G到G上的双射。

-1-1-1-1

对a，bG，因为G是可交换群，则 f(a·b)=(a·b)=(b·a)=a·b=f(a)·f(b)。

故f是G 的自同构。

图论部分

一、选择题：

1．欧拉回路是（B）

A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 2．哈密尔顿回路是（C）

A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 3．设G是简单有向图，可达矩阵P(G)刻划下列关系中的是（C） A、点与边 B、边与点 C、点与点 D、边与边

4．下列哪一种图不一定是树（C）。

A.无简单回路的连通图 B. 有n个顶点n-1条边的连通图 C. 每对顶点间都有通路的图 D. 连通但删去一条边便不连通的图 5.下列哪个不是两个图同构的必要条件

A. 结点数目相等B. 边数相等C. 度数相同的结点数目相同D. 两个图都是平面图

- 16 -

6．在有n个结点的连通图中，其边数（B）

A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条 7．下列图为树的是（C）。 A、G1{a,b,c,d},{a,a,a,b,c,d} B、G2{a,b,c,d},{a,b,b,d,c,d} C、

G3{a,b,c,d},{a,b,a,d,c,a}

D、G4{a,b,c,d},{a,b,a,c,d,d} 二、填充题：

1、n阶无向完全图Kn 的边数是(

n(n1))，每个结点的度数是(n-1)。 22、n个结点的有向完全图边数是(n(n-1))，每个结点的度数是(2n-2)。

010110113、设有向图G = < V，E >，V{v1,v2,v3,v4}的邻接矩阵A，

11001000则v1的入度deg(v1)= 3 ，v4的出度deg(v4)=1 ，从v2到v4的长度为2的路有 1 条。

4、一棵无向树的顶点数为n，则其边数为n-1 ，其结点度数之和是2n-2。 5、一个无向图有生成树的充分必要条件是(它是连通图)。

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

7、任何连通无向图G至少有(1)棵生成树，当且仅当G 是(树)，G的生成树只有一棵。 8、设T是一棵树，则T是一个连通且(无简单回路)的图。

9、设无向图G有1边且每个顶点的度数都是3，则图G有(12)个顶点。 10、任一有向图中，度数为奇数的结点有(偶数)个。

11、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（9）。 三、问答题

1、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？

解：设G中度数小于3的顶点有k个，由欧拉定理24=

deg(v)知，度数小于3 的顶点度

vV数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。 2、判断下列图是否为欧拉图？说明理由，存在是否哈密尔顿回路。 解：一个无向图D是欧拉图 D是连通的，且所有顶点的度等于偶数。 所以是欧拉图，但无哈密尔顿回路。

  

 

四、计算题

1、有向图DV,E，其中结点集V{v1,v2,v3,v4}，

有向边集E{v1,v2,v1,v3,v1,v4,v2,v1,v4,v2,v4,v3} （1）求D的邻接矩阵A；（2）求D的可达性矩阵P； （3）说明v1到v3长度为4的路径有几条？ （4）说明v1到其它各顶点长度为3的路径有几条？

- 17 -

01解：（1）A00111000 0001103553111133321111234，P （2）R4AAAA0000000023311111（3）v1到v3长度为4的路径有2条，（4）v1到其它各顶点长度为3的路径有3条.

2、设有如下有向图G=， （1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？

v1 v4

v2  v3 11解：（1）A=0011021010，A2=000101001213

2111，A3=0010

00102425

3131，A4=0001

0100374

243 010



001

（2）G中v1到v4的长度为4 的通路有4条； （3）G中经过v1的长度为3 的回路有3条；

（4）G中长度不超过4 的通路有72条，其中有19条回路。 五、证明题

1、设图G=，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk= (k+1)n -2m。

证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉定理可知

2m=

deg(v)=kn+(k+1)(n-n)=(k+1)n-n，故n=(k+1)n -2m。

k

k

k

k

vV2、设G=是n个顶点的无向图(n>2)，若对任意u,vV，有d(u)+d(v) n-2，则G是连通图。

证明：用反证法证明。

若G 不连通，则它可分成两个的子图G1和G2，其中

|V(G1)|+|V(G2)|n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取uV(G1),vV(G2),则 d(u)|V(G1)|-1, d(v)|V(G2)|-1。

故d(u)+d(v) (|V(G1)|-1)+(|V(G2)|-1)|V(G1)|+|V(G2)|-2 =n-2，这与已知矛盾。故G是连通图。

- 18 -