当前位置：文档之家 › 第三章：命题逻辑的推理理论

第三章：命题逻辑的推理理论

  • 格式：docx
  • 大小：19.31 KB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

离散数学课件03命题逻辑的推理理论

离散数学课件03命题逻辑的推理理论

((┐p∧┐q)∨p) ∨ q
((┐p∨p )∧(┐q∨p)) ∨ q
(┐q∨p) ∨ q 1
精选课件ppt
由定理 3.1可知， 推理正确。
15
推理定律--重言蕴含式
(1) A (A∨B)
附加律
(2) (A∧B) A
化简律
(3) (A→B)∧A B
假言推理
(4) (A→B)∧┐B ┐A
拒取式
(5) (A∨B)∧┐B A
析取三段论
(6) (A→B) ∧ (B→C) (A→C)
假言三段论
(7) (AB) ∧ (BC) (A C)
等价三段论
(8) (A→B)∧(C→D)∧(A∨C) (B∨D) (A→B)∧(┐A→B)∧(A∨┐A) B
构造性二难 构造性二难
(特殊形式)
(9)(A→B)∧(C→D)∧(┐B∨┐精D选)课件pp(t ┐A∨┐C) 破坏性二难16
只要不出现(3)中的情况，推理就是正确的，因而判断 推理是否正确，就是判断是否会出现(3)中的情况。
推理正确，并不能保证结论B一定为真。
精选课件ppt
8
例题
例3.1 判断下列推理是否正确。（真值表法）
(1) {p,p→q}├ q (2) {p,q→p}├ q
正确 不正确
p q p(p→q) q p(q→p)
推理是指从前提出发推出结论的思维过程。
前提是已知命题公式集合。
结论是从前提出发应用推理规则推出的命题公式。
证明是描述推理正确或错误的过程。
要研究推理，首先应该明确什么样的推理是有效的或 正确的。
精选课件ppt
4
命题逻辑的推理理论
概念
描述问题 的句子

2.数理逻辑12

2.数理逻辑12
∨(﹁q∧﹁p) (p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(p∧﹁q) m3∨m1∨m0∨m2
该蕴含式的主析取范式中含精有品课4件个极小项，因而是重言式。10
为了更好地判断推理的正确性，引入构造 证明的方法。
在数理逻辑中，证明是一个描述推理过程 的命题公式序列，其中的每个命题公式或者是已 知的前提，或者是由某些前提应用推理规则得到 的结论。其中有些规则建立在推理定律（重言蕴 涵式）的基础之上。
记I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I)>是 I 的 形式语言系统, <AX(I),R(I)> 是 I 的形式演算系统.
自然推理系统: 无公理, 即AX(I)=
公理推理系统 推出的结论是系统中的重言式, 称作定理
精品课件
13
自然推理系统P
定义3.3 自然推理系统 P 定义如下:
第三章 命题逻辑的推理理论
主要内容: 推理的形式结构 推理的正确与错误 判断推理正确的方法 推理定律
自然推理系统P
形式系统的定义与分类
自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法
精品课件
1
推理理论 数理逻辑的主要任务是借助于数 学的方法来研究推理的逻辑。
推理是从前题推出结论的思维过
((p→﹁q)∧p)→﹁q
((﹁p∨﹁q)∧p)→﹁q
﹁((﹁p ∨﹁q)∧p)∨﹁q
﹁(﹁p ∨﹁q)∨﹁p∨﹁q
﹁(﹁p∨﹁q)∨(﹁p∨﹁
q)
1
该蕴含式是重言精式品课，件 所以推理正确。
9
（3）主析取范式法
((p→﹁q)∧p)→﹁q ((﹁p∨﹁q)∧p)→﹁q ﹁((﹁p∨﹁q)∧p)∨﹁q ﹁(﹁p∨﹁q)∨﹁p∨﹁q (p∧q)∨(﹁p∧(q∨﹁q))∨(﹁q∧(p∨﹁p)) (p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(﹁q∧p)

x本科数理逻辑-命题3-15

x本科数理逻辑-命题3-15

4) 几种连接词相互的关系
（1) ┓p ⇔ ┓(p∧ p ) ⇔ p↑p ┓p ⇔ ┓(p∨ p ) ⇔ p↓p (2） p∧ q ⇔ ┓┓(p∧ q ) ⇔ ┓( p↑q ) ⇔ ( p↑q ) ↑ ( p↑q ) （3）(p∨ q) ⇔ ┓┓(p∨ q) ⇔ ┓(p ↓ q) ⇔ (p↓q)↓(p↓q) （4）p∧ q ⇔ ┓┓(p∧ q ) ⇔ ┓(┓ p∨┓q ) ⇔ (┓p ↓┓q ) （5）(p∨ q) ⇔ ┓┓(p∨ q) ⇔ ┓(┓p ∧┓ q) ⇔ (p↓p) ↑(q↓q) （6） (a) ┐(P ↑ Q ) ⇔ ┐P ↓ ┐Q (b) ┐(P ↓ Q ) ⇔ ┐P ↑ ┐Q
注：1）由前提集合A1，A2，A3，…，Am 推出B的推理是否是有效的与前提 集合各命题公式的次序无关。 2）由推理形式 A1∧A2∧…∧Am → B 取得真值的几种情况： a) A1∧A2∧…∧Am 真值为F ， B为F b) A1∧A2∧…∧Am 真值为F ， B为T c) A1∧A2∧…∧Am 真值为T ， B为F d) A1∧A2∧…∧Am 真值为T ， B为T 当取得a)、b)、d) 三种情况均称为有效推理 3）由推理有效的定义可得出： 推理有效（推理正确）并不能保证结论B一定为真 推理有效（推理正确）与结论B的真值无关 推理有效（推理正确）是指推理过程是合乎逻辑的 （即：只要前提集合是真的，那么结论一定是真的） 3．推理形式结构的另外等价形式： 定理：由前提集合A1，A2，A3，…，Am 推出B的推理是有效的或是正确的 当且仅当 (A1∧A2∧…∧Am) → B为重言式（永真式） 从开始的例来验证：
二、联接词的完备集 1、定义 设S是一个联结词集合，如果任何n(n≥1)元公式都可以由仅含S 中的联结词构成的等值公式表示，则称S是联结词完备集． 可验证 s0={ ┓、∨、 ∧、 →、↔ } 2、冗余的联接词 如果某个联接词可用功能完备集中的其他连接词所表示，则称该连 接词为冗余的连接词 s0 中的→、↔ 均为冗余的连接词 s1= { ┓、 ∨ 、 ∧ } 是否还含有冗余的连接词？ s2= { ┓、 ∨ } 将公式 ( p → ┓q ) ∧ r 在s2下表示 3、极小功能完备集：若联结词完备集中不含冗余的连接词 s3 = { ┓、 ∧ } 将 ( p → r ) ∧ q 在s3下表示 s4= { ┓、→ } 将 ( p ↔ r ) ∧ ┓ q 在s4下 均为极小功能完备集 将公式（p ↔ r) ∨( s ∧ p)在极小功能完备集s5= { ┓、→ }中表示 特别地 s5 = { ↑ } s6 = { ↓ } 均为联接词的极小功能完备集 将(p ∧ q) ∨ ┓r 在s5 下

离散数学作业

离散数学作业

-离散数学 专业班级 学号 姓名 第一章 命题逻辑的基本概念一、单项选择题1．下列语句中不是命题的有（ ）.A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗？D.我要努力学习。

2. 下列语句是真命题为( )．A. 1+2=5当且仅当2是偶数B. 如果1+2=3，则2是奇数C. 如果1+2=5，则2是奇数D. 你上网了吗？3. 设命题公式)(r q p∧→⌝,则使公式取真值为1的p ，q ，r 赋值分别是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 4. 命题公式q q p →∨)(为 ( )(A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式5. 设p:我将去市里,q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为为( )q p q p q p p q ⌝∨⌝↔→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ）A. Q P ⌝→ ；B. Q P →⌝；C. P Q ⌝∧⌝ ；D. )(Q P ∧⌝二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化（1）中国有四大发明。

（2）2是有理数。

（3）“请进！”（4）刘红和魏新是同学。

（5）a+b（6）如果买不到飞机票，我哪儿也不去。

（8）侈而惰者贫，而力而俭者富。

（韩非：《韩非子∙显学》）（9）火星上有生命。

（10）这朵玫瑰花多美丽啊！二、将下列命题符号化，其中p:2<1,q:3<2（1）只要2<1，就有3<2。

（2）如果2<1，则3≥2。

（3）只有2<1，才有3≥2。

（4）除非2<1，才有3≥2。

（5）除非2<1，否则3≥2。

（6）2<1仅当3<2。

离散数学专业班级学号姓名三、将下列命题符号化(1)小丽只能从筐里拿一个苹果或一个梨。

离散数学第1讲

离散数学第1讲

30
第一章 命题逻辑基本概念——第1讲
以上5种最基本、最常用、最重要的联结词可以组 成一个集合{‫,∨,∧ ,ר‬,}，成为一个联 结词集，其运算的优先级为：‫,∨,∧,ר‬,, 对于同一级者，先出现者先运算。参见课本 第9页，基本复合命题的真值表。 例1.7：令p：北京比天津人口多。 q：2＋2＝4。 r：乌鸦是白色的。 求下列符合命题的真值： (1)((‫ר‬p∧q)∨(p∧q))r (2)(q∨r)(p‫ר‬r)
1) 这朵花多好看呀！ 不是命题，感叹句 2) 请你关上门！ 3) 全体立正！
不是命题，祈使句 不是命，祈使句
4) 明天是否开大会？ 不是命题，疑问句
5) 你听懂了吗？
不是命题，疑问句
11
第一章 命题逻辑基本概念——第1讲
例：凡是悖论都不是命题。
1) 我正在说谎。
不是命题，悖论
由真推出假，又由假推出真的陈述句称为悖论， 都不是命题。
命题的分类
简单/原子命题：由不能再分解为更简单的 陈述句的陈述句构成。 如上例中的命题。 复合命题：由简单命题通过联结词联结而 成的陈述句。 如下例。
16
第一章 命题逻辑基本概念——第1讲
例：将下面这段陈述句中所出现的原子命题符号化，并指出 它们的真值，然后再写出这段陈述。 2 是有理数是不对的；2是偶素数；2或4是素数；如果2 是素数，则3也是素数；2是素数当且仅当3也是素数。 解：这段陈述句中出现5个原子命题，将它们分别符号化为： p: 是有理数； q：2是素数； r：2是偶数； 2 s：3是素数； t：4是素数。 将原子命题的符号代入上面陈述中： 非p； q并且r； 如果q，则s； q当且仅当s。（半形式 化的语言）。 形式语言：完全由符号所构成的语言。

3 命题逻辑的推理理论

3 命题逻辑的推理理论

（7）拒取式规则
AB B A
（8） 假言三段论规则
AB BC AC
（9）析取三段论规则
AB B A
（10）构造性二难推理规则
AB CD AC BD
（11）破坏性二难推理规则
AB CD BD AC
（12） 合取引入规则
A B AB
证明方法： ◦ 直接证明法 ◦ 附加前提法 ◦ 归谬法（或称反证法）
（2） 联结词符号： ┐， ， ， ， （3） 括号与逗号：( )，， 2. 合式公式（同合取联接词定义）
3. 推理规则
（1）前提引入规则 在证明的任何步骤上都可以引入前提。
（2）结论引入规则 在证明的任何步骤上所得到的结论都可以作为后继证明的前提。
（3）置换规则 在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公
1、用不同的方法验证下面推理是否正确。对于正确的推理还 要在P系统中给出证明。 （1） 前提：pq, q
结论：p （2） 前提：qr, pr
结论：qp
（1）不正确。 验证答案，只需证明(pq)qp不是重言式。 方法一 等值演算
(pq)qp ((pq)q)p (pq)qp ((pq)(qq))p pq 易知10是成假赋值，故(pq)qp不是重言式，所以推理不正确。
数理逻辑
命题逻辑 一阶逻辑
命题和联结 词
命题变项
复合命题 公式
真值表 等值式与等
值演算 公式类型
范式
实际应用
析取范式 合取范式
主析取范式 主合取范式
根据下列真语句，请判断是谁谋害了张先生？ (1)A、B、C三人中至少有一人。 (2)如果张先生生前未饮过麻醉剂，那不是C。 (3)如果张先生曾饮过麻醉剂，那不是A。 (4)如果是A谋害的，那么B也参加了。 (5)如果作案在落雨前，则是A谋害的。 (6)如果作案不在落雨前，张先生临死前搏斗过。 (7)张先生临死前搏斗过，就不是B谋害的。 (8)经过法医解剖化验，张先生死前曾饮过麻醉剂。

3第三章 命题逻辑的推理理论


从语言角度, 推理分为语义和语法两种。 从语言角度, 推理分为语义和语法两种。 语义(semantics)推理注重内涵的正确性 也就是从真 语义(semantics)推理注重内涵的正确性, 也就是从真 推理注重内涵的正确性, 要推出真的结论来, 的前提出发要推出真的结论来 推理过程考虑得少, 的前提出发要推出真的结论来, 推理过程考虑得少,关 心的是结论的正确性。 心的是结论的正确性。 语法推理则注重形式上的有效, 注重推理过程是否符 语法推理则注重形式上的有效, 注重推理过程是否符 则注重形式上的有效 合某些事先规定的逻辑规则, 结论是严格遵循规则 合某些事先规定的逻辑规则, 若结论是严格遵循规则 有效的 得到的, 那便是有效 得到的, 那便是有效的。 数理逻辑主要采用语法推理, 数理逻辑主要采用语法推理, 它关心的是结论的有效 不关心前提的实际真值, 性，而不关心前提的实际真值, 当然语法推理作为一 种推理方法, 种推理方法, 它必须能反映客观事物中真实存在的逻 辑关系, 语法推理必须保证语义上的正确性 必须保证语义上的正确性。 辑关系, 即 语法推理必须保证语义上的正确性。
3、2.1节给出的24个等值式中的每个都可以 2.1节给出的 个等值式中的每个都可以 节给出的24 派生出两条推理定律。 派生出两条推理定律。 例如：双重否定律 A⇔¬¬A ⇔¬¬A 例如： 可以产生两条推理定律 A⇒¬¬A ¬¬A ¬¬A ¬¬A ⇒A
§3.2 自然推理系统P 自然推理系统P
由上一节知识可知，可以利用真值表法、等值演算法 由上一节知识可知，可以利用真值表法、 真值表法 和主析取范式法三种方法来判断推理是否正确。 和主析取范式法三种方法来判断推理是否正确。 三种方法来判断推理是否正确 但是，当推理中包含的命题变项较多时，以上三种 命题变项较多时 但是，当推理中包含的命题变项较多 方法的演算量太大。因此对于由前提A1, A2,…,Ak推 方法的演算量太大。因此对于由前提A B的正确推理应给出严谨的证明。 正确推理应给出严谨的证明。 证明是一个描述推理过程的命题公式序列， 证明是一个描述推理过程的命题公式序列，其中的每 是一个描述推理过程的命题公式序列 个公式是已知前提或者是由某些前提应用推理规则得 个公式是已知前提或者是由某些前提应用推理规则得 已知前提或者是 到的结论。 到的结论。

命题逻辑的推理理论

精品课件
精品课件
实例
例 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所 以明天是5号.
解 设 p：今天是1号，q：明天是5号. 证明的形式结构为: (p®q)Ùp®q
证明（用等值演算法）
(p®q)Ùp®q Û Ø((ØpÚq)Ùp)Úq Û ØpÚØqÚq Û 1
得证推理正确
A Þ (AÚB)
附加律
(AÙB) Þ A
化简律
(A®B)ÙA Þ B
假言推理
(A®B)ÙØB Þ ØA
拒取式
(AÚB)ÙØB Þ A
论
析取三段
(A®B)Ù(B®C) Þ (A®C)
假言三段论
(A«B)Ù(B«C) Þ (A«C)
等价三段论
(A®B)Ù(C®D)Ù(AÚC) Þ (BÚD)
难
构造性二
推理的形式结构。
精品课件
说明（2）
设任一A1组，赋A2值，a…1a，2…Aka，n （B中ai＝共0出或现1n，个命i＝题1变，项2，，…对n于），
前提和结论的取值情况有以下四种：
（1） A1ÙA2Ù…ÙAk 为0，B为0； （2） A1ÙA2Ù…ÙAk 为0，B为1； （3） A1ÙA2Ù…ÙAk 为1，B为0； （4） A1ÙA2Ù…ÙAk 为1，B为1。
AB
(12) 合取引入规则
CD
课件
构造证明——直接证明法
例3.3 在自然推理系统P中构造下面推理的证明；
（1） 前提：p Ú q， q ® r， p ® s ， Ø s 结论：r Ù （p Ú q）
（2）前提： Ø p Ú q， r Ú Ø q ，r ® s 结论：p ® s
精品课件

逻辑学导论第三章


14
也可以用否定词、等值把矛盾关系表述如下：
◦ （1）SAP↔¬SOP ◦ （2）SEP↔¬SIP ◦ （3）SIP↔¬SEP ◦ （4）SOP↔¬SAP
15
差等关系
◦ 亦称“从属关系”，指A与I、E与O之间的关系。我们可 以把它概括为：如果全称命题真，则相应的特称命题真； 如果特称命题假，则相应的全称命题假；如果全称命题假， 则相应的特称命题真假不定；如果特称命题真，则相应的 全称命题真假不定。
SAP 等 关 系 差 等 关 系 关 系 SIP 下反对关系 SOP 矛 盾 盾 矛 关 反对关系 系 差 等 关 关 系 系 差 SEP 差 等 关
差 a （某个 S） 是P 差
系 系 a（某个 S） 不是 P
等
等
关
19
直言命题中词项的周延性
◦ 在直言命题中，若断定了一个词项的全部外延，则称它是 周延的，否则是不周延的。由此可知，直言命题中词项的 周延性有下述特点：
41
以上五条三段论规则是基本的，用它们就足以把有 效的三段论与无效的三段论区分开来。为明确和方 便起见，有时还从它们证明、推导出一些规则，例 如：
◦ （6）两个特称前提不能得结论。 ◦ （7）如果两个前提中有一个特称，结论必然特称。
42
根据三段论的一般规则，还可以证明有关三段论的 一些定理，例如：
◦ 定理 一个结论全称的正确三段论，其中项不能周延两次。
43
三段论的特殊规则
第一格规则：
◦ （1）小前提必须肯定。 ◦ （2）大前提必须全称。
44
第二格规则：
◦ （1）两个前提必须有一个否定。 ◦ （2）大前提必须全称。
45
第三格规则：
◦ （1）小前提必须肯定。 ◦ （2）结论必须特称。

第三章推理的形式结构


充分性: 若蕴涵式(A1∧A2∧…∧Ak)→B为重言式，则对于任何赋 值此蕴涵式均为真，因而不会出现前件为真后件为假 的情况，即在任何赋值下，或者A1∧A2∧…∧Ak为假， 或者A1∧A2∧…∧Ak和B同时为真，这正符合定义3.1中 推理正确的定义。 由此定理知，推理形式： 前提：A1,A2,…,Ak 结论：B 是有效的当且仅当(A1∧A2∧…∧Ak)→B为重言式。
以引入前提。
（2） 结论引入规则：在证明的任何步骤上所得 到的结论都可以作为后继证明的前提。 （3） 置换规则：在证明的任何步骤上，命题公 式中的子公式都可以用与之等值的公式置换，得到 公式序列中的又一个公式。
（4） 假言推理规则
（5） 附加规则：
（6） 化简规则：
（7） 拒取式规则：
（8） 假言三段论规则：
A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，
或者A1∧A2 ∧…∧Ak为假，或者当A1∧A2 ∧…∧Ak为 真时，B也为真，则称由前提A1,A2,…,Ak推出B的推 理是有效的或正确的，并称B是有效结论。 其中，前提是一个有限的公式集合，记为Г。 将由Г推B的推理记为Г├ B。 若推理是正确的，则记为Г B，否则记为Г B。
（9） 析取三段论规则：
（10） 构造性二难推理：
（11） 破坏性二难推理规则：
（12） 合取引入规则：
P中的证明就是由一组P中公式作为前提，利用P 中的规则，推出结论。当然此结论也为P中公式。
例3.3 在自然推理系统P中构造下面推理的证明： (1)前提：p∨q,q→r,p→s,┐s 结论：r∧(p∨q) 证明： ① p→s ② ┐s 前提引入
结论的否定 前提引入 前提引入 ②③析取三段 前提引人 ④⑤拒取式 ⑥置换 前提引入 ⑦⑧析取三段
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第三章：命题逻辑的推理理论3.1推理形式结构何为推理？何为证明？例子：（1）若A?B且C?D，则A?C?B?D（2）若今天是星期一，则明天是星期二（3）若A?C?B?D，则A?B且C?D推理——从前提出发推出结论的思维过程上例中，（1），（2）是正确的推理，而（3）是错误的推理证明——描述推理正确或错误的过程3.1推理形式结构推理定律推理定律——重言蕴涵式重要的推理定律：A?(A?B)附加律(A?B)?A化简律例1：如果谁骄傲自满，那么他就要落后；小张骄傲自满，所以，小张必定要落后(A?B)?A?B假言推理例2：如果谁得了肺炎，他就一定要发烧；小李没发烧，所以，小李没患肺炎(A?B)??B??A拒取式3.1推理形式结构例3：如果降落的物体不受外力的影响，那么，它不会改变降落的方向；这个物体受到了外力的影响，所以，它会改变降落的方向例4：如果赵某是走私犯，那么，他应受法律制裁；经查明，赵某确实受到了法律制裁，所以，赵某是走私犯3.1推理形式结构例5：我要么选择汤要么选择色拉；我不选择汤。

所以，我选择色拉(A?B)??B?A析取三段论例6：如果我不能起床，则我不能上班。

如果我不能上班，则我不能得到报酬。

所以，如果我不能起床，则我不能得到报酬(A?B)?(B?C)?(A?C)假言三段论(A?B)?(B?C)?(A?C)等价三段论3.1推理形式结构例7：东方朔偷饮了汉武帝求得的据说饮了能够不死的酒，汉武帝要杀他，他说：“如果这酒真能使人不死，那么你就杀不死我；如果这酒不能使人不死(你能杀得死我)，那么它就没有什么用处（不必杀我）；这酒或者能使人不死，或者不能使人不死；所以你或者杀不死我，或者不必杀我。

”(A?B)?(C?D)?(A?C)?(B?D)构造性二难(A?B)?(?A?B)?B构造性二难（特殊形式）3.1推理形式结构例8：Ifitrains,wewillstayinside.Ifitissunny,wewillgoforawalk.Eitherwewillnotstayinside,orwewillnotgoforawalk.Therefore,eitheritwillnotrain,oritwillnotbesunny.(A?B)(C?D)?(?B??D)?(?A??C)破坏性二难3.1推理形式结构普罗泰戈拉收了一名学生叫欧提勒士。

普氏与他签订了这样一份合同：前者向后者传授辩论技巧，教他帮人打官司；后者入学时交一半学费，另一半学费则在他毕业后帮人打官司赢了之后再交。

时光荏苒，欧氏从普氏那里毕业了。

但他总不帮人打官司，普氏于是就总得不到那另一半学费。

普氏为了要那另一半学费，他去与欧氏打官司，并打着这样的如意算盘：如果欧氏打赢了这场官司，按照合同的规定，他应该给我另一半学费。

如果欧氏打输了这场官司，按照法庭的裁决，他应该给我另一半学费。

欧氏或者打赢这场官司，或者打输这场官司。

总之，他应该付给我另一半学费。

但欧氏却对普氏说：如果这场官司我打赢了，按照法庭的裁决，我不应该给您另一半学费。

如果这场官司我打输了，按照合同的规定，我不应该给您另一半学费。

我或者打赢这场官司，或者打输这场官司。

总之，我不应该付另一半学费究竟谁的说法对呢？3.2自然推理系统P证明:p,q,p?q?r?r3.2自然推理系统P例：考虑下述论证如果这里有球赛，则通行是困难的如果他们按时到达，则通行是不困难的他们按时到达了问：得到什么结论？3.2自然推理系统P证明((p?(q?s))?(?r?p)?q)?(r?s)3.2自然推理系统P证明((r??q)?(r∨s)?(s??q)?(p?q))??p练习1：判断推理是否正确(2)前提：q?r,p??r结论：q??p练习2：构造证明(1)前提：p?q 结论：p?(p?q)(2)前提：p?(q?r),s?p,q结论：s?r(3)前提：p??q, r?q,r??s结论：?p作业14（4），（6）15（2）16（2）1718（2）3.2自然推理系统P例：考虑下述论证如果这里有球赛，则通行是困难的如果他们按时到达，则通行是不困难的他们按时到达了问：得到什么结论？设p:这里有球赛q:通行是困难的r:他们按时到达p?qr??qr??p3.2自然推理系统P证明前提：p?q，r??q，r结论：?p解：rr??q?qp?q?p前提引入前提引入假言推理前提引入拒取式3.2自然推理系统P证明cd,c?r,d?s?r?s解：c?d?c?dd?s?c?scr?r??c?r?sr?s前提引入前提引入假言三段论前提引入置换规则置换规则假言三段论置换规则3.2自然推理系统P构造证明的方法附加前提证明法归谬法3.2自然推理系统P附加前提证明法对形如(A1?…?Ak)?(A?B)的证明转化为：A1,…,Ak,A?B3.2自然推理系统P证明((p?(q?s))?(?r?p)?q)?(r?s)解：r?r?pr?ppp?(q?s)q?sqs前提引入前提引入假言推理前提引入置换规则假言推理假言推理前提引入3.2自然推理系统P归谬法对形如(A1?…?Ak)?B的证明转化为：A1?…?Ak??B为矛盾式3.2自然推理系统P证明((r??q)?(r∨s)?(s??q)?(p?q))??p解：pp?q qs??qq??s?sr∨srr??q?q第三章习题课主要内容推理的形式结构判断推理是否正确的方法真值表法等值演算法主析取范式法推理定律自然推理系统P构造推理证明的方法直接证明法附加前提证明法归谬法(反证法)基本要求理解并记住推理形式结构的两种形式：1.(A1?A2?…?Ak)?B2.前提：A1,A2,…,Ak结论：B熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记P系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证明法和归谬法会解决实际中的简单推理问题练习1：判断推理是否正确1.判断下面推理是否正确:(1)前提：?p?q,?q结论：?p解推理的形式结构:(?p?q)??q??p方法一：等值演算法(?p?q)??q??p??((p?q)??q)??p?(?pq)?q??p?((?p?q)?(?q?q))??p??p?q易知10是成假赋值，不是重言式，所以推理不正确.练习1解答方法二：主析取范式法，(?p?q)??q??p??((p?q)??q)??pp?q?M2?m0?m1?m3未含m2,不是重言式,推理不正确.练习1解答方法三真值表法不是重言式,推理不正确111001110100(?p?q)??q??pqp?p?q0111(?p?q)??q0010方法四直接观察出10是成假赋值练习1解答用等值演算法(q?r)?(p??r)?(q??p)?((?q?r)?(?p??r))?(?q??p)??((q??r)?(p?r))?(?q??p)??((q?p)?(q?r)?(?r?p))?(?q??p)?((q?p)?(q?r)?(?r?p))?(?q??p)?1推理正确(2)前提：q?r,p??r结论：q??p解推理的形式结构：(q?r)?(p??r)?(q??p)练习3：实际问题3.在系统P中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩.如果颐和园游人太多，就不去颐和园.今天是周六，并且颐和园游人太多.所以,我们去圆明园或动物园玩.证明：(1)设p：今天是周六，q：到颐和园玩，r：到圆明园玩，s：颐和园游人太多t：到动物园玩(2)前提：p?(q?r),s??q,p,s结论：r?t练习3解答(3)证明：①p?(q?r)前提引入②p前提引入③q?r①②假言推理④s??q前提引入⑤s前提引入⑥?q④⑤假言推理⑦r③⑥析取三段论⑧r?t⑦附加第三章:命题逻辑的推理理论主要内容推理的形式结构自然推理系统P本章与其他各章的联系本章是第五章的特殊情况和先行准备第一节：推理的形式结构3.1推理形式结构逻辑(语义)蕴涵：给定A1,…,Ak和B对任意赋值v:如果v(Ai)=T,则v(B)=T或者存在Aj，使得v(Aj)=F称由前提A1,…,Ak推出结论B的推理是有效的B为有效结论符号：{A1,…,Ak}?B讨论蕴涵跟蕴涵式的关系？注意:推理正确不能保证结论一定正确例子{p,p?q}?q{p,q?p}?qpqp?(p?q)qp?(q?p)qFFFFFFFTFTFTTFFFTFTTTTTT3.1推理形式结构定理：{A1,…,Ak}?B当且仅当A1?…?Ak?B为重言式证明必要性：任意v,不会出现A1?…?Ak为真且B为假的情况，所以v(A1?…?Ak?B)=T充分性：任意v,v(A1?…?Ak?B)=T则或者：A1?…?Ak和B同时为T或者：A1?…?Ak为假所以{A1,…,Ak}?B3.1推理形式结构蕴涵元符号：?A1?…?Ak?B代表{A1,…,Ak}?B推理的形式结构前提：A1,…,Ak结论：B推理的形式结构：A1?…?Ak?B3.1推理形式结构判断推理是否正确方法真值表法等值演算法主析取范式法3.1推理形式结构推理实例例判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以,明天是5号.(2)若今天是1号，则明天是5号.明天是5号.所以,今天是1号.解设p：今天是1号，q：明天是5号.(1)推理的形式结构:(p?q)?p?q用等值演算法(p?q)?p?q??((?p?q)?p)?qp??q?q?1由定理3.1可知推理正确推理实例(2)推理的形式结构:(p?q)q?p用主析取范式法(p?q)?q?p?(?p?q)?q?p((?p?q)?q)?p??q?p?(?p??q)?(p??q)?(p??q)?(p?q)?m0?m2?m3结果不含m1,故01是成假赋值，所以推理不正确推理定律A?(A?B)(A?B)?A(A?B)?A?B(A?B)??B?A(A?B)??B?A(A?B)?(B?C)?(A?C)(A?B)?(BC)?(A?C)(A?B)?(C?D)?(A?C)?(B?D)(A?B)?(A?B)?B(A?B)?(C?D)?(?B??D)?(?A??C)附加律破坏性二难构造性二难（特殊形式）构造性二难等价三段论假言三段论析取三段论拒取式假言推理化简律3.1推理形式结构证明：(A?B)?(B?C)?(A?C)((A?B)?(B?C))?(A?C)((?A?B)?(?B?C))?(A?C)?((?A?B)?(?B?C))?(A?C)((A??B)?(B??C))?(A?C)((A??B)?(B??C))?(?A?C)((A??B)??A)?((B??C)?C)(?B??A)?(B?C)13.1推理形式结构第二节：自然推理系统P3.2自然推理系统P自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑推理规则推出结论的过程为什么要自然演绎(NaturalDeduction)？给出验证的推理过程需要引入证明的概念一个描述推理过程的命题公式序列，其中的每个公式或者是已知前提，或者是由前面的公式应用到推理规则得到的结论自然演绎模拟人类的推理A1?…?Ak?B3.2自然推理系统P定义3.2一个形式系统I由下面四个部分组成：(1)非空的字母表，记作A(I).(2)A(I)中符号构造的合式公式集，记作E(I).(3)E(I)中一些特殊的公式组成的公理集，记作AX(I).(4)推理规则集，记作R(I).记I=,其中是I的形式语言系统,是I的形式演算系统.自然推理系统:无公理,即AX(I)=?公理推理系统推出的结论是系统中的重言式,称作定理自然推理系统P定义3.3自然推理系统P定义如下:1.字母表(1)命题变项符号：p,q,r,…,pi,qi,ri,…(2)联结词符号：?,?,?,?,?(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则3.2自然推理系统P假言推理规则A?BA结论：B(A?B)?A?BAllmenaremortalSocratesisamanThereforeSocratesismortal3.2自然推理系统P附加规则A结论：A?BA?(A?B)3.2自然推理系统P化简规则A?B结论：A合取引入规则AB结论：A?B(A?B)?A3.2自然推理系统P证明:p,q,p?q?r?rpqpqp?q?rr推理过程可以写成证明树3.2自然推理系统P拒取式规则A?BB结论：?A假言三段式规则A?BB?C结论：A?C(A?B)?B??A(A?B)?(B?C)?(A?C)3.2自然推理系统P析取三段式规则A?BB结论：A构造二难推理规则A?BC?DA?C结论：B?D(A?B)??B?A(A?B)?(C?D)?(A?C)?(B?D)3.2自然推理系统P破坏性二难推理规则A?BC?D?B??D结论：?A??C(A?B)?(C?D)?(?B??D)?(?A??C)3.2自然推理系统P形式推演(语法蕴涵)：给定A1,…,Ak和B符号：{A1,…,Ak}?B存在公式序列C1,C2,…,Cn，对每个i(i=1,…,n),Ci是某个Aj或者Ci是由序列中前面的公式应用推理规则得到Cn=B称C1,…,Cn是由A1,…,Ak推B的证明。