离散数学_第_3_章_习题解答ж

《离散数学_第_3_章_习题解答ж》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章公理系统习题解答1.证明：(1)

2、−→→→→→()ABB(()CA()C)(2)

3、(−→→→→→A(BC))(BAC())(3)

4、−¬¬→AA(4)

5、−→¬A¬A(5)

6、(−→→¬→ABBA)(¬)(6)

7、(−→¬→A(BA¬→(B)))(7)

8、−→∨AAB(8)

9、−→∨ABA(9)

10、−∧→ABA(10)

11、−∧→ABB解(1)A,,

12、AB→→−BCAA,,

13、AB→→−BCAB→A,,

14、AB→→−BCBA,,

15、AB→→−BCBC→A,,

16、AB→→−BCCA→→−BB,

17、CA→C

18、−→→→→→()ABB(()CA()C)(2)AA→→()B

19、CBC→BC

20、(−→→→→→A(BC))(BAC())(3)(4)(5)A→B()A→→¬→BBA(¬)¬→¬BA

21、(−→→¬→ABBA)(¬)(6)A,

22、ABB→−A

23、(−→→ABB)A

24、(−¬→¬BA→B)

25、(()−→¬→¬→ABAB)(7)

26、()−→¬→ABA

27、(−¬→BA)(→¬→¬¬AB)

28、−¬¬→BB

29、(−¬→¬¬→¬→ABA)(B)

30、(−¬→BA)(→¬→AB)

31、()−→¬→AAB

32、−→∨AAB(8)A∨⇔¬→BAB

33、()−→¬→ABA

34、−→∨ABA(9)(10)2.以下结论对吗？若对，加以证明；若不对，举出反例。(1)Γ

35、−A

36、且Γ

37、−B当且仅当Γ

38、−∧AB。(2)Γ

39、−A或Γ

40、−B当且仅当Γ

41、−∨AB。证明(1)()⇒若Γ

42、,

43、−ΓA−B，则Γ

44、−∧AB()⇐若Γ

45、−A∧B，则Γ

46、,

47、−ΓA−BΓ−

48、AΓ

49、−∧ABΓ−

50、BΓ

51、−∧→ABAΓ−→¬¬→¬→¬

52、(ABAB())Γ

53、−AΓ−→¬¬

54、BBΓ

55、−∧→ABBΓ−¬¬→¬

56、(()BABBAB→¬)→(()→¬→¬)Γ

57、−BΓ−→

58、(()ABAB→¬→¬)Γ

59、,

60、−AΓ−BΓ−→¬

61、()BAB→¬Γ−¬→¬

62、(AB)Γ−∧

63、AB(2)结论不对

64、−¬¬→AA

65、−¬∨AA

66、−¬/A和

67、−/A3.证明空集是协调的公式集

68、。证由可靠性定理可知，若Γ

69、−A，则A是永真式。因此对于任意命题变元p，

70、−/p，空集是协调的公式集。4.若Γ⊆Γ且Γ

71、−A，则Γ

72、−A。1212证若Γ⊆Γ且Γ

73、−A，则存在一个A的从Γ的推演，该推演也是A的从Γ的推演。因此，Γ

74、−A。1211225.若Γ⊆Γ且Γ是协调的，则Γ也是协调的。1221证若Γ是协调的，则存在公式A使得Γ

75、−/A，由上题知道，若Γ⊆Γ，则Γ

76、−/A。所以Γ也是协调的。2212116.证明定理3.4的逆定理。7.用定理3.5证明定理3.4。8.用定理3.7证明定理3.6。9.证明：x(1)

77、−→A∃xA，其中t对于A中

78、的x是可代入的。t(2)

79、(−∀xA→B)(→∃xA→∃xB)(3)

80、()−∀xAB∧↔∀xAxB∧∀(4)

81、()−∃xA∨B↔∃xA∨∃xB(5)

82、()−∃xA∧B→∃xA∧∃xB(6)

83、−∀xAx↔¬∃¬A(7)

84、(−∀xAB→)(↔∃xAB→)，其中x不是B的自由变元(8)

85、−∃∀xyA→∀∃yxA证明x(1)

86、−∀¬→¬xAAtx

87、−¬¬A→¬∀¬xAtxx

88、−→A¬¬Attx

89、−→A∃xAt(2)

90、−∃xAA→

91、(−∀→→→xABAB)()

92、−→∃BxB

93、(−→→→ABAx)(∃B)

94、(−→A∃→∃→xB)(xA∃xB)

95、(−→→∃

96、→ABx)(Ax∃B)

97、(−∀xA→B)(→∃xA→∃xB)(3)若

98、()−∀xA∧B→∀xA∧∀xB且

99、(−∀xAx∧∀Bx→∀AB∧)则

100、()−∀xA∧B↔∀xA∧∀xB

101、()−∀xABAB∧→∧

102、−∀∧xAx∀→∀BxA

103、−∧→ABA

104、−∀→xAA

105、−→∀AxA

106、−∀∧xAx∀→BA

107、−∧→∀ABxA

108、−∀∧xAx∀→∀BxB

109、−∧→ABB

110、−∀→xBB

111、−→∀BxB

112、−∀∧xAx∀→BB

113、−∧→∀ABxB

114、−∀∧xAx∀→∧BAB

115、()−∀xAB∧→∀xA

116、(−A∧→∀∧BxAB)

117、()−∀xAB∧→∀xB

118、(−∀∧xAx∀→∀∧Bx

119、AB)

120、()−∀xA∧B→∀xA∧∀xB(4)若

121、()−∃xA∨B→∃xA∨∃xB且

122、(−∃xAx∨∃Bx→∃AB∨)则

123、()−∃xA∨B↔∃xA∨∃xB

124、(−¬A∨BAB)↔¬∧¬

125、()(−∀¬xAB∨↔∀¬∧¬xAB)

126、(−∀¬∧¬xAB)(↔∀¬∧∀¬xAxB)

127、()(−∀¬xAB∨↔∀¬∧∀¬xAxB)

128、(−∀¬∧∀¬↔∀¬∨xAxB)xAB()

129、()(−¬∀¬∨xAB↔¬∀¬∧∀¬xAxB)

130、(−¬∀¬∧∀¬xAxB)(↔¬∀¬∨¬∀¬xAxB)

131、()−¬∀¬xAB∨↔¬∀¬∨¬∀¬xAxB

132、()−∃xA∨B↔∃xA∨∃xB(5)

133、

134、()−∃xABAB∧→∧

135、−∧→ABA

136、−→∃AxA

137、−∧→ABB

138、−→∃BxB

139、−∧→∃∧∃ABxAxB

140、()−∃xA∧B→∃xA∧∃xB(6)

141、−→¬A¬A

142、−