2.数理逻辑课件

1、1,主要内容: 推理的形式结构 推理的正确与错误 判断推理正确的方法 推理定律 自然推理系统P 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法,第三章 命题逻辑的推理理论,2,数理逻辑的主要任务是借助于数学的方法来研究推理的逻辑。 推理是从前题推出结论的思维过程，前提是已知的命题公式，结论是从前题出发应用推理规则推出的命题公式。,推理理论,3,3.1 推理的形式结构,定义3.1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值， A1A2 Ak 为假，或当A1A2Ak为真时，B也为真， 则称由前提A1, A2, , Ak推出结论B的推理是有

2、效的或正确 的, 并称B是有效结论.,定理3.1 由命题公式A1, A2, , Ak 推B的推理正确当且仅当 A1A2AkB为重言式 注意: 推理正确不能保证结论一定正确,4,推理的形式结构,2. A1A2AkB 若推理正确, 记为A1 A2 Ak B 3. 前提： A1, A2, , Ak 结论： B 判断推理是否正确的方法: 真值表法 等值演算法 主析取范式法,推理的形式结构 1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B,5,推理实例,例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则

3、明天是5号. 明天是5号. 所以, 今天是1号.,解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构:,(pq)pq,用等值演算法 (pq)pq (pq)p)q pqq 1 由定理3.1可知推理正确,6,推理实例,(2) 推理的形式结构:,(pq)qp,用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,7,例2,判断下列推理是否正确：如果天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。,解这类推理问题，应先将命题符号化，然后写出前提、结论和推理的形式结构，最后

4、进行判断。 设p：天气凉快；q：小王去游泳。 前提：pq, p。结论：q。 推理的形式结构： (pq )p)q 。 下面分别用三种方法来判断该蕴含式是否为重言式。,8,（1）真值表法,真值表的最后一列全为1，因而（*）是重言式，所以推理正确。,9,（2）等值演算法,(pq)p)q (pq)p)q (p q)p)q (p q)pq (pq)(pq) 1,该蕴含式是重言式，所以推理正确。,10,(pq)p)q (pq)p)q (pq)p)q (pq)pq (pq)(p(qq)(q(pp) (pq)(pq)(pq)(qp) (qp) (pq)(pq)(pq)(pq) m3m1m0m2,（3）主析取范

5、式法,该蕴含式的主析取范式中含有4个极小项，因而是重言式。,11,为了更好地判断推理的正确性，引入构造证明的方法。 在数理逻辑中，证明是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论。其中有些规则建立在推理定律（重言蕴涵式）的基础之上。 重要的9条推理定律：附加、化简、假言推理、拒取式、析取三段论、假言三段论、等价三段论、构造性二难、 破坏性二难。 除此之外，每个等值式均产生两条推理定律。,12,推理定律重言蕴涵式,1. A (AB) 附加律 2. (AB) A 化简律 3. (AB)A B 假言推理 4. (AB)B A 拒取式 5

6、. (AB)B A 析取三段论 6. (AB)(BC) (AC) 假言三段论 7. (AB)(BC) (AC) 等价三段论 8. (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式) 9. (AB)(CD)( BD) (AC) 破坏性二难 每个等值式可产生两个推理定律 如, 由AA可产生 AA 和 AA,13,3.2 自然推理系统P,定义3.2 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4

7、) 推理规则集，记作 R(I). 记I=, 其中是 I 的 形式语言系统, 是 I 的形式演算系统. 自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理,14,自然推理系统P,定义3.3 自然推理系统 P 定义如下: 1. 字母表 (1) 命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：, , , , (3) 括号与逗号：(, ), ， 2. 合式公式（同前） 3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则,15,推理规则,(4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则,(

8、5) 附加规则 (7) 拒取式规则 (9) 析取三段论规则,16,推理规则,(10) 构造性二难推理规则 (11) 破坏性二难推理规则 (12) 合取引入规则,17,在自然推理系统P中构造证明,设前提A1, A2, Ak,结论B及公式序列C1, C2, Cl. 如果每 一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理 规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2, Ak推 出B的证明 例3 构造下面推理的证明： 若明天是星期一或星期三，我明天就有课. 若我明天有 课，今天必备课. 我今天没备课. 所以，明天不是星期一、 也不是星期三. 解 (1) 设命题并符号

9、化 设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课,18,直接证明法,(2) 写出证明的形式结构 前提：(pq)r, rs, s 结论：pq (3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换,19,例4,写出对应下面推理的证明： 若数a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数。所以a是无理数。,解：将简单命题符号化： p：a是实数； q：a是有理数； r：a是无理数； s：a能表示成分数。 前提：p(qr), sq, ps 。 结论：r。,推理理论,20,

10、证明： ps 前提引入 p 化简 s 化简 p(qr) 前提引入 qr 假言推理 sq 前提引入 q 假言推理 r 析取三段论,前提：p(qr), sq, ps 。 结论：r。,21,在使用构造证明法来进行推理时，常常采用一些技巧，下面介绍两种： 1、附加前提证明法 2、归谬法,22,附加前提证明法,附加前提证明法 适用于结论为蕴涵式 欲证 前提：A1, A2, , Ak 结论：CB 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,23,附加前提证明法实例,例5 构造下面推理

11、的证明 2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pq, pr, rs 结论：sq,24,附加前提证明法实例,(3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论,前提：pq, pr, rs 结论：sq,25,例6,如果小张去看电影，则当小王去看电影时，小李也去。小赵不去看电影或小张去看电影。小王去看电影。所以当小赵去看电影时

12、，小李也去。,解：将简单命题符号化： p：小张去看电影； q：小王去看电影； r：小李去看电影； s：小赵去看电影。 前提：p(qr), sp, q 。 结论：sr。,26,证明： sp 前提引入 s 附加前提引入 p 析取三段论 p(qr) 前提引入 qr 假言推理 q 前提引入 r 假言推理,前提：p(qr), sp, q 。 结论：sr。,27,归谬法（反证法）,归谬法 (反证法) 欲证 前提：A1, A2, , Ak 结论：B 做法 在前提中加入B，推出矛盾. 理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,28,归谬法实例,例7

13、前提：(pq)r, rs, s, p 结论：q 证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取,29,例8,用归谬法构造下面推理的证明： 前提：p(rs)q), p, s 。 结论：q 。,30,证明： p(rs)q) 前提引入 p 前提引入 (rs)q 假言推理 (q) 否定结论引入 q 置换 rs 拒取式 s 化简 s 前提引入 ss 合取 为矛盾式，根据归谬法说明推理正确。,前提：p(rs)q), p, s 。 结论：q 。,31,第三章 习题课,主要内容 推理的

14、形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P 构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法),32,基本要求,理解并记住推理形式结构的两种形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等） 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法 会解决实际中的简单推理问题,33,练习1：判断推理是否正确,1. 判断下面推理是否正确: (1) 前提：pq, q 结论：p,解 推理的形式结构:,

15、(pq)qp,方法一：等值演算法 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq,易知10是成假赋值，不是重言式，所以推理不正确.,34,练习1解答,方法二：主析取范式法， (pq)qp (pq)q)p pq M2 m0m1m3 未含m2, 不是重言式, 推理不正确.,35,练习1解答,方法三 真值表法 不是重言式, 推理不正确,方法四 直接观察出10是成假赋值,36,练习1解答,用等值演算法 (qr)(pr)(qp) (qr)(pr)(qp) (qr)(pr)(qp) (qp)(qr)(rp)(qp) (qp)(qr)(rp)(qp) 1 推理正确,(2) 前提：qr,

16、 pr 结论：qp,解 推理的形式结构：,(qr)(pr)(qp),37,练习2：构造证明,2. 在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩.,证明： (1) 设 p：今天是周六，q：到颐和园玩， r：到圆明园玩，s：颐和园游人太多 t：到动物园玩 (2) 前提：p(qr), sq, p, s 结论：rt,38,练习2解答,(3) 证明： p(qr) 前提引入 p 前提引入 qr 假言推理 sq 前提引入 s 前提引入 q 假言推理 r 析取三段论 rt 附

17、加,前提：p(qr), sq, p, s 结论：rt,39,作业： 习题三（52页） 9, 12, 14(5), 15(1), 16(2),40,第四章 一阶逻辑基本概念,问题的提出：一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。这样有一些逻辑问题无法解决。 所有的人都是要死的； 苏格拉底是人； 所以，苏格拉底是要死的。 令P：所有的人都是要死的； Q：苏格拉底是人； R：苏格拉底是要死的。 则原问题符号化为：PQ R。,41,主要内容 一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑命题符号化 一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式,

18、42,4.1 一阶逻辑命题符号化,个体词所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域(论域)个体变项的取值范围 有限个体域，如 a, b, c, 1, 2 无限个体域，如 N, Z, R, 全总个体域由宇宙间一切事物组成,43,谓词,定义：用以刻画客体的性质或者客体之间关系的即是谓词。用一个大写英文字母后边有括号，括号内是若干个客体变元表示谓词，如果括号内有n个客体变元，称该谓词为n元谓词。 例如 S(x):表示x是大学生。 一元谓词 G(x,y)：表示 xy。 二元谓词 B(x,y,z)：表示x在y

19、与z之间。三元谓词 一般地 P(x1,x2,xn) 是n元谓词。,44,n（n1）元谓词 一元谓词(n=1)表示性质 多元谓词(n2)表示事物之间的关系 如, L(x,y)：x与 y 有关系 L，L(x,y)：xy， 0元谓词不含个体变项的谓词, 即命题常项 或命题变项 谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质F,45,量词,量词表示数量的词 全称量词: 表示所有的. x : 对个体域中所有的x 如, xF(x)表示个体域中所有的x具有性质F xyG(x,y)表示个体域中所有的x和y有关系G 存在量词: 表示存在, 有一个. x : 个体域中有一个x 如, xF(x)表示个体域中有一个x具有性质F xyG(x,y)表示个体域中存在x和y有关系G xyG(x,y)表示对个体域中每一个x都存在一个y使得 x