离散数学课件：2-3-1 一阶逻辑

1、请交作业二P33: 10, 12, 15P35: 19(1)(3)(5), 20, 23P52: 1(1)(4), 2(1),P53: 3(1)(2)(5), 5(1)P54: 7,10,12(1),14(1),15(2)作业讲评一P32: 5(3)(7), 6P33: 7(1)(8), 11n虽然天气很冷,老王还是来了。 p qn合取“ ” ” 在自然语言中可表示为在自然语言中可表示为: :P32. 5(3)p q n除非天下大雨,否则他不乘公共汽车上班 q pn “如果如果 p ，则，则 q ”( pq)的不同表述法很多的不同表述法很多: :n 若若 p，就就 qn 只要只要 p，就就 q

2、n p 仅当仅当 qn 只有只有 q 才才 pn 除非除非 q, 才才 p n 除非除非 q, 否则非否则非 pP32. 5(7)p qP32. 6n设设p=q=0，r=s=1，求下各命题公式的真值 (1) p (q r ) (4) (p (q(r p) (r s) p q p q 0 00 11 01 1 1101 P33. 7 判断命题公式的类型(1) p(p q r) n解1: (真值表法)n解2: (等值式法) 原式 p (p q r) p p q r1n所以,是重言式！ p q r p q r p(p q r)0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1

3、 1 1 0111111 1 11111111P33. 7 判断命题公式的类型(8) (pq) (p q) n解1: (真值表法)n所以，是可满足式！pqpq p q (p q) (pq) (p q)001011010101100101111100P33. 7 判断命题公式的类型(8) (pq) (p q) n解2: (等值式法)原式原式 (pq) (qp) (p q) ( p q) ( q p) (p q) (p q) (q p) ( p q) (p q) p q p 所以，是可满足式！P33. 7 判断命题公式的类型(8) (pq) (p q) n解3: (主析取范式法)原原式式 (pq)

4、 (qp) (p q) ( p q) ( q p) (p q) (p q) (q p) ( p q) m10 m01 m00 (0,1,2) 所以，是可满足式！P33：11n设A、B、C为任意的命题公式。(1) 已知已知 A C = B C，问，问A = B 吗？吗？ 当当C = 0 时，时，A = B 成立；成立； 当当C = 1 时，时，A = B 不一定成立；不一定成立；(2) 已知已知 A C = B C，问，问A = B 吗？吗？ 当当C = 1 时，时，A = B 成立；成立； 当当C = 0 时，时，A = B 不一定成立不一定成立；(3) 已知已知 A = B，问问A = B

5、吗？吗？ 无论无论 A、B取取 0 或或 1 时时，A = B 成立成立。在一阶逻辑中将下面命题符号化n 在数学分析中极限定义为：n任给任给e e 00，必存在一个必存在一个d d 00，对所有，对所有x，若若 0|x-a|d d ， 则必有则必有 |f (x)-b|0) ( d d) (R(d d ) (d d 0) ( x)(R(x)(0(|x-a|d d) (|f (x)- b|00，必存在一个必存在一个d d 00，对所有，对所有x，若若 0|x-a|d d ， 则必有则必有 |f (x)-b|0) ( d d) (R(d d ) (d d 0) ( x)(R(x)(0|x-a|d d

6、) (|f (x)- b|e e)bxfax)(lim ( x)(A(x) B) ( x)A(x) B ( x)(BA(x) B ( x)A(x) ( x)(B A(x) B ( x)A(x) 当当e e、d d R+，x R，则此极限定义可表示为，则此极限定义可表示为( e e)( d d)( x)(0|x-a|d d) (|f (x)- b|e e)第2章 一阶逻辑 2.1 一阶逻辑基本概念、命题符号化2.2 一阶逻辑公式、解释及分类2.3 一阶逻辑等值式、前束范式2.4 一阶逻辑推理理论 2.4 一阶逻辑推理理论 n推理的形式结构有两种： n 第一种第一种 A1 A2 AkB (*)n

7、第二种第二种 前提：前提：A1，A2，Ak 结论：结论： BnA1,A2,Ak,B为一阶逻辑公式为一阶逻辑公式. n若若(*)为永真式为永真式, 则称则称推理正确推理正确, 否则，称否则，称推理不正确推理不正确.真值表真值表法法, ,等值演算法等值演算法主析取范式法主析取范式法构造证明法构造证明法直接直接证明法证明法附加前提证明法附加前提证明法归缪法归缪法的推理规则 前提引入规则前提引入规则 结论引入规则结论引入规则 置换规则置换规则 假言推理规则假言推理规则 (AB) A B 附加规则附加规则 A (A B) 化简规则化简规则 (A B) A 拒取式规则拒取式规则 (AB)B A 假言三段论

8、规则假言三段论规则 (AB) (BC) (AC) 析取三段论规则析取三段论规则 (A B)B A 构造性二难推理规则构造性二难推理规则 (AB) (CD) (A C) (B D) 合取引入规则合取引入规则 A, B A A B B有关量词的推理规则(12) 全称量词消去规则全称量词消去规则 ( - 规则规则) (13) 全称量词引入规则全称量词引入规则 ( + 规则规则)()(cAxxA (14) 存在量词引入规则存在量词引入规则 ( + 规则规则)(15) 存在量词消去规则存在量词消去规则 ( - 规则规则) )()(xxAyA)()(xxAcA )()(cAxxA 构造推理证明举例 例1

9、证明古典推理三段论: “金属都是导电体, 铜是金属，所以铜是导电体。” 令 M(x): x是金属, G(x): x是导电体, a: 铜 前提：前提： x(M(x)G(x)，M(a) 结论：结论：G(a) 证明：证明： M(a) 前提引入前提引入 x(M(x)G(x) 前提引入前提引入 M(a)G(a) - 规则规则 G(a) 假言推理假言推理注意：使用注意：使用 - 规则规则 时，用时，用a取代取代x .构造推理证明举例 例例2 乌鸦都不是白色的乌鸦都不是白色的. 北京鸭是白色的北京鸭是白色的. 因此，北京鸭不是乌鸦因此，北京鸭不是乌鸦. 解：令解：令F(x): x是乌鸦是乌鸦, G(x):

10、x是北京鸭是北京鸭, H(x): x是白色的是白色的前提：前提： x(F(x)H(x)， x(G(x)H(x)结论：结论： x(G(x)F(x)构造推理证明举例 前提：前提： x(F(x)H(x)， x(G(x)H(x)结论：结论： x(G(x)F(x)证明：证明： x(F(x)H(x) 前提引入前提引入 F(y)H(y) - 规则规则 x(G(x)H(x) 前提引入前提引入 G(y)H(y) - 规则规则 H(y)F(y) 置换置换 G(y)F(y) 假言三段论假言三段论 x(G(x)F(x) + 规则规则构造推理证明举例 例例3 构造下述推理证明构造下述推理证明 前提：前提： x(F(x)

11、G(x)， xF(x) 结论：结论： xG(x)证明：证明： xF(x) 前提引入前提引入 x(F(x)G(x) 前提引入前提引入 F(c) - 规则规则 F(c)G(c) - 规则规则 G(c) 假言推理假言推理 xG(x) + 规则规则注意：必须先消注意：必须先消存在量词存在量词! F(c)G(c) - 规则规则 F(c) - 规则规则构造推理证明附加前提证明法例例4 构造下述推理证明构造下述推理证明 前提：前提： x(F(x)G(x) 结论：结论： xF(x)xG(x)证明：证明： xF(x) 附加前提引入附加前提引入 F(y) - 规则规则 x(F(x)G(x) 前提引入前提引入 F(y)G(y) - 规则规则 G(y) 假言推理假言推理 xG(x) + 规则规则构造推理证明举例 例例5 构造下述推理证明构造下述推理证明 前提：前提： xF(x)xG(x) 结论：结论： x(F(x)G(x)证明：证明： xF(x)xG(x) 前提引入前提引入 xF(x)yG(y)