离散数学 杨圣洪等著 第一章习题三解答.pdf

《离散数学 杨圣洪等著 第一章习题三解答.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、利用定义1.6.1，并利用等值演算或真值表，证明如下各推理式，要注明每步的理由。1、(A→B)∧¬B⇒¬A(1)¬B为真前提条件(2)A→B为真前提条件(3)¬B→¬A为真因为¬B→¬A⇔A→B为真(4)¬A为真(¬B→¬A)∧¬B⇒¬A假言推理2、(A∨B)∧¬B⇒A(1)¬B为真前提条件(2)(A∨B)为真前提条件(3)¬B→A为真因为¬B→A⇔A∨B为真(4)A为真(¬B→A)∧¬B⇒A假言推理3、(A↔B)∧(B↔C)⇒(A↔C)(1)(A↔B)为真前提条件(2)(A→B)∧(B→A)为真因(A↔B)⇔(A→B)∧(B→A)(3)(A→B)为真由(2)及合取的定

2、义(4)(B→A)为真由(2)及合取的定义(5)(B↔C)为真前提条件(6)(B→C)∧(C→B)为真因(B↔C)⇔(B→C)∧(C→B)(7)(B→C)为真由(6)及合取的定义(8)(C→B)为真由(6)及合取的定义(9)(C→A)为真由(8)(4)及传递律(10)(A→C)为真由(3)(7)及传递律(11)(A↔C)为真由(9)(10)及双条件的定义(4)(A→B)∧(¬A→B)⇒B((A→B)∧(¬A→B))→B⇔¬((¬A∨B)∧(¬¬A∨B))∨B⇔¬((¬A∨B)∧(A∨B))∨B⇔((A∧¬B)∨(¬A∧¬B))∨B⇔((A∨¬A)∧¬B))∨B⇔(1∧¬B)

3、)∨B⇔¬B∨B⇔1故为永真式(A→B)∧(¬A→B)⇒B2、采用定义1.6.2方法证明如下推理式，并注明每步理由，可采用CP规则、反证法。1、¬p∨q，¬q∨r，r→s，p⇒s(1)p(2)¬p∨q(3)q(1)(2)∨的定义，或(1)(2)分离原则(4)¬q∨r(5)r(4)(5)∨的定义，或(4)(5)分离原则(6)r→s(7)s(5)(6)分离原则2、p→(q→r)，q→(r→s)⇒(p∧q)→s(1)(p∧q)附加条件(2)p(1)与∧的定义附加条件(3)q(2)与∧的定义附加条件(4)p→(q→r)(5)q→r(2)与(4)分离原则(6)r(3)与(5)分离原则

4、(7)q→(r→s)(8)r→s(3)与(7)分离原则(9)s(6)与(8)分离原则3、p→(q→r)，p，q⇒r∨s(1)p为真前提条件(2)p→(q→r)为真前提条件(3)(q→r)为真(1)(2)假言推理(4)q为真前提条件(5)r为真(4)(3)假言推理(6)r∨s为真(5)与析取的定义4、p→q，¬(p∧r)，r⇒¬p(1)¬(p∧r)为真前提条件(2)¬p∨¬r为真(1)与德摩律(3)r→¬p为真与(2)等值(4)r为真前提条件(5)¬p为真(4)(3)假言推理反证法(1)¬¬p为真反证法即假设结论为真(2)p为真否定的否定为真(3)¬(p∧r)为真前提条件(4

5、)¬p∨¬r为真(3)与德摩律(5)p→¬r为真与(4)等值(6)¬r为真(2)(5)假言推理(7)r为真前提条件显然(6)(7)矛盾，故假设错了，即“¬¬p为真”错了，所以¬p为真5、p→q⇒p→(p∧q)(1)p为真附加前提(2)p→q为真前提条件(3)q为真(1)(2)假言推理(4)(p∧q)为真(1)(3)及合取的性质6、q→p，q↔s，s↔t，t↔r,r⇒p∧q(1)t↔r为真前提条件(2)(t→r)∧(r→t)为真与(1)等值(3)(r→t)为真(2)及合取的定义(4)r为真前提条件(5)t为真(3)(4)假言推理(6)s↔t为真前提条件(7)(s→t)∧(t→

6、s)为真与(6)等值(8)(t→s)为真(7)及合取的定义(9)s为真(5)(8)与假言推理(10)q↔s为真前提条件(11)(q→s)∧(s→q)为真与(10)等值(12)(s→q)为真(11)与合取的定义(13)q为真(9)(12)与假言推理(14)q→p为真前提条件(15)p为真(13)(14)假言推理(16)p∧q为真(13)(15)及合取的定义7、p→r，q→s，p∧q⇒r∧s(1)p∧q为真前提条件(2)p为真(1)与合取的性质(3)q为真(1)与合取的性制(4)p→r为真前提条件(5)r为真(2)(4)假言推理(6)q→s为真前提条件(7)s为真(3)(6)及

7、假言推理(8)r∧s为真(5)(7)及合取的性质8、¬p∨r，¬q∨s，p∧q⇒t→r∧s(1)t为真附件前提(2)p∧q为真前提条件(3)p为真(2)与合取的定义(4)q为真(2)与合取的定义(5)¬p∨r为真前提条件(6)p→r为真与(5)等值(7)r为真(6)(3)与假言推理(8)¬q∨s为真前提条件(9)q→s为真与(8)等值(10)s为真(9)(4)与假言推理(11)r∧s为真(7)(10)与合取的性质9、p→(q→r)，s→p，q⇒s→r(1)s为真附加前提(2)s→p为真前提条件(3)p为真(1)(2