数学参考答案破解版
数理逻辑练习
一、证明下面推理
1） 前提：p →(q→(s∧r)), ┐s ∧p 结论：¬q
2） 前提：∀x(F(x)∨G(x))，┐∃x(G(x)∧R(x))，∀xR(x)
结论：∃x(F(x))
3) 前提：∀x(F(x)→(G(a)∧H(x)))，∃x F(x)
结论：∃x (F(x)∧H(x))
证明:用归谬法,
(1) q 附加前提 (2) ┐s ∧p P
(3) p T(2),I (4) p →(q→(s∧r)) P (5) q→(s∧r) T(3)(4),I (6) s∧r T(1)(5),I (7) ┐s T(2),I (8) s T(6),I (9) ┐s ∧s T(7)(8),I
由于最后－步┐s ∧s ⇔0，所以推理正确，结论┐q 为有效结论。
2) 证明：
① ┐∃x(G(x)∧R(x)) P
② ∀x(┐G(x)∨┐R(x)) T (1),E ③ ┐G(c)∨┐R(c) T(2),I
P ④ ∀xR(x)
⑤ R (c) T(4),I
⑥ ┐G(c) T(3)(5),I
P ⑦ ∀x(F(x)∨G(x))
⑧ F(c)∨G(c) T(7),I ⑨ F(c) T(6)(8),I
T(9),I ⑩ ∃x(F(x))
3) 证明： 注意，在证明序列中先引进带存在量词的前提。 ① ∃x F(x) P ② F(c) T(1),I ③ ∀x(F(x)→(G(a)∧H(x))) P ④ F(c)→(G(a)∧H(c)) T(3),I ⑤ G(a)∧H(c) T(4),I ⑥ H(c) T(5),I ⑦ F(c)∧H(c) T(2)(6),I ⑧ ∃x (F(x)∧H(x)) T(7),I 二、在谓词逻辑中，构造下面推理的证明:
1、每个有理数都是实数，有的有理数是整数，因此有的实数是整数。 解: 设F(x):x是有理数，G(x)：x是实数，H(x):x是整数。
则上述推理可以符号化为：∀x(F(x)→(G(x)) ，∃x(F(x)∧H (x)) |- ∃x(G(x)∧H (x)) 证明： ① ∃x(F(x)∧H (x)) P
② F(c)∧H (c) T(1),I ③ ∀x(F(x)→(G(x)) P ④ F(c)→G(c) T(3),I ⑤ F (c) T(2),I ⑥ G(c) T(4)(5),I ⑦ H(c) T(2),I ⑧ G(c) ∧H (c) T(6)(7),I ⑨ ∃x(G(x)∧H (x)) T(8),I
2、任何人，如果他喜欢步行，他就不喜欢乘汽车。每一个人或者喜欢乘汽车，或者喜欢骑
自行车。并非每个人都喜欢骑自行车。因此，有的人不爱步行。（个体域为人类集合） 解: 设F(x):x喜欢步行，G(x)：x喜欢乘汽车，H(x):x喜欢骑自行车 则上述推理可以符号化为：
∀x(F(x)→┐(G(x)), ∀x(G(x)∨H (x)), ┐∀xH(x) |-∃x ┐F(x)
证明：
(1) ┐∀xH(x) P
T(1),E (2) ∃x ┐H(x)
(3) ┐H(c) T(2),I
P (4) ∀x(G(x)∨H (x))
(5) G(c)∨H(c) T(4),I
(6) G(c) T(3)(5),I (7) ∀x(F(x)→┐(G(x)) P (8) F(c)→┐(G(c) T(7),I (9) ┐F(c) T(6)(8),I (10) ∃x ┐F(x) T(9),I
3) 如果2是偶数，则3是奇数。或者2是偶数或者2整除3，结果2整除3，所以3不是奇数。
解 设A ：2是偶数；B ：3是奇数，C ：2整除3；则推理化形式为： A →B ，A ∨C ，
C ¬B
该推理形式不正确。例如，设有一赋值：A ＝F，B ＝T ，C ＝T，则A →B 、A ∨C 、C 都为真，但¬B 为假。
4) 如果A 努力工作，那么B 或C 感到愉快；如果B 愉快，那么A 不努力工作；如果D 愉快那么C 不愉快。所以，如果A 努力工作，则D 不愉快。
解：
设A ：A 努力工作；B 、C 、D 分别表示B 、C 、D 愉快；则推理化形式为： A →B ∨C ，B →¬A ，D →¬
C A →¬D 该推理形式正确。下面给出证明：
(1)A 附加前提 (2)A →B ∨C P
(3)B ∨C T(1)(2)，I (4)B →¬A P (5)A →¬B T(4)，E (6)¬B T(1)(5)，I (7)C T(3)(6)，I (8)D →¬C P
(9)¬D T(7)(8)，I (10)A →¬D CP
三、求下列命题公式的主析取范式和主合取范式，并求其成真赋值。 1） P →(Q →R ) 2） (p ∨q ) →r
3） (¬p ∨¬q ) ∨(p →¬q )
4） (¬P ∨¬Q ) →(P ¬Q )
1）公式法：因为P →(Q →R ) ⇔¬P ∨¬Q ∨R
⇔M 6
⇔m 0∨m 1∨m 2∨m 3∨m 4∨m 5∨m 7
所以，公式P →(Q →R )为可满足式，其相应的成真赋值为000、001、010、011、100、101、111：成假赋值为：110。
真值表法：
P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Q →R 1 1 0 1 1 1 0 1
P →(Q →R )
1 1 1 1 1 1 0 1
由真值表可知，公式P →(Q →R )为可满足式，其相应的成真赋值为000、001、010、011、100、101、111：成假赋值为：110。
2）（p∨q ）→r ⇔ ┐( p∨q )∨r ⇔ (┐p∧┐q )∨r
⇔ (┐p∨r) ∧ (┐q ∨r)
⇔ (┐p∨(┐q∧q )∨r) ∧ ((┐p∧p )∨┐q ∨r)
⇔ (┐p∨┐q∨r) ∧ (┐p∨q∨r) ∧ (┐p∨┐q ∨r) ∧ (p∨┐q ∨r)
⇔ M 2∧M 4∧ M 6 ⇔ m 0∨m 1∨m 3∨m 5∨m 7
其成真赋值为000，001，011，101，111 3）（┐p∨┐q）∨ (p→┐q) ⇔ (┐p∨┐q)∨（┐p∨┐q）
⇔ ┐p∨┐q ⇔ M 3 ⇔ m 0∨m 1∨m 2 其成真赋值为00，01，10 4)
公式法：因为(¬P ∨¬Q ) →(P ¬Q ) ⇔¬(¬P ∨¬Q )∨(P ∧¬Q )∨(¬P ∧Q )
⇔(P ∧Q )∨(P ∧¬Q )∨(¬P ∧Q ) ⇔m 1∨m 2∨m 3 ⇔M 0
所以，公式(¬P ∨¬Q ) →(P ¬Q )为可满足式，其相应的成真赋值为01、10、11：成假赋值为：00。
真值表法：
P Q 0 0 0 1 1 0 1 1
¬P ∨¬Q
1 1 1 0
P ¬Q 0 1 1 0
(¬P ∨¬Q ) →(P ¬Q )
0 1 1 1
由真值表可知，公式(¬P ∨¬Q ) →(P ¬Q )为可满足式，其相应的成真赋值为01、10、11：成假赋值为：00。
四、求下列各公式的前束范式
1） ¬∃x (P (x ) →∀yQ (x , y )) 2） (∃xP (x , y ) ∧∃yQ (y )) →∃zR (z )
1）┐∃x (P(x)→∀yQ(x,y)) ⇔ ∀x ┐(┐P(x)∨∀yQ(x,y)) ⇔ ∀x (P(x)∧┐∀yQ(x,y)) ⇔ ∀x (P(x)∧∃y ┐Q(x,y))
⇔ ∀x ∃y (P(x)∧┐Q(x,y)) 2）(∃x (P(x,y)∧∃yQ(y))→∃zR(z) ⇔ ∃x(P(x,y)∧∃yQ(y))→∃zR(z)
⇔ ∃x(P(x,t)∧∃yQ(y))→∃zR(z) ⇔ ∃x ∃y (P(x,t)∧Q(y))→∃zR(z)
⇔ ∀x(∃y (P(x,t)∧Q(y))→∃zR(z))
⇔ ∀x ∀y ((P(x,t)∧Q(y))→∃zR(z)) ⇔ ∀x ∀y ∃z (P(x,t)∧Q(y)→R(z))
五、构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？
1） P ∧(Q ∨R )。
2） ¬(P ∨Q ) (¬P ∧¬Q )。
解 (1)
P Q R
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
Q ∨R 0 1 1 1 0 1 1 1
P ∧(Q ∨R )
0 0 0 0 0 1 1 1
由真值表可知，公式P ∧(Q ∨R )的成真赋值为：101、110、111，成假赋值为000、001、010、011、100。 2) 解：
P Q 0 0 0 1 1 0 1 1
¬( P∨Q )
1 0 0 0
¬P ∧¬Q
1 0 0 0
¬(P ∨Q ) (¬P ∧¬Q )
1 1 1 1
由真值表可知，公式¬(P ∨Q ) (¬P ∧¬Q )的成真赋值为：00、01、10、11，没有成假赋值。
六、分别用真值表法和公式法判断下列命题公式的类型：
(1)(P ∨Q ) →(P ∧Q )。
(3)(¬P ∨Q )∧¬(Q ∨¬R )∧¬(R ∨¬P ∨¬Q )。 (5)(Q →P )∧(¬P ∧Q )。 解 (1)真值表法：
P Q 0 0 0 1 1 0 1 1
P ∨Q 0 1 1 1
P ∧Q 0 0 0 1
(P ∨Q ) →(P ∧Q )
1 0 0 1
由真值表可知，公式(P ∨Q ) →(P ∧Q )为可满足式。
公式法：因为(P ∨Q ) →(P ∧Q ) ⇔¬(P ∨Q )∨(P ∧Q ) ⇔(¬P ∧¬Q )∨(P ∧Q )，所以，公式(P ∨Q ) →(P ∧Q )为可满足式。
(3)真值表法：
P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
¬P ∨Q 1 1 1 1 0 0 1 1
Q ∨¬R 1 0 1 1 1 0 1 1
R ∨¬P ∨¬Q
1 1 1 1 1 1 0 1
(¬P ∨Q )∧¬(Q ∨¬R )∧¬(R ∨¬P ∨¬Q )
0 0 0 0 0 0 0 0
由真值表可知，公式(¬P ∨Q )∧¬(Q ∨¬R )∧¬(R ∨¬P ∨¬Q )为矛盾式。
公式法：因为(¬P ∨Q )∧¬(Q ∨¬R )∧¬(R ∨¬P ∨¬Q ) ⇔(¬P ∨Q )∧¬Q ∧R ∧(¬R ∧P ∧Q ) ⇔F，所以，公式(¬P ∨Q )∧¬(Q ∨¬R )∧¬(R ∨¬P ∨¬Q )为矛盾式。
(5)真值表法：
P Q 0 0 0 1 1 0 1 1
Q →P 1 0 1 1
¬P ∧Q 0 1 0 0
(Q →P )∧(¬P ∧Q )
0 0 0 0
由真值表可知，公式(Q →P )∧(¬P ∧Q )为矛盾式。
公式法：因为(Q →P )∧(¬P ∧Q ) ⇔(¬Q ∨P )∧(¬P ∧Q ) ⇔¬(Q ∧¬P )∧(¬P ∧Q ) ⇔F，所以，公式为矛盾式。
集合论练习
1.给定自然数集N 的子集：A ＝{1，3，7，8}，B ＝{i |i ＜30 }，C ＝{i |i 可以被3整除且0≤i ≤20}。求下列集合：
(1)A ∪B (2)B ∩C。 (3)B －(A ∪C )。 (4)B⊕C
解 由题意得A ＝{1，3，7，8}，B ＝{0，1，2，3，4，5}，C ＝{0，3，6，9，12，15，18}所以
(1)A ∪B ＝{0，1，2，3，4，5，7，8} (2) B∩C ＝{0,3}
(3)B －(A ∪C )＝B-{0,1,3,6,7,8,9,12,15,18}={2,4,5}
(4) B⊕C=B∪C-B∩C={0,1,2,3,4,5,6,9,12,15,18}-{0,3}={1,4,5,6,9,12,15,18}
2、已知A∪B＝A∪C，A∩B＝A∩C，请用集合恒等式证明B＝C。
证明
B ＝B ∩(A ∪B ) ＝B ∩(A ∪C )
＝(B ∩A ) ∪(B ∩C ) ＝(A ∩C ) ∪(B ∩C ) ＝(A ∪B ) ∩C ＝(A ∪C ) ∩C ＝C
3.求由数字1、2、3、4、5、6组成的四位数(每个数字都不允许重复出现)中，数字2在5前面的四位数共有多少个？
21
解 当2在第1位时，A 4×C 3=12×3=36
2
当2在第2位时，A 4×C 2=12×2=24
2
当2在第3位时，A 4=12
21
任取4个不同的数字，且数字2在5前面的4位数个数为 36+24+12=72
4. 求1到2500之间能被2，3，5和7中任何一个数整除的整数个数。
解：设A 1表示1到2500之间能被2整除的整数集合，A 2表示能被3整除的整数集合，A 3表
示能被5整除的整数集合，A 4表示能被7整除的整数集合。|x | 表示小于或等于x 的最大整数。
|A 1|=|
[**************]0
|=1250 |A 2|=||=833|A 3|=||=500|A 4|=||=357 [**************]0
|A 1∩A 2|=||=416 |A 1∩A 3|=||=250|A 1∩A 4|=||=178
2×32×52×[1**********]00
|A 2∩A 3|=||=166 |A 2∩A 4|=||=119|A 3∩A 4|=||=71
3×53×75×7
|A 1∩A 2∩A 3|=|
25002500
|=83 |A 1∩A 2∩A 4|=||=59
2×3×52×3×725002500
|A 1∩A 3∩A 4|=||=35|A 2∩A 3∩A 4|=||=23
2×5×73×5×7
2500
=11 |A 1∩A 2∩A 3∩A 4|=|
2×3×5×7
根据容斥原理
|A 1∪A 2∪A 3∪A 4|=1250+833+500+357−416−250−178−166−119
−71+83+59+35+23−11=1929
5、今有111人购买A,B,C 三种股票，已知只买了一种股票的共75人，买了A 股和B 股的共有20人，买了B 股和C 股的共有9人，买了A 股和C 股的共17人，只买A 股的共31人，只买B 股的共23人。试求：（10分） 1） 三种股票都买的有几人？
2） 买A 股、B股和C 股的各几人？
解：设集合A，B，C分别表示购买A,B,C 三种股票的人的集合。根据题意画出文氏图如下图所示。
设三种股票都买的有x 人，由已知条件填写图中相应区域。
B 20-x 31∣C-(A∩B)∣= 75-31-23=21
由已知条件，可得以下方程： 23 x (20-x)+x+(9-x)+(17-x)+31+23+21 = 111 解得：x=5
故∣A∣=31+(20-5)+5+(17-5)=63 21 ∣B∣=23+(20-5)+5+(9-5)=47 ∣C∣=21+(9-5)+5+(17-5)=42
C
因而可得，三种股票都买的有5人。
买A 股的有63人，买B 股的有47人，买C 股的有42人。
关系练习
1.设A ＝{1，2}，构造集合P (A )×A 。
解 P (A )×A ＝{∅，{1}，{ 2}，{1，2}}×{1，2}＝{，，，，，，，}。
R R 、
R {1}、R [{1}]、
R ∅、R {∅}、2.设R ＝{，，，}，求D R 、
R [∅]和R [{∅}]。
解 D R ＝{0，1，2}
R R ＝{0，1，2}
R {1}＝{，} R [{1}]＝{1，2}
R ∅＝∅
R {∅}＝∅ R [∅]＝∅ R [{∅}]＝∅
3. 证明R [A ∪B ]＝R [A ]∪R [B ]。
(1)因为y ∈R [A ∪B ]⇔∃x (x ∈A ∪B ∧xR y)
⇔∃x ((x ∈A ∨x ∈B )∧xR y) ⇔∃x ((x ∈A ∧xR y)∨(x ∈B ∧xR y)) ⇔∃x (x ∈A ∧xR y)∨∃x (x ∈B ∧xR y) ⇔y ∈R [A ]∨y ∈R [B ] ⇔y ∈R [A ]∪R [B ]
所以R [A ∪B ]＝R [A ]∪R [B ]。
4.设X ＝{1，2，3，4}，R 是X 上的二元关系，R ＝{，，，，，， }
(1)画出R 的关系图。 (2)写出R 的关系矩阵。
(3)说明R 是否是自反、反自反、对称、传递的。 解 (1)R 的关系图如图所示：
(2) R的关系矩阵为：
⎛0⎜1⎜M (R ) =⎜1⎜⎝1
11000011
0⎞⎟0⎟ 0⎟⎟0⎠
(3)对于R 的关系矩阵，由于对角线上不全为1，R 不是自反的；由于对角线上存在非0元，R 不是反自反的；由于矩阵不对称，R 不是对称的；
经过计算可得
⎛0⎜12
M (R ) =⎜
⎜1⎜⎝1
11000011
0⎞⎛0⎟⎜0⎟⎜1×⎟0⎜1⎟⎜0⎠⎝1
11000011
0⎞⎛1⎟⎜0⎟⎜1=⎟0⎜1⎟⎜0⎠⎝1
11110011
0⎞⎟0⎟
，所以R 不是传递的。 ⎟0⎟0⎠
5.令A={1,2,3};B={a,b},求R1={,,,}的关系矩阵。
⎡1M R 1=⎢⎢0
⎢⎣11⎤
1⎥⎥ 0⎥⎦
6.令A={1,2,3};求R2={,,,}的关系图。
7.令F={,,,}，G={,,,}求F*G, G*F, F*F F*G={,,,} G*F={,,}
F*F={,,,,}
8.设集合A={a, b, c ,d}上的二元关系R={, , , ,}
1） 试分析指出R 所具有的性质（即是否具有自反性，反自反性，对称性，反对称性，
传递性这五种性质）
2） 求R 0，R 2，r(R)，s(R)，t(R)的集合表达式。
解 1）
R 既不具有自反性也不具有反自反性；R既不具有对称性也不具备反对称性； R 也不具备传递性。
2) R =I A ={, , , }
⎡1⎢1
写出R 的关系矩阵，M R =⎢
⎢0⎢⎣1
2
10000000
0⎤⎡11
⎢110⎥⎥，M 2=M R . M R =⎢
R
⎢101⎥
⎥⎢0⎦⎣11
000
0⎤0⎥⎥ 0⎥⎥0⎦
故R ={, , , , , , }
r (R ) =R ∪I A ={, , , , , , , } s (R ) =R ∪R −1={, , , , , , }
画出R 的关系图（如下图所示），并根据沃舍尔算法画出t(R)的关系图
R t(R)
t (R ) ={, , , , , , , , }
9.设A =⎨1,2,3,4,5⎬，A 上的等价关系R 定义为：
R =⎨, , , ⎬∪I A
画出关系图，找出所有等价类。 解：R 的关系图如图4.34所示。
[1]R =[2]R =⎨1,2⎬，[3]R =[4]R =⎨3,4⎬，[5]R =⎨5⎬
关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每一个等价类导出了关系图的一个连通分支。
10.求出下列各偏序集的盖住关系COV A ，画出哈斯图，找出A 的子集B 1、B 2和B 3的极大元、极小元、最大元、最小元。
⑴
A =⎨a , b , c , d , e ⎬，
≼=⎨, , , , ⎬∪I A
B 1=⎨b , c , d ⎬，B 2=⎨a , b , c , d ⎬，B 3=⎨b , c , d , e ⎬
⑶ A =P (⎨a , b , c ⎬) ，≼=⎨⏐ x ∈P (A ) ∧y ∈P (A ) ∧x ⊆y ⎬ B 1=⎨∅, ⎨a ⎬, ⎨b ⎬⎬，B 2=⎨⎨a ⎬, ⎨c ⎬⎬，B 3=⎨⎨a , c ⎬, ⎨a , b , c ⎬⎬
解：⑴COV A =⎨, , , , , ⎬ 哈斯图如图所示。
A 的子集B 1、B 2和B 3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.3所示。
表4.3
B 1B 2B 3
极大元 b , c , d b , c , d e
极小元 b , c , d a b , c , d
最大元无 无 e
最小元无 a 无
上界 e e e
下界 a a a
上确界 e e e
下确界 a a a
⑶A =P (⎨a , b , c ⎬)=⎨∅, ⎨a ⎬, ⎨b ⎬, ⎨c ⎬, ⎨a , b ⎬, ⎨a , c ⎬, ⎨b , c ⎬, ⎨a , b , c ⎬⎬
≼=⎨, , , , , , ,
, , , , , , , , , , , ⎬∪I A COV A =⎨
⎬>, , , , , ,
, , , , , ⎬ 哈斯图如图4.45所示。
A 的子集B 1、B 2和B 3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.5所示。
表4.5
B 1B 2B 3
极大元 ⎨a ⎬, ⎨b ⎬
极小元
最大元无 无 ⎨a , b , c ⎬
最小元
∅
⎨a , c ⎬
∅
无 ⎨a , c ⎬
⎨a ⎬, ⎨c ⎬ ⎨a ⎬, ⎨c ⎬ ⎨a , b , c ⎬
线性代数练习
1−31
5x =0，求x。 1. 若0
−12−2
参考答案：
1−311−31
5x
5x =05x =1×(−1) 1+1×=−5+x =0 0
−1−−12−20−1−1
解得x=5
⎧λx 1+x 2+x 3=0⎪
2．设齐次线性方程组⎨x 1+λx 2+x 3=0 只有零解， 则λ满足条件？
⎪x +x +λx =0
3⎩12
参考答案：
由题意，系数行列式不等于0，即
11λ112+λ2+λ2+λ
A =1λ1=11=(2+λ) ×λ1λ
11λ111λλ
111
=(2+λ）×0λ-10=(2+λ）×λ×(λ-1）≠0
00λ
∴λ≠1并且λ≠0λ≠-2
x +a a
3.计算行列式
a a
参考答案：
b c x +b c b x +c b c d
d
d x +d
x +a a a a
b x +b b b
c c x +c c
d d d x +d b
=
x +a +b +c +d x +a +b +c +d x +a +b +c +d x +a +b +c +d c c x +c c
d d d x +d
b x +b b b
c c x +c c
d d d x +d
x +b
=(x +a +b +c +d )
b b
2
4. 计算行列式
1b c d
0x 00
=(x +a +b +c +d ) =(x +a +b +c +d ) x 3
00x 0
000
x
120
413262
3−12115
23解： 151−12042361c −c
23−1221=4====
3分
212302
5
62
2140
r 4−r 22
3=====12
r 4−r 12
3=====10
1−1211−120
42344230
020
0 3分 02=00
0.
⎛120⎞
⎛23−1⎞⎜⎟T
5. 设A =⎜340⎟，B =⎜（2）|4A |. ⎟. 求（1）AB ；
⎝−240⎠⎜⎟
⎝−121⎠
120⎛120⎞⎛2−2⎞⎛86⎞
⎟⎜⎟⎜⎟⎜
解（1）AB T =⎜340⎟⎜34⎟=⎜1810⎟. （2）|4A |=43|A |=64|A |，而|A |=340=−2.
⎟⎟⎜⎟⎜⎜
−121⎝−121⎠⎝−10⎠⎝310⎠
所以 |4A |=64·（-2）=-128
⎡123⎤6.
⎥的逆矩阵. 求A =⎢221 ⎥⎢
⎢ ⎦⎣343⎥
参考答案：
3⎡123100⎤r −2r ⎡12
21
⎢0−2−5⎥⎯r 3−3r 1
(A E )=⎢⎯⎯→221010⎢⎥⎢
⎢⎢⎣343001⎥⎦⎣0−2−6
⎡10−2r 1+r 2
3−r 2⎯r ⎯⎯→⎢⎢0−2−5
⎢⎣00−1
100⎤
−210⎥⎥−301⎥⎦−110⎤
−210⎥⎥
−1−11⎥⎦
013−2⎤⎡10
⎥020365⎯⎯⎯→⎢−−⎢⎥
⎢⎣00−1−1−11⎥⎦
r 1−2r 3
r 2−5r 3
7. 求下列非齐次方程组的通解
⎡1001⎢3
⎯⎯⎯⎯→⎢010−
⎢00112⎣
3−2⎤⎡1⎥∴A −1=⎢−−3⎢⎥⎢1−1⎥⎣1⎦
⎛1⎞
r 2×⎜−⎟⎝2⎠r 3×(−1)
−2⎤5⎥−3
2⎥1−1⎥⎦3
⎧x 1
⎪
⎪x 1−x 2⎨
⎪2x 1−x 2⎪⎩3x 1−x 2
参考答案：
−x 3
+2x 3+x 3
+x 4+x 4+2x 4+3x 4
====21 35
对增广矩阵(A b )做行变换
⎛10−1⎜1−12⎜
⎜2−11⎜
⎝3−10⎛1r 3−r 2⎜0∼⎜r 4−r 2⎜0⎜⎝0
2⎞⎛10−112⎞⎟r 2−r 1⎜0−130−1⎟1⎟⎟⎜∼3−2r 1⎜03⎟r −1301⎟r 4−3r 1
⎟⎟⎜
−5⎠01301−⎠⎝
0−112⎞⎛10−112⎞
⎟−r 2⎜01−301⎟−130−1⎟⎟∼⎜
0000⎟−r 3⎜00000⎟
⎟⎟⎜
0000⎠⎝00000⎠
1123
R (A ) =R (A b ) =2，所以原方程组有解，其同解方程组为：
⎧x 1⎪⎪⎨⎪⎪⎩
x 2
−x 3
−3x 3
+x 4
=2=1
x 3, x 4为自由变量，令x 3=c,x4=c2得：⎧x 1=2+c 1−c 2 所以方程的同解为：
⎪x =1+3c ⎪21⎨
x 3=c 1
⎪⎪x 4=c 2⎩
⎛x 1⎞⎛1⎞⎛−1⎞⎛2⎞
⎜x ⎟⎜3⎟⎜0⎟⎜1⎟⎜2⎟=c ⎜⎟+c ⎜⎟+⎜⎟ ⎜x 3⎟1⎜1⎟2⎜0⎟⎜0⎟⎜⎟⎜⎟⎜⎟⎜⎟x 0⎝⎠⎝1⎠⎝0⎠⎝4⎠
⎛101⎞
⎜⎟
8. 设A=⎜212⎟, 且矩阵A,X 满足AX=A+X,求矩阵X
⎜011⎟⎝⎠
解：AX=A+X 所以有：(A-E)X=A
⎛001101⎞r 1r 2⎜⎟
→⎜202212⎟
⎜010011⎟r r
2⎝⎠3⎛202212⎞⎜⎟⎜010011⎟ ⎜001101⎟⎝⎠
1
12→r 1−r 3
⎛10000. 50⎞⎜⎟⎜010011⎟ ⎜001101⎟⎝⎠
⎛00. 50⎞⎜⎟所以X=⎜011⎟
⎜101⎟⎝⎠
⎡110⎤
9. 设A =⎢011⎥, 求A n ，用数学归纳法证明。
⎢⎥
⎢⎣001⎥⎦
参考答案：（一）推出通项
⎡121⎤⎡110⎤⎡133⎤⎡110⎤⎡110⎤⎡121⎤
⎢012⎥⎢011⎥=⎢013⎥⎥⎢011⎥=⎢012⎥32
A 2=⎢A =A A =011⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥
⎢⎢⎣001⎥⎦⎢⎣001⎥⎦⎢⎣001⎥⎦⎣001⎥⎦⎢⎣001⎥⎦⎢⎣001⎥⎦
1⎡⎤⎡133⎤⎡110⎤⎡146⎤1n (−1) n n ⎢⎥ A 4=A 3A =⎢013⎥⎢011⎥=⎢014⎥2n ⎢⎥⎢⎥⎢⎥⎥=⎢01n 推断A ⎢⎢⎥⎣001⎥⎦⎢⎣001⎥⎦⎢⎣001⎥⎦ 1⎢00⎥
⎢⎥⎣⎦（二）利用数学归纳法证明
⎡110⎤
⎥⎢当n=1时，A=011成立 ⎥⎢
⎢⎦⎣001⎥
⎡
⎢1k
假设n=k时成立，即A k =⎢01
⎢⎢00⎢⎣
⎡
⎢1k
=A k ×A =⎢01
⎢⎢00⎢⎣
1⎤
k (k −1) ⎥2
⎥ k
⎥1⎥
⎥⎦
A k +1
11⎤⎡⎤
k (k −1) ⎥⎡110⎤⎢1k +1k (k +1) ⎥
22⎢⎥⎥⎢×⎢011⎥=01k +1⎥，也成立 k
⎥⎢⎥⎢⎥011⎥⎣001⎦⎢0⎥⎥⎢⎥⎦⎣⎦
⎡
⎢1n n
故A =⎢01
⎢⎢00⎢⎣1⎤
n (n −1) ⎥2
⎥成立 n
⎥1⎥
⎥⎦
⎡111⎤⎡121⎤
⎢⎥⎢⎥10. 设A =-111, B =13-1，求(A-B)(A+B) ⎢⎥⎢⎥⎢⎢⎣1-11⎥⎦⎣214⎥⎦
参考答案：
⎡111⎤⎡121⎤⎡0−10⎤
⎥−⎢13-1⎥=⎢−2−22⎥
A −B =⎢-111⎥⎢⎥⎢⎥⎢
⎢⎣1-11⎥⎦⎢⎣214⎥⎦⎢⎣−1−2−3⎥⎦
⎡111⎤⎡121⎤⎡232⎤
⎥+⎢13-1⎥=⎢040⎥
A +B =⎢-111⎢⎥⎢⎥⎢⎥
⎢⎣1-11⎥⎦⎢⎣214⎥⎦⎢⎣305⎥⎦
−40⎤⎡0−10⎤⎡232⎤⎡0
⎥×⎢040⎥=⎢2−146⎥
(A-B)(A+B)=⎢−2−22⎥⎢⎥⎢⎥⎢
⎢⎦⎣−1−2−3⎥⎦⎢⎣305⎥⎦⎢⎣−11−11−17⎥
11. 编写矩阵乘法函数 void multi_matrix(int a[M][S],int b[S][N],int c[M][N]); 并用主函数调用，验证
#include
#define M 2 #define N 3 #define S 3
void multi_matrix(int a[M][S],int b[S][N],int c[M][N]) {
int i,j,k;
for(i=0;i
for(j=0;j
for(k=0;k
c[i][j]+=a[i][k]*b[k][j]; } } }
int main() {
int a[M][S]={{2,0,-1}, {1,3,2}}; int b[S][N]={{1,7,-1}, {4,2,3}, {2,0,1}}; int c[M][N]; int i,j;
multi_matrix(a,b,c); for(i=0;i
printf("%5d",c[i][j]); printf("\n"); }
⎡17−1⎤−201⎡⎤⎢⎡014−3⎤⎥AB =⎢⎥⎢423⎥=⎢171310⎥, 132⎣⎦⎢⎣⎦⎥201⎣⎦
return 0;
}
12. 求矩阵的秩
⎡−882−31⎤
⎡⎢1−1
210⎤1). A =⎢4−20⎥⎢2−22126⎥; 2). B =⎢
2−2⎢1132⎥
⎣−1⎥⎦
⎢⎢
306−11⎥⎥ ⎣03
00
1⎥⎦
参考答案：
r ⎡A 1r →3
⎢1−1−1−3−2⎤⎥r −2r ⎡1−1−1−3−2⎤
21
⎥−r ⎢2−22126⎥→⎢00418101⎢r 3+8r 1⎢⎥⎣−882−31⎦⎥⎢⎣00−6−27−15⎥⎦
1）1
⎡1−1−1−3−2⎤ 4r 2⎢9⎥r →⎢r 0015⎥∴R =23+61⎢⎢22⎥
⎣00000⎥⎦
2⎡1−1
210⎤⎡1−1
210⎤⎡1−1
21r 2−2r B 1⎢⎢000−40⎥0−40⎥r 4+r 2⎢030−4r →3−3r 1⎢⎢
03
0−41⎥r 4−r 3⎢00⎥→⎢
⎢030−41⎥⎥r →⎢
3r 0−4⎣03001⎥⎦⎢
⎣00040⎥2⎢⎦⎢
00
⎣00
00
⎡100⎤
13. 求逆矩阵 1). A =⎢⎢020⎥, 求A −2). A =⎡⎢21⎤
参考答案：
⎢3⎥1
⎣00⎥⎦⎣74⎥
⎦
, 求A −1. ⎡
⎢⎢
100⎤⎥⎥
1）A −1
=⎢10⎥1*⎡4−1⎢0
⎢
2⎥ 2）A −1=A =⎢⎤−72⎥ ⎢1⎥A ⎣⎦
⎣
003⎥⎦
）
0⎤1⎥1⎥⎥∴R =3
0⎥⎦
（1） 当λ满足什么条件时， 下面的向量组线性相关：α1=(λ, −
11, −) ，22
α2=(−, λ, −，α3=(−, −, λ) .
1或1/2
12121212
解：由定义，k 1α1+k 2α2+k 3α3=0
⎛1⎞⎛⎞1⎛⎞⎜-2⎟⎜λ⎟-⎜2⎟⎜⎟⎛0⎞⎧k 1λ+2k 1+4k 1=0⎜⎟ ⎜⎟1⎟1⎟⎜⎟⎪⎜⎜k 1-+k 2⎜λ⎟+k 3-=⎜0⎟⇒⎨2k 1+λ+k 1=0⎜2⎟⎜2⎟⎜0⎟⎪−k +k +λ=0⎜⎟1⎜⎟⎝⎜1⎟⎠⎩11λ⎟⎜-⎟⎜⎜-⎟⎝2⎠⎜⎟
⎝2⎠⎝⎠
⎡3⎤⎡4⎤⎡1⎤
⎢⎥⎢⎥⎢⎥（2） 已知向量α1=1，α2=λ，α3=0，则当λ满足什么条件时，α1，α2，⎢⎥⎢⎥⎢⎥⎢⎢⎢⎣λ⎥⎦⎣0⎥⎦⎣λ⎥⎦
α3 线性相关。
0或2
（3） 已知向量组α1=(1,2,3, 4) ，α2=(2,3,4,5) ，α3=(3,4,5,6) ，α4=(4,5,6,7)，
则该向量组的秩是？
2
（4） 向量组α1=(0,4, 2−λ) ，α2=(2,3−λ,1) ，α3=(1−λ, 2,3) 线性相关， 则实数
λ应满足什么条件？
6
⎡1⎤⎡0⎤⎡0⎤⎡−1⎤
⎢⎥⎢⎥⎢⎥⎢⎥（5） 设向量α1=0，α2=1，α3=0，则向量β=−1可表示为α1，α2，α3⎢⎥⎢⎥⎢⎥⎢⎥⎢⎢⎢⎢⎣0⎥⎦⎣1⎥⎦⎣1⎥⎦⎣0⎥⎦
的线性组合是？
-α1-α2+α3
1.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？
(1)(1，1，1，2，3)。 (2)(2，2，2，2，2)。 (3)(3，3，3，3)。 (4)(1，2，3，4，5)。 (5)(1，3，3，3)。
解 由于非负整数列d ＝(d 1，d 2，…，d n ) 是可图化的当且仅当∑d i ≡0(mod 2)，
i =1n
所以(1)、(2)、(3)、(5)能构成无向图的度数列。
(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。
(5)是不可简单图化的。若不然，存在无向图G 以为1，3，3，3度数列，不妨设G 中结点为v 1、v 2、v 3、v 4，且d(v 1)＝1，d(v 2)＝d(v 3)＝d(v 4)＝3。而v 1只能与v 2、v 3、v 4之一相邻，设v 1与v 2相邻，于是d(v 3)＝d(v 4)＝3不成立，矛盾。
2.有向图D 如图10-51
所示：
(1)求D 的邻接矩阵A 。
(2)D 中v 1到v 4长度为4的路有多少？ (3)D 中v 1到自身长度为3的回路有多少？
(4)D 中长度为4的路数为多少？其中有几条回路？ (5)D 中长度小于等于4的路有多少？其中有多少条回路？ (6)D 是哪类连通图？
解 (1) 求D 的邻接矩阵为：
⎛1⎜⎜0A =⎜
⎜0⎜0⎝
210⎞
⎟
010⎟
001⎟⎟010⎟⎠
且有
⎛1⎜2⎜0A =⎜
⎜0⎜0⎝1⎞⎛12⎟⎜
001⎟3⎜00 A =⎜010⎟⎟⎜00
⎜000001⎟⎠⎝
23
43⎞⎛12
⎟⎜10⎟4⎜00 A =⎜01⎟⎟⎜00
⎜0010⎟⎠⎝64⎞
⎟01⎟
10⎟⎟01⎟⎠
(4)
=4可知，e 1e 1e 4e 6、e 4e 6e 7e 6、(2)由A 4中a 14D 中v 1到v 4长度为4的路有4条，分别为：
e 1e 2e 5e 6、e 1e 3e 5e 6。
(3)
=1可知，D 中v 1到自身长度为3的回路只有1条，为e 1e 1e 1。 (3)由A 3中a 11
(4)D 中长度为4的路总数为路为3条。
∑∑a
i =1j =1
44
(4)
ij
=16，其中对角元素之和为3，说明长度为4的回
(5)D 中长度小于等于4的路总数为A 、A 2、A 3、A 4中全体元素之和：7＋10＋13＋16＝46，其中回路数为：1＋3＋1＋3＝8。
⎛4
⎜⎜0
(6)由B 4=A +A 2+A 3+A 4=⎜
0⎜⎜0⎝
8148⎞
⎟
022⎟
可知，D 是单向连通图。
022⎟
⎟
022⎟⎠
3. 如下图所示的赋权图表示某七个城市v 1, v 2, , v 7及预先算出它们之间的一些直接通信
线路造价
，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。
参考答案：
用库斯克（Kruskal ）算法求产生的最优树。算法为：
w (v 1, v 7) =1w (v 7, v 2) =4w (v 7, v 3) =9w (v 3, v 4) =3w (v 4, v 5) =17w (v 1, v 6) =23
结果如图：
选e 1=v 1v 7选e 2=v 7v 2选e 3=v 7v 3选e =v 3v 4选e =v 4v 5选e =v 1v 6
树权C(T)=23+1+4+9+3+17=57（万元）即为总造价
4. 如下图所示的赋权图表示某六个城市a,b,c,d,e,f 及预先算出它们之间的一些直接通信线
路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。
e
(1)
W (T 1') =15=W (T )
5. 在二叉树中
1） 求带权为2，3，5，7，8的最优二叉树T 。
2） 求T 对应的二元前缀码。
参考答案：
由Huffman 方法, 得最佳二叉树为： （4分）
（2）最佳前缀码为：000，001，01，10，11 （2分）
6. 用Huffman 算法求带权为1，2，3，5，7，9最优二叉树，并计算其权值。
解：1）画出最优二叉树，如下图所示： （6
分）
9
2)计算其权值 （3分）
W (T ) =1×4+2×4+3×3+5×2+7×2+9×2=63
7. 一棵无向树T 有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T
中有几片树叶？ 答案是： m=n-1=7
x+(2+3+4)*1=7*2 x=5
8. 一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是多少？ 14
3*4+4*2+x*1=(3+4+x-1)*2 12+8+x=12+2x x=8 m=7+8-1=14