离散数学 命题逻辑3.ppt

第一章命题逻辑,范式,命题与联结词,析取范式与合取范式主析取范式和主合取范式,范式的引入,同一命题公式可以有多种相互等价的表达形式，例如：PQPQ(PQ)方便研究工作，需要将命题公式规范化，即制定范式。定义基本合取项(式)单个命题变元、单个命题变元的否定或者若干个命题变元或其否定的合取构成的命题公式称为基本合取项。如P，Q，PQ，PQR定义基本析取项(式)单个命题变元、单个命题变元的否定或者若干个命题变元或其否定的析取构成的命题公式称为基本析取项。如P，Q，PQ，PQR,析取范式、合取范式,定义析取范式一个命题公式A称为析取范式，当且仅当它具有形式如A1A2An(n1)其中A1，A2，An是基本合取项。例如：(PQ)(PQR)R定义合取范式一个命题公式称为合取范式，当且仅当它具有形式B1B2Bn(n1)其中B1，B2，Bn是基本析取项。例如：(PQ)(QR)(PQR),析取与合取范式定理,定理：任意一个命题公式都可化为析取(合取)范式。证明思路：包含，的命题公式可化为只有，和的命题公式。括号前的符号可通过德.摩根定律放到每个命题变元前面。利用分配率：P（QR）（PQ）（PR）可得析取范式。,范式的求法命题(等价)演算法,利用常用的逻辑等价公式将命题公式转换成符合析取范式的形式。步骤：（1）将命题公式中的联结词都转化成、及。（2）利用德摩根律，将符号移到各个命题变元的前面。（3）利用分配律、结合律将公式转化为合取范式或析取范式。（4）（添加）（4.1）若转化为析取范式，则删除永假的基本合取项，重复的基本合取项只保留一个。（4.2）若转化为合取范式，则删除永真的基本析取项，重复的基本析取项只保留一个。,重要的逻辑等价公式,PQPQPQ(PQ)(PQ)(PQ)(PQ)PQ(PQ)(QP)(PQ)(PQ),等价演算法：求析取范式举例,例1：求(PQ)(PQ)的析取范式。解:(AB)(AB)(AB)原式(PQ)(PQ)(PQ)(PQ)/*消去*/(PQPQ)(PQ)(PQ)/*德摩根律*/(PQPQ)(PP)(QP)(PQ)(QQ)/*分配律，析取范式*/(PQ)(PQ)/*消去重复项和值为0的项*/,等价演算法：求合取范式举例,例2：求(P(QR)S的合取范式。解:(P(QR)S(P(QR)S/*消去*/(P(QR)S/*德摩根律*/P(QR)S/*德摩根律*/(PQS)(PRS)/*分配律，没有需要消去的项*/,注意：（1）范式不一定唯一,一个命题公式的合取范式或析取范式并不是唯一的。例：求(PQ)P的析取范式和合取范式。解：(PQ)P(PQ)P/*消去*/(PQ)P/*摩根律，析取范式*/P(析取范式)/*吸收率*/(PQ)P(PQ)P(析取范式)(PP)(QP)(合取范式)P(QP)(合取范式),注意：（2）析取范式与合取范式有可能同一,请判断下列命题公式是析取范式还是合取范式？pqrpqr回答：既是析取范式，又是合取范式。一个基本合取项或基本析取项既是析取范式，又是合取范式。,命题与联结词,析取范式与合取范式主析取范式和主合取范式,1.极小项,定义极小项由n个命题变元或其否定的合取组成的基本合取项，称为n个变元的极小项，在一个极小项中每个变元与它的否定两者之一必须出现且仅出现一次。例如：两个命题变元p和q构成的极小项为：pqpqpqpq三个变元p、q和r的极小项为：pqrpqrpqrpqrpqrpqrpqrpqr思考：包含n个给定变元的极小项共有几个？回答：2n个,2.极大项,定义极大项n个命题变元或其否定的组成的基本析取项，称为n个变元的极大项，在一个极大项中，每个变元与它的否定两者之一必须出现且仅出现一次。例如：两个命题变元p和q构成的极大项为：pqpqpqpq三个变元p、q和r的极大项为：pqrpqrpqrpqrpqrpqrpqrpqr注意：一般地，极小项和极大项中的变元按字母序排列。思考：包含n个命题变元的极大项共有几个？回答：2n个,极小项和极大项性质,每个极小项都只对应一组真值指派，使得该极小项的真值为T。如：PQ00PQ01PQ10PQ11每个极大项都只对应一组真值指派，使得该极大项的真值为F。如：PQ00PQ01PQ10PQ11每一组真值指派与在该真值指派下值为真的极小项存在一一对应的关系每一组真值指派与在该真值指派下值为假的极大项存在一一对应的关系,3.极小项与极大项的编码,举例：,p,q,p,q,p,q,p,q,p,q,p,q,p,q,p,q,mi称为指派i所对应的极小项，Mi称为指派i所对应的极大项,练习,请选出由p,q,r三个命题变元构成的极小项m101与m110A、m101pqr，m110pqr；B、m101pqr，m110pqr；C、m101pqr，m110pqr；D、m101pqr，m110pqr；请选出由p,q,r三个命题变元构成的极大项M101与M110A、M101pqr，M110pqr；B、M101pqr，M110pqr；C、M101pqr，M110pqr；D、M101pqr，M110pqr；,极小项与极大项的编码举例2,由p,q,r三个命题变项形成的极小项与极大项,极小项与极大项的关系,p,q,p,q,p,q,p,q,p,q,p,q,p,q,p,q,miMi,主析取范式和主合取范式,定义主析取范式一个包含n个命题变元的命题公式A称为主析取范式，当且仅当它具有形式如A1A2Am(m1)其中A1，A2，Am是包含n个命题变元的极小项。例如：仅包含3个命题变元p,q,r的命题公式：(pqr)(pqr)是主析取范式m001m011定义主合取范式一个包含n个命题变元的命题公式A称为主合取范式，当且仅当它具有形式如A1A2Am(n1)其中A1，A2，Am是包含n个命题变元的极大项。例如：仅包含3个命题变元p,q,r的命题公式：(pqr)(pqr)是主合取范式M001M101,命题与联结词,析取范式与合取范式主析取范式和主合取范式的定义范式的求法：命题演算法主析取范式和主合取范式极小项与极大项主析取范式和主合取范式的定义主范式的求法命题演算法真值表法主范式的用途,1.命题演算法：求主析取范式,步骤：（1）将命题化为析取范式（2）对每一个合取项补入没有出现的命题变元，补入的方法：若某基本合取项没有出现命题变元P，则将该基本合取项与(PP)式合取，然后应用分配律展开整理（包括删除永假的基本析取项和重复的基本析取项）。例：P(PQ)(P(QQ)(QP)(PQ)(PQ)(QP),命题演算法：求主析取范式举例,P(PQ)(QP)解：原式P(PQ)(QP)/*消去*/P(PQ)(PQ)/*利用摩根律*/P(PPQ)(PQQ)/*()内应用分配率*/P(PQ)/*消去重复的变元Q和永假式*/(P(QQ)(PQ)/*对合取项P和Q补入命题变元，添加(QQ)*/(PQ)(PQ)(PQ)/*应用分配率整理*/,命题演算法：求主析取范式练习,练习题：求(PQ)Q的主析取范式解：原式(PQ)Q/*消去*/(PQ)(QQ)/*应用分配率*/(PQ)Q/*消去重复的变元Q*/(PQ)(PP)Q)/*对合取项Q补入命题变元，添加(PP)*/(PQ)(PQ)(PQ)/*应用分配率整理*/m1m3m2/*极小项化*/,命题演算法：求主合析取范式,步骤：（1）将命题化为合取范式（2）对每一个基本析取项补入没有出现的命题变元，补入的方法：如果一个析取项中没有出现变元P，则将该析取项与(PP)析取，然后应用分配律展开整理（包括删去永真的基本析取项和重复的基本析取项）。例：Q(PQ)(Q(PP)(PQ)(QP)(QP)(PQ),命题演算法：求合析取范式举例,求PQ的主合取范式解：原式(P(QQ)(PP)Q)/*补入命题变元*/(PQ)(PQ)(PQ)(PQ)/*分配率*/(PQ)(PQ)(PQ)/*化简整理*/M00MM/*极大项化*/,01,10,主合取范式：由极大项的合取所组成,2.真值表法：求主析取范式,定理求主析取范式定理在一个命题公式的真值表中，该公式的真值为T的指派所对应的极小项的析取式，即为此公式的主析取范式。定理求主合取范式定理在一个命题公式的真值表中，该公式的真值为F的指派所对应的极大项的合取式，即为此公式的主合取范式。注：该定理说明了任何命题公式都存在着与之等价的主析取范式和主合取范式。,求主析取范式定理证明,定理：在一个命题公式的真值表中，该公式的真值为T的指派所对应的极小项的析取式，即为此公式的主析取范式。证明：,真值表法：求主析取范式举例,例1：求A=(PQ)(PR)的主析取范式。解：该公式的真值表：,提取命题真值为真的指派所对应的极小项：m111=(PQR)m110=(PQR)m011=(PQR)m001=(PQR)Am111m110m011m001,1,1,1,1,0,0,0,0,真值表法：求主合取范式举例,例1：求A=(PQ)(PR)的主合取范式。解：该公式的真值表：,提取命题真值为假的指派所对应的极大项：M101(PQR)M100(PQR)M010(PQR)M000(PQR)M101M100M010M000,主范式的用途,主范式的用途与真值表相同。(1)求公式的成真赋值和成假赋值。例如(pq)rm1m3m5m6m7，其成真赋值为:001,011,101,110,111，其成假赋值为:类似地，由主合取范式也可立即求出成假赋值和成真赋值.,000,010,100,主范式的用途(续),(2)判断公式的类型。设A含n个命题变项，则A为永真式A的主析取范式含2n个极小项A的主合取范式为1.A为永假式A的主析取范式为0A的主合析取范式含2n个极大项A为非永真和永假式：A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项ABAB的主析取范式含2n个极小项A的主合取范式为1.,主范式的用途(续),例用主析取范式判断下述两个公式是否逻辑等价：p(qr)与(pq)rp(qr)与(pq)r解p(qr)=m0m1m2m3m4m5m7(pq)r=m0m1m2m3m4m5m7(pq)r=m1m3m4m5m7显见，中的两公式逻辑等价，而的不等价.,(3)判断两个公式是否逻辑等价,主范式的用途举例,例：某公司要从赵、钱、孙、李、周五人中选派一些人出国学习.选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析，该公司应该如何选派他们出国，才能满足上面给出的5个条件？,主范式的用途举例(续),解此类问题的步骤为：将原子命题符号化用中定义的原子命题和联结词将题目的条件符号化。写出由中复合命题组成的合取式求中所得公式的主析取范式,主范式的用途举例(续),解设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.(1)若赵去，钱也去：(2)李、周两人中至少有一人去：(3)钱、孙两人中有一人去且仅去一人：(4)孙、李两人同去或同不去(5)周去，则赵、钱也去(1)(5)构成的合取式为A=(pq)(su)(qr)(qr)(rs)(rs)