离散数学基础：数理逻辑导论(3)

解答：

(1)令Γ={q→p,q?s,s?t,t∧r}，验证Γ p∧q的证明序列为：

(1)Γ s?t//前提引入

(2)Γ t→s//(1)等价消除

(3)Γ q?s//前提引入

(4)Γ s→q//(3)等价消除

(5)Γ t→q//(2),(4)传递规则

(6)Γ t∧r//前提引入

(7)Γ t//(6)合取消除

(8)Γ q//(5),(7)蕴涵消除

(9)Γ q→p//前提引入

(10)Γ t→p//(5),(9)传递规则

(11)Γ p//(7),(10)蕴涵消除

(12)Γ p∧q//(8),(11)合取引入

14

(2)令Γ={(p∨q)→(r∧s),(s∨t)→u}，验证Γ p→u的证明序列如下：

(1)Γ,p p//前提引入

(2)Γ,p p∨q//(1)析取引入

(3)Γ,p (p∨q)→(r∧s)//前提引入

(4)Γ,p r∧s//(2),(3)蕴涵消除

(5)Γ,p s//(4)合取消除

(6)Γ,p s∨t//(5)析取引入

(7)Γ,p (s∨t)→u//前提引入

(8)Γ,p u//(6),(7)蕴涵消除

(9)Γ p→u//(8)蕴涵引入(3)令Γ={p→?q,?r∨q,r∧?s}，验证Γ ?p的证明序列如下：

(1)Γ,p p//前提引入

(2)Γ,p p→?q//前提引入

(3)Γ,p ?q//(1),(2)蕴涵消除

(4)Γ,p ?r∨q//前提引入

(5)Γ,p ?r//(3),(4)析取三段论

(6)Γ,p r∧?s//前提引入

(7)Γ,p r//(6)合取消除

(8)Γ ?p//(5),(7)归谬律

(4)令Γ={p→(q→r),r→?r,s→p,t→q}，验证Γ s→?t的证明如下：

(1)Γ,s,t s//前提引入

(2)Γ,s,t s→p//前提引入

(3)Γ,s,t p//(1),(2)蕴涵消除

(4)Γ,s,t p→(q→r)//前提引入

(5)Γ,s,t q→r//(3),(4)蕴涵消除

(6)Γ,s,t t//前提引入

(7)Γ,s,t t→q//前提引入

(8)Γ,s,t q//(6),(7)蕴涵消除

(9)Γ,s,t r//(5),(8)蕴涵消除

(10)Γ,s,t r→?r//前提引入

(11)Γ,s,t ?r//(9),(10)蕴涵消除

(12)Γ,s ?t//(9),(11)归谬律

(13)Γ s→?t//(12)蕴涵引入

15

作业3.5在自然推理系统中验证下述推理的有效性：

(1)只要张三曾到过受害者房间并且11点以前没有离开，则张三犯了谋杀罪。张三曾到过受害者房间。如果张三在11点以前离开，则看门人会看见他。看门人没有看见他。所以，张三犯了谋杀罪。

(2)在大城市球赛中，如果北京队第三，那么上海队第二意味者天津队第四。沈阳队不是第一或北京队第三。上海队第二。因此，如果沈阳队第一，则天津队第四。

(3)如果法官是公正严明的，则就应当宣判张大侠有罪，除非现有的证据尚不充分。如果法官是公正严明的，则不会不认定现有的证据是充分的，除非这些证据有假。证据都没有假。因此，如果法官是公正严明的，就应当宣判张大侠有最。

(1).通读句子，我们可发现有如下原子命题：

p:张三曾到过受害者房间q:张三11点以前离开

r:张三犯了谋杀罪s:看门人看见张三

而句子“只要张三曾到过受害者房间并且11点以前没有离开，则张三犯了谋杀罪”符号化为：

(p∧?q)→r

而句子“如果张三在11点以前离开，则看门人会看见他”符号化为q→s。因此我们要验证的推理是：

(p∧?q)→r,p,q→s,?s r

验证上述推理的证明序列如下：令Γ={(p∧q)→r,p,q→s,?s}，

(1)Γ ?s//前提引入

(2)Γ q→s//前提引入

(3)Γ ?q//(1),(2)假言易位

(4)Γ p//前提引入

(5)Γ p∧?q//(3),(4)合取引入

(6)Γ (p∧?q)→r//前提引入

(7)Γ r//(5),(6)蕴涵消除

(2).通读句子，我们可发现有如下原子命题：

p:北京队第三q:上海队第二

r:天津队第四s:沈阳队第一

而句子“如果北京队第三，那么上海队第二意味者天津队第四”符号化为：

p→(q→r)

句子“沈阳队不是第一或北京队第三”符号化为：

?s∨p

16

而推理结论“如果沈阳队第一，则天津队第四”符号化为：s→r，因此要验证的推理是：

p→(q→r),?s∨p,q s→r

验证上述推理的证明序列如下：令Γ={p→(q→r),?s∨p,q}，

(1)Γ,s s//前提引入

(2)Γ,s ?s∨p//前提引入

(3)Γ,s p//(1),(2)析取三段论

(4)Γ,s p→(q→r)//前提引入

(5)Γ,s q→r//(3),(4)蕴涵消除

(6)Γ,s q//前提引入

(7)Γ,s r//(5),(6)蕴涵消除

(8)Γ s→r//(7)蕴涵引入

(3).通读句子，我们可发现有如下原子命题：

p:法官是公正严明的q:法官应当宣判张大侠有罪

r:现有的证据是充分的s:证据有假

而句子“如果法官是公正严明的，则就应当宣判张大侠有罪，除非现有的证据尚不充分”的含义是“如果法官是公正严明的，则只有在现有的证据尚不充分时，法官才不会宣判张大侠有罪”，也即“如果法官是公正严明的，则法官不宣判张大侠有罪意味着现有的证据尚不充分”，从而应该符号化为：

p→(?q→?r)

类似的，句子“如果法官是公正严明的，则不会不认定现有的证据是充分的，除非这些证据有假”的含义是“如果法官是公正严明的，则只有当这些证据有假时，法官才不会认定现有的证据是充分的”，也即“如果法官是公正严明的，则它不认定现有的证据是充分的，意味着这些证据有假”，因此应该符号化为：

p→(?r→s)

句子“证明都没有假”符号化为?s，而“如果法官是公正严明的，就应当宣判张大侠有罪”则应符号化为：

p→q

从而我们要验证的推理是：

p→(?q→?r),p→(?r→s),?s p→q

17

验证上述推理的证明序列如下：令Γ={p→(?q→?r),p→(?r→s),?s}，

(1)Γ,p p→(?r→s)//前提引入

(2)Γ,p p//前提引入

(3)Γ,p ?r→s//(1),(2)蕴涵消除

(4)Γ,p ?s//前提引入

(5)Γ,p r//(3),(4)假言易位

(6)Γ,p p→(?q→?r)//前提引入

(7)Γ,p ?q→?r//(2),(6)蕴涵消除

(8)Γ,p q//(5),(7)假言易位

(9)Γ p→q//(8)蕴涵引入

作业3.6我们在自然推理系统中验证一些基本等值式：

1.p∨q q∨p

(1)p∨q,p p//前提引入

(2)p∨q,p q∨p//(1)析取引入

(3)p∨q,q q//前提引入

(4)p∨q,q q∨p//(3)析取引入

(5)p∨q p∨q//前提引入

(6)p∨q q∨p//(2),(4),(5)析取消除

2.(p∨q)∨r p∨(q∨r)

(1)(p∨q)∨r,p∨q,p p//前提引入

(2)(p∨q)∨r,p∨q,p p∨(q∨r)//(1)析取引入

(3)(p∨q)∨r,p∨q,q q//前提引入

(4)(p∨q)∨r,p∨q,q q∨r//(3)析取引入

(5)(p∨q)∨r,p∨q,q p∨(q∨r)//(4)析取引入

(6)(p∨q)∨r,p∨q p∨q//前提引入

(7)(p∨q)∨r,p∨q p∨(q∨r)//(2),(5),(6)析取消除

(8)(p∨q)∨r,r r//前提引入

(9)(p∨q)∨r,r q∨r//(8)析取引入

(10)(p∨q)∨r,r p∨(q∨r)//(9)析取引入

(11)(p∨q)∨r (p∨q)∨r//前提引入

(12)(p∨q)∨r p∨(q∨r)//(7),(10),(11)析取消除

18

3.p∧(q∨r) (p∧q)∨(p∧r)

(1)p∧(q∨r),q p∧(q∨r)//前提引入

(2)p∧(q∨r),q p//(1)合取消除

(3)p∧(q∨r),q q//前提引入

(4)p∧(q∨r),q p∧q//(2),(3)合取引入

(5)p∧(q∨r),q (p∧q)∨(p∧r)//(4)析取引入

(6)p∧(q∨r),r p∧(q∨r)//前提引入

(7)p∧(q∨r),r p//(6)合取消除

(8)p∧(q∨r),r r//前提引入

(9)p∧(q∨r),r p∧r//(7),(8)合取引入

(10)p∧(q∨r),r (p∧q)∨(p∧r)//(9)析取引入

(11)p∧(q∨r) p∧(q∨r)//前提引入

(12)p∧(q∨r) q∨r//(11)合取消除

(13)(p∨q)∨r (p∧q)∨(p∧r)//(5),(10),(12)析取消除4.p∨(p∧q) p

(1)p∨(p∧q),p∧q p∧q//前提引入

(2)p∨(p∧q),p∧q p//(1)合取消除

(3)p∨(p∧q),p p//前提引入

(4)p∨(p∧q) p∨(p∧q)//前提引入

(5)p∨(p∧q) p//(2),(3),(4)析取消除

5.?(p∧q) (?p∨?q)

(1)?(p∧q),?(?p∨?q),?p ?p//前提引入

(2)?(p∧q),?(?p∨?q),?p ?p∨?q//(1)析取引入

(3)?(p∧q),?(?p∨?q),?p ?(?p∨?q)//前提引入

(4)?(p∧q),?(?p∨?q) p//(2),(3)否定消除

(5)?(p∧q),?(?p∨?q),?q ?q//前提引入

(6)?(p∧q),?(?p∨?q),?q ?p∨?q//(5)析取引入

(7)?(p∧q),?(?p∨?q),?q ?(?p∨?q)//前提引入

(8)?(p∧q),?(?p∨?q) q//(6),(7)否定消除

(9)?(p∧q),?(?p∨?q) p∧q//(4),(8)合取引入

(10)?(p∧q),?(?p∨?q) ?(p∧q)//前提引入

(11)?(p∧q) ?p∨?q//(9),(10)否定消除

19

6.(?p∨?q) ?(p∧q)

(1)(?p∨?q),??(p∧q),?(p∧q) ??(p∧q)//前提引入

(2)(?p∨?q),??(p∧q),?(p∧q) ?(p∧q)//前提引入

(3)(?p∨?q),??(p∧q) p∧q//(1),(2)否定消除

(4)(?p∨?q),??(p∧q),?q p∧q//(3)弱化规则

(5)(?p∨?q),??(p∧q),?q,??p p∧q//(4)弱化规则

(6)(?p∨?q),??(p∧q),?q,??p q//(5)合取消除

(7)(?p∨?q),??(p∧q),?q,??p ?q//前提引入

(8)(?p∨?q),??(p∧q),?q ?p//(6),(7)否定消除

(9)(?p∨?q),??(p∧q),?p ?p//前提引入

(10)(?p∨?q),??(p∧q) ?p∨?q//前提引入

(11)(?p∨?q),??(p∧q) ?p//(8),(9),(10)析取消除

(12)(?p∨?q),??(p∧q) p//(3)合取消除

(13)(?p∨?q) ?(p∧q)//(11),(12)否定消除7.?(p∨q) (?p∧?q)

(1)?(p∨q),??p,?p ?p//前提引入

(2)?(p∨q),??p,?p ??p//前提引入

(3)?(p∨q),??p p//(1),(2)否定消除

(4)?(p∨q),??p p∨q//(3)析取引入

(5)?(p∨q),??p ?(p∨q)//前提引入

(6)?(p∨q) ?p//(4),(5)否定消除

(7)?(p∨q),??q,?q ?q//前提引入

(8)?(p∨q),??q,?q ??q//前提引入

(9)?(p∨q),??q q//(7),(8)否定消除

(10)?(p∨q),??q p∨q//(9)析取引入

(11)?(p∨q),??q ?(p∨q)//前提引入

(12)?(p∨q) ?q//(10),(11)否定消除

(13)?(p∨q) ?p∧?q//(6),(12)合取引入

20

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新外语学习离散数学基础：数理逻辑导论(3)全文阅读和word下载服务。