离散-1-3-命题逻辑(1).ppt

主要内容:
永真蕴涵关系(§)
证明方法
基本永真蕴涵式
永真蕴涵关系的性质
联接词的全功能集(§)
1
§ 永真式 (1)
定义:若 A→B 是永真式,则称 A永真蕴涵 B,记作 A  B
证明方法: 真值表、等价推导、前真导后真、后假导前假
例1: 证明 P∧(P→Q) Q
证明:若 P∧(P→Q)为 T,
则P为T且(P→Q)为T。
∴ Q 也为 T。
因此,P∧(P→Q)→Q 是永真式,
故 P∧(P→Q)Q。
例2:证明(P→Q)∧(Q→R) P→R
证明:若 P→R 为F,
则 P为T,R为F
若Q为T,则 Q→R为F
∴(P→Q)∧(Q→R)为F
若Q为F,则 P→Q为F
∴(P→Q)∧(Q→R)为F
∴((P→Q)∧(Q→R))→P→R 永真,
因此,(P→Q)∧(Q→R)P→R
2
基本永真蕴涵式
永真蕴涵关系的性质:
自反性:对任意公式 A, 有 AA
传递性:若 AB, BC, 则 AC
AB 当且仅当 AB 且 BA
若 AB, 则┐B┐A
证明:若┐B为T,
§ 永真式 (2)
则 B为F,
∵ AB,
∴ A为F
∴┐A为T,
因此,┐B┐A
: 设 A,B 为仅含┐,∧,∨的公式,
若 AB,则 B*A*
3
定理:设 A,B 为仅含┐,∧,∨的公式, 若 AB, 则 B*A*
证明:设 P1,…, Pn 为出现在A和B的所有变元,AB,
则有┐B┐A
∴┐B→┐A是永真式
∵┐B→┐AB*(┐P1,…, ┐Pn)→A*(┐P1,…, ┐Pn)
∴ B*(┐P1,…, ┐Pn)→A*(┐P1,…, ┐Pn)永真。
现用┐Pi取代Pi (1≤i≤n), 得到上式的一个代入实例:
B*(P1,…, Pn )→A*(P1,…, Pn )
即 B*→A* 仍为永真式
∴ B*A*
4
§ 联接词的全功能集(1)
定义符号系统的重要问题:“完备性”论证。
{ ┐,∧,∨,→,}是否能表达所有公式?
含一个变元公式的真值表
A0
0
0
A1
0
1
A2
1
0
A3
1
1
P
0
1
含两个变元公式的真值表
P Q
0 0
0 1
1 0
1 1
B0
0
0
0
0
B1
0
0
0
1
B2
0
0
1
0
B3
0
0
1
1
…
…
B15
1
1
1
1
A0 P∧┐P
A1 P
A2┐P
A3 P∨┐P
5
联接词全功能集:
设C是联接词集合,若任何公式均可用仅含C中联接词的公式等价地
表示,则称C是联接词全功能集;
设C是联接词全功能集,如果从C中删去任意一个联接词,C就不是
全功能集,则称C是联接词的极小全功能集。
{ ┐,∧,∨,→,}是联接词全功能集,但不是极小的。
{ ┐,∧},{ ┐,∨}都是极小全功能集。
(证明方法P33)
与非↑,或非↓
定义:P↑Q ┐(P∧Q)
P↓Q ┐(P∨Q)
§ 联接词的全功能集(2)
»基本恒等式
» {↑}是全功能集
6
§ 联接词的全功能集(3)
{↑},{↓}是极小全功能集.
如