当前位置：文档之家 › 第二章命题逻辑的等值和推理演算

第二章命题逻辑的等值和推理演算

  • 格式：ppt
  • 大小：996.00 KB
  • 文档页数：100

下载文档原格式

  / 100

合集下载

离散数学-第一部分 数理逻辑-第二章 命题逻辑等值演算

离散数学-第一部分 数理逻辑-第二章 命题逻辑等值演算

名称
M0 M1 M2 M3
20
实例
由三个命题变项 p, q, r 形成的极小项与极大项.
极小项
公式
成真赋值 名称
p q r 0 0 0 m0
p q r 0 0 1 m1
p q r 0 1 0 m2
p q r 0 1 1 m3
p q r 1 0 0 m4
p q r 1 0 1 m5
p q r 1 1 0 m6
p(qr) (pq) r p(qr) 不与 (pq) r 等值
2
等值式例题
例1 判断下列各组公式是否等值: (1) p(qr) 与 (pq) r
p q r qr p(qr) pq (pq)r
000 1
1
001 1
1
010 0
1
011 1
1
100 1
1
101 1
1Hale Waihona Puke 110 00111 1
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
1
1
结论: p(qr) (pq) r
3
等值式例题
(2) p(qr) 与 (pq) r
p q r qr p(qr)
000 1
1
001 1
1
010 0
1
011 1
1
100 1
1
101 1
1
110 0
0
111 1
1
pq (pq)r
1
0
1
1
1
0
1
1
0
1
0

离散数学-第二章命题逻辑等值演算习题及答案

离散数学-第二章命题逻辑等值演算习题及答案

第二章作业评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式. 等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律 真值表法2. (p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔ (¬p∨q)∧(¬p∨r)蕴含等值式⇔¬p∨(q∧r)析取对合取的分配律⇔ p→(q∧r)蕴含等值式3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔¬( (p→q)∧(q→p) )等价等值式⇔¬( (¬p∨q)∧(¬q∨p) )蕴含等值式⇔¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律⇔ (p∨q)∧¬(p∧q)德摩根律4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔ (p∨q)→(¬q∨p)蕴含等值式⇔ (¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔ (¬p∧¬q)∨¬q ∨ p结合律⇔ p∨¬q吸收律, 交换律⇔ M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设 (¬p→q)∧(q∧r) =1, 则¬p→q=1且 q∧r=1,解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)(p q)(q r) 蕴含等值式(p q r)(q r) 对分配律, 幂等律(p q r) (p q r)(p q r) 同一律, 矛盾律, 对分配律m7 m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r((p q)(q p))r 等价等值式((p q)(q p))r 蕴含等值式(p q)(q p)r 德摩根律, 蕴含等值式的否定(参见PPT)(p q r)(q p r) 对分配律, 矛盾律, 同一律M0 M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)(p q)(q r) 蕴含等值式(p q)(p r)(q r) 对分配律, 矛盾律, 同一律(p q r)(p q r) (p q r)(p q r)(p q r)(p q r)m1 m0 m3 m7主合取范式为M2 M4 M5 M6.解逻辑方程法设 (p q) (q r) = 1, 则p q =1 且 q r =1.前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1.后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m0m1m3m7, 主合取范式为M2 M4 M5 M6.真值表法公式 (p q) (q r) 真值表如下:p q r(p q) (qr)00010011010001111000101011001111013724 M5 M6.。

命题逻辑_ls第2章_2.1

命题逻辑_ls第2章_2.1
例：人不犯我，我不犯人；人若犯我，我必犯人。 解：令 P：人犯我。 Q：我犯人。 该命题符号化为： (PQ)∧(PQ) 或： PQ
2.1.2 命题公式及分类
本节主要讨论：
命题公式的定义 命题公式的层次 命题公式的真值表 命题公式的分类
一、命题公式的概念
命题常项：简单命题。 命题变项：真值可以变化的陈述句。
p∧q 的逻辑关系是 p与q同时为真
p∧q真值表如图所示：
P
Q
P∧ Q
0
0
0
0
1
0
1
0
0
1
1
1
(2) 合取联结词“∧” －－且
例如，p: 李军聪明 q: 李军用功 则命题 “李军既聪明又用功” 可描述为： p∧q
以下自然语言中的联结词等都可以抽象为“∧” 。 “并且”、“既…又…”、 “与”、“和”、“以及”、
一、命题公式的概念
例: (1) A = p ∨q，
则 A是2层公式。
(2) A = p ∧ q ∧ r ， 则 A是2层公式。
(3) A =(p ∧q) (r ∨s)， 则A为4层公式。
二、公式的赋值或解释
定义2.8 (P.44) －－公式的赋值或解释
设A 为含有命题变项 p1, p2,…, pn的命题公式, 给 p1, p2, …, pn 一组确定的真值, 称作对公式 A
举例：
令：p：天气好。
q：我去公园。
如果天气好，我就去公园。符号化为：pq
只要天气好，我就去公园。
pq
仅当天气好，我才去公园。
qp
只有天气好，我才去公园。
qp
我去公园玩，除非天气好。
qp
例2.5 将下列命题符号化，并求其真值。

21命题逻辑的等值和推理演算

21命题逻辑的等值和推理演算

A,B代表任意 的命题公式
摩根律 : (AB) = AB，
(AB) = AB
吸收律: A(AB) = A, A(AB) = A
零律:
AT = T, AF = F
同一律: AF = A, AT = A
TA = A， T A = A，
补余律: AA = T， AA = F，
等值公式
2. 常用等值公式
公式A的子公式置换后，A化为公式B，必有A = B
n 等值演算
n 由已知的等值公式推演出新的等值公式的过程 n 如已知: AA = A
则: BAA = BA
n 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则
三个重要的等值式
P Q = P Q P Q = (P Q) ( P Q )
C
P∧Q
FF
T
T
F
T
P∧Q
FT
T
T
F
F
TF
F
F
T
T
P∧Q
TT
T
F
F 任意
2.3 命题公式与真值表的关系
按真值表列出命题公式的方法
从F来列出
如下表中B为F有二种可能
所以，B的命题公式形式为：□ ∧ □
而取F相应的P、Q解释分别为： P∨Q 、 P∨ Q
所以，B=(P∨Q)∧(P∨Q ) 同理，A= P∨Q
按真值表列出命题公式的方法
从T来列出
如下表中A为T有三种可能
所以，A的命题公式形式为：□∨ □ ∨□ 而取T相应的P、Q解释分别为： P∧Q、P∧Q、 P∧Q
所以，A=(P∧Q) ∨(P∧Q) ∨(P∧Q)

第2章 命题逻辑(1)

第2章 命题逻辑(1)

析取
符号
读作“析取”
定义2.3：设p，q为两命题，复合命题“p或q” 称为p与q的析取式，
记作p Ú q ，符号 称为析取联结词。并规定p q为假当且仅当p与q
同时为假。
真值表：
PQ 00
P Q
0
例子 小李是学数学或者计算
01
1
10
1
11
1
机科学pq p：小李是学数学 q：小李是学计算机 科学
2.1.1 命题与联结词
例3：判断下列命题是否为复合命题
（1）5能被2整除。
原子命题
（2）2是素数当且仅当三角形有三条边。 复合命题
（3）4是2的倍数或是3的倍数。
复合命题
（4）李明与王华是同学。
原子命题
（5）蓝色和黄色可以调配成绿色。
原子命题
（6）3不是偶数。
复合命题
（7）林芳学过英语或日语。
复合命题
合取
例：将下列命题符号化。
（1）吴颖既用功又聪明。
p q
（2）吴颖不仅用功而且聪明。
p q
（3）吴颖虽然聪明，但不用功。
p q
（4）张辉与王丽都是三好学生。
r s
（5）张辉与王丽是同学。
t
p:吴颖用功。
q:吴颖聪明。
r:张辉是三好学生。
s:王丽是三好学生。
t:张辉与王丽是同学。
注意：若“和”、“与”连接的是主语成分，则该陈述句为简单命题。
FT
T
F
F
补充：翻译语句
因为语言（包括一切人类语言）常有二义性，把 句子译成逻辑表达式可以消除歧义
把语言翻译成由命题变量和逻辑联接词组成的表 达式

《离散数学》命题逻辑

《离散数学》命题逻辑
由原子命题组合而成的命题称为复合 命题（compound proposition）。
例如：
和 e 都是无理数。 6和8至少有一个是合数。 说刘老师讲课不好是不正确的。 不下雨我就去买书。
7
命题与命题联结词
将命题连接起来的方式叫做命题联结词
（ proposition connective ） 或 命 题 运 算 符
3
命题与命题联结词
逻辑
如何表示？ 如何“操作”？
非真即假的陈述句称为命题（proposition）。 一个命题如果是对的或正确的，则称为真命
题，其真值为“真”（true），常用T或1表示； 一个命题如果是错的或不正确的，则称为假
命题，其真值为“假”（false），常用F或0表示。
4
命题与命题联结词
32
命题公式及其分类
为简化公式的形式，作如下规定：
(1) 优先级 , (∧, ∨), (, ) (2) 公式 (~p) 的括号可以省略，写成 ~p (3) 整个公式最外层的括号可以省略
例1
(((p)∧q)(q∨p)) p∧q q∨p
例2
p∧q∨r 不是 命题公式 应写作 (p∧q)∨r 或 p∧(q∨r)
例 判断下列句子哪些是命题，哪些不是
这门课程题为“离散数学”。 这门“离散数学”讲得好吗？ X 这门“离散数学”讲得真好！ X 请学习“离散数学” 。 X 5是素数。 太阳从西方升起。 如果明天晴，而且我有空，我就去踢球。 天王星上没有生命。 x + 3 > 5。 X 5 本命题是假的。X
俞伯牙和钟子期是好朋友。 俞伯牙是好朋友 ∧ 钟子期是好朋友 俞伯牙 ∧ 钟子期是好朋友 Friend (俞伯牙,钟子期)
23

离散数学第2章 命题逻辑等值演算

6/2/2013 9:02 PM Discrete Math. , Chen Chen 15
例2.6
CHAPTER TWO
例2.6 在某次研讨会的休息时间，3名与会者根据王教授的口音 对他是哪个省市的人进行了判断： 甲说王教授不是苏州人，是上海人。
乙说王教授不是上海人，是苏州人。 丙说王教授不是上海人，也不是杭州人。 听完3人的判断，王教授笑着说，他们3人中有一人说得全对， 有一人说对了一半，有一人说得全不对。试用逻辑演算法分析 王教授到底是哪里的人？ 解： 设命题 p, q, r分别表示 ： 王教授是苏州、上海、杭州人。 则p, q, r中必有一个真命题，两个假命题。要通过逻辑演算将 真命题找出来。 设： 甲的判断为： A1= ┐p∧q; 乙的判断为：A2= p∧┐q; 丙的 判断为：A3= ┐q∧r。
等值式模式
CHAPTER TWO
当命题公式中变项较多时，用上述方法判断两个公式是否 等值计算量很大。为此，人们将一组经检验为正确的等值式作 为等值式模式，通过公式间的等值演算来判断两公式是否等值。 常用的等值式模式如下：
1.双重否定律：A⇔ ┐(┐A) 2.幂等律：A⇔A∨A, A⇔A∧A
3.交换律: A∨B⇔B∨A, A∧B⇔B∧A 4.结合律: (A∨B)∨C⇔A∨(B∨C), (A∧B)∧C⇔A∧(B∧C) 5.分配律：A∨(B∧C)⇔(A∨B)∧(A∨C) (∨对∧的分配律)
⇔ ┐(┐p∨q)∨r (蕴含等值式，置换规则） ⇔ (p∧┐q)∨r (德摩根律，置换规则）
⇔(p∨r)∧(┐q∨r)(分配律，置换规则） 为简便起见, 以后凡用到置换规则时, 均不必标出。
6/2/2013 9:02 PM Discrete Math. , Chen Chen 10

离散数学-第二章命题逻辑


设A( P1，P2，…,Pn )是一个命题公式，
P1，P2，…,Pn是出现于其中的全部命题变元，对P1， P2，…,Pn分别指定一个真值,称为对P1，P2，…,Pn公式A 的一组真值指派。
列出命题公式A在P1，P2，…,Pn的所有2n种真值指 派下对应的真值，这样的表称为A的真值表。
16
例3
值表。
例12 用符号形式表示下列命题。
（1） （2） 如果明天早上下雨或下雪，那么我不去学校 如果明天早上不下雨且不下雪，那么我去学校。
（3）
（4）
如果明天早上不是雨夹雪，那么我去学校。
只有当明天早上不下雨且不下雪时，我才去学校。 解 令P：明天早上下雨； Q：明天早上下雪； R：我去学校。 （1）（P∨Q）→ ¬ R； （2）（¬ ∧¬ P Q）→R； （3）¬ (P∧Q）→R （4）R→（¬ ∧¬ Q） P
4
例4
2．合取“∧” 定义2.2.2
设P和Q是两个命题，则P和Q的合取 是一个复合命题，记作“P ∧ Q”（读作“P且Q”）。
当且仅当命题P和Q均取值为真时，P ∧ Q才取值为真。
P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1
例5
设P：我们去看电影。Q：房间里有十张桌子。则
P ∧ Q表示“我们去看电影并且房间里有十张桌子。”
5
3. 析取“∨” 定义2.2.3
设P和Q是两个命题，则P和Q的析取是一个复 合命题，记作“P∨Q”（读作“P或Q”）。
当且仅当P和Q至少有一个取值为真时，P∨Q取值为真。
P
0 0 1 1 Q 0 1 0 1 P∨Q 0 1 1 1
例6 设命题P：他可能是100米赛跑冠军；
Q：他可能是400米赛跑冠军。

离散数学第二章 命题逻辑等值演算


范式存在定理
定理2.3 任何命题公式都存在着与之等值的析取范式与合 定理 取范式. 取范式. 求公式 的范式的步骤 的范式的步骤： 证 求公式A的范式的步骤： (1) 消去 中的→, ↔ 消去A中的 中的→ A→B⇔¬ ∨B ⇔¬A∨ → ⇔¬ A↔B⇔(¬A∨B)∧(A∨¬ ∨¬B) ↔ ⇔ ¬ ∨ ∧ ∨¬ (2) 否定联结词¬的内移或消去 否定联结词¬ ¬ ¬A⇔ A ⇔ ⇔¬A∧¬ ¬(A∨B)⇔¬ ∧¬ ∨ ⇔¬ ∧¬B ⇔¬A∨¬ ¬(A∧B)⇔¬ ∨¬ ∧ ⇔¬ ∨¬B
真值表法
例1 判断 ¬(p∨q) 与 ¬p∧¬q 是否等值 ∨ ∧ 解 p q 0 0 0 1 1 0 1 1 ¬p ¬q 1 1 0 0 1 0 1 0 p∨q ¬(p∨q) ¬p∧¬q ¬(p∨q)↔(¬p∧¬q) ∨ ∨ ∧ ∨ ↔¬ ∧ 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1
实例(续)
(2) (p→q)↔(¬q→¬ → ↔ ¬ →¬ →¬p) 解 (p→q)↔(¬q→¬ → ↔ ¬ →¬ →¬p) ∨¬p) ⇔ (¬p∨q)↔(q∨¬ ¬ ∨ ↔ ∨¬ ⇔ (¬p∨q)↔(¬p∨q) ¬ ∨ ↔¬ ∨ ⇔1 该式为重言式. 该式为重言式 （蕴涵等值式） 蕴涵等值式） （交换律） 交换律）
实例(续)
(3) ((p∧q)∨(p∧¬ ∧r) ∧¬q))∧ ∧ ∨ ∧¬ 解 ((p∧q)∨(p∧¬ ∧r) ∧ ∨ ∧¬ ∧¬q))∧ （分配律） 分配律） （排中律） 排中律） （同一律） 同一律） ∨¬q))∧ ⇔ (p∧(q∨¬ ∧r ∧ ∨¬ ⇔ p∧1∧r ∧ ∧ ⇔ p∧r ∧ 成假赋值. 成假赋值 总结:A为矛盾式当且仅当 ⇔ 为重言式当且仅当A⇔ 总结 为矛盾式当且仅当A⇔0; A为重言式当且仅当 ⇔1 为矛盾式当且仅当 为重言式当且仅当 说明:演算步骤不惟一, 说明 演算步骤不惟一,应尽量使演算短些 演算步骤不惟一

交大数理逻辑课件2-3 命题逻辑的等值和推理演算


9. Q (PQ) PBiblioteka 拒取式基本的推理公式
10. (PQ)(QR) PR 假言三段论 11.(PQ)(QR) P R 等价三段论 12. (PR)(QR) (PQ) R 13. (PQ)(RS)(PR) QS 构造性二难 14. (PQ)(RS)( QS) (PR) 破坏性二难 15. (QR) ((PQ) (PR)) 16. (QR) ((PQ) (PR))
附加前提证明法 ——举例
例如：证明下列推理。 前提： P(QR)，S∨P, Q 结论： S R 证明：(1) S P 前提 (2) S 附加前提引入 (3) P (1)(2) 析取三段论 (4) P (Q R) 前提 (5) Q R (3)(4) 假言推理 (6) Q 前提 (7) R (5)(6) 假言推理
((PQP Q
例：判断下面推理是否正确
（1）若天气凉快，小王就不去游泳。天气凉快，所 以小王没去游泳。 ③判断 ((PQ)P) Q是否为重言式 方法3：主析取范式法 ((PQ)P) Q = ((PQ)P)Q = (PQ) P Q = m11m0xmx0 = m11m00m01m00m10 = (0,1,2,3) = T ((PQP Q
(PQ(RS(PRQS 构造性二难
写出对应下面推理的证明
在大城市球赛中，如果北京队第三，那么如果上海队第 二，则天津队第四；沈阳队不是第一或北京队第三，上海队第 二。从而知：如果沈阳队第一，那么天津队第四。 解：设 (1) P (Q R) 前提 P：北京队第三 Q：上海队第二 (2) Q (P R) (1)置换 R：天津队第四 (3) Q 前提 S：沈阳队第一 (4) P R (2)(3)假言推理 前提：
P(QR)，S∨P, Q 结论： S R
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

P∨(P∧Q) = P
P∧(P∨Q) = P
理解等式: Venn图，自然语言
(P∨Q) = P∧Q
Venn图(理解集合间、命题逻辑中、部分 信息量间的一些关系)
对这些等式使用自然用语加以说明，将有助 于理解
如P表示张三是学生, Q表示李四是工人, 那么 (P∨Q)就表示并非“张三是学生或者李四是 工人”。这相当于说，“张三不是学生而且李 四也不是工人”，即可由P∧Q表示, 从而有 (P∨Q) = P∧Q
对蕴涵词、双条件词作否定有 (PQ) = P∧Q (PQ) = PQ = PQ = ∨F = P P∧T = P TP = P TP = P
还有 PF = P FP = P
9. 零律 P∨T = T P∧F = F
还有 PT = T FP = T
10. 补余律 P∨P = T P∧P = F
2.2.2 常用的等值公式
由于人们对、∨、∧更为熟悉，常将含有 和的公式化成仅含有、∨、∧的公式。这 也是证明和理解含有，的公式的一般方 法
公式11-18是等值演算中经常使用的, 也该 掌握它们, 特别是能直观地解释它们的成立
11. PQ = P ∨Q
通常对PQ进行运算时, 不如用P∨Q来 得方便。而且以P∨Q表示PQ帮助我们 理解如果P则Q的逻辑含义
注：根据该等值定理，证明两个公式等值，只要证 明由这两个公式构成的双条件式是重言式即可
“＝”作为逻辑关系符是一种等价关系
不要将“＝”视作联结词，在合式公式定义 里没有“＝”出现
A = B是表示公式A与B的一种关系。这种 关系具有三个性质: 1. 自反性 A = A 2. 对称性 若A = B, 则B = A 3. 传递性 若A = B, B = C, 则A = C 这三条性质体现了“＝”的实质含义。
例1中公式(P∧P)∨Q与Q的真值都同P无关 例2中P∨P, Q∨Q都是重言式, 它们的真值也
都与P、Q无关。
2.1.2 等值定理
定理 对公式A和B, A=B的充分必要条件是 AB是重言式。
A、B不一定都是简单命题, 可能是由简单命 题P1, …, Pn构成的. 对A, B的一个解释, 指的是对P1, …, Pn的一组具体的真值设定.
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)
注: 所有这些公式，都可使用真值表加以验证
3. 交换律 P∨Q = Q∨P P∧Q = Q∧P PQ=QP
严格的形式化的讨论见第三章所建立的公理 系统。
等值演算(考察逻辑关系符⇔(=))
等值定理、公式 联结词的完备集(由个别联结词表示所有联
结词的问题) 对偶式(命题公式的对偶性) 范式(命题公式的统一标准)
由真值表写命题公式(由T写、由F写)
推理演算(考察逻辑关系符⇒)
推理形式(正确推理形式的表示) 基本推理公式(各种三段论及五种证明方法) 推理演算(证明推理公式的第六种方法，使
4. 分配律 P∨(Q∧R) = (P∨Q)∧(P∨R) P∧(Q∨R) = (P∧Q)∨(P∧R) P(QR) = (PQ)(PR)
5. 等幂律(恒等律) P∨P = P P∧P = P PP = T PP = T
6. 吸收律 P∨(P∧Q) = P P∧(P∨Q) = P
7. 摩根律 (P∨Q) = P∧Q (P∧Q) = P∨Q
若AB为重言式, 则在任一解释下A和B都 只能有相同的真值, 这就是定理的意思。
证明
若A B是重言式, 即在任一解释下, A B 的真值都为T
依A B的定义只有在A、B有相同的值时, 才 有A B = T。于是在任一解释下, A和B都有 相同的真值, 从而有A=B。
反过来，若有A = B, 即在任一解释下A和B都 有相同的真值, 依A B的定义, A B只有为 真, 从而A B是重言式。
第二章 命题逻辑的等值和推理演算
推理形式和推理演算是数理逻辑研究的基本 内容
推理形式是由前提和结论经蕴涵词联结而成 的
推理过程是从前提出发，根据所规定的规则 来推导出结论的过程
重言式是重要的逻辑规律，正确的推理形式、 等值式都是重言式
本章对命题等值和推理演算进行讨论，是以 语义的观点进行的非形式的描述，不仅直观 且容易理解，也便于实际问题的逻辑描述和 推理。
例1: 证明(P∧P)∨Q = Q
证明: 画出(P∧P)∨Q与Q的真值表可看出等 式是成立的。
例2: 证明P∨P = Q∨Q
证明: 画出P∨P, Q∨Q的真值表, 可看出 它们是等值的, 而且它们都是重言式。
说明
从例1、2还可说明, 两个公式等值并不一定 要求它们一定含有相同的命题变项
若仅在等式一端的公式里有变项P出现, 那么等 式两端的公式其真值均与P无关。
还有 PP = P PP = P PP = F
Venn图(理解等式)
将P、Q理解为某总体论域上的子集合，并 规定：
P∧Q为两集合的公共部分(交集合) P∨Q为两集合的全部(并集合) P为总体论域(如矩形域)中P的余集
Venn图(理解等式)
从Venn 图，因P∧Q较P来得“小”, P∨Q较 P来得“大”，从而有
用推理规则) 归结推理法(证明推理公式的第七种方法，
常用反证法)
2.1 等值定理
若把初等数学里的＋、－、×、÷等运算符看作是 数与数之间的联结词，那么由这些联结词所表达的 代数式之间，可建立许多等值式如下： x2－y2 = (x＋y)(x－y) (x＋y)2 = x2＋2xy＋y2 sin2x＋cos2x = 1 ……
在命题逻辑里也同样可建立一些重要的 等值式
2.1.1 等值的定义
给定两个命题公式A和B, 而P1…Pn是出现于A和B 中的所有命题变项, 那么公式A和B共有2n个解释, 若对其中的任一解释, 公式A和B的真值都相等, 就 称A和B是等值的(或等价的)。记作A = B或 AB
显然，可以根据真值表来判明任何两个公式是否是 等值的