离散数学 命题逻辑3.ppt

《离散数学 命题逻辑3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑范式命题与联结词析取范式与合取范式主析取范式和主合取范式范式的引入同一命题公式可以有多种相互等价的表达形式，例如：PQרP∨Qר(P∧רQ)方便研究工作，需要将命题公式规范化，即制定范式。[定义]基本合取项(式)单个命题变元、单个命题变元的否定或者若干个命题变元或其否定的合取构成的命题公式称为基本合取项。如P，רQ，P∧Q，רP∧Q∧R[定义]基本析取项(式)单个命题变元、单个命题变元的否定或者若干个命题变元或其否定的析取构成的命题公式称为基本析取项。如P，רQ，P∨Q，רP

2、∨Q∨רR析取范式、合取范式[定义]析取范式一个命题公式A称为析取范式，当且仅当它具有形式如A1∨A2∨···∨An(n≥1)其中A1，A2，···，An是基本合取项。例如：(┓P∧Q)∨(P∧Q∧R)∨┓R[定义]合取范式一个命题公式称为合取范式，当且仅当它具有形式B1∧B2∧···∧Bn(n≥1)其中B1，B2，···，Bn是基本析取项。例如：(P∨┓Q)∧(Q∨R)∧(┓P∨┓Q∨R)析取与合取范式定理定理：任意一个命题公式都可化为析取(合取)范式。证明思路：包含→，，的命题公式可化为

3、只有，┐和的命题公式。括号前的┐符号可通过德.摩根定律放到每个命题变元前面。利用分配率：P（QR）（PQ）（PR）可得析取范式。范式的求法——命题(等价)演算法利用常用的逻辑等价公式将命题公式转换成符合析取范式的形式。步骤：（1）将命题公式中的联结词都转化成∧、∨及┓。（2）利用德•摩根律，将┓符号移到各个命题变元的前面。（3）利用分配律、结合律将公式转化为合取范式或析取范式。（4）（添加）（4.1）若转化为析取范式，则删除永假的基本合取项，重复的基本合取项只保留一个。（4.2）

4、若转化为合取范式，则删除永真的基本析取项，重复的基本析取项只保留一个。重要的逻辑等价公式PQ⇔P∨QPQ⇔(P∧Q)∨(┐P∧┐Q)⇔(P∨┐Q)∧(┐P∨Q)P▽Q⇔(P∧┐Q)∨(Q∧┐P)⇔(P∨Q)∧(┐P∨┐Q)等价演算法：求析取范式举例例1：求ר(P∨Q)(P∧Q)的析取范式。解:∵(AB)(A∧B)∨(רA∧רB)∴原式(ר(P∨Q)∧(P∧Q))∨((P∨Q)∧ר(P∧Q))/*消去*/(רP∧רQ∧P∧Q)∨((P∨Q)∧(רP∨רQ))/*德•摩根律*/(

5、רP∧רQ∧P∧Q)∨(P∧רP)∨(Q∧רP)∨(P∧רQ)∨(Q∧רQ)/*分配律，析取范式*/(רP∧Q)∨(P∧רQ)/*消去重复项和值为0的项*/等价演算法：求合取范式举例例2：求(P∧(QR))S的合取范式。解:(P∧(QR))Sר(P∧(רQ∨R))∨S/*消去*/(רP∨ר(רQ∨R))∨S/*德•摩根律*/רP∨(Q∧רR)∨S/*德•摩根律*/(רP∨Q∨S)∧(רP∨רR∨S)/*分配律，没有需要消去的项*/注意：（1）范式不一定唯一一个命题公式的合取范

6、式或析取范式并不是唯一的。例：求(PQ)P的析取范式和合取范式。解：(PQ)Pר(רP∨Q)∨P/*消去*/(P∧רQ)∨P/*摩根律，析取范式*/P(析取范式)/*吸收率*/(PQ)P(P∧רQ)∨P(析取范式)(P∨P)∧(רQ∨P)(合取范式)P∧(רQ∨P)(合取范式)注意：（2）析取范式与合取范式有可能同一请判断下列命题公式是析取范式还是合取范式？pqrpqr回答：既是析取范式，又是合取范式。一个基本合取项或基本析取项既是析取范式，又

7、是合取范式。命题与联结词析取范式与合取范式主析取范式和主合取范式1.极小项[定义]极小项由n个命题变元或其否定的合取组成的基本合取项，称为n个变元的极小项，在一个极小项中每个变元与它的否定两者之一必须出现且仅出现一次。例如：两个命题变元p和q构成的极小项为：pqpqpqpq三个变元p、q和r的极小项为：pqrpqrpqrpqrpqrpqrpqrpqr思考：包含n个给定变元的极小项共有几个？回答：2n个2.极大项[定义]极大项

8、n个命题变元或其否定的组成的基本析取项，称为n个变元的极大项，在一个极大项中，每个变元与它的否定两者之一必须出现且仅出现一次。例如：两个命题变元p和q构成的极大项为：pqpqpqpq三个变元p、q和r的极大项为：pqrpqrpqrpqrpqrpqrpqrpqr注意：一般地，极小项和极大项中的变元按字母序排列。思考：包含n个命题变元的极大项共有几个？回答：2n个极小项和极大项性质每个极小项都只对应一组真值指派，使得该极小项的真