数学参考答案破解版.pdf

数理逻辑练习 一、证明下面推理 1） 前提：p(q(sr),sp 结论：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) sp P (3) p T(2),I (4) p(q(sr) P (5) q(sr) T(3)(4),I (6) sr T(1)(5),I (7) s T(2),I (8) s T(6),I (9) ss T(7)(8),I 由于最后步ss0，所以推理正确，结论q 为有效结论。 2) 证明： x(G(x)R(x) P x(G(x)R(x) T(1),E G(c)R(c) T(2),I xR(x) P R(c) T(4),I G(c) T(3)(5),I x(F(x)G(x) P F(c)G(c) T(7),I F(c) T(6)(8),I x(F(x) T(9),I 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) |-xF(x) 证明： (1) xH(x) P (2) xH(x) T(1),E (3) H(c) T(2),I (4) x(G(x)H(x) P (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) xF(x) T(9),I 3) 如果 2 是偶数，则 3 是奇数。或者 2 是偶数或者 2 整除 3，结果 2 整除 3，所以 3 不是奇 数。 解 设 A：2 是偶数；B：3 是奇数，C：2 整除 3；则推理化形式为： AB，AC，CB 该推理形式不正确。例如，设有一赋值：AF，BT，CT，则 AB、AC、C 都 为真，但B 为假。 4) 如果 A 努力工作，那么 B 或 C 感到愉快；如果 B 愉快，那么 A 不努力工作；如果 D 愉 快那么 C 不愉快。所以，如果 A 努力工作，则 D 不愉快。 解： 设 A：A 努力工作；B、C、D 分别表示 B、C、D 愉快；则推理化形式为： ABC，BA，DCAD 该推理形式正确。下面给出证明： (1)A 附加前提 (2)ABC P (3)BC T(1)(2)，I (4)BA P (5)AB T(4)，E (6)B T(1)(5)，I (7)C T(3)(6)，I (8)DC P (9)D T(7)(8)，I (10)AD CP 三、求下列命题公式的主析取范式和主合取范式，并求其成真赋值。 1） P(QR) 2） rq p )( 3） ) ()(qpqp 4） (PQ)(PQ) 1）公式法：因为 P(QR)PQR 6 M 0 m 1 m 2 m 3 m 4 m 5 m 7 m 所以，公式 P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、100、 101、111：成假赋值为：110。 真值表法： P Q R QR P(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 由真值表可知， 公式 P(QR)为可满足式， 其相应的成真赋值为 000、 001、 010、 011、 100、101、111：成假赋值为：110。 2） （pq）r ( pq )r (pq )r (pr) (qr) (p(qq )r) (pp )qr) (pqr) (pqr) (pqr) (pqr) 24 6 MMM 0135 mmmmm 7 其成真赋值为 000，001，011，101，111 3） （pq） (pq) (pq)（pq） pq 3 M 0 m 1 m 2 m 其成真赋值为 00，01，10 4) 公式法：因为(PQ)(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ) 1 m 2 m 3 m 0 M 所以，公式(PQ)(PQ)为可满足式，其相应的成真赋值为 01、10、11：成 假赋值为：00。 真值表法： P Q PQ PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 由真值表可知，公式(PQ)(PQ)为可满足式，其相应的成真赋值为 01、10、 11：成假赋值为：00。 四、求下列各公式的前束范式 四、求下列各公式的前束范式 1） ),( )(yxyQxPx 2） )()(),(zzRyyQyxxP 1）x(P(x) yQ(x,y) x (P(x) yQ(x,y) x (P(x) yQ(x,y) x (P(x)yQ(x,y) xy (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) xy (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 yz (P(x,t)Q(y)R(z) 五、构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？ 五、构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？ 1） P(QR)。 2） (PQ)(PQ)。 解 (1) P Q R QR P(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 由真值表可知，公式 P(QR)的成真赋值为：101、110、111，成假赋值为 000、 001、010、011、100。 2) 解： P Q ( PQ) PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 由真值表可知，公式(PQ)(PQ)的成真赋值为：00、01、10、11，没有 成假赋值。 六、分别用真值表法和公式法判断下列命题公式的类型： (1)(PQ)(PQ)。 (3)(PQ)(QR)(RPQ)。 (5)(QP)(PQ)。 解 (1)真值表法： P Q PQ PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 1 由真值表可知，公式(PQ)(PQ)为可满足式。 公式法：因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)，所以， 公式(PQ)(PQ)为可满足式。 (3)真值表法： P Q R PQ QR RPQ(PQ)(QR)(RPQ) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 由真值表可知，公式(PQ)(QR)(RPQ)为矛盾式。 公式法：因为(PQ)(QR)(RPQ)(PQ)QR(RP Q)F，所以，公式(PQ)(QR)(RPQ)为矛盾式。 (5)真值表法： P Q QP PQ (QP)(PQ) 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 由真值表可知，公式(QP)(PQ)为矛盾式。 公式法：因为(QP)(PQ)(QP)(PQ)(QP)(PQ)F， 所以，公式为矛盾式。 集合论练习 1.给定自然数集N的子集：A1，3，7，8，Bi|i 230 ，Ci|i可以被 3 整除且 0i20。求下列集合： (1)AB (2)BC。 (3)B(AC)。 (4)BC 解 由题意得 A1，3，7，8，B0，1，2，3，4，5，C0，3，6，9，12，15， 18所以 (1)AB0，1，2，3，4，5，7，8 (2) BC0,3 (3)B(AC)B-0,1,3,6,7,8,9,12,15,18=2,4,5 (4) BC=BC-BC=0,1,2,3,4,5,6,9,12,15,18-0,3=1,4,5,6,9,12,15,18 2、已知 ABAC，ABAC，请用集合恒等式证明 BC。 证明证明 BB(AB) B(AC) (BA)(BC) (AC)(BC) (AB)C (AC)C C 3.求由数字 1、2、3、4、5、6 组成的四位数(每个数字都不允许重复出现)中，数字 2 在 5 前面的四位数共有多少个？ 解 当 2 在第 1 位时， 21 43 12 336AC= 当 2 在第 2 位时， 21 42 12224AC= 当 2 在第 3 位时， 2 4 12A = 任取 4 个不同的数字，且数字 2 在 5 前面的 4 位数个数为 36+24+12=72 4. 求求 1 到到 2500 之间能被之间能被 2，3，5 和和 7 中任何一个数整除的整数个数。中任何一个数整除的整数个数。 解：设A1表示 1 到 2500 之间能被 2 整除的整数集合，A2表示能被 3 整除的整数集合，A3表 示能被 5 整除的整数集合，A4表示能被 7 整除的整数集合。|x| 表示小于或等于x的最大整 数。 1 2500 | | 1250 2 A = 2 2500 | | 833 3 A = 3 2500 | | 500 5 A = 4 2500 | | 357 7 A = 12 2500 | | 41 2 3 AA = 6 13 2500 | | 250 2 5 AA =| 14 2500 | | 2 7 AA =178 23 2500 | | 16 3 5 AA = 6 24 2500 | | 119 3 7 AA =| 34 2500 | | 5 7 AA71= 123 2500 | | 2 3 5 AAA =83 124 2500 | 59 2 3 7 AAA|= 234 2500 | | 3 5 7 AAA = | 23 1234 2500 | | 2 3 5 7 AAAA 134 2500 | | 2 5 7 AAA = | 35 11= 根据容斥原理 1234 | 1250833500357416250 178 166 119 71 83593523 111929 AAAA =+ += 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 人，由已知条件填写图中相应区域。 C-(AB)= 75-31-23=21 由已知条件，可得以下方程： (20-x)+x+(9-x)+(17-x)+31+23+21 = 111 解得：x=5 故A=31+(20-5)+5+(17-5)=63 B=23+(20-5)+5+(9-5)=47 C=21+(9-5)+5+(17-5)=42 因而可得，三种股票都买的有 5 人。 买 A 股的有 63 人，买 B 股的有 47 人，买 C 股的有 42 人。 31 23 21 A B C x 17-x 20-x 9-x 关系练习 1.设 A1，2，构造集合 P(A)A。 解 P(A)A，1， 2，1，21，2， ，。 2.设R， ， ， ， 求DR、 RR R R、 R 1、 R1、 R 、 R 、 R和R。 解 DR0，1，2 R RR0，1，2 R R 1， R11，2 R R R R 3.证明 RABRARB。 (1)因为yRABx(xABxR y) x(xAxB)xR y) x(xAxR y)(xBxR y) x(xAxR y)x(xBxR y) RARB yy RARB y 所以 RABRARB。 4.设 X1，2，3，4，R 是 X 上的二元关系，R， ， (1)画出 R 的关系图。 (2)写出 R 的关系矩阵。 (3)说明 R 是否是自反、反自反、对称、传递的。 解 (1)R 的关系图如图所示： 1 2 3 4 (2) R 的关系矩阵为： 0100 1100 ( ) 1010 1010 M R = (3)对于 R 的关系矩阵，由于对角线上不全为 1，R 不是自反的；由于对角线上存在非 0 元，R 不是反自反的；由于矩阵不对称，R 不是对称的； 经过计算可得 2 010001001 100 110011001 100 () 101010101 110 101010101 110 M R = ，所以 R 不是传递的。 5.令 A=1,2,3;B=a,b,求 R1=,的关系矩阵。 1 11 01 10 R M = 6.令 A=1,2,3;求 R2=,的关系图。 1 2 3 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） 求R0，R2，r(R)，s(R)，t(R)的集合表达式。 解 1） R 既不具有自反性也不具有反自反性；R 既不具有对称性也不具备反对称性； R 也不具备传递性。 2) , 0 =bdaddcbcacbbabbaaaRt 9.设 A=1,2,3,4,5，A 上的等价关系 R 定义为： R=,IA 画出关系图，找出所有等价类。 解：R 的关系图如图 4.34 所示。 1R=2R R R=1,2，3R=4R R R=3,4，5R=5R 关系图每一个连通分支的结点构成的集合是一个等价类。 或者说， 每一个等价类导出了关系图的一个连通分支。 10.求出下列各偏序集的盖住关系COV A，画出哈斯图，找出A 的子集B1、B2和 B3的极大元、极小元、最大元、最小元。 A=a,b,c,d,e， =,IA B1=b,c,d ，B2=a,b,c,d ，B3=b,c,d,e A=P(a,b,c)，= xP(A)yP(A)xy B1=,a,b，B2=a,c，B3=a, c,a,b,c 解：COV A=, 哈斯图如图所示。 A 的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、 下界、上确界和下确界如表 4.3 所示。 表 4.3 极大元 极小元 最大元最小元上界 下界 上确界 下确界 B1b,c,d b,c,d 无 无 e a e a B2b,c,d a 无 a e a e a B3e b,c,d e 无 e a e a A=P(a,b,c)=,a,b,c,a, b,a, c,b, c,a,b,c =, , , IA COV A=, , 哈斯图如图 4.45 所示。 A 的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下 确界如表 4.5 所示。 表 4.5 极大元 极小元 最大元最小元 B1a,b 无 B2a,c a,c 无 无 B3a,b,c a,c a,b,ca,c 线性代数练习 1. 若0 221 50 131 = x，求 x。 参考答案： 参考答案： 05 11 5 ) 1(1 110 50 131 221 50 131 11 =+= = = + x x xx 解得 x=5 2设齐次线性方程组 只有零解， 则 123 123 123 0 0 0 xxx xxx xxx += += += 满足条件？ 参考答案： 参考答案： 由题意，系数行列式不等于 0，即 2-01 01-(2( 00 01-0 111 2( 11 11 111 )2( 11 11 222 11 11 11 A +=+= += + = 并且 ） 3.计算行列式 xabcd axbcd abxcd abcx + + + d+ 参考答案： 参考答案： 3 )( 000 000 000 1 )( 1 1 1 1 )(xdcbax x x x dcb dcbax dxcb dcxb dcbx dcb dcbax dxcbdcbax dcxbdcbax dcbxdcbax dcbdcbax dxcba dcxba dcbxa dcbax +=+= + + + += + + + + = + + + + 4. 计算行列式 2141 3121 1232 5062 解： 2605 2321 1213 1412 2605 0321 2213 0412 24 = cc ?3分 0412 0321 2213 0412 24 = rr ?3分 0 0000 0321 2213 0412 14 = = rr . 5. 设A= ，B= .求（1）AB 120 340 121 2 2 3 4 1 0 T； （2）|4A|. 解（1）ABT=.（2）|4A|=4 120 340 121 22 34 10 86 1810 310 3|A|=64|A|，而|A|= 120 340 121 2 = . 所以 |4A|=64 （-2）=-128 . 343 122 321 的逆矩阵求 =A 6. 参考答案：参考答案： () = + 111100 012520 011201 103620 012520 001321 100343 010122 001321 23 21 13 12 3 2 rr rr rr rr EA? () 111100 2 5 3 2 3 010 231001 111100 563020 231001 1 2 1 5 2 3 2 32 31 r r rr rr = 111 2 111 2 5 3 2 3 231 1 A 7. 求下列非齐次方程组的通解 134 1234 1234 124 2 21 22 33 xxx xxxx xxxx xxx += += += + 3 5= ) = 参考答案： 对增广矩阵做行变换 (bA? 21 31 41 322 423 2 3 1011210112 1121101301 2112301301 3103501301 1011210112 0130101301 0000000000 0000000000 rr rr rr rrr rrr ( )()2R AR Ab=，所以原方程组有解，其同解方程组为： 134 23 2 31 xxx xx += = x3,x4为 自 由 变 量 ， 令 x3=c,x4=c2得 ： 11 21 31 42 2 13 2 xcc xc xc xc =+ = + = = 所 以 方 程 的 同 解 为 ： 1 2 12 3 4 11 30 10 01 x x cc x x =+ 2 1 0 0 8.设 A=,且矩阵 A,X 满足 AX=A+X,求矩阵 X 110 212 101 解：AX=A+X 所以有：(A-E)X=A 110010 212202 101100 101100 110010 212202 23 21 rr rr 101100 110010 05.00001 2 1 31 1 rr r 所以 X= 101 110 05.00 9. 参考答案： （一）推出通项参考答案： （一）推出通项 （二）利用数学归纳法证明 当 n=1 时，A=成立 100 110 011 假设 n=k 时成立，即 = 100 k10 ) 1( 2 1 k1 k kk A + + = = + 100 1k10 ) 1( 2 1 1k1 100 110 011 100 k10 ) 1( 2 1 k1 k1k kkkk AAA，也成立 故 = 100 n10 ) 1( 2 1 n1 n nn A成立 10. 设 111121 -111 ,B13-1 1-1 1214 A = ，求(A-B)(A+B) 参考答案：参考答案： 111121010 -11113-1222 1-1 1214123 AB = 求，用数学归纳法证明。 n 110 011 , 001 AA = 设 = = 100 210 121 100 110 011 100 110 011 2 A = = 100 310 331 100 110 011 100 210 121 23 AAA = 100 n10 ) 1( 2 1 n1 n nn A推断 = = 100 410 641 100 110 011 100 310 331 34 AAA 111121232 -11113-1040 1-1 1214305 AB += = 010232040 2220402146 123305111117 = = (A-B)(A+B) 11.编写矩阵乘法函数 void multi_matrix(int aMS,int bSN,int cMN); 171 2010143 423, 132171310 201 AB = 并用主函数调用，验证 #include #define M 2 #define N 3 #define S 3 void multi_matrix(int aMS,int bSN,int cMN) int i,j,k; for(i=0;iM;i+) for(j=0;jN;j+) cij=0; for(k=0;kS;k+) cij+=aik*bkj; int main() int aMS=2,0,-1, 1,3,2; int bSN=1,7,-1, 4,2,3, 2,0,1; int cMN; int i,j; multi_matrix(a,b,c); for(i=0;iM;i+) for(j=0;jN;j+) printf(“%5d“,cij); printf(“n“); return 0; 12.求矩阵的秩 = = 10030 11603 02422 01211 ).2; 23111 612222 13288 ).1BA 参考答案：参考答案： 1） 1321 131 2 31 2 8 1 4 6 1113211132 2221260041810 882310062715 11132 95 0012 22 00000 rrrr rrr r rr A R + + = = 2） 13.求逆矩阵 432142 3132 2 3 112101121011210 000400004003041 3 030410304100041 030010004000000 rrrrrr rrrr BR + ., 47 12 ).2, 300 020 001 ).1 11 = =AAAA求求 参考答案：参考答案： 1） 1 100 1 00 2 1 00 3 A = 2） 1* 41 1 72 AA A = （1） 当满足什么条件时 ， 下 面 的 向 量 组 线 性 相 关 ： 1 11 ( ,) 22 =， 2 11 (, ,)， 22 = 3 11 (, ) 22 . = 1 或 1/2 112233 111 12311 11 0 1 1- - 2 240 2 11 -02 + 22 10+0 1- - 2 2 kkk kkk kkkkk kk += 0 0 += + +=+= += 解：由定义， （2） 已知向量 1 3 1 = ， 2 4 0 = ， 3 1 0 = ，则当满足什么条件时， 1 ， 2 ， 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 （5） 设向量 1 1 0 1 = ， 2 ， 3 0 1 0 = 0 0 1 = ，则向量 1 1 0 = 可表示为 1 ， 2 ， 3 的线性组合是？ 123 -+ 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(d1，d2，dn)是可图化的当且仅当0(mod 2)， 所以(1)、(2)、(3)、(5)能构成无向图的度数列。 = n i i d 1 (1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。 (5)是不可简单图化的。若不然，存在无向图 G 以为 1，3，3，3 度数列，不妨设 G 中 结点为、，且 d()1，d()d()d()3。而只能与、 之一相邻，设与相邻，于是 d()d()3 不成立，矛盾。 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v 2.有向图 D 如图 10-51 所示： (1)求 D 的邻接矩阵 A。 (2)D中v1到v4长度为 4 的路有多少？ (3)D中v1到自身长度为 3 的回路有多少？ (4)D 中长度为 4 的路数为多少？其中有几条回路？ (5)D 中长度小于等于 4 的路有多少？其中有多少条回路？ (6)D 是哪类连通图？ 解 (1) 求 D 的邻接矩阵为： = 0100 1000 0100 0121 A 且有 = 01000 0100 1000 1321 2 A = 0100 1000 0100 3421 3 A = 1000 0100 1000 4621 4 A (2)由 4 A中可知， D中