《离散数学答案(尹宝林版)第三章习题解答》由会员分享，可在线阅读，更多相关《离散数学答案(尹宝林版)第三章习题解答（11页珍藏版）》请在金锄头文库上搜索。
1、第三章 公理系统1. 证明：(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 解 (1) ，A，A，A，A，A最后，使用3次演绎定理得到：(2)，B，A，B，A，B，A，B，A，B，A最后，使用3次演绎定理得到：(3) 公理一 演绎定理 公理三 MP规则 公理三 MP规则 MP规则最后，由演绎定理得到：(4) 本题 (3)公理三MP规则(5) 本题 (3), A演绎定理, , BMP规则, 本题 (4), MP规则演绎定理公理三 MP规则演绎定理(6) ，A，BMP规则演绎定理本题 (5)MP规则演绎定理(7) 例3.4演绎定理演绎定理即(8) 公理一即(9)
2、例3.4演绎定理本题 (4)MP规则演绎定理公理三MP规则即(10) 公理一演绎定理本题 (4)MP规则演绎定理公理三MP规则即2. 以下结论对吗？若对，加以证明；若不对，举出反例。(1) 且 当且仅当 。(2) 或 当且仅当 。解 (1) 对。设且。题1 (6)已知 MP规则已知题1 (4)MP规则MP规则即设。题1 (9)题1 (10)已知MP规则MP规则(2) 不对。，即，但且。3. 证明空集是协调的公式集。证明 由可靠性定理知道，若，则A是永真式。因此，空集是协调的公式集。4. 若且，则。证明 若且，则存在一个A的从的推演，该推演也是A的从的推演。因此，。5. 若且是协调的，则也是协调
3、的。证明 若且是协调的，则存在公式A使得，由上题知道，。所以，也是协调的。6. 证明定理3.4的逆定理。证明 定理3.4的逆定理叙述如下：若可满足，则协调。若不协调，则，由可靠性定理得到。因此，不可满足。7. 用定理3.5证明定理3.4。证明 若不可满足，则。由定理3.5得到。由定理3.3得出不协调。8. 用定理3.7证明定理3.6。证明 若，则不可满足。由定理3.7知道，有的有穷子集不可满足。令，则，因此不可满足。由第二章习题19知道，。9. 证明：(1) ，其中t对于A中的是可代入的。(2) (3) (4) (5) (6) (7) ，其中不是B的自由变元。(8) 证明 (1) 公理四重言式
4、即(2) 重言式公理四重言式MP规则重言式公理四重言式MP规则重言式MP规则UG规则公理五MP规则重言式MP规则即(3) 重言式例3.8重言式例3.8重言式MP规则重言式公理四重言式MP规则重言式公理四重言式MP规则重言式MP规则UG规则公理五MP规则重言式MP规则(4) 首先证明：若，则。已知重言式MP规则例3.8重言式MP规则例3.8重言式MP规则然后证明。重言式已证本题 (3)重言式MP规则重言式MP规则即。(5) 重言式第10题 (1)重言式第10题 (1)重言式MP规则(6) 重言式本题(4)的证明重言式MP规则即(7)公理四重言式MP规则UG规则公理五MP规则重言式MP规则即本题(1)重言式MP规则UG规则公理五MP规则重言式MP规则(8) 本题(1)例3.8第10题 (2)10. 证明：(1) 若，则。(2) 若且不是B的自由变元，则。证明 (1)已知重言式MP规则例3.8重言式MP规则即(2) 已知重言式MP规则UG规则公理五MP规则重言式MP规则即
