離散數(shù)學(xué) 尹寶林等編 第三章習(xí)題解答

1、第三章 公理系統(tǒng)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規(guī)則 公理三 MP規(guī)則 MP規(guī)則最后，由演繹定理得到：(4) 由上題知道公理三MP規(guī)則(5) 本題 (3), A演繹定理, , BMP規(guī)則, 本題 (4), MP規(guī)則演繹定理公理三演繹定理(6) ，A，BMP規(guī)則演繹定理本題 (5)MP規(guī)則演繹定理(7) 例3.4演繹定理演繹定理即(8) 公理一即(9) 例3.4演繹

2、定理本題 (4)MP規(guī)則演繹定理公理三MP規(guī)則即(10) 公理一演繹定理本題 (4)MP規(guī)則演繹定理公理三MP規(guī)則即2. 以下結(jié)論對(duì)嗎？若對(duì)，加以證明；若不對(duì)，舉出反例。(1) 且 iff 。(2) 或 iff 。解 (1) 對(duì)。設(shè)且。題1 (6)已知已知題1 (4)MP規(guī)則MP規(guī)則即設(shè)。題1 (9)題1 (10)已知MP規(guī)則MP規(guī)則(2) 不對(duì)。，即，但且。3. 證明空集是協(xié)調(diào)的公式集。證明 由可靠性定理知道，若，則A是永真式。因此，空集是協(xié)調(diào)的公式集。4. 若且，則。證明 若且，則存在一個(gè)A的從的推演，該推演也是A的從的推演。因此，。5. 若且是協(xié)調(diào)的，則也是協(xié)調(diào)的。證明 若且是協(xié)調(diào)的，則

3、存在公式A使得，由上題知道，。所以，也是協(xié)調(diào)的。6. 證明定理3.4的逆定理。證明 定理3.4的逆定理敘述如下：若可滿足，則協(xié)調(diào)。若不協(xié)調(diào)，則，由可靠性定理得到。因此，不可滿足。7. 用定理3.5證明定理3.4。證明 若不可滿足，則。由定理3.5得到。由定理3.3得出不協(xié)調(diào)。8. 用定理3.7證明定理3.6。證明 若，則不可滿足。由定理3.7知道，有的有窮子集不可滿足。令，則，因此不可滿足。由第二章習(xí)題19知道，。9. 證明：(1) ，其中t對(duì)于A中的是可代入的。(2) (3) (4) (5) (6) (7) ，其中不是B的自由變?cè)?8) 證明 (1) 公理四重言式即(2) 重言式公理四重言式MP重言式公理四重言式MP重言式MPUG公理五MP重言式MP即(3) 重言式例3.8重言式例3.8重言式MP重言式公理四重言式MP重言式公理四重言式MP重言式MPUG公理五MP重言式MP(4) 首先證明：若，則。已知重言式MP例3.8重言式MP例3.8重言式MP然后證明。重言式已證本題 (3)重言式MP重言式MP即。(5) 重言式第10題 (1)重言式第10題 (1)重言式MP(6) 重言式本題(4)的證明重言式重言式MP即(7)公理四重言式MPUG公理五MP重言式MP即本題(1)重言式MPUG公理五MP重言式MP(8) 本題(1)例3.8第10題 (2)10. 證明：(1) 若，則。