02 命题逻辑等值演算-课件(PPT)

Show that (p∨( p∧q)) and p∧q are
logically equivalent.
EXAMPLE 6
Propositional E q u i v a命l 题e n演c算e s
Show that (p∧q) → (p∨q) is a tautology.
Propositional E q u i v a命l 题e n演c算e s
1.2 命题演算
Propositional E q u i v a命l 题e n演c算e s
Propositional Equivalences
1、命题(Proposition)
Propositional E q u i v a命l 题e n演c算e s
2、从简单命题(atomic proposition)到
例3：否认和析取组成的逻辑结合词组是极小功能 完备的。
进一步的思索：
Propositional E q u i v a命l 题e n演c算e s
三、命题公式的进一步分类。
命题公式的规范化-----范式
Propositional E q u i v a命l 题e n演c算e s
文字〔literal〕/符号〔symbol〕： 原子命题或其否认
Table 6
Propositional E q u i v a命l 题e n演c算e s
p ∨ (p ∧ q) p p ∧ (p ∨ q) p
Absorption Laws/吸收律
p → q p ∨ q
p q (p → q) ∧( q → p)
EXAMPLE 5
Propositional E q u i v a命l 题e n演c算e s

(分配律) (矛盾律) (同一律) (德摩根律) (结合律) (排中律) (零律)
等值演算旳例子
解：⑵ (p∨¬p)→((q∧¬q)∧r)
1→((q∧¬q)∧r)
(排中律)
1→(0∧r)
(矛盾律)
1→0
(零律)
0
(条件联结词旳定义)
由此可知，⑵为矛盾式。
⑶ (p→q)∧¬p
(¬p∨q)∧¬p
(蕴涵等值式)
范式存在定理
定理2.3
• 任一命题公式都存在着与之等值旳 析取范式
求•范任式旳一环命节题如公下式：都存在着与之等值旳合 ⑴取消范去式联结词“→”和“↔”
⑵ 利用双重否定律消去否定联结词“¬”或 利用德摩根律将否定联结词“¬”移到各命题 变元前(¬内移)。
⑶ 利用分配律，结合律将公式归约为合取 范式和析取范式。
极大项：简朴析取式中满足如上条件。
极小（大）项旳关键性质
• 定理：n个命题变元共有2n个极小项（极大项）。
p
q p∧q p∧¬q
¬p∧q
¬p∧¬q
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
• 每个极小（大）项只有一种成真（假）赋值，且 各极小项旳成真赋值互不相同。
• 极小项和它旳成真赋值构成了一一相应旳关系。
¬p
(吸收律)
由此可知，⑶是可满足式。
练习
1.用等值演算验证等值式 （1） (p∨q)→r (p→r)∧ (q→r) （2） （(p∨q)∧ ¬（p∧q））

保持等值性的两条规则
代入规则: 等值式模式的代换实例是等值式. 在蕴涵等值式 A B AB 中取 A 为 p, B 为 q 得
p q p q. 而取 A 为 p q r, B 为 p q 则得
(p q r) (p q) (p q r) (pq). †具体的等值式叫做等值式模式的代入实例.
101 1 1
011
110 1 1
110
111 1 1
111
离散数学(60). W&M.
§2.1 等值式

涉及联结词 , 的运算律有
蕴涵等值式: A B A B 等价等值式: (AB) (AB)(BA) 假言易位: A B B A 等价否定律: A B A B 以及: A (B C) (A∧B) C 等.
离散数学(60). W&M.
§2.1 等值式

第二章 命题逻辑等值演算
§2.1 等值式 §2.2 析取范式与合取范式 §2.3 联结词的完备集
离散数学(60). W&M.
§2.2 析取范式与合取范式

公式的标准形式
实数代数 R, +, * 中, 函数有不同的表达式, 其中多项 式和多因式是“标准形式”.
即 (pq) r (pq)r.
离散数学(60). W&M.
§2.1 等值式

例2 用等值演算法证明 (pq) q p q.
证 (p q) q
q (p q)
交换律
(q p) (q∨ q)
分配律
(q p) 1
排中律和替换规则
A = A1 A2 … As; 一个合取范式是重言式 它的每个简单析取式都 是重言式.

2.1 等值式
由已知的等值式推演出另外一些等值式的过程 等值演算。 为等值演算。 置换规则： 是含公式A的命题公式 置换规则：设Φ(A)是含公式 的命题公式，Φ(B)是 是含公式 的命题公式， 是 用公式B置换了 置换了Φ 中所有的A后得到的命题公式 用公式 置换了Φ (A)中所有的 后得到的命题公式， 中所有的 后得到的命题公式， Φ(A)。 若BA，则Φ (B) Φ 。 ，
2.1 等值式
证明等值式 验证p→ → 例：验证 →(q→r) (p ∧ q) → r
(蕴涵等值式 蕴涵等值式) 右 (p ∧ q) ∨ r 蕴涵等值式 (德摩根律 德摩根律) p ∨ q ∨ r 德摩根律 结合律) p ∨ ( q∨r) (结合律 ∨ 结合律 蕴涵等值式) p∨ ( q → r) (蕴涵等值式 ∨ 蕴涵等值式 (蕴涵等值式 蕴涵等值式) p → ( q → r) 蕴涵等值式
原式?p?q?rr?p?q?p?qrrp?q?pqrrpq?pqrrpq?prqrrpq合取范式?pqrpqrrpq?pqrrprq析取范式22析取范式与合取范式定义24在含有n个命题变项的简单合取式简单析取式中若每个命题变项和它的否定式不同时出现而二者之一必出现一次而者出现次且第i个命题变项或它的否定式出现在从左算起的第i位上称这样的简单合取式简单析取式为极小项极大项
2.1 等值式
例：什麽，如果她不来那么我也不去，没有那回事。 什麽，如果她不来那么我也不去，没有那回事。 P：她来。 Q：我去。 ：她来。 ：我去。 ( P→ Q) → (P ∨Q) P ∧Q 结论: 她不来, 我去. 结论 她不来 我去 P24例2.4、2.6 例 、
人百米竞赛， 例：A，B，C，D4人百米竞赛，观众甲、乙、丙预 ， ， ， 人百米竞赛 观众甲、 测比赛的名次为： 测比赛的名次为： 第一， 第二 第二； 甲：C第一，B第二； 第一 第二， 第三 第三； 乙：C第二，D第三； 第二 第二， 第四 第四。 丙：A第二，D第四。 第二 比赛结束后发现甲、 丙各对一半， 比赛结束后发现甲、乙、丙各对一半，试问实际名次 如何（假设无并列名次）？ 如何（假设无并列名次）？

解 令P：我得到这本小说；Q：我今夜就读完它。
于是上述命题可表示为P→Q。
7
5．等值“”
定义2.2.5 设P和Q是两个命题，则它们的等值命
题是一个复合命题，称为等值式复合命题，记作“P Q” （读作“P当且仅当Q”）。
当P和Q的真值相同时,PQ取真,否则取假。
例10
P
Q
P Q
0
0
1
0
1
0
1
0
0
德.摩根定律
E11
PQP∨Q
E12
P Q (P∧Q)∨(P∧Q)
E13
P (QR) (P∧Q) R
E14
P Q (PQ)∧(QP)
E15
PQQP
23
三、等价式的判别
有两种方法：真值表方法，命题演算方法
1、真值表方法
例1 用真值表方法证明 E10： (PQ) PQ
解 令：A= (PQ)，B= PQ，构造A，B
一个复合命题，记作“P→Q”（读作“如果P，则Q”）。
当P为真，Q为假时，P→Q为假，否则 P→Q为真。
P
Q
P→Q
0
0
1
0
1
1
1
0
0
1
1
1
例8 若P：雪是黑色的；Q：太阳从西边升起；
R：太阳从东边升起。则P→Q和P→R所表示的命题都是真的.
例9 将命题“如果我得到这本小说，那么我今夜
就读完它。”符号化。
对于上述五种联结词，应注意到： 复合命题的真值只取决于构成它的各原子命题的真 值，而与这些原子命题的内容含义无关。
9
命题符号化
利用联结词可以把许多日常语句符号化。基本步骤如下：

详细描述
概率命题演算在传统命题演算的基础上，引 入概率函数来量化命题的不确定性。通过概 率算子和概率分布，描述了命题在各种情况 下的可能性，从而更准确地表达现实世界中
的不确定性。
感谢您的观看
THANKS
逆否命题
对原命题的条件和结论都进行否定， 然后互换它们的位置，例如“如果天 下雨，那么地面会湿”的逆否命题是 “如果地面不湿，那么天不下雨”。
复合命题的表示与转换
复合命题
由两个或多个简单命题通过逻辑运算符组合而成的命题，例如“如 果天不下雨并且地面不湿，那么没有人在家”。
复合命题的表示方法
使用逻辑运算符（如“∧”、“∨”、“→”等）将简单命题组合 起来。
总结词
时序命题演算是命题演算的一种扩展，它引 入了时间因素来描述命题在时间序列上的状 态和变化。
详细描述
时序命题演算考虑了时间因素对命题状态的 影响，通过引入时间算子和时间依赖关系来 扩展命题演算。它能够描述在特定时间点上 命题的真假状态，以及随着时间推移命题的 变化情况。
概率命题演算
总结词
概率命题演算是命题演算的一种扩展，它引 入概率概念来描述命题的不确定性。
复合命题的真假判定
根据真值表或逻辑运算规则判断复合命题的真假值。
03 命题逻辑推理
推理规则
1 2 3
推理规则
推理规则是逻辑推理的基本准则，包括前提和结 论两部分。前提是推理的依据，结论是根据前提 得出的结果。
推理形式
推理形式是指推理的逻辑结构，包括前提和结论 的逻辑表达式。根据不同的逻辑表达式，可以得 出不同的推理形式。
模态命题演算
总结词
模态命题演算是命题演算的一种扩展，它引入了模态算子来描述命题之间的可能性、必 然性等关系。

（同一律）
1∨┐p
（排中律）
1
（零律）
例2.5 解答
(2) ┐(p→(p∨q))∧r ┐(┐p∨p∨q)∧r (p∧┐p∧┐q)∧r 0∧r 0
(3) p∧(((p∨q)∧┐p)→q) p∧(┐((p∨q)∧┐p)∨q) p∧(┐((p∧┐p)∨(q∧┐p))∨q) p∧(┐(0∨(q∧┐p))∨q) p∧(┐q∨p∨q) p∧1 p
A=(p→q)→r (┐p∨q)→r
（蕴涵等值式）
┐(┐p∨q)∨r
（蕴涵等值式）
(p∧┐q)∨r
（德摩根律）
B=p→(q→r) ┐p∨(┐q∨r)
（蕴涵等值式）
┐p∨┐q∨r
（结合律）
000，010是A旳成假赋值，而它们是B旳成真赋值。
例题
例题2.5 用等值演算判断下列公式旳类型： （1）(p→q)∧p→q （2）(p→(p∨q))∧r （3）p∧(((p∨q)∧┐p)→q)
(蕴含等值式) (分配律) (德摩根律) (蕴含等值式)
例题
例2.4 证明：(p→q)→r 与 p→(q→r) 不等值
解答 措施一、真值表法。
措施二、观察法。易知，010是(p→q)→r旳成假赋值，而010 是p→(q→r)旳成真赋值，所以原不等值式成立。
措施三、经过等值演算化成轻易观察真值旳情况，再进行判断。
例题
例题2.2 判断下列各组公式是否等值 (1)p→(q→r)与(p∧q)→r (2)(p→q)→r与(p∧q)→r
解答
等值 不等值
基本等值式
1.双重否定律
A ┐┐A
2.幂等律
A A∨A, A A∧A
3.互换律
A∨B B∨A， A∧B B∧A

2019-8-29
谢谢欣赏
12
2.2 等值公式
2.2.1 基本的等值公式(命题定律, P和Q是任意的命题公式) 1. 双重否定律 P = P 2. 结合律 (P∨Q)∨R = P∨(Q∨R) (P∧Q)∧R = P∧(Q∧R) (P Q) R = P (Q R)
注: 所有这些公式，都可使用真值表加以验证
从Venn 图，因P∧Q较P来得“小”, P∨Q较 P来得“大”，从而有
P∨(P∧Q) = P
P∧(P∨Q) = P
2019-8-29
谢谢欣赏
19
理解等式: Venn图，自然语言
(P∨Q) = P∧Q
Venn图(理解集合间、命题逻辑中、部分 信息量间的一些关系)
对这些等式使用自然用语加以说明，将有助 于理解
2019-8-29
谢谢欣赏
14
6. 吸收律 P∨(P∧Q) = P P∧(P∨Q) = P
7. 摩根律 (P∨Q) = P∧Q (P∧Q) = P∨Q
对蕴涵词、双条件词作否定有 (PQ) = P∧Q
(PQ) = PQ = PQ = (P∧Q)∨(P∧Q)
2019-8-29
谢谢欣赏
3
推理演算(考察逻辑关系符⇒)
推理形式(正确推理形式的表示) 基本推理公式(各种三段论及五种证明方法) 推理演算(证明推理公式的第六种方法，使
用推理规则) 归结推理法(证明推理公式的第七种方法，
常用反证法)
2019-8-29
谢谢欣赏
4
2.1 等值定理
若把初等数学里的＋、－、×、÷等运算符看作是 数与数之间的联结词，那么由这些联结词所表达的 代数式之间，可建立许多等值式如下： x2－y2 = (x＋y)(x－y) (x＋y)2 = x2＋2xy＋y2 sin2x＋cos2x = 1 ……

如果将真值1，0 看做是数，则每一个解释对应一 个n位二进制数。 假设使极小项m取1值的解释对应的二进制数为i， 今后将m记为mi。
例:
对p，q，r而言，pqr是极小项 解释{p，q，r}使该极小项取1值，解释{p，q， r} 对应的二进制数是2 (010) 于是pqr记为m2
例：
(p(qr))s (p(qr))s p(qr)s p(qr)s …………….
式)
(ps)(qr) (psq)(psr)
( 析取范
…… (合取范式)
主范式
定义2. 4 设p1,…,pn是n个不同原子，一个简单合取式如果 恰好包含所有这n个原子或其否定，且其排列顺序与 p1,…,pn的顺序一致，则称此简单合取式为关于p1,…,pn的 一个极小项。 显然，共有2n个不同的极小项。 例如: 对原子 p，q，r 而言， pqr，pqr，pqr 都是 极小项，但是，p，pq不是极小项， 对原子p，q而言,pq是极小项。
例
判断公式 (pq)(qr)(rp)是否永假? 解： (pq)(qr)(rp) (pq)(qr)(rp) ((pq)(qq)(pr)(qr))(rp) (pqr)(qqr)(prr)(q rr)(pqp)(qqp)(prp) (qrp) 故公式(pq)(qr)(rp)不是永假的。
命题公式和真值表的关系
从0来列写
B (…) ∧ (…)
由1列写的方式进行转化： B (…)∨ (…) B (…) ∧ (…) (…) 写成析取式，表示一种 B 值为假的情况。如 p=1，q=0 时为假，
(…) 写成p ∧q， (…)写成 p ∨ q
1值取p形式
定理
对于任意公式G，存在唯一一个与G等值的主析取 范式。