L2命题逻辑2 离散数学

命题逻辑二LuChaojun,SJTU22主要内容命题与命题联结词命题公式等值演算命题公式的范式联结词的功能完全集永真蕴涵式命题逻辑推理LuChaojun,SJTU3等值关系一种重要的数学论证方法是:将一个命题用另一个等值命题替换.两个命题公式A和B若在任一赋值下的真值都相同,则称A和B等值(equivalence).记作AB.例如:ab(a)b这两个公式语法上是不同的,但语义上相同.LuChaojun,SJTU4与的关系等值定理:对公式A和B, AB

iff

AB是永真式证明:若AB永真,则在任一赋值下其真值都为1,依的定义知A和B真值相同.

若AB,则在任一赋值下A和B都有相同的真值,依的定义即AB真值为1.注:教材中干脆用此关系作为等值的定义.LuChaojun,SJTU5与的不同从形式系统角度看是系统内的符号,

AB是系统内的命题公式.(语法)是系统外的符号,

AB不是命题公式!在系统外观察系统内两个公式是否等值.(语义)从真假性来看AB是表示A和B是否等值的一个命题.只有AB为真,才肯定A和B等值.但AB可为假.AB则肯定地表示A和B等值.LuChaojun,SJTU6补充:等值关系的性质和数学里的等号一样,具有下面三个性质:

1.自反性:

A

A 2.对称性:若A

B,

则B

A 3.传递性:若A

B且B

C,则A

C这三条性质刻画了两事物“等同”、“同一性”概念.满足这三条性质的关系称为等价关系.在等值概念下,命题常量可看成只有两个:1,06LuChaojun,SJTU7如何证明两公式等值?真值表技术利用等值定理利用基本等值式进行等值演算7LuChaojun,SJTU8例:利用真值表证明等值证明(aa)b

b.证:列出真值表即可看出等式成立.abaa(aa)b0000010110001101LuChaojun,SJTU9例:利用等值定理证明等值证明(ab)

(ab).根据等值定理,可转化为证明 (ab)(ab)是永真式.比如列出此公式的真值表.这样本质上还是真值表技术.还可利用重言式推理系统.9LuChaojun,SJTU10基本等值式1.结合律 (AB)C

A(BC) (AB)C

A(BC) (A

B)

C

A

(B

C)2.交换律

AB

BA

AB

BA

A

B

B

A

注意:没有的结合律和交换律.

LuChaojun,SJTU11基本等值式(续)3.分配律

A(BC)(AB)(AC)

A(BC)(AB)(AC)

A(BC)(AB)(AC)4.吸收律

A(AB)

A

A(AB)

ALuChaojun,SJTU12基本等值式(续)5.关于否定词的等值式

(A)

A (对合律) (AB)

AB (DeMorgan律)

(AB)

AB (DeMorgan律)

(AB)

A

B

(AB)

AB

AB

(AB)(AB)基本等值式(续)6.相同命题变量的等值式AA

A(等幂律)AA

A(等幂律)AA

1AA

1AA

1(排中律)AA

0(矛盾律)AA

AAA

AAA

0此处的1/0代表任意真值恒为1/0的命题公式.LuChaojun,SJTU13LuChaojun,SJTU14基本等值式(续)7.部分赋值的等值式 A0

A A1

A

1A

A A0

A

1A

A

0A

A

A11

A00

A11 0A

114LuChaojun,SJTU15基本等值式(续)8.关于的等值式AB

(A)B

(AB)AB

BA[假言易位]A(BC)(AB)C[合取前提]A(BC)

B(AC)[交换前提](AC)(BC)(AB)C[析取前提](AB)(AB)

A[归谬论]A(BC)(AB)(AC)A(BC)(AB)(AC)基本等值式(续)9.关于的等值式AB

ABAB

(AB)(AB)[同真或同假]AB

(AB)(AB)[一真一假]AB

(AB)(BA)[充分必要]由于,,更易理解和处理,常利用8和9类的等值式将含和的公式改写成仅含有,,的公式.LuChaojun,SJTU16置换规则定理:设AA,BB,则有(1)

AA(2)AB

AB(3)AB

AB(4)AB

AB(5)AB

AB置换:将公式的一部分用等值公式替换.定理(置换规则):设BC.若将A中出现的一个或几个B换成C后得到公式A,则有AA.LuChaojun,SJTU17LuChaojun,SJTU18等值演算等值演算:利用等值定律,基本等值式以及替换规则进行公式推演.一般是将两边的公式推演成相同形状的公式,从而证明等值式成立.例:等值演算证明(a(bc))(bc)(ac)

c.证明:左端(a(bc))((ba)c) (分配律)

((ab)c)((ba)c)

(结合律)

((ab)c)((ba)c) (德摩根律)

((ab)(ba))c

(分配律)

((ab)(ab))c

(交换律)

1c (置换)

cLuChaojun,SJTU19LuChaojun,SJTU20对偶式和内否式观察下面两个等值式(分配律):A(BC)(AB)(AC)A(BC)(AB)(AC)可见,命题逻辑公式存在“对偶”规律.限制性公式:公式中只用到联结词,,.将限制性公式A中的,,1,0分别以,,0,1替换,所得公式称为A的对偶式A*.

将限制性公式A中所有肯定形式出现的变元x换成x,所有否定形式出现的变元x换成x,所得公式称为A的内否式A－.其实,求A－时A不必是限制性公式,即可包含和.LuChaojun,SJTU21A*和A－的性质定理(1)(A*)*

A (A－)－

A(2)(AB)*A*B* (AB)－A－B－(3)(AB)*A*B* (AB)－A－B－定理(1)(A)*(A*) (A)－

(A－)(2)A

(A*)－(DeMorgan律的一般形式)(3)(A*)－(A－)*LuChaojun,SJTU22命题公式的对偶性质推论:若AB,则(A*)－(B*)－.推论:若AB,则

A*B*.一旦证明了两公式等值,则同时证明了它们的对偶式也等值.LuChaojun,SJTU2323主要内容命题与命题联结词命题公式等值演算命题公式的范式联结词的功能完全集永真蕴涵式命题逻辑推理LuChaojun,SJTU24公式有没有标准形式?命题公式的数量是无穷多的.即便只有一个命题变量x,也可以写出x,xx,xxx,x

xxx,……但若按等值关系对全体公式进行划分,n个命题变量所能形成的不同公式仅有22n个.(Why?)问题:与命题公式A等值的公式能否都化为某种标准形式?借助于标准形容易判断两个公式是否等值.借助于标准形容易判断公式是否永真式或永假式.LuChaojun,SJTU25简单析(合)取式一个命题符号a及其否定a统称为文字.由文字利用()联结而成的公式称为简单析(合)取式.简单析取式例:x,x,xy,xyx简单合取式例:x,x,xy,xyx定理(1)一个简单析取式是永真式iff它同时包含一个命题符号及其否定.(2)一个简单合取式是矛盾式iff它同时包含一个命题符号及其否定.析(合)取范式由若干个简单合取式利用联结而成的公式称为析取范式.形如:

A1

A2

…An(诸Ai是简单合取式)由若干个简单析取式利用联结而成的公式称为合取范式.形如:A1

A2

…An(诸Ai是简单析取式)定理(1)一个析取范式是矛盾式iff它的每个简单合取式都是矛盾式.(2)一个合取范式是永真式iff它的每个简单析取式都是永真式.LuChaojun,SJTU26LuChaojun,SJTU27范式存在定理及求法范式定理:对任一命题公式都存在与之等值的析取范式和合取范式.等值变换法求范式(1)消去,(2)深入到命题符号之前(3)()深入至此已是范式.(4)

(可选)化简27LuChaojun,SJTU28求范式(1):消去,方法:利用下列等值式AB

AB

AB

(AB

)(AB

) [用于求析取范式]AB

(AB

)(AB

) [用于求合取范式]例:求(xy)(xy)的析取范式(xy)(xy)((xy)(xy))((xy)(xy))28LuChaojun,SJTU29求范式(2):否定词深入方法:利用下列等值式(A

B

)

A

B

(A

B

)

A

BA

A例 (xy)(xy)((xy)(xy))((xy)(xy))

(xy

xy)((xy)(xy))29LuChaojun,SJTU30求范式(3):合(析)取词深入方法:利用分配律A(BC)(AB)(AC)[用于求析取范式]A(BC)(AB)(AC)[用于求合取范式]例 (xy)(xy)((xy)(xy))((xy)(xy))

(xyxy)((xy)(xy))(xy

xy)

(xx)(xy)(yx)(yy)30LuChaojun,SJTU31求范式(4):(可选)化简方法:利用下列等值式消去矛盾式A

0

0A

0

A例 (xy)(xy)((xy)(xy))((xy)(xy))

(xyxy)((xy)(xy))(xy

xy)(xx)(xy)(yx)(yy)(xy)(xy)31LuChaojun,SJTU32范式的用途判断A是否永真式求A的合取范式,若每个简单析取式都含有某个变元及其否定(如x和x),则A是永真式.判断A是否矛盾式求A的析取范式,若每个简单合取式都含有某个变元及其否定(如x和x),则A是矛盾式.判断A

B?求A和B的同一种范式,看是否相同.这里有问题:范式唯一吗?32LuChaojun,SJTU33极小项与极大项设公式只涉及n个命题变量x1,…,

xn.极小项:n个文字的简单合取式,诸xi以xi或xi形式出现且只出现一次,且xi出现在左起第i个位置.极小项有2n个:根据对应的成真赋值,可记为m0…00=x1

…xn1

xnm0…01=x1

…xn1

xnm0…10=x1

…xn1

xn…m1…11=x1

…xn1

xn设公式只涉及n个命题变量x1,…,

xn.极大项:n个文字的简单析取式,诸xi以xi或xi形式出现且只出现一次,且xi出现在左起第i个位置.极大项有2n个:根据对应的成假赋值,可记为M0…00=x1

…

xn1

xnM0…01=x1

…

xn1xnM0…10=x1

…xn1xn…M1…11=x1…xn1xnLuChaojun,SJTU34极小/大项的性质每个极小项只在一个赋值下为真.一个赋值不能使两个极小项都为真.两个极小项的合取为0极小项两两不等值.若A由k个极小项的析取组成,则其余2nk个极小项的析取就是A.若k=2n,则A是重言式.每个极大项只在一个赋值下为假.一个赋值不能使两个极小项都为假.两个极大项的析取为1极大项两两不等值.若A由k个极大项的合取组成,则其余2n

k个极大项的合取就是A.若k=2n,则A是矛盾式.34LuChaojun,SJTU35主范式主析取范式:仅由极小项构成的析取范式.定理:任何非永假的命题公式都存在唯一与之等值的主析取范式.主合取范式:仅由极大项构成的合取范式.定理:任何非永真的命题公式都存在唯一与之等值的主合取范式.LuChaojun,SJTU36主范式的求法(1)利用基本等值式(1)先求一个析取范式.(2)若简单合取式A中未出现命题变量x,则通过AA(xx)

(Ax)(Ax)来补足x.(3)消去重复出现的变量,矛盾式及重复出现的极小项.利用基本等值式(1)先求一个合取范式.(2)若简单析取式A中未出现命题变量x,则通过AA(xx)

(Ax)(Ax)来补足x.(3)消去重复出现的变量,永真式及重复出现的极大项.36LuChaojun,SJTU37例:基本等值式方法例:求xy的主析取范式(1)xyxy(2)x

x

(yy)(xy)(xy)y

y(xx)

(xy)(xy)(3)消去一个(xy)于是:xy

m00

m01m11例:求(xy)的主合取