离散数学答案(尹宝林版)第三章习题解答 VIP免费

1/11第三章公理系统1.证明：(1)))()(()(|CACBBA(2)))(())((|CABCBA(3)AA|(4)AA|(5))()(|ABBA(6)))((|BABA(7)BAA|(8)ABA|(9)ABA|(10)BBA|解(1)BA，CB，AA|BA，CB，ABA|BA，CB，AB|BA，CB，ACB|BA，CB，AC|最后，使用3次演绎定理得到：))()(()(|CACBBA(2))(CBA，B，AA|)(CBA，B，A)(|CBA)(CBA，B，ACB|)(CBA，B，AB|2/11)(CBA，B，AC|最后，使用3次演绎定理得到：))(())((|CABCBA(3))(|AAA公理一AAA|演绎定理A)()(|AAAA公理三AAA|MP规则A)()(|AAAA公理三AAA|MP规则AA|AA|MP规则最后，由演绎定理得到：AA|(4)AA|本题(3))()(|AAAA公理三AA|MP规则(5)BA|AA本题(3)BA,A|A演绎定理BA,A|BABA,A|BMP规则BA,A|BB本题(4)BA,A|BMP规则BA|BA演绎定理BA|)()(ABBA公理三3/11BA|ABMP规则)()(|ABBA演绎定理(6)A，BA|AA，BA|BAA，BA|BMP规则A|BBA)(演绎定理A|))(())((BABBBA本题(5)A|)(BABMP规则))((|BABA演绎定理(7))(|BAA例3.4BAA|,演绎定理)(|BAA演绎定理即BAA|(8))(|ABA公理一即ABA|(9))(|BAA例3.4ABA|演绎定理A)()(|BABA本题(4)A)(|BAMP规则)(|BAA演绎定理))(())((|ABABAA公理三ABA)(|MP规则4/11即ABA|(10))(|BAB公理一BAB|演绎定理)()(|BABAB本题(4))(|BABMP规则)(|BAB演绎定理))(())((|BBABAB公理三BBA)(|MP规则即BBA|2.以下结论对吗？若对，加以证明；若不对，举出反例。(1)A|且B|当且仅当BA|。(2)A|或B|当且仅当BA|。解(1)对。设A|且B|。))((|BABA题1(6)A|已知)(|BABMP规则B|已知BB|题1(4)B|MP规则)(|BAMP规则即BA|设BA|。ABA|题1(9)5/11BBA|题1(10)BA|已知A|MP规则B|MP规则(2)不对。11|pp，即11|pp，但1/|p且1/|p。3.证明空集是协调的公式集。证明由可靠性定理知道，若A|，则A是永真式。因此，1/|p，空集是协调的公式集。4.若21且A|1，则A|2。证明若21且A|1，则存在一个A的从1的推演，该推演也是A的从2的推演。因此，A|2。5.若21且2是协调的，则1也是协调的。证明若21且2是协调的，则存在公式A使得A/|2，由上题知道，A/|1。所以，1也是协调的。6.证明定理3.4的逆定理。证明定理3.4的逆定理叙述如下：若可满足，则协调。若不协调，则11|pp，由可靠性定理得到11|pp。因此，不可满足。7.用定理3.5证明定理3.4。证明若不可满足，则11|pp。由定理3.5得到11|pp。由定理3.3得出不协调。8.用定理3.7证明定理3.6。证明若A|，则}{A不可满足。由定理3.7知道，有}{A的有穷子集1不可满足。令12，则}{21A，因此}{2A不可满足。由第二章习题19知道，A|2。9.证明：(1)AxAixti|，其中t对于A中的ix是可代入的。(2))()(|BxAxBAxiii6/11(3))()(|BxAxBAxiii(4))()(|BxAxBAxiii(5))()(|BxAxBAxiii(6)AxAxii|(7))()(|BAxBAxii...