当前位置：文档之家 › 左孝凌离散数学课件1.8推理理论

左孝凌离散数学课件1.8推理理论

  • 格式：ppt
  • 大小：431.00 KB
  • 文档页数：47

下载文档原格式

  / 47

合集下载

左孝凌离散数学1

左孝凌离散数学1

4
第一章 命题逻辑（Propositional Logic）1.3命题
公式与翻译
• 联结词旳优先级：┐、∧、∨、→、。
则：
P∧Q→R 是合式公式
等价于Wff ： （（P∧Q）→R ）命题公式外层旳括号能够省略
等价于Wff ： （P∧Q）→R
不等价于Wff ： P∧（Q→R）
第一章 命题逻辑（Propositional Logic）1.3命题
P Q ┐P∨Q
TT T TF F FT T
P→Q
T F T
FF T
T
第一章 命题逻辑（Propositional Logic） 1.4真值表 与等价公式
1.4.2 等价公式
同理(P∧Q)∨(┐P∧┐Q)与P↔ Q相应旳真值相同，如表1-4.6所示。
表1-4.6
P Q P↔Q TT T TF F FT F FF T
公式与翻译
• 1.3.2 复合命题旳符号化(翻译) • 自然语言旳语句用Wff 形式化：
① 要精确拟定原子命题，并将其形式化。 ② 要选用恰当旳联结词，尤其要善于辨认自然语言中旳联 结词（有时它们被省略），否定词旳位置要放精确。 ③ 必要时能够进行改述，即变化原来旳论述方式， 但要确保体现意思一致。 ④ 需要旳括号不能省略，而能够省略旳括号， 在需要提升公式可读性时亦可不省略。
例2：构造公式 (P Q) ∧R旳 真值表。
P Q R PQ (P Q) ∧R
00 0 00 1
01 0 01 1 10 0 10 1 11 0 11 1
20
第一章 命题逻辑（Propositional Logic） 1.4真值表 与等价公式
例2：构造公式 (P Q) ∧R旳 真值表。

左孝凌离散数学课件1.8推理理论

左孝凌离散数学课件1.8推理理论

例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) S∨R 证法2 (1) P→R P (2) P∨Q →R∨Q T(1) I3 (3) Q→S P (4) Q∨R →S∨R T(3) I (5) P∨Q →S∨R T(2),(4) I13 (6) P∨Q P (7) S∨R T(5),(6) I11P,P→Q Q假言 推理
E1 E2 ┐┐P P P∧Q Q∧P E12 E13 R ∨(P∧┐P) R R∧ (P ∨ ┐P) R
E3
E4 E5 E6 E7 E8 E9
P∨QQ∨P
(P∧Q) ∧R P∧ (Q∧R) (P ∨ Q) ∨ R P ∨(Q ∨ R)
E14
E15 E16
R ∨(P ∨ ┐P) T
T T T T T F F
从真值表看到，P→R，Q→R，P∨Q的真值都为T的 情况为第1行、第3行和第5行，而在这三行中R的真值均为 T。故 (P→R)∧(Q→R)∧(P∨Q) R
二、直接证法
• 直接证法：由一组前提，利用一些公认的推理规则， 根据已知的等价或蕴含公式推演得到有效结论。 • 常用的推理规则 P规则:（前提引入规则）前提在推导过程中的任何时候 都可以引用。 T规则（结论引用规则）在推导过程中，如果有一个或多 个公式重言蕴含着公式S，则公式S可以引入推导之。 如 P→Q, Q→R P→R，这时 P→R可引入推导之中
d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S) ┐S (1) (┐Q∨R) ∧┐R P (2) ┐Q∨R T(1),I1 (3) ┐R T(1),I2 (4) ┐Q T(2)(3),I10析取三段论 (5) P→Q P (6) ┐P T(4)(5),I12 (7) ┐(┐P∧┐S) P (8) P∨┐S T(7),E (9) ┐S T(6)(8),I10析取三段论

离散数学-命题逻辑-4-左孝凌

离散数学-命题逻辑-4-左孝凌
定义1-7.6 在基本积中，每个变元及其否定不同时存在，但两 者之一必须出现且仅出现一次，这样的基本积叫做布尔合取 也叫小项或极小项。 p，q的极小项为：p∧q，p∧q，p∧q，p∧q 两个命题变元的极小项共4(=22)个, 三个命题变元的极小项 共8(=23)个, …。一般地说，n个命题变元共有2n个极小项。 表1-7.1是两个变元p和q的极小项的真值表。
1.8 命题逻辑的推论理论
数理逻辑的主要任务是用逻辑的方法研究数 学中的推理。所谓推理是指从前提出发，应用推 理规则推出结论的思维过程。任何一个推理都由 前提和结论两部分组成。前提就是推理所根据的 已知命题，结论则是从前提出发通过推理而得到 的新命题。要研究推理，首先应该明确什么样的 推理是有效的或正确的。
求析取范式
⑵ 求析取范式 (p∨q)p ((p∨q)∧p)∨((p∨q)∧p) p∨(p∧q∧p) p∨(p∧p∧q) p∨(p∧q) (消去) ((p∨q)∧p)∨((p∧q)∧p) (内移) (吸收律，析取范式) (交换律) (幂等律，析取范式)
由此例可以看出，命题公式的析取范式也不惟一。
主范式
析取范式与合取范式
定义1-7.4 由基本和的合取构成的公式叫做合取范 式。约定单个基本和是合取范式。 例如 P,P∨R,P∧Q,(P∨Q)∧R,(P∨Q)∧(Q∨R) 是合取范式。 定义1-7.5 由基本积的析取构成的公式叫做析取范 式。约定单个基本积是析取范式。 例如 P,P∨R,P∧Q,(P∧Q)∨R,(P∧Q)∨(Q∧R) 是析取范式。
极大项的性质
⑵ 任意两个不同的极大项的析取式为永真式。 例如： M001∨M100 T ⑶ 全体极大项的合取式为永假式。记为：
2 n 1 i =0
∏ Mi M0∧M1∧…∧M 2 1

离散数学 推理理论

离散数学 推理理论
S ( P∨Q) S ∨ (P∨Q) ( S ∨P ) ∨Q ( S ∧ P ) ∨Q ( S ∧ P ) Q 例题 证明: (P∨Q) ∧(P R) ∧(Q S) S ∨ R
作业：P46(1)a, b (2)a,c (3)a,c (4)c
结束
T规则：由前提得出的阶段性有效结论（由一个或多 个公式重言蕴含着的公式）也可以在证明中使用。
P43两个表要熟练
例2：用推理规则证明下列各式。
1 . 证明: (P∨Q) ∧(P R) ∧(Q S) S ∨ R
(1) P∨Q
Ｐ
(2)E Ｐ
证法2见书P44
(4) P S
T (7) E
(9) C ( D E)
T (8) E
(10) D E
T (5) (9) I
(11) (D∧ E) (12) F (D∧ E) (13) F (14) BF (15) A(BF)
T (10) E P T (11) (12) I CP CP
3 . 半反证法
当结论是析取式，具有形式P∨Q时，我们把其中一析取 项的否定（ P或 Q）作为假设前提，并和其它前提 一起共同得出另外一析取项（ Q或P） 。 即要证S P∨Q，可通过证明( S ∧ P ) Q 半反证法的正确性证明：
Ｔ (1) I Ｔ (2) (3) I Ｐ
(6) P (7) ( P ∧S)
Ｔ (4) (5) I Ｐ
(8) P ∨ S (9) S
Ｔ (7) E Ｔ (6) (8) I
例3：公安人员破案问题。
一公安人员审查某工厂失窃案，他认为下列情况 是真的： (1)有两个怀疑对象，保管员小王和材料科长老李； (2)值班员小张工作一贯负责； (3)失窃案发生的那天白天，老李去兄弟厂开会； (4)如果晚上仓库上锁，就不会发生失窃案； (5)如果晚上仓库未上锁或灯未亮，则值班员小张失职。 请问谁是盗窃犯？

离散数学.第1章

离散数学.第1章
P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1
例4
设P：我们去看电影。Q：房间里有十张桌子。则
P ∧ Q表示“我们去看电影并且房间里有十张桌子。”
10
3. 析取“∨”（相容或）[讲解教材P3-5关于或]
4. 定义1.3
由命题P和Q利用“∨”组成的复合命题，称 为析取式复合命题，记作“P∨Q”（读作“P或Q”）。 当且仅当P和Q至少有一个取值为真时，P∨Q取值为真。
练习1-1
1. 判断下列语句哪些是命题，若是命题，则指出其真值。
（1） （2） 只有小孩才爱哭。 X+6=Y ( 是 假 ) ( 不是 ) (是 真) ( 不是 )
（3）
银是白的。
（4） 起来吧，我的朋友。 2． 将下列命题符号化
（1） 我看见的既不是小张也不是老李。 解 令P：我看见的是小张；Q：我看见的是老李。 则该命题可表示为¬ P∧¬ Q （2） 如果晚上做完了作业并且没有其它的事，他就会 看电视或听音乐。 解 令 P：他晚上做完了作业；Q：他晚上有其它的事； R：他看电视； S：他听音乐。 则该命题可表示为（P∧¬ Q）→（R∨S）
28
1.3 等值演算
• 定义1.10 设A和B是两个命题公式, 若等价式A↔B 是重言式，则称公式A 和B等值，记为A B,称 AB为等 值式。
• 注意： （1）符号“”与“↔”的区别与联系 “”不是联结词，AB不表示一个公式， 它表示两个公式间的一种关系，即等值关系。 “↔”是联结词，A↔B是一个公式。 AB 当且仅当 A↔B 是永真公式。
1 0 1 0 1 0 1 0
0 0 1 1 1 1 1 1
0 0 0 1 0 0 0 1
1 1 0 1 0 0 0 1

离散数学左孝陵版答案公开课一等奖优质课大赛微课获奖课件

离散数学左孝陵版答案公开课一等奖优质课大赛微课获奖课件
第4页
§1 谓词概念与表示法
（1）谓词填式：谓词字母后填以客体所得式子。
例：H(a, b)
（2）若谓词字母联系着一个客体，则称作一元谓词；若谓 词字母联系着二个客体，则称作二元谓词；若谓词字母联 系着n个客体，则称作n元谓词。
（3）客体顺序必须是有要求。 例：河南省北接河北省。
nL
b
写成二元谓词为：L(n,b)，但不能写成L(b,n) 。
例：P(x)表示x是质数。这是一个命题函数。 其值取决于个体域。 能够将命题函数命题，有两种办法：
第7页
§2 命题函数与量词
a)将x取定一个值。如：P(4)，P(5) b)将谓词量化。如：xP(x)，xP(x) 个体域给定形式有二种： ①详细给定。 如：｛j, e, t｝ ②全总个体域任意域：所有个体从该域中取得。
第13页
§3谓词公式与翻译
写成符号形式：
x(M(x) D(x))， M(s) D(s)
2.因为对个体描述性质刻划深度不同，可翻译 成不同形式谓词公式。
第14页
§4变元约束
1.辖域：紧接在量词后面括号内谓词公式。 例： xP(x) , x(P(x) Q(x)) 。 若量词后括号内为原子谓词公式，则括号能够省去。
第18页
§4变元约束
6.个体域（叙述域，客体域）:用特定集合表示 被约束变元取值范围。
(1)个体域不同，则表示同一命题谓词公式形 式不同。 例：“全部人必死。”令D(x)，x是要死。
下面给出不同个体域来讨论：
(ⅰ)个体域为：{人类}，
则可写成 xD(x)；
(ⅱ)个体域为任意域（全总个体域），则人必 须首先从任意域中分离出来，
(b)每一个自然数都是偶数 x(N(x) E(x))

左孝凌离散数学PPT课件

左孝凌离散数学PPT课件
25
第一章 命题逻辑（Propositional Logic） 1.2逻辑
联结词(Logical Connectives)
例3. 将下列命题符号化.
(1) 李平既聪明又用功.
(2) 李平虽然聪明, 但不用功.
(3)李平不但聪明,而且用功.
(4)李平不是不聪明,而是不用功.
解: 设 P:李平聪明. Q:李平用功.
第一章 命题逻辑（Propositional Logic）
1.1 命题及其表示方法
• 1.1.1 命题（Proposition) • 1.1.2 命题的表示方法 • 1.1.3 命题的分类
第一章 命题逻辑（Propositional Logic）
1.1 命题及其表示方法
1.1.1 命题
数理逻辑研究的中心问题是推理（inference),而 推理的前提和结论都是表达判断的陈述句，因而表达
第一部分 数理逻辑（Mathematical Logic)
❖1931年Godel不完全性定理的提出，以及递 归 函 数 可 计 算 性 的 引 入 ， 促 使 了 1936 年 Turing 机 的 产 生 ， 十 年 后 ， 第 一 台 电 子 计 算机问世。
❖从 广 义 上 讲 ， 数 理 逻 辑 包 括 四 论 、 两 演 算——即集合论、模型论、递归论、证明 论和命题演算、谓词演算，但现在提到数 理逻辑，一般是指命题演算和谓词演算。 本书也只研究这两个演算。
逻辑可分为：1. 形式逻辑（通过数学方法） 数理逻辑 2. 辩证逻辑 指引进一套符号体系的方法。
辩证逻辑是研究反映客观世界辩证发展过程的人类思 维的形态的。
第一部分 数理逻辑（Mathematical Logic)
❖ 形式逻辑是研究思维的形式结构和规律的科学，它撇 开具体的、个别的思维内容，从形式结构方面研究概 念、判断和推理及其正确联系的规律。

离散数学-1-8 推理理论

离散数学-1-8 推理理论

18
间接证法（间接推理）
例 构造下面推理的证明。
如果小张守第一垒并且小李向B队投球，则A队将取胜； 或者A队未取胜，或者A队获得联赛第一名； A队没有获得联赛的第一名； 小张守第一垒。 因此，小李没有向B队投球。 解:设 P:小张守第一垒。 Q:小李向B队投球。 R:A队取胜。 S:A队获得联赛第一名。
设P1，P2，…，Pn出现于前提H1，H2，…，Hm 和结论C的 全部命题变元，假定对P1，P2，…，Pn作了全部的真值指 派，这样就能对应地确定H1，H2，…，Hn 和C的所有真值， 列出这个真值表，即可看出 H1∧H2∧…∧HmC 是 否成立
即找出H1，H2，…，Hm 均为１的行，对于每一个这样的行，若 C也为１,则上式成立。或C为０， H1，H2，…，Hm 中起码有一 个为０
19
间接证法（间接推理）
前提：(P∧Q)→R,┐R∨S,┐S ,P 结论：┐Q 证明：(用归谬法)
(1) Q P(附加前提） (2)┐R∨S Ｐ (3)┐S Ｐ (4)┐R T(2)(3) I(析取三段论) (5)(P∧Q)→R P (6)┐(P∧Q) T(4)(5) I(拒取式) (7) ┐P∨┐Q T(6) E(德摩根律，置换） (8)P P (9)┐Q T(7)(8) I(析取三段论 (10)Q∧┐Q（矛盾） Ｔ(1)(9) I(合取引入规则）
10
间接证法（间接推理）
定义1-8.2 假设公式H1，H2，…，Hm中的 命题变元P1，P2，…，Pn，对于P1，P2，…， Pn的一些真值指派，如果能使 H1∧H2∧…∧Hm的真值为Ｔ，则称公式H1， H2，…，Hm是相容的。如果对于P1，P2，…， Pn的每一组真值指派，使H1∧H2∧…∧Hm 的真值均为Ｆ，则称公式H1，H2，…，Hm是 不相容的。

离散数学课堂PPT(左孝凌版)

离散数学课堂PPT(左孝凌版)
P T T F F Q T F T F ᄀP F F T T ᄀP∨Q T F T T P→Q T F T T
（P∧Q）∨（ᄀP∧ᄀQ）与P⇄Q对应的真值相同。
定义1－4.2 给定两个命题公式A和B，设P1， P2，…，Pn为所有出现于A和B中的原子变元,若给P1， P2，…，Pn任一组真值指派,A和B的真值都相同,则 称A和B是等价的或逻辑相等。记作A⇔B。
P T T
Q ᄀP ᄀQ T F F F F T
P∧Q ᄀP∧ᄀQ （P∧Q）∨ （ᄀP∧ᄀQ） T F T F F F
F
F
T T
F T
F
T
F
F
F
T
F
T
例4 给出ᄀ（P∧Q）⇄（ᄀP∨ᄀQ）的真值表。
P Q P∧Q ᄀ（P∧Q） ᄀP ᄀQ ᄀP∨ᄀQ ᄀ（P∧Q）⇄ （ᄀP∨ᄀQ）
T T T T F F
定义1－2.3 设P、Q为两命题，复合命题“P或Q” 称为 P与Q的析取式，记作P∨Q，∨为析取联结 词。 P Q P ∨Q T T T T F T F T T F F F
析取式P∨Q表示的是一种相容性或，即允许P 和Q同时为真。 例：“王燕学过英语或日语” P∨Q 自然语言中的“或”具有二义性，有时表示 不相容的或。 例：“派小王或小李中的一人去开会” 。为排斥 性的或。 P：派小王去开会；Q：派小李去开会。 （P∧ᄀQ）∨（ᄀP∧Q） ， （P∨Q）∧ᄀ（P∧Q）
其中P、Q和R代表任意的命题公式。
例6 验证吸收律
P∨（P∧Q）⇔P和 P∧（P∨Q）⇔P
P T T F F
Q T F T F
P∧Q T F F F
P∨（P∧Q）P∨Q T T T T F T F F

左孝凌离散数学课件1知识讲解176页PPT

左孝凌离散数学课件1知识讲解176页PPT

31、只有永远躺在泥坑里的人，才不会再掉进坑里。——黑格尔 32、希望的灯一旦熄灭，生活刹那间变成了一片黑暗。——普列姆昌德 33、希望是人生的乳母。——科策布 34、形成天才的决定因素应该是勤奋。——郭沫若 35、学到很多东西的诀窍，就是一下子不要学很多。——洛克
左孝凌离散数学课件1知识讲解
6、法律的基础有两个，而且只有两个……公平和实用。—伯克 7、有两种和平的暴力，那就是法律和礼节。——歌德
8、法律就是秩序，有好的法律才有好的秩序。——亚里士多德 9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿 10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯

离散数学课件 第一章

离散数学课件 第一章
离 散 数 学
主讲教师 李红军 北京林业大学 理学院
BEIJING FOREST UNIVERSITY
教材及参考资料
教材：
1耿素云，屈婉玲，张立昂编著，离散数学，清华大学出版 社, 2008年3月（第4版） 2耿素云,屈婉玲编著.离散数学(修订版).高等教育出版社, 2004年
参考资料：
1 左孝凌编著，离散数学，上海科学技术出版社
1.1 命题与联结词 命题：能判断真假而不是可真可假的陈述句。 命题的真值：命题为真或者假的判断。 真命题：真值为真的命题。 假命题：真值为假的命题。 注：任何命题的真值都是惟一的；
用“1”表示真，用“0”表示假。
例 1.1 ：判断下列句子哪些是命题.
(1)
3 是有理数。
(2) 2是素数。 (3) X＋Y>10。
1 3
m z 1 r m 1
z m 1
1 2
1
3
比赛结束，三位观众各猜对了一半，并且没有并列名次.问：中 国、美国、日本的各排名第几？ 设z1:中国第一;z2 :中国第三；r1:日本第一； m1:美国第一；m2:美国第二； m3:美国第三.
例1的参考答案 m1 z3 1 r1 m3 1 z1 m2 1
对偶原理
A和A*是互为对偶式，P1， P2 ，……Pn是出现在A和A*的原子变元，则 A（P1，…，Pn） A*（ P1，…， Pn） A（ P1，…， Pn） A*（P1，…，Pn）
即公式的否定等值于其变元否定的对偶式。 例：A为PQ，则A*为PQ， 则（PQ） PQ
真值表
将命题公式A在所有赋值下取值情况列成表
试考虑求公式A的真值表的步骤？ 例1 求下列公式的真值表，并求出成真赋值和成假赋值. 1) p(¬ r∧q) 2) (p∨q)(¬ p q)

左孝凌离散数学课件

左孝凌离散数学课件

01
集合论
集合的基本概念
总结词
集合是离散数学中的基本概念，它是由一组确定的、不同的、互不相同的元素所组成的 。
详细描述
集合是离散数学中一个最基本的概念，它是由一组确定的、不同的、互不相同的元素所 组成的。这些元素可以是数字、字母、图形等，它们在集合中表示不同的个体或对象。
集合的运算和性质
总结词
详细描述
邻接矩阵是一种常用的图表示方法，通过二维矩阵表示节点之间的关系，矩阵中的元素表示边的权重 或连接状态；邻接表是一种更有效的图表示方法，通过链表或数组等数据结构表示节点和其相邻节点 之间的关系。
图的连通性
总结词
图的连通性是指图中任意两个节点之间是否 存在路径。
详细描述
图的连通性分为强连通和弱连通两种情况。 强连通是指图中任意两个节点之间都存在有 向路径；弱连通是指图中任意两个节点之间 都存在无向路径。判断图的连通性是图论中 的重要问题之一。
左孝凌离散数学课件
THE FIRST LESSON OF THE SCHOOL YEAR
• 离散数学简介 • 集合论 • 图论 • 逻辑学 • 离散概率论 • 离散统计学
目录CONTENTS
01
离散数学简介
离散数学的起源和定义
总结词
离散数学的起源可以追溯到古代数学，它与连续数学相对应，研究的是非连续的、分离的对象。
置信区间
置信区间是指根据样本数据估计 总体参数的可能范围，用于衡量 估计的准确性。
单侧检验和双侧检
验
单侧检验是指只检验一个方向的 假设，而双侧检验则是同时检验 两个方向的假设。
感谢观看
THANKS
THE FIRST LESSON OF THE SCHOOL YEAR

离散数学讲义ppt课件

离散数学讲义ppt课件

课程概况
教材：
《离散数学（第三版）》，耿素云等编著 清华大学出版社，2004年3月
参考书：
（1） 《离散数学(第二版)》及其配套参考书《离散 数学题解》作者：屈婉玲，耿素云，张立昂 清华大学出版社
（2） 《离散数学》焦占亚主编 电子工业出版社 2005年1月
2
课程概况
选修课/必修课：选修 周学时：3（学时） 上课周：1－16周 总学时：48（学时）
3
课程内容及学时安排
第一篇 数理逻辑（14学时）
第一章 命题逻辑（8） 第二章 谓词逻辑（6）
第二篇 集合论（12学时）
第三章 集合（4） 第四章 二元关系与函数（8）
第四篇 图论（14学时）
第七章 图论（8） 第八章 一些特殊图（4） 第九章 树 （2）
4
课程考核
第四篇 代数系统（8学时）
第5、6章 图论（8）
所以，伊勒克持拉既知道并且又不知道这个人是她的 哥哥。
20
NO.3 M：著名的理发师悖论是伯特纳德·罗素提出的。一个理发 师的招牌上写着： 告示：城里所有不自己刮脸的男人都由我给他们刮脸，我 也只给这些人刮脸。 M：谁给这位理发师刮脸呢？ M：如果他自己刮脸，那他就属于自己刮脸的那类人。但 是，他的招牌说明他不给这类人刮脸，因此他不能自己来 刮。 M：如果另外一个人来给他刮脸，那他就是不自己刮脸的 人。但是，他的招牌说他要给所有这类人刮脸。因此其他 任何人也不能给他刮脸。看来，没有任何人能给这位理发 师刮脸了！
P
Q
PQ
P
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1

离散数学左孝凌 ppt课件

离散数学左孝凌 ppt课件
计算机学院
2-2.1 命题函数
定义2-2.1：简单命题函数(simple propositional function)：
由一个谓词，一些客体变元组成的表达式称为 简单命题函数。
比如：A(x)，B(x,y)，L(x,y,z) 简单命题函数不是命题，只有当变元x,y,z等 取特定的客体才确定了一个命题。 对于n元谓词，当n=0时，称为0元谓词，它 本身就是一个命题，故命题是n元谓词的一个特 殊情况。
计算机学院
2-2.2 量词
例4: “不存在最大的自然数”。 解: 设: F(x): x是自然数; G(x,y): x＞y; 原命题符号化成: (x)(F(x)(y)(F(y)G(x,y))) 或: (x)(F(x)(y)(F(y)G(x,y)))
计算机学院
2-2.2 量词
例5: “火车比汽车快”。 解: 设: F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 原命题符号化成:
2-1.1 客体和谓词 在谓词逻辑中，可将原子命题划分为客体
和谓词两部分。 客体：可以独立存在的具体事物的或抽象的概 念。例如，电子计算机、李明、玫瑰花、黑 板、实数、中国、思想、唯物主义等，客体也 可称之为主语。
计算机学院
第二章 谓词逻辑（Predicate Logic）
2-1 谓词的概念与表示(Predicate and Its Expression)
(1) F(a) a：张明 (2) F(b) b：李华
(3) G(c) c：王红 (4) H(s,t) s：小李 t：小赵
(5) R(a,b,c)
(6) S(a,b) a:阿杜。b:阿寺。
其中(1)、(2)、 (3)为一元谓词， (4) 、 (6)为二元谓词，
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 真值表法
前提全部为 真是结论为 真1,3,5 结论为假， 前提中至少 有一个为假 2,6,8
P Q R P→R C H1 T T T T T T F F T F T T T F F F F T T T F T F T F F T T F F F T
Q→R H2
T
P∨Q H3
T
F T T T F T T
• 判断C是A的有效结论的方法就是判别重言蕴 含的方法. • 最基本、最常用的方法有三种：
推理证明的方法
7
一、真值表法
• 设P1，P2，…，Pn是出现于前提H1，H2，…，Hn 和结论 C中的全部命题变元，假定对 P1 ， P2 ，…， Pn作了全部的真值指派，这样就能对应地确定H1， H2 ，…， Hn 和 C 的所有真值，列出这个真值表， 即可看出(A)式是否成立
P T T F
Q
（C）
P∨Q
（H1）
┐P
（H2）
┐P∧(P∨Q)
T F T
T T T
F F T
F F T
F
F
F
T
F
• 例题2 如果张老师来了，这个问题可以得到解答， 如果李老师来了，这个问题也可以得到解答， • 总之张老师或李老师来了， • 这个问题就可得到解答。 解 若设 P：张老师来了。 Q：李老师来了。 R：这个问题可以得到解答。 上述语句可翻译成下述命题关系式 (P→R)∧(Q→R)∧(P∨Q) R
4
推广到有n个前提的情况：
定义：设H1，H2，……，Hn，C是命题公式，当 且仅当： H1∧H2∧…∧Hn C (A) 称C是一组前提H1，H2，……，Hn的有效结论。
定义：判别有效结论的过程就是论证过程。
•注意: 在形式逻辑中,我们并不关心结论是否真实 ,而主要关心结论是否可以由给定的前提推出来 ,我们只注意推理的形式是否正确.因此,有效结 论并不一定是正确的,只有正确的前提经过正确 的推理得到的逻辑结论才是正确的.
第一章 命题逻辑（Propositional Logic） 1.8推理理
论(Inference Theory)
常用论证过程：
1真值表法 2直接证法 3 间接证法
1
数学符 号系统
运算法 则公式
条件： 甲说：这不是 铁，也不是铜； 乙说：这不是 铁，是锡 分解 丙说：这不是 锡，是铁。 结论：……
条件： 条件： 命题1； P； 命题2； Q； 命题…… P∧Q… 翻译 结论： 结论： 命题1； ﹁P； 命题…… Q…
这份统计表格的错误不是由于材料不可靠，
所以：这份统计表格的错误是由于计算有错误。 解 设各命题变元为 P：统计表格的错误是由于材料不可靠。 Q：统计表格的错误是由于计算有错误。 本例可译为：Q是前提P∨Q，┐P的有效结论， 即 ┐P∧(P∨Q) Q
• 真值表法：
或者考察Q的真值为F的 情况，在第2行和第4行， 其相应的P∨Q或┐P中至 少有一真值为F，故 (P∨Q)∧(┐P) Q成立 只有在第3行P∨Q和┐P 的真值都为T，这时Q的 真值亦为T。故 (P∨Q)∧(┐P) Q 成立。
13
•真值表法是把所给前提一起使用 •直接证法中，不是一次使用前提，而 是不断使用部分前提及前面推出的结 论，构成推导序列，是把前提一步一 步拿来使用
常用的蕴含式（43页表1-8.3） I1 P∧Q P化简式 I9 P,Q P∧Q I2 P∧Q Q化简式 I10 ┐P,P∨Q Q析取三段论 I3 P P∨Q附加式 I11 P,P→Q Q假言推理 I4 Q P∨Q附加式 I12 ┐Q,P→Q ┐P据取式
I5 ┐P P→Q
I6 Q P→Q I7 ┐(P→Q) P I8 ┐(P→Q) ┐Q
I13 P→Q, Q→R P→R假 言三段论 I14 P∨Q,P→R,Q→R R
I15 A→B (A∨C)→(B∨C) I16 A→B (A∧C)→(B∧C)
常用的等价式(43页表1-8.4)
– 1 ）从真值表上 找出 H1 ， H2 ，…， Hn 真值均为 T 的行 ， 对于每一个这样的行，若C的真值为T，则蕴含式成立。 即C是有效结论： 2）或者 找出 C 的真值为 F 的行 ，在每一个这样的行中， 若H1，H2，…，Hn的真值至少有一个为F，则蕴含式成 立。
8
–
• 例题1 一份统计表格的错误或者是由于材料不可靠， 或者是由于计算有错误；
E1 E2 ┐┐P P P∧Q Q∧P E12 E13 R ∨(P∧┐P) R R∧ (P ∨ ┐P) R
T T T T T F F
从真值表看到，P→R，Q→R，P∨Q的真值都为T的 情况为第1行、第3行和第5行，而在这三行中R的真值均为 T。故 (P→R)∧(Q→R)∧(P∨Q) R
二、直接证法
• 直接证法：由一组前提，利用一些公认的推理规则， 根据已知的等价或蕴含公式推演得到有效结论。 • 常用的推理规则 P规则:（前提引入规则）前提在推导过程中的任何时候 都可以引用。 T规则（结论引用规则）在推导过程中，如果有一个或多 个公式重言蕴含着公式S，则公式S可以引入推导之。 如 P→Q, Q→R P→R，这时 P→R可引入推导之中
3
第一章 命题逻辑1.8推理理论
（2）若A,B都是偶数，则A+B为偶数 P→Q A+B为偶数 Q 所以 A,B都是偶数 所以P （3）如果狗有翅膀，那么狗会飞 P→Q 狗有翅膀 P 所以,狗会飞 所以Q 解（1）的推理过程是正确的，结论有效； (（ P→Q ） ∧P) →Q=T （ 2 ）的结论不是有效结论， ( （ P→Q ） ∧ Q) →P不 是重言式； （3）的结论看起来似乎很荒唐，但是有效结论。
推理 运算
推理 结论
采用数理逻辑研究推理的过程
第一章 命题逻辑1.8推理理论
定义 ：设Ａ和Ｃ是两个命题公式 , 当且仅当Ａ Ｃ 为重言式，即ＡＣ,称Ｃ是Ａ的有效结论;或称Ｃ可 由Ａ逻辑推出. 例如：若两个加数都是偶数，则和是偶数。 P:两个加数都是偶数；Q:和是偶数。 可表示为：P→Q （1）若A,B都是偶数，则A+B为偶数 P→Q A,B都是偶数 P 所以 A+B是偶数 所以Q