逻辑部分习题课

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

2、1) pr(qp),矛盾式,.,7,练习2解答,(2) (pq) (qp) r,永真式,.,8,练习2解答,(3) (pq) (pr),非永真式的可满足式,.,9,第二章 习题课,等值式与等值演算 基本等值式（16组，24个公式） 主析取范式与主合取范式,.,10,练习1: 判断公式类型,解 用等值演算法求主范式 (pq)(qp) (pq)(qp) (pq)(qp) (pq)(pq)(pq)(pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式 1 主合取范式,1. 判断下列公式的类型: (1) (pq)(qp),重言式,.,11,练习题1(续),解 用等值演算法求公式的主范式

3、(pq)q (pq)q pqq 0 主析取范式 M0 M1 M2 M3 主合取范式,(2) (pq)q,矛盾式,.,12,解 用等值演算法求公式的主范式 (pq)p (pq)p p (pq)(pq) m0 m1 主析取范式 M2 M3 主合取范式,(3) (pq)p,练习1(续),非重言式的可满足式,.,13,第三章 习题课,理解并记住推理形式结构的两种形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 结论：B 熟练掌握构造证明的直接证明法、附加前提证明法和归谬法 会解决实际中的简单推理问题,.,14,练习1：判断推理是否正确,1. 判断下面推理是否正确: (1) 前提：

4、pq, q 结论：p,解 推理的形式结构:,(pq)q)p,方法一：等值演算法 (pq)q)p (pq)q)p (pq)qp (pq)(qq)p pq,不是重言式, 推理不正确,.,15,练习1解答,方法二：主析取范式法 (pq)q)p (pq)q)p pq M2 m0m1m3,不是重言式, 推理不正确,.,16,练习1解答,方法三 真值表法,方法四 直接观察出10是成假赋值,不是重言式, 推理不正确,不是重言式, 推理不正确,.,17,练习1解答,用等值演算法 (qr)(pr)(qp) (qr)(pr)(qp) (qr)(pr)(pq) (qr)(pr)pq (pr)(qr) 1,(2) 前

5、提：qr, pr 结论：qp,解 推理的形式结构：,(qr)(pr)(qp),是重言式, 推理正确,.,18,练习2：构造证明,2. 在自然推理系统P中构造下面推理的证明： 只要A曾到过受害人房间并且11点以前没离开, A就是谋杀嫌犯. A曾到过受害者房间. 如果A在11点以前离开, 看门人会看见他. 看门人没有看见他. 所以, A是谋杀嫌犯.,证明： (1) 设 p：A曾到过受害者房间，q：A 11点以前离开， r：A是谋杀嫌犯，s：看门人看见A (2) 前提：(p q) r, p, q s, s 结论：r,.,19,练习2解答,(3) 证明： q s 前提引入 s 前提引入 q 拒取 p

6、前提引入 pq 合取 (p q) r 前提引入 r 假言推理,.,20,归谬法（反证法）,2. 归谬法 (反证法) 欲证： 前提：A1, A2, , Ak 结论：B 等价地证明：前提：A1, A2, , Ak, B 结论：0,归谬,.,21,附加前提证明法,1. 附加前提证明法 适用于结论为蕴涵式 欲证： 前提：A1, A2, , Ak 结论：AB 等价地证明：前提：A1, A2, , Ak, A 结论：B,附加前提,.,22,3. 在自然推理系统P中构造下面推理的证明. 前提： pq, r q, rs 结论： ps,证明 p 附加前提引入 pq 前提引入 q 析取三段论 r q 前提引入 r

7、 析取三段论 rs 前提引入 s 假言推理,.,23,第四章 习题课,准确地将给定命题符号化 深刻理解一阶语言的解释 熟练地给出公式的解释 深刻理解永真式、矛盾式、可满足式的概念, 会判断简单公式的类型,.,24,练习1,1. 在一阶逻辑中将下列命题符号化 (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),.,25,练习1,(4) 没有不爱吃糖的人,(5) 任何两

8、个不同的人都不一样高,(6) 不是所有的汽车都比所有的火车快,设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) 或 xy(F(x)F(y)H(x,y)L(x,y),设F(x):x是汽车, G(y):y是火车, H(x,y):x比y快 xy(F(x)G(y)H(x,y) 或 xy(F(x)G(y)H(x,y),.,26,(2) xy(F(f(x,a), y)F(f(y,a), x),练习2,x(2x=x) 假,2. 给定解释

9、 I 如下: (a) 个体域D=N (b) =2 (c) (d) 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a), x),xy(x+2=yy+2=x) 假,.,27,练习2,(3) xyzF(f(x, y), z),(5) xF(f(x, x), g(x, x),(4) xyzF(f(y, z), x),xyz(y+z=x) 假,xyz(x+y=z) 真,x(x+x=xx) 真,(3),(4)说明与不能随意交换,.,28,练习3,3. 证明下面公式既不是永真式，也不是矛盾式.,(1) x(F(x)G(x),(2) xy(F(x)G(y)H(x,y),解释1: D1=N,

10、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是奇数, H(x,y):xy 假,.,29,练习4,4. 证明下列公式为永真式: (1)(xF(x)yG(y)xF(x)yG(y),(2) x(F(x)(F(x)G(x),(AB)A)B的代换实例,设I是任意的一个解释, 对每一个xDI, F(x)(F(x)G(x)恒为真,.,30,第五章 习题课,一阶逻辑等值式 基本等值

11、式，置换规则、换名规则、代替规则 前束范式 推理的形式结构 自然推理系统N 推理定律、推理规则,.,31,练习1,1.求下述公式的前束范式: 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) zy(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) xy(F(x)(G(z,y)H(z,y),.,32,练习2,2.构造下面推理的证明: (1) 前提：

12、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) +,.,33,练习2(续),(2) 前提：x(F(x)G(x), xG(x) 结论：xF(x),证明：用归谬法 xF(x) 结论否定引入 xF(x) 置换 xG(x) 前提引入 xG(x) 置换 x(F(x)G(x), 前提引入 F(c) G(c) F(c)G(c) G(c) 析取三段论 G(c)G(c) 合取引入,.,34,练习2(续),(3)前提：x(F(x)G(x), x(G(x)H(x) 结论：xF(x)xH(x

13、),证明: 用附加前提法 xF(x) 附加前提引入 F(y) x(F(x)G(x) 前提引入 F(y)G(y) x(G(x)H(x) 前提引入 G(y)H(y) F(y)H(y) 假言三段论 H(y) 假言推理 xH(x) +,.,35,练习3,3. 在自然推理系统N中，构造推理的证明 人都喜欢吃蔬菜但不是所有的人都喜欢吃鱼所以, 存在喜欢吃蔬菜而不喜欢吃鱼的人,解 令F(x): x是人, G(x): x喜欢吃蔬菜, H(x): x喜欢吃鱼 前提：x(F(x)G(x), x(F(x)H(x) 结论：x(F(x)G(x)H(x),证明：用归谬法 (1) x(F(x)G(x)H(x) 结论否定引入 (2) x(F(x)G(x)H(x) (1)置换