留侯论读后感:数理逻辑

您查询的关键词是：第一章数理逻辑  。如果打开速度慢，可以尝试快速版；如果想保存快照，可以添加到搜藏。

(百度和网页http://www.i07006.com/UpFile/UpAttachment/2009-5/2009510191420.pdf的作者无关，不对其内容负责。百度快照谨为网络故障时之索引，不代表被搜索网站的即时页面。)

---

数理逻辑
§1.1命题
§1.2.重言式
§1.3.范式
§1.4.联结词的扩充和归约
§1.5.推理规则和证明方法
§1.6.谓词和量词
§1.7.谓词演算的永真公式
§1.8.谓词演算的推理规则
1
§1.2.1 重言式
命题公式的永真式,永假式和可满
足式
举最简单例子,如左图真值表
P PP∨ PP∧ P
FT T F
TF T F
2
』完全指派设公式A中有n个不同的原子变元P1,…Pn,(n为
正整数).该变元组的任意一组确定的值(u1,…un)称为A关于
P1,…Pn的一个完全指派, 其中ui或为T,或为F.
』部分指派如果对于A中部分变元赋以确定值,其余变元没
有赋以确定的值, 则这样的一组值称为公式A的关于该变元
组的部分指派.
』成真指派凡使公式A取真的指派称为A的成真指派.
§1.2.1 重言式(永真式)
』永真式如果一个命题公式的所有完全指派均为成真指派,则该公式
称为永真式.
』永假式如果一个命题公式的所有完全指派均为成假指派,则该公式
称为永假式.
』可满足式既不是永真式,又不是永假式,则称此命题公式是可满足
式.
为什么需要考虑重言式的情况
1. 永真式的否定为永假式( T F), 永假式的否定为永真式
( F T).
2.二个永真式的析取,合取,蕴含,等价均为永真式.
3.永真式中存在许多有用的恒等式和永真蕴含式.
3
§1.2.2.恒等式
恒等式
如果对两个公式A, B不论作何种指派,它们真值均相同,则称A,
B是逻辑等价的, 亦说A等价于B.
并记作:A B
4
P Q P∨ PQ ∨ Q
F F T T
F T T T
T F T T
T T T T
例1 P∨ P Q∨ Q
例2 判断公式A: (P∨ Q)∧(P∨Q)与B: (P∨ R) ∧(P∨R)是否等价.
§1.2.2.恒等式
定理1.命题公式A B的充要条件是A B为永真式.
说明:
为等价关系符, A B表示A和B有等价关系;
A B不为命题公式,表示一永真式.
为联结词(运算符), A, B为命题公式,则(A B)也为
一命题公式.
5
由定理可知:A A(自反性)
若A B, 则B A(对称性)
若A B, B C,则A C(传递性)
例1 证明 P P; P →Q P ∨Q
§1.2.2.恒等式
下面列出15组等价公式
(1) 双重否定律 P P
(2) 等幂律P∨P P;P ∧P P
(3) 交换律P∨Q R∨P;
P ∧Q Q ∧P;
P Q Q P
(4) 结合律(P∨Q)∨R P∨(Q∨R);
(P ∧Q) ∧R P ∧(Q ∧R);
(P Q) R P ( Q R)
6
§1.2.2.恒等式
(5) 分配律
P ∧(Q∨R) (P ∧Q) ∨( P ∧R)
P ∨(Q ∧R) ( P ∨Q) ∧( P ∨R)
(6) 德.摩根律
(P ∨Q) P ∧ Q
(P ∧Q) P ∨ Q
(7) 吸收律
P ∨(P ∧Q) P
P ∧(P∨Q) P
7
§1.2.2.恒等式
(8) 蕴含律P →Q P ∨Q
(9) 等价律P Q (P →Q) ∧( Q →P)
(10)零律P ∨T T;P ∧F F
(11)同一律P ∨F P;P ∧T P
(12)互补律P∨ P T;P ∧ P F
(13)输出律P ∧Q →R P →(Q →R)
(14)归缪律(P →Q) ∧(P → Q) P
(15)逆反律P →Q Q → P
8
§1.2.2.恒等式
说明∨证明上述15组等价公式的方法可用真值表法,把 改为
所得的命题公式为永真式, 则 成立.
∨∧,∨, 均满足结合律,则在单一用∧,∨, 联结词组成的
命题公式中, 括号可以省去.
∨每个等价模式实际给出了无穷多个同类型的具体的命题公
式.
9
例如 (P ∨Q) ( P ∧ Q),
((P ∧Q) ∨(R ∧S)) ( (P ∨Q) ∧ (R ∨S),
((P→Q) ∨ R) ( (P →Q) ∧ R)
§1.2.3.永真蕴含式
永真蕴含式命题公式A称为永真蕴含命题公式B,当且仅当A→B是一
个永真式,记作: A B.
说明:A B读作A永真蕴含B,A蕴含B,A 能推得B
是关系符, A B不为命题公式.
证明方法, 真值表法, 由定义出发给出证明.
例:证明:P P∨Q; P ∧Q P
10
PQ P→(P∨Q) (P∧Q)→P
F F F T F F T F
F T F T T F T F
T F T T T F T T
T T T T T T T T
§1.2.3.永真蕴含式
下面给出常用的永真蕴含式
I1 P P∨Q( Q P ∨Q)加法式
I2P ∧Q P( P ∧Q Q)简化式
I3 P∧(P →Q) Q假言推理
I4 ( P →Q ) ∧ Q P拒取式
I5 P ∧( P∨Q ) Q析取三段论
I6 (P →Q) ∧(Q →R ) ( P →R)前提三段论
I7 (P →Q) ∧(R →S) (P ∧R →Q ∧S)
I8 (P Q ) ∧( Q R) ( P R )
I9 P P →Q善意的推定
11
§1.2.3.永真蕴含式
I10 Q P→Q
I11 (P →Q) P
I12 (P→Q) Q
I13 (P∨Q)∧( P →R)∧(Q→R) R构造性两难推理
PQP→Q
FFT
FTT
TFF
TTT
12
§1.2.3.永真蕴含式
13
证明上述永真蕴含式的方法有下述三种:
(1) 把 关系符改为→联结词,证明它为永真式.
(a) 真值表法
(b) 命题演算法
(2) 找出使条件命题前件为T的所有真值指派,试看能否导
致后件均为T,若为T,则永真蕴含关系成立(肯定前件,推出
后件为真).
(3) 找出使条件命题的后件均为F的所有真值指派,试看前件
的所有真值是否为F,若是则蕴含成立.(否定后件,推出前件
为假)
§1.2.3.永真蕴含式
例1P ∧( P→Q) Q
例2 Q ∧(P→Q) P
例3 (P →Q) ∧(R →S) (P ∧R →Q ∧S)
例4 (P →Q) ∧(R →S) (P ∧R →Q ∧S)
14
§1.2.3.永真蕴含式
定理1 设A,B是二个命题公式,A B的充分必要条件是
A B 且B A.
(此定理在 和 之间建立了相应的联系)
定理2 给定命题公式A, B, C,若A B,且B C,则A C.
推论若A B1, B1 B2…Bm B, 则A B
定理3给定命题公式A, B, C, 若A B, A C, 则A
( B ∧C)
15
§1.2.3.永真蕴含式
H1, H2 ,…,Hm,Q均为命题公式, 若(H1 ∧H2∧…Hm)
C,则称H1, H2,…, Hm,共同蕴含C,并记作H1,
H2 ,…,Hm C.
定理4 若(H1 ∧H2∧…Hm), H C, 则( H1 ∧H2
∧…Hm) ( H →C).
(CP 规则)
16
§1.2.3.永真蕴含式
讨论一下永真式, 可得出以下三个结论:
∨若一个命题公式等价于另一个永真式,则该公式一定
为永真式.
∨若一个永真的命题公式永真蕴含另一个命题公式,则
此命题公式一定也为永真式.
∨若一个永假的命题公式P永真蕴含一个命题公式Q,则
公式Q可能是永真式,永假式或可满足的.
17
§1.2.5 代入规则和替换规则
代换实例给定一命题公式B, 其中P1, P2 …Pn是B中的原子命题
变元.
若
∨用某些命题公式代换B中的原子命题变元Pi
∨用命题公式Ai代换Pi, 则必须用Ai代换B中的所有Pi
由此而得到的新命题公式A称为命题公式B的代换实例.
代入规则重言式中的某个命题变元出现的每一处均代入同一公
式后, 所得的仍是重言式.
18
§1.2.5 代入规则和替换规则
讨论∨用命题公式只能代入原子命题变元,而不能去代换分
子命题公式;
∨要用命题公式同时代入同一个原子命题变元;
∨一个命题公式的代换实例有许多个,但不一定都等价
于原来的命题公式;
∨永真式的代换实例仍为永真式, 反之代换实例为永真
式时, 则不能断定原公式也一定是永真式.
19
§1.2.5 代入规则和替换规则
例1
B: P →( Q ∧P ) 若用(R S)代换B中的P,
得A: (R S) →( Q ∧(R S))是B的代换实例
而A': (R S) →( Q ∧P) 不是B的代换实例.
例2
P → Q的代换实例有:
(R ∧ S)→ M, (R∧ S) →P, Q → ( P→ Q)等
所以,一个命题公式的代换实例有无限个.
20
§1.2.5 代入规则和替换规则
给定一命题公式A, A'是A的任何部分.若A'也是一命题
公式, 则称A'是A的子命题公式.
例1 A (P∨Q) →( Q ∨( R ∧ S) )
其子命题公式有: P, Q, R, S, (P ∨Q), ( R ∧
S ), (Q∨( R ∧ S) ), (P∨Q)→( Q ∨( R ∧
S))等.
替换规则给定一命题公式A, A'是A的子公式.设B'
是一命题公式,若A' B',并用B'取代A中的A', 从而生
成一新的命题公式B,则A B.
21
§1.2.5 代入规则和替换规则
应用代入规则和替换规则和已有的重言式可以得出新的
重言式.
例1 证明: P→(Q→R) ( P ∧Q)→R
例2 证明: ((P∨Q)∧ ( P∧( Q∨ R))) ∨( P∧ Q)
∨( P ∧ R) 为一永真式
课本P11-例2
22
§1.2.6 对偶原理
对偶式给定二个命题公式A和A*, A和A*中仅有∧,∨, .
若用∧代换∨, 用∨代换∧, 用T代换F, 用F代换T, 则其中一个
命题公式可由另一个命题公式得来, 称A和A*是互为对偶的,而
联结词∧和∨也是互为对偶的.
例: 写出下列命题公式的对偶式:
A : P∨(Q ∧R)
对偶式A*: P ∧( Q∨R)
23
§1.2.6 对偶原理
讨论定义
∨若命题公式中有联结词→, 则必须把化成由联结词∧, ∨组成
的等价的命题公式,然后求它的对偶式
例求(P→Q)∧(P→R)的对偶式
( P ∨Q) ∧( P ∨R) 对偶式: ( P ∧Q) ∨( P ∧R)
∨在写对偶式时, 原命题公式中括号不能省去, 必须按优先级的次
序画上括号,并在求其对偶式时仍将保留括号.
例(P∧Q)∨R对偶式写成(P∨Q)∧R,
而不能写成P∨Q∧R
24
§1.2.6 对偶原理
设A和A*为对偶式P1, P2…Pn是出现在A和A*中的所有原子命题变元,
于是有:
A(P1,P2…Pn) A*( P1, P2 … Pn) ——(1)
A( P1, P2… Pn) A*(P1, P2 …Pn)——(2)
证明: 由德.摩根定理
( P∨Q ) P ∧ Q——(1)
( P ∧Q ) P ∨ Q ——(2)
对于具体的命题公式,通过连续使用德.摩根定律可证.
德.摩根推广原理
不难看出, 一个命题公式的否定等价于它的对偶式, 且把变元的否定
代替每一个变元.
25
§1.2.6 对偶原理
例:设A(P, Q, R) P ∧ (Q∨R), 验证上述定理.
证明:
(1) A( P, Q, R) P ∧ Q ∧ R
A( P,Q, R) P∨Q∨R
A*(P, Q, R) P∨ Q∨ R
A*( P, Q, R) P∨Q∨R
(2) A( P, Q, R) P ∧Q ∧R
A*(P, Q, R) ( P∨Q∨ R)
P ∧Q ∧R
有A( P, Q, R) A*(P, Q, R)
26
§1.2.6 对偶原理
若A B, 且A, B为命题变元P1, P2…Pn及联接词∧,∨, 构成的公
式,则A* B*成立.
若A B, 且A, B为命题变元P1, P2…Pn及联接词∧,∨, 构成的公
式,则B* A*成立.
若P∨F P , 则P ∧T P
若P∨T T, 则P ∧F F
作业:习题1.2 P11-154, 7, 9
27
第一章数理逻辑
§1.1命题
§1.2.重言式
§1.3.范式
§1.4.联结词的扩充和归约
§1.5.推理规则和证明方法
§1.6.谓词和量词
§1.7.谓词演算的永真公式
§1.8.谓词演算的推理规则
28
1.3.范式
范式命题公式的一种标准表示形式称为范式.
一些定义
∨设命题变元为P, Q, R,则P∨Q∨R的析取式称为和,P∧Q∧R的合
取式称为积.
∨命题公式的变元和变元的否定之积称为基本积,而变元和变元的
否定之和称为基本和.
例设P,Q为二个命题变元, 则P∨P, Q∨Q, P∨Q, Q∨ P,
P∨Q, P∨ Q称为基本和; P∧P,Q∧Q, P∧Q, Q∧ P, P∧Q,
P∧ Q称为基本积.
29
∨基本和或基本积中的子公式,称为此基本积(和)的因子.
例: Q∧P∧ P的因子有: Q, P, P, Q∧P,P∧ P
1.3.范式
定理1 一个基本积必定是永假式的充分必要条件是:至少包含一
对因子, 其中一个因子是另一个的否定.
定理2 一个基本和必定为永真式的充要条件是,它至少包含一对
因子,其中一个因子是另一个的否定.
析取范式与给定命题公式等价的一个公式,如果是由基本积之和组成,
则称为命题公式的析取范式.
并记为P P1∨P2 ∨…∨Pn(n∈I+)
其中P1,P2…Pn均为基本积.
30
1.3.范式
合取范式与给定命题公式等价的一个公式,如果它是由基本
和之积所组成,则称它是给定命题公式的合取范式.
并表示成:Q Q1∧Q2∧…∧Qn,(n∈I+),其中Q1, Q2, …
Qn均为基本和.
31
讨论定义:
∨一个命题公式的析(合)取范式不是唯一的, 但同一命题
公式的析(合)取范式一定是等价的.
∨若一个命题公式的析(合)取范式中每一个基本积(和)均
为永假(真)式, 则该公式也一定为永假式.
1.3 范式
析取范式求解方法可按下列三步(或四步)进行:
1. 利用等价公式:化去"→"," "联结词,把命题公式变为与
其等价的用{ ,∧,∨}表达的公式.
例: P→Q P∨Q
P Q (P∧Q)∨( P∧ Q)
( P∨Q)∧(P∨ Q)
2. 深入到原子命题变元之前,并使变元之前最多只有一个
词.
例: ( P∨ Q) P∧ Q P∧Q
3. 利用∧对∨的分配,将公式化成为析取范式.
4. 去掉永假项得最简析取范式.
32
1.3.范式
例1 求 (P∨Q) (P∧Q) 的析取范式:
求一个命题公式的合取范式和求析取范式的方法类似:
第1, 2步相同;
第3步,利用∨对∧的分配;
第4步,去掉永真项.
例2求Q∨ (P→Q)∨ (P∨Q)的合取范式
33
1.3 范式
主析取范式对给定的命题公式, 仅含有极小项的析取的等价式称为
给定命题公式的主析取范式.
在n 个变元的基本积中,若每个变元及其否定并不同时存在,且二者之
一出现一次且仅出现一次,则称此基本积为极小项.
34
对一个命题变元讲, 极小项有21=2个, 即P, P
对二个命题变元, 极小项有22=4个, 即P ∧Q, P ∧Q, P ∧
Q, P ∧ Q
n个命题变元构成的不同极小项有2n个(n∈I+), 每个极小项
为真的赋值仅有一个.
1.3 范式
在真值表中, 一个公式的真值为T的指派所对应的极小项的析
取, 即为此公式的主析取范式.
例求出P →Q, P∨ Q, (P∧Q), P∧ Q的主析取范式
35
PQP∨ Q (P∧Q) P∧ QP→Q
FF T T F T
FT F T F T
TF T T T F
TT T F F T
P →Q ( P ∧ Q ) ∨( P ∧Q ) ∨( P ∧Q )
P ∨ Q ( P ∧ Q ) ∨( P ∧ Q ) ∨( P ∧Q )
1.3 范式
36
讨论:
(1) 只要命题公式不是永假式, 则可以根据该命题公式
的真值表直接写出其主析取范式,且是唯一的.方法是
找出该公式为T的行, 对应写出极小项的析取式,
(2) 若命题公式是含有n个变元的永真式, 则它的主析取
范式一定含有2n个极小项.
(3) 若二个命题公式对应的主析取范式相同, 则二个命
题公式一定是等价的.
(4) 命题公式的主析取范式中极小项的个数等于真值表
中真值为T的行数.
1.3 范式
下面介绍直接求命题公式主析取范式的方法,分四步:
(1) 将命题公式化归为与其等价的析取范式;
(2) 除去永假项, 合并相同项( P∧P∧Q P∧Q ), 变为最
简析取范式;
(3) 利用添变元的方法,将所有基本积变为极小项.
(4) 合并相同的极小项变为一项.
例:二个变元P, Q,用∧对∨的分配添项
P P ∧( Q ∨ Q ) ( P ∧Q ) ∨( P ∧ Q)
Q Q ∧( P ∨ P ) ( P ∧Q ) ∨( P ∧Q)
37
例求(P∧(P→Q))∨Q的主析取范式
1.3 范式
在n个变元的基本和中, 若每个变元与其否定,并不同时
存在且二者之一出现一次且仅出现一次, 则称这种基本
和为极大项.
主合取范式对给定的命题公式,仅含有极大项的合取
的等价公式式称为给定命题公式的主合取范式.
例:有二个变元P, Q的极大项有22=4个, (P∨Q), (P ∨ Q ),
( P∨Q), ( P∨ Q)
有n个变元,则有2n个极大项(n∈I+).
38
1.3 范式
在真值表中,一个公式的真值为F的指派所对应极大项的合
取, 即为此公式的主合取范式.
例求出(P→Q), (P∨Q), (P∧Q), (P∧Q)的主合取范式.
PQP∨Q (P∧Q) P∧QP→Q
FF F T F T
FT T T F T
TF T T F F
TT T F T T
P ∨Q P ∨Q( P →Q ) ( P ∨Q )
P ∧Q (P ∨Q) ∧(P ∨ Q ) ∧( P ∨Q)
39
1.3 范式
讨论
(1)与命题公式等价的主合范式中极大项的个数等于其真值
表中真值为F的行数.
(2)只要命题公式不是永真式, 则一定可以写出与其等价的
唯一的主合取范式.
(3) 已知一个命题公式的主析取范式, 则可写出与其等价的主
合取范式来.
(4) 对应于有n个变元的命题公式, 则一定有主析取范式极小
项数+主合取范式极大项数=2n
例:P∨ Q ( P∧ Q)∨(P∧ Q)∨(P∧Q)主析取范式
P∨ Q主合取范式
40
1.3 范式
下面介绍直接命题公式主合取范式的方法:
(1) 化为与命题公式等价的合取范式;
(2) 除去真值为T的析取项和除去析取项中相同变元且只保留
一个,简化合取式;
(3) 添项, 使析取项均变为极大项;
例如P, Q为二个变元, 即
P P∨(Q∧ Q) (P∨Q) ∧(P∨ Q)
(4) 合并相同的极大项, 保留一项.
例:求P∧( P →Q ) ∨Q的主合取范式
41
1.3 范式
为了确保主范式的唯一性,我们需要做如下安排:
(a) 各命题变元的位置安排一固定次序;
(b) 对极小项, 极大项安排一个次序.
对于有n个变元的命题公式, 则最多可有2n个极小项, 用m0
∨m1 …∨m2n-1来表示.
例:设一命题公式有五个变元,P0,P1,P2,P3,P4 (次序已定),则必可
写出25=32个极小项,
如m(11)十=m(01011) =( P0∧P1∧ P2∧P3∧P4)
m(18)十=m(10010) =( P0∧ P1∧ P2∧P3∧ P4)
42
1.3 范式
极小项m(i)十的表示方法:
(a) 把(i)十变换成等价的(J0, J1…Jn-1) 二;
(b) 由二进制写出其对应的极小项;
43
用M0, M1,…, M2n-1表示有n个变元的命题公式的极大项.
极大项的表示方法:
(a) 把(i)十变换成等价的(J0, J1 …Jn-1)二;
(b) 由二进制数写出其对应的极大项;
极大项和极小项编码约定刚好相反.
极大项的构造
F/0 对应着变量本身;
T/1 对应着变量否定.
极小项的构造
F/0对应着变量的否定;
T/1对应着变量本身.
1.3 范式
例1求(P∧Q)∨( P∧R)的编码表达式(设P, Q, R次序已
定)
44
例3 写出( P ∨ Q)的主析取范式和主合取范式编码表示.
极大项与极小项性质
mi ∧mj F(i ≠j)
Mi∨Mj T(i ≠j)
…(见书P19)
例2 求(P∧Q)∨( P∧R)的极大项编码表示(设P,Q,R次序
已定)
1.3 范式
一个原子命题变元有4个不同的真值表(221
);
二个原子命题变元有16个不同的真值表(222
);
n个原子命题变元有22n
个不同的真值表;
对于含有n个变元的命题公式,必定可写出个主范式
, 若排除永真式或永假式,则实际可写出( 22n
-1) 个
主析(合)范式.
主范式的个数
45
1.3 范式
(1) 真值表法对于变元的所有真值指派,看对应命题公
式的真值.
(2) 命题演算方法化简命题公式至最简式, 看是否存
在和(P∨ P), (P∧ P)等价, 若否则为可满足的.
(3) 范式方法找到其主析取和主合取的形式.
如何判定命题公式为永真式, 永假式和可满足或二
个命题公式等价, 归纳有三种方法:
作业习题1.3 2, 3