邏輯部分習(xí)題課

1、1 邏輯部分知識(shí)結(jié)構(gòu)圖邏輯部分知識(shí)結(jié)構(gòu)圖 2 第一章第一章 習(xí)題課習(xí)題課 l 命題符號(hào)化命題符號(hào)化 l 公式的類型公式的類型 l 真值表及應(yīng)用真值表及應(yīng)用 3 1. 將下列命題符號(hào)化將下列命題符號(hào)化 (1) 由于交通阻塞，他遲到了由于交通阻塞，他遲到了. (2) 如果交通不阻塞，他就不會(huì)遲到如果交通不阻塞，他就不會(huì)遲到. (3) 他沒遲到，所以交通沒阻塞他沒遲到，所以交通沒阻塞. (4) 除非交通阻塞，否則他不會(huì)遲到除非交通阻塞，否則他不會(huì)遲到. (5) 他遲到當(dāng)且僅當(dāng)交通阻塞他遲到當(dāng)且僅當(dāng)交通阻塞. 練習(xí)練習(xí)1 4 答案答案: 設(shè)設(shè) p: 交通阻塞，交通阻塞，q: 他遲到他遲到 (1) pq

2、 (2) pq (3) qp (4) qp (5) qp 練習(xí)練習(xí)1解答解答 5 2. 用真值表判斷下面公式的類型用真值表判斷下面公式的類型 (1) p r(qp) (2) (pq) ( qp) r (3) (pq) (pr) 練習(xí)練習(xí)2 6 練習(xí)練習(xí)2解答解答 (1) p r(qp) 矛盾式矛盾式 p q rqp (qp) p r(qp) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 7 練習(xí)練習(xí)2解答解答 (2) (pq) ( qp) r 永真式

3、永真式 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (pq) ( qp) r qp pq p q r 8 練習(xí)練習(xí)2解答解答 (3) (pq) (pr)非永真式的可滿足式非永真式的可滿足式 p q rpq pr (pq) (pr) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 9 第二章第二章 習(xí)題課習(xí)題

4、課 l等值式與等值演算等值式與等值演算 l基本等值式（基本等值式（1616組，組，2424個(gè)公式）個(gè)公式） l主析取范式與主合取范式主析取范式與主合取范式 10 練習(xí)練習(xí)1: 判斷公式類型判斷公式類型 解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (pq) ( p q) (p q) ( pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式 1 主合取范式主合取范式 1. 判斷下列公式的類型判斷下列公式的類型: : (1) (pq)( qp) 重言式重言式 11 練習(xí)題練習(xí)題1(續(xù)續(xù)) 解解 用等值演算法求

5、公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式 (2) (pq) q 矛盾式矛盾式 12 解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式 (3) (pq)p 練習(xí)練習(xí)1(續(xù)續(xù)) 非重言式的可滿足式非重言式的可滿足式 13 第三章第三章 習(xí)題課習(xí)題課 l理解并記住推理形式結(jié)構(gòu)的兩種形式：理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1 A2 Ak)B 2.

6、 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B l熟練掌握構(gòu)造證明的直接證明法、附加前熟練掌握構(gòu)造證明的直接證明法、附加前 提證明法和歸謬法提證明法和歸謬法 l會(huì)解決實(shí)際中的簡(jiǎn)單推理問題會(huì)解決實(shí)際中的簡(jiǎn)單推理問題 14 練習(xí)練習(xí)1：判斷推理是否正確：判斷推理是否正確 1. 判斷下面推理是否正確判斷下面推理是否正確: (1) 前提：前提： pq, q 結(jié)論：結(jié)論： p 解解 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): ( pq)q)p 方法一：等值演算法方法一：等值演算法 ( pq)q)p (p q)q)p ( pq) qp ( p q) ( q q)p p q 不是重言式不是重言式, , 推理不正

7、確推理不正確 15 練習(xí)練習(xí)1解答解答 方法二：主析取范式法方法二：主析取范式法 ( pq)q)p (p q)q)p p q M2 m0 m1 m3 不是重言式不是重言式, , 推理不正確推理不正確 16 練習(xí)練習(xí)1解答解答 方法三方法三 真值表法真值表法 111 001 110 100 ( pq)q)pqp pq 0 1 1 1 ( pq)q 0 0 1 0 方法四方法四 直接觀察出直接觀察出10是成假賦值是成假賦值 不是重言式不是重言式, , 推理不正確推理不正確 不是重言式不是重言式, , 推理不正確推理不正確 17 練習(xí)練習(xí)1解答解答 用等值演算法用等值演算法 (qr) (pr)(qp

8、) ( q r) ( pr)( qp) (qr) (p r)( pq) (qr) (p r)pq ( p r) ( qr) 1 (2) 前提：前提：qr, pr 結(jié)論：結(jié)論：qp 解解 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： (qr) (pr)(qp) 是重言式是重言式, , 推理正確推理正確 18 練習(xí)練習(xí)2：構(gòu)造證明：構(gòu)造證明 2. 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 只要只要A曾到過受害人房間并且曾到過受害人房間并且11點(diǎn)以前沒離點(diǎn)以前沒離 開開, A就是謀殺嫌犯就是謀殺嫌犯. A曾到過受害者房間曾到過受害者房間. 如果如果A在在11點(diǎn)以前離開點(diǎn)以前離開

9、, 看門人會(huì)看見他看門人會(huì)看見他. 看看 門人沒有看見他門人沒有看見他. 所以所以, A是謀殺嫌犯是謀殺嫌犯. 證明證明： (1) 設(shè)設(shè) p：A曾到過受害者房間，曾到過受害者房間，q：A 11點(diǎn)以前離開，點(diǎn)以前離開， r：A是謀殺嫌犯，是謀殺嫌犯，s：看門人看見：看門人看見A (2) 前提：前提：(p q) r, p, q s, s 結(jié)論：結(jié)論：r 19 練習(xí)練習(xí)2解答解答 (3) 證明：證明： q s 前提引入前提引入 s 前提引入前提引入 q 拒取拒取 p 前提引入前提引入 pq 合取合取 (p q) r 前提引入前提引入 r 假言推理假言推理 20 歸謬法（反證法）歸謬法（反證法） 2.

10、 歸謬法歸謬法 (反證法反證法) 欲證：欲證： 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B 等價(jià)地證明：前提：等價(jià)地證明：前提：A1, A2, , Ak, B 結(jié)論：結(jié)論：0 歸謬歸謬 21 附加前提證明法附加前提證明法 1. 附加前提證明法附加前提證明法 適用于結(jié)論為蘊(yùn)涵式適用于結(jié)論為蘊(yùn)涵式 欲證：欲證： 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：AB 等價(jià)地證明：前提：等價(jià)地證明：前提：A1, A2, , Ak, A 結(jié)論：結(jié)論：B 附加前提附加前提 22 3. 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明. 前提：前提： p q, r q, r

11、s 結(jié)論：結(jié)論： ps 證明證明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段論析取三段論 r q 前提引入前提引入 r 析取三段論析取三段論 rs 前提引入前提引入 s 假言推理假言推理 23 第四章第四章 習(xí)題課習(xí)題課 l 準(zhǔn)確地將給定命題符號(hào)化準(zhǔn)確地將給定命題符號(hào)化 l 深刻理解一階語言的解釋深刻理解一階語言的解釋 l 熟練地給出公式的解釋熟練地給出公式的解釋 l 深刻理解永真式、矛盾式、可滿足式的深刻理解永真式、矛盾式、可滿足式的 概念概念, , 會(huì)判斷簡(jiǎn)單公式的類型會(huì)判斷簡(jiǎn)單公式的類型 24 練習(xí)練習(xí)1 1. 在一階邏輯中將下列命題符號(hào)化在一階邏輯中將下列命題

12、符號(hào)化 (1) 大熊貓都可愛大熊貓都可愛 (2) 有人愛發(fā)脾氣有人愛發(fā)脾氣 (3) 說所有人都愛吃面包是不對(duì)的說所有人都愛吃面包是不對(duì)的 設(shè)設(shè)F(x): x為大熊貓，為大熊貓，G(x): x可愛可愛 x(F(x)G(x) 設(shè)設(shè)F(x): x是人，是人，G(x): x愛發(fā)脾氣愛發(fā)脾氣 x(F(x) G(x) 設(shè)設(shè)F(x): x是人，是人，G(x): x愛吃面包愛吃面包 x(F(x)G(x) 25 練習(xí)練習(xí)1 (4) 沒有不愛吃糖的人沒有不愛吃糖的人 (5) 任何兩個(gè)不同的人都不一樣高任何兩個(gè)不同的人都不一樣高 (6) 不是所有的汽車都比所有的火車快不是所有的汽車都比所有的火車快 設(shè)設(shè)F(x):

13、x是人，是人，G(x): x愛吃糖愛吃糖 x(F(x)G(x) 或或 x(F(x)G(x) 設(shè)設(shè)F(x):x是人是人, H(x,y): x與與y相同相同, L(x,y): x與與y一樣高一樣高 x(F(x)y(F(y)H(x,y)L(x,y) 或或 x y(F(x) F(y)H(x,y)L(x,y) 設(shè)設(shè)F(x):x是汽車是汽車, G(y):y是火車是火車, H(x,y):x比比y快快 x y(F(x) G(y)H(x,y) 或或 x y(F(x) G(y)H(x,y) 26 (2) x y(F(f(x,a), y)F(f(y,a), x) 練習(xí)練習(xí)2 x(2x=x) 假假 2. 給定解釋給定

14、解釋 I 如下如下: (a) 個(gè)體域個(gè)體域D=N (b) =2 (c) (d) 說明下列公式在說明下列公式在 I 下的涵義下的涵義,并討論真值并討論真值 (1) xF(g(x,a), x) yxyxgyxyxf ),(,),( a yxyxF :),( x y(x+2=yy+2=x) 假假 27 練習(xí)練習(xí)2 (3) x y zF(f(x, y), z) (5) xF(f(x, x), g(x, x) (4) x y zF(f(y, z), x) x y z(y+z=x) 假假 x y z(x+y=z) 真真 x(x+x=x x) 真真 (3),(4)說明說明 與與 不能隨意交換不能隨意交換 2

15、8 練習(xí)練習(xí)3 3. 證明下面公式既不是永真式，也不是矛盾式證明下面公式既不是永真式，也不是矛盾式. (1) x(F(x) G(x) (2) x y(F(x) G(y)H(x,y) 解釋解釋1: D1=N, F(x):x是偶數(shù)是偶數(shù), G(x): x是素?cái)?shù)是素?cái)?shù), 真真 解釋解釋2: D2=N, F(x):x是偶數(shù)是偶數(shù), G(x): x是奇數(shù)是奇數(shù), 假假 解釋解釋1: D1=Z, F(x): x是正數(shù)是正數(shù), G(x): x是負(fù)數(shù)是負(fù)數(shù), H(x,y):xy 真真 解釋解釋2: D2=Z, F(x): x是偶數(shù)是偶數(shù), G(x): x是奇數(shù)是奇數(shù), H(x,y):xy 假假 29 練習(xí)練習(xí)

16、4 4. 證明下列公式為永真式證明下列公式為永真式: (1)( xF(x)yG(y)xF(x)yG(y) (2) x(F(x)(F(x) G(x) (AB) A)B的代換實(shí)例的代換實(shí)例 設(shè)設(shè)I是任意的一個(gè)解釋是任意的一個(gè)解釋, 對(duì)每一個(gè)對(duì)每一個(gè)x DI, F(x)(F(x) G(x)恒為真恒為真 30 第五章第五章 習(xí)題課習(xí)題課 l 一階邏輯等值式一階邏輯等值式 基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則 l 前束范式前束范式 l 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) l 自然推理系統(tǒng)自然推理系統(tǒng)N 推理定律、推理規(guī)則推理定律、推理規(guī)則 31 練習(xí)練習(xí)1 1.求下

17、述公式的前束范式求下述公式的前束范式: xF(x)y(G(x,y) H(x,y) 解解 使用換名規(guī)則使用換名規(guī)則 xF(x)y(G(x,y) H(x,y) zF(z)y(G(x,y) H(x,y) z(F(z)y(G(x,y) H(x,y) z y(F(z)(G(x,y) H(x,y) 使用代替規(guī)則使用代替規(guī)則 xF(x)y(G(x,y) H(x,y) xF(x)y(G(z,y) H(z,y) x(F(x)y(G(z,y) H(z,y) x y(F(x)(G(z,y) H(z,y) 32 練習(xí)練習(xí)2 2.構(gòu)造下面推理的證明構(gòu)造下面推理的證明: (1) 前提：前提： x(F(x)G(x), xF

18、(x) 結(jié)論：結(jié)論： xG(x) 證明：證明： x(F(x)G(x) 前提引入前提引入 F(y)G(y) xF(x) 前提引入前提引入 F(y) G(y) 假言推理假言推理 xG(x) + 33 練習(xí)練習(xí)2(續(xù)續(xù)) (2) 前提：前提： x(F(x) G(x), xG(x) 結(jié)論：結(jié)論： xF(x) 證明：用歸謬法證明：用歸謬法 xF(x) 結(jié)論否定引入結(jié)論否定引入 x F(x) 置換置換 xG(x) 前提引入前提引入 x G(x) 置換置換 x(F(x) G(x), 前提引入前提引入 F(c) G(c) F(c) G(c) G(c) 析取三段論析取三段論 G(c) G(c) 合取引入合取引入 34 練習(xí)練習(xí)2(續(xù)續(xù)) (3)前提：前提： x(F(x)G(x), x(G(x)H(x) 結(jié)論：結(jié)論： xF(x)xH(x) 證明證明: 用附加前提法用附加前提法 xF(x) 附加前提引入附加前提引入 F(y) x(F(x)G(x) 前提引入前提引入 F