逻辑部分习题课

1、2021/6/161逻辑部分知识结构图逻辑部分知识结构图2021/6/162第一章第一章 习题课习题课l 命题符号化命题符号化l 公式的类型公式的类型l 真值表及应用真值表及应用2021/6/1631. 将下列命题符号化将下列命题符号化 (1) 由于交通阻塞，他迟到了由于交通阻塞，他迟到了. (2) 如果交通不阻塞，他就不会迟到如果交通不阻塞，他就不会迟到. (3) 他没迟到，所以交通没阻塞他没迟到，所以交通没阻塞. (4) 除非交通阻塞，否则他不会迟到除非交通阻塞，否则他不会迟到. (5) 他迟到当且仅当交通阻塞他迟到当且仅当交通阻塞.练习练习12021/6/164答案答案: 设设 p: 交

2、通阻塞，交通阻塞，q: 他迟到他迟到 (1) pq (2) pq (3) qp (4) qp (5) qp练习练习1解答解答2021/6/1652. 用真值表判断下面公式的类型用真值表判断下面公式的类型 (1) p r(qp) (2) (pq) ( qp) r (3) (pq) (pr)练习练习22021/6/166练习练习2解答解答(1) p r(qp) 矛盾式矛盾式p q rqp (qp) p r(qp)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11001111 00110000 00000000 2021/6/167练习练习2解答解答(2) (pq

3、) ( qp) r 永真式永真式11111111 11110011 11110011 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq) ( qp) r qp pq p q r2021/6/168练习练习2解答解答(3) (pq) (pr)非永真式的可满足式非永真式的可满足式p q rpq pr (pq) (pr)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11110011 11110101 11111001 2021/6/169第二章第二章 习题课习题课l等值式与等值演算等值式与等值演算l基本等值式（基本等值式（1

4、616组，组，2424个公式）个公式）l主析取范式与主合取范式主析取范式与主合取范式2021/6/1610练习练习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)重言式重言式2021/6/1611练习题练习题1(续续)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)

5、q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式2021/6/1612解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p练习练习1(续续)非重言式的可满足式非重言式的可满足式2021/6/1613第三章第三章 习题课习题课l理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, ,

6、Ak 结论：结论：Bl熟练掌握构造证明的直接证明法、附加前熟练掌握构造证明的直接证明法、附加前提证明法和归谬法提证明法和归谬法l会解决实际中的简单推理问题会解决实际中的简单推理问题2021/6/1614练习练习1：判断推理是否正确：判断推理是否正确1. 判断下面推理是否正确判断下面推理是否正确: (1) 前提：前提： pq, q 结论：结论： p 解解 推理的形式结构推理的形式结构: ( pq)q)p 方法一：等值演算法方法一：等值演算法 ( pq)q)p (p q)q)p ( pq) qp ( p q) ( q q)p p q不是重言式不是重言式, , 推理不正确推理不正确2021/6/16

7、15练习练习1解答解答方法二：主析取范式法方法二：主析取范式法 ( pq)q)p (p q)q)p p q M2 m0 m1 m3不是重言式不是重言式, , 推理不正确推理不正确2021/6/1616练习练习1解答解答方法三方法三 真值表法真值表法111001110100( pq)q)pqp pq 0 1 1 1( pq)q 0 0 1 0方法四方法四 直接观察出直接观察出10是成假赋值是成假赋值不是重言式不是重言式, , 推理不正确推理不正确不是重言式不是重言式, , 推理不正确推理不正确2021/6/1617练习练习1解答解答用等值演算法用等值演算法 (qr) (pr)(qp) ( q r

8、) ( pr)( qp) (qr) (p r)( pq) (qr) (p r)pq( p r) ( qr)1(2) 前提：前提：qr, pr 结论：结论：qp 解解 推理的形式结构：推理的形式结构：(qr) (pr)(qp) 是重言式是重言式, , 推理正确推理正确2021/6/1618练习练习2：构造证明：构造证明2. 在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明： 只要只要A曾到过受害人房间并且曾到过受害人房间并且11点以前没离点以前没离开开, A就是谋杀嫌犯就是谋杀嫌犯. A曾到过受害者房间曾到过受害者房间. 如果如果A在在11点以前离开点以前离开, 看门人会

9、看见他看门人会看见他. 看看门人没有看见他门人没有看见他. 所以所以, A是谋杀嫌犯是谋杀嫌犯.证明证明： (1) 设设 p：A曾到过受害者房间，曾到过受害者房间，q：A 11点以前离开，点以前离开， r：A是谋杀嫌犯，是谋杀嫌犯，s：看门人看见：看门人看见A (2) 前提：前提：(p q) r, p, q s, s 结论：结论：r2021/6/1619练习练习2解答解答(3) 证明：证明： q s 前提引入前提引入 s 前提引入前提引入 q 拒取拒取 p 前提引入前提引入 pq 合取合取 (p q) r 前提引入前提引入 r 假言推理假言推理 2021/6/1620归谬法（反证法）归谬法（反

10、证法）2. 归谬法归谬法 (反证法反证法)欲证：欲证： 前提：前提：A1, A2, , Ak 结论：结论：B等价地证明：前提：等价地证明：前提：A1, A2, , Ak, B 结论：结论：0归谬归谬2021/6/1621附加前提证明法附加前提证明法1. 附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证：欲证： 前提：前提：A1, A2, , Ak 结论：结论：AB等价地证明：前提：等价地证明：前提：A1, A2, , Ak, A 结论：结论：B附加前提附加前提2021/6/16223. 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明.前提：前提：

11、p q, r q, rs 结论：结论： ps 证明证明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段论析取三段论 r q 前提引入前提引入 r 析取三段论析取三段论 rs 前提引入前提引入 s 假言推理假言推理2021/6/1623第四章第四章 习题课习题课l 准确地将给定命题符号化准确地将给定命题符号化l 深刻理解一阶语言的解释深刻理解一阶语言的解释l 熟练地给出公式的解释熟练地给出公式的解释l 深刻理解永真式、矛盾式、可满足式的深刻理解永真式、矛盾式、可满足式的概念概念, , 会判断简单公式的类型会判断简单公式的类型2021/6/1624练习练习11. 在一阶逻辑中

12、将下列命题符号化在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱大熊猫都可爱(2) 有人爱发脾气有人爱发脾气(3) 说所有人都爱吃面包是不对的说所有人都爱吃面包是不对的设设F(x): x为大熊猫，为大熊猫，G(x): x可爱可爱 x(F(x)G(x) 设设F(x): x是人，是人，G(x): x爱发脾气爱发脾气 x(F(x) G(x)设设F(x): x是人，是人，G(x): x爱吃面包爱吃面包 x(F(x)G(x)2021/6/1625练习练习1 (4) 没有不爱吃糖的人没有不爱吃糖的人 (5) 任何两个不同的人都不一样高任何两个不同的人都不一样高 (6) 不是所有的汽车都比所有的火车快不是

13、所有的汽车都比所有的火车快设设F(x): x是人，是人，G(x): x爱吃糖爱吃糖x(F(x)G(x) 或或 x(F(x)G(x)设设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)设设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)2021/6/1626(2) x y(F(f(x,a), y)F(f(y,a), x)练习

14、练习2 x(2x=x) 假假2. 给定解释给定解释 I 如下如下: (a) 个体域个体域D=N (b) =2 (c) (d) 说明下列公式在说明下列公式在 I 下的涵义下的涵义,并讨论真值并讨论真值 (1) xF(g(x,a), x)yxyxgyxyxf ),(,),(ayxyxF :),( x y(x+2=yy+2=x) 假假2021/6/1627练习练习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

15、)说明说明 与与 不能随意交换不能随意交换2021/6/1628练习练习33. 证明下面公式既不是永真式，也不是矛盾式证明下面公式既不是永真式，也不是矛盾式.(1) x(F(x) G(x)(2) x y(F(x) G(y)H(x,y)解释解释1: D1=N, F(x):x是偶数是偶数, G(x): x是素数是素数, 真真解释解释2: D2=N, F(x):x是偶数是偶数, G(x): x是奇数是奇数, 假假解释解释1: D1=Z, F(x): x是正数是正数, G(x): x是负数是负数, H(x,y):xy 真真解释解释2: D2=Z, F(x): x是偶数是偶数, G(x): x是奇数是奇

16、数, H(x,y):xy 假假2021/6/1629练习练习44. 证明下列公式为永真式证明下列公式为永真式: (1)( xF(x)yG(y)xF(x)yG(y)(2) x(F(x)(F(x) G(x)(AB) A)B的代换实例的代换实例设设I是任意的一个解释是任意的一个解释, 对每一个对每一个x DI, F(x)(F(x) G(x)恒为真恒为真2021/6/1630第五章第五章 习题课习题课l 一阶逻辑等值式一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则基本等值式，置换规则、换名规则、代替规则l 前束范式前束范式l 推理的形式结构推理的形式结构l 自然推理系统自然推理系统N 推理定

17、律、推理规则推理定律、推理规则2021/6/1631练习练习11.求下述公式的前束范式求下述公式的前束范式: xF(x)y(G(x,y) H(x,y)解解 使用换名规则使用换名规则 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) 使用代替规则使用代替规则 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) 2021/6/1632练习练习22.构造下面

18、推理的证明构造下面推理的证明:(1) 前提：前提： x(F(x)G(x), xF(x) 结论：结论： xG(x)证明：证明： x(F(x)G(x) 前提引入前提引入 F(y)G(y) xF(x) 前提引入前提引入 F(y) G(y) 假言推理假言推理 xG(x) + 2021/6/1633练习练习2(续续)(2) 前提：前提： x(F(x) G(x), xG(x) 结论：结论： xF(x) 证明：用归谬法证明：用归谬法 xF(x) 结论否定引入结论否定引入 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) 合取引入合取引入 2021/6/1634练习练习2(续续)(3)前提：前提： x(F(x)G(x), x(G(x)H(x) 结论：结论： xF(x)xH(x)证明证明: 用附加前提法用附加前提法 xF(x) 附加前提引入附加前提引入 F(y) x(F(x)G(x) 前提引入前提引入 F(y)G(y) x(G(x)H(x)