左孝凌离散数学课件.ppt

由上表可知,9个联结词足以直接表达命题之间的各种联系.二元运算中，9个联结词并不都是必要的。PQPQP?Q┓QQ→P┓PP→QPQT0011111111010000111110001100111101010101定义：在一个联结词的集合中,如果一个联结词可由该集合中的其它联结词定义,则称此联结词为冗余联结词,否则称为独立联结词.不含冗余联结词的联结词组称为最小联结词组.说明:最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。对于9个联结词的集合{┐,?,?,→,?,,,,}由于(1)P?Q?(P→Q)?(Q→P)(2)P?Q?┐P?Q(3)P?Q?┐(┐P?┐Q)(4)P?Q?┐(┐P?┐Q)*(5)(PQ)??(P?Q)(6)P↑Q??(P∧Q)(7)P↓Q??(P∨Q)(8)PQ??(P?Q)故任意命题公式都可由仅包含{┐,?}或{┐,?}的命题公式等价代换.即9个联结词的集合中至少有七个冗余联结词.又注意到联结词{┐,?}和{┐,?}不再有冗余联结词,故{┐,?}或{┐,?}为最小联结词组.但实际中为了使用方便,命题公式常常同时包含{┐,?,?}.例1:试证{↑}是最小联结词组. 证：┐P?┐(P?P)?P↑PP?Q?┐┐(P?Q)?┐(P↑Q)?(P↑Q)↑(P↑Q)P?Q?┐(┐P?┐Q)?┐((P↑P)?(Q↑Q))?(P↑P)↑(Q↑Q)例2.试证{┐，→}是最小联结词组证：P?Q?┐(┐P?┐Q)?┐(P→┐Q)P?Q?┐(┐P)?Q?┐P→Q小结:本节主要介绍了四种新的联结词及最小联结词组.作业:1.P29(1),(2),(4) 2.预习§1.7思考题:1.何谓命题公式的(主)析(合)取范式?2.命题公式的(主)析(合)取范式唯一吗?3.为何要将命题公式化为与之等价的主析(合)取范式?4.如何将命题公式化为与之等价的主析(合)取范式?5.两个等价的命题公式其(主)析(合)取范式有何关系?*离散数学(DiscreteMathematics)张捷DualityPrinciple)1.7.1对偶式与对偶原理(DualisticFormulaConjunctiveNormalFormsofaPropositionalFormula)命题公式的析(合)取范式(TheDisjunctiveDisjunctiveConjunctiveNormalFormofaPropositionalFormula)命题公式的主析(合)取范式(ThePrincipal1.7.1对偶式与对偶原理(DualisticFormulaDualityPrinciple)在第四节(1.4)中我们给出了命题定律(P15表1-4.8),其中多数等价公式都是成对出现的,每一对公式的不同之处是将?与?互换,我们把这样的公式称为是对偶的.定义1.7.1:设命题公式A仅含有联结词┐,?,?,在A中将?,?，F，T分别换以?，?，T，F得出公式A*，则A*称为A的对偶公式。说明:(A*)*=A例1.(┐P?(Q?R))*=┐P?(Q?R)01020304((P?Q)?1)*=((P?Q)?0)由P↑Q?┐(P∧Q)和P↓Q?┐(P∨Q)可知05(P↑Q)*=P↓Q关于对偶式我们有如下两个定理:定理1.7.1:设A，A*是对偶式，P1,P2,…,Pn是出现于A和A*中的所有原子变元,则(1)┐A(P1,P2,…,Pn)?A*（┐P1,┐P2,…,┐Pn）(2)A(┐P1,┐P2,…,┐Pn)?┐A*（P1,P2,…,Pn）证明:因为┐(P?Q)?┐P?┐Q┐(P?Q)?┐P?┐Q所以┐A(P1,P2,…,Pn)?A*（┐P1,┐P2,…,┐Pn）同理┐A*(P1,P2,…,Pn)