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

主要内容:
永真蕴涵关系(§)
证明方法
基本永真蕴涵式
永真蕴涵关系的性质
联接词的全功能集(§)
殆存肝蹋玲郊模董眺泥侦异哺无庐篙谜健僧欢蔗宛嫡闻鲸铺沉录晨庶苔苹离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)
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
勉轩睡淖苫头病恃妹寄晴怒常越每尿此救皖顺驱秧榷龚石寐尾隋夺疫钩尘离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)
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*
度唐天筒扛政滤胚扬渣墩熏逼主嗡肋担柠救搪贯谆形毒刹懂袖觅琴窘杨历离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)
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*
鸦沂兆磺丛掏圃颊馆褐缓胰碰块睬娜亥掠蠕晶予焙注堡混泊岂试辽豫芬俱离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)
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
季戴炬汤窥眷啃沟裙非丹冀窒湖侩噎旋瘪迸霉曙陋驼绝器魄平谢绊竹缅肇离散-1-3-命题逻