数学参考答案破解版.pdf

数理逻辑练习 一 证明下面推理 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 s0 所以推理正确 结论 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 x F x 证明 1 xH x P 2 x H 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 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 CA 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 rq p 3 qpqp 4 P Q P Q 1 公式法 因为 P Q R P Q R 6 M 0 m 1 m 2 m 3 m 4 m 5 m 7 m 所以 公式 P Q R 为可满足式 其相应的成真赋值为 000 001 010 011 100 101 111 成假赋值为 110 真值表法 P Q R Q R 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 1 1 0 1 1 1 0 1 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 24 6 MMM 0135 mmmmm 7 其成真赋值为 000 001 011 101 111 3 p q p q p q p q p q 3 M 0 m 1 m 2 m 其成真赋值为 00 01 10 4 公式法 因为 P Q P Q P Q P Q P Q P Q P Q P Q 1 m 2 m 3 m 0 M 所以 公式 P Q P Q 为可满足式 其相应的成真赋值为 01 10 11 成 假赋值为 00 真值表法 P Q P Q P Q P Q P Q 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 由真值表可知 公式 P Q P Q 为可满足式 其相应的成真赋值为 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 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 Q R 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 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 由真值表可知 公式 P Q R 的成真赋值为 101 110 111 成假赋值为 000 001 010 011 100 2 解 P Q P Q P Q P Q P Q 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 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 P Q P Q P Q P Q 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 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 P Q Q R R P Q P Q Q R R P Q 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 由真值表可知 公式 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 Q P P Q Q P P Q 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 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 2 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 前面的四位数共有多少个 解 当 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 A B 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 设 A 1 2 构造集合 P A A 解 P A A 1 2 1 2 1 2 2 设R 求DR RR R R R 1 R 1 R R R 和R 解 DR 0 1 2 R RR 0 1 2 R 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 R A R B yy R A R B y 所以 R A B R A R B 4 设 X 1 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 所示 1 R 2 R R R 1 2 3 R 4 R R R 3 4 5 R 5 R 关系图每一个连通分支的结点构成的集合是一个等价类 或者说 每一个等价类导出了关系图的一个连通分支 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 x P A y P A x y 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 极大元 极小元 最大元最小元 B1 a b 无 B2 a c a c 无 无 B3 a b c a c a b c a 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 a M S int b S N int c M N 171 2010143 423 132171310 201 AB 并用主函数调用 验证 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 M i for j 0 j N j c i j 0 for k 0 k S 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 M i for j 0 j N j printf 5d c i j 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中v4 4 14