离散数学命题逻辑4.ppt

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

1、勿在浮沙筑高台！38--1程序设计领域里，每一个人都想飞。但是，还没有学会走之前，连怕跑都别想！勿在浮沙筑高台！28七月2021勿在浮沙筑高台！38--2单个的命题变元和一些命题变元的否定是一个基本和、基本积、析取范式、合取范式。单个的基本和是合取范式、析取范式单个的基本积是析取范式、合取范式析取范式、合取范式仅含联结词┐、∧、∨，且┐仅出现在命题变元前。结论从上述定义和例子可以得出如下关系：勿在浮沙筑高台！38--3求一个命题公式的与之等价的析取范式和合取范式，其步骤如下：（1）利用恒等公式中的等值式和蕴涵式将公式中的→、用联结词┐、∧、∨来取代；（2）利用德摩根定律将否定号

2、┐移到各个命题变元的前端；（3）利用结合律、分配律、吸收律、等幂律、交换律等将公式化成其等价的析取范式和合取范式。勿在浮沙筑高台！38--4定义1.3-4在n个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本积叫极小项。1.3.2主析取范式和主合取范式勿在浮沙筑高台！38--5对应情况如下:P∧Q∧R——000——0P∧Q∧R——001——1P∧Q∧R——010——2P∧Q∧R——011——3P∧Q∧R——100——4P∧Q∧R——101——5P∧Q∧R——110——6P∧Q∧R—111—7勿在浮沙筑高台！38--6我们把对应的十进制数当作足标

3、,用mi表示这一项,即;m0P∧Q∧Rm1P∧Q∧Rm2P∧Q∧Rm3P∧Q∧Rm4P∧Q∧Rm5P∧Q∧Rm6P∧Q∧Rm7P∧Q∧R一般地,n个变元的极小项是:m0P1∧P2∧P3…∧Pnm1P1∧P2∧P3…∧Pn……m2n-1P1∧P2∧P3…∧Pn勿在浮沙筑高台！38--7定义1.3-6在n个变元的基本和中,若每一个变元与其否定不同时存在,而二者之一必出现一次且仅出现一次,则这种基本和叫极大项。n个变元可构成2n个不同的极大项。类似于(但不同)极小项的记法,它们是:M0P1∨P2∨…∨PnM1P1∨P2∨…∨PnM2P1∨P2∨…∨Pn

4、-1∨Pn…M2n-1P1∨P2∨…∨Pn勿在浮沙筑高台！38--82.由有限个极小项组成的析取范式称为主析取范式。3.由有限个极大项组成的合取范式称为主合取范式。勿在浮沙筑高台！38--9极小项与极大项的性质对于n个命题变元，共有2n个不同的极小项和2n个不同的极大项，分别记为m0，m1，…，m2n-1和M0，M1，…，M2n-1。对于两个命题变元P,Q，(┐P∧┐Q)、(┐P∧Q)、(P∧┐Q)、(P∧Q)为对应的4个极小项，(P∨Q)、(P∨┐Q)、(┐P∨Q)、(┐P∨┐Q)为对应的4个极大项。(┐P∧Q)是2个变元P和Q的极小项，但不是3个变元P、Q和R的极小项；(P

5、∨┐Q)是2个变元P和Q的极大项，但不是3个变元P、Q和R的极大项。勿在浮沙筑高台！38--10如公式G1=（P→Q）∧QG2（P，Q，R）=（P→Q）∧Q其求出的相应的主析取范式和主合取范式却是不同的，前者是依赖于两个命题变元的，后者应依赖于三个命题变元。定理任何一个公式都有与之等价的主析取范式和主合取范式。方法：真值表技术，公式转换法。勿在浮沙筑高台！38--11例G=(P→Q)R，求出它的主析取范式和主合取范式。真值表技术求主范式PQRP→Q(P→Q)R0001000111010100111110001101001101011111解：首先列出其真值表如下：勿在浮沙筑高台！38

6、--12将极小项全部进行析取后，可得到相应的主析取范式：G=（Ｐ→Ｑ）Ｒ=（┐P∧┐Ｑ∧Ｒ）∨（┐P∧Ｑ∧Ｒ）∨（Ｐ∧┐Ｑ∧┐Ｒ）∨（Ｐ∧Ｑ∧Ｒ）勿在浮沙筑高台！38--13将极大项全部进行析取后，可得到相应的主合取范式：G=（Ｐ→Ｑ）Ｒ=（P∨Ｑ∨Ｒ）∧（P∨┐Ｑ∨Ｒ）∧（┐Ｐ∨Ｑ∨┐Ｒ）∧（┐Ｐ∨┐Ｑ∨Ｒ）勿在浮沙筑高台！38--14求主析取范式和主合取范式的简要方法：（a）从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项的析取即可得到相应的主析取范式。（b）从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中

7、，找到其每一个解释所对应的极大项，将这些极大项的合取即可得到相应的主合取范式。勿在浮沙筑高台！38--15PQRP→Q┐（P→Q）┐(P→Q)∨R000100001101010100011101100011101011110100111101解：首先列出其真值表如下：例G=┐(Ｐ→Ｑ)∨Ｒ，求主析取和主合取范式。勿在浮沙筑高台！38--16(1).求主析取范式(a).从真值表知，该公式G恰有五个解释使其公式取值为“真”。为此，