离散数学第一章命题演算基础-真假性.ppt

《离散数学第一章命题演算基础-真假性.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题演算基础1.1命题和联结词1.2真假性1.2.1解释1.2.2等价公式1.2.3联结词的完备集1.2.4对偶式和内否式1.3范式及其应用完全解释、部分解释定义：设n元公式中所有的不同的命题变元为P1,…,Pn如果对每个命题变元均给予一个确定的值，则称对公式给了一个完全解释；如果仅对部分变元给予确定的值，则称对公式给了一个部分解释。n元公式有2n个完全解释。例考察公式=（PQ）RPQRTTTTTTFFTT*不能确定F**T成真解释与成假解释定义：对于任何公式，凡使得取真值的解释，不管是完全解释还是部分解释，均称为的成真解释。定义：对于任何

2、公式，凡使得取假值的解释，不管是完全解释还是部分解释，均称为的成假解释。例考察公式=（PQ）RPQRTTTT1个成真解释TTFF1个成假解释TT*不能确定1个成真解释1个成假解释F**T4个成真解释永真公式与永假公式定义：如果一个公式的所有完全解释均为成真解释，则称该公式为永真公式或称为重言式。定义:如果一个公式的所有完全解释均为成假解释，则称该公式为永假公式或称为予盾式。例由定义可知：PP为永假公式；PP为永真公式。可满足公式与非永真公式定义：如果一个公式存在成真解释，则称该公式为可满足公式；如果一个公式存在成假解释，则称该公式为非永真公式。例

3、由定义可知：PP永假公式PP永真公式PQ可满足公式，非永真公式PQ可满足公式，非永真公式第一章命题演算基础1.1命题和联结词1.2真假性1.2.1解释1.2.2等价公式1.2.3联结词的完备集1.2.4对偶式和内否式1.3范式及其应用逻辑等价定义：给定两个公式和，设P1，P2，……，Pn为和的所有命题变元，那么和有2n个解释。如果对每个解释，和永取相同的真假值，则称和是逻辑等价的，记为=。⇔八组重要的等价公式双重否定律P=P结合律（PQ）R=P（QR）（PQ）R=P（QR）分配律P（QR）=（PQ）（

4、PR）P（QR）=（PQ）（PR）交换律PQ=QPPQ=QP八组重要的等价公式等幂律PP=PPP=PPP=TPP=T等值公式PQ=PQPQ=（PQ）（QP）=（PQ）（PQ）=（PQ）（PQ）（PQ）=PQ（PQ）=PQ八组重要的等价公式部份解释PT=PPF=FPT=TPF=PTP=PFP=TPT=TPF=PTP=PFP=P吸收律P（PQ）=PP（PQ）=P?例判断下列公式的类型q∨((p∨q)∧p)永真解:q∨((p∨q)∧p)=q∨((p∨

5、q))∨p=(q∨p)∨((p∨q))=T所以，它是永真的。例判断下列公式的类型(p∨p)((q∧q)∧r)永假解:(p∨p)((q∧q)∧r)=T((q∧q)∧r)=(q∧q)∧r=F∧r=F所以，它是永假的。例判断下列公式的类型(pq)∧p可满足解:(pq)∧p=(p∨q)∧p=p所以，它是可满足的。成真解释和成假解释的求解方法（1）否定深入：即把否定词一直深入至命题变元上；（2）部分解释：选定某个出现次数最多的变元对它作真或假的两种解释从而得公式；（3）化简；（4）依次类推，直至产生公式的所有解释。例(p7)试判定公式(

6、PQ)((QP)R)的永真性和可满足性。解1：否定深入原式=(PQ)((QP)R)对P=T进行解释并化简，结果见教材。例(p7)(PQ)((QP)R)解2：在否定深入的基础上对P=F进行解释并化简。原式=（FQ）（（QF）R）=（QF）R=QRQ=T时，原式=TR=R，于是R=T时，原式=FR=F时，原式=T因此，公式存在成真解释（P，Q，R）=（F，T，F）；公式存在成假解释（P，Q，R）=（F，T，T）。故公式可满足但非永真。例(p7)(PQ)((QP)R)解3：所以，公式

7、存在成真解释：(T,T,*),(T,F,F),(F,T,F),(F,F,T);公式存在成假解释：(T,F,T),(F,T,T),(F,F,F)。故公式可满足但非永真。(P,Q,R)A=(PQ)B=QPC=BRAC(T,T,T)FTFT(T,T,F)FFFT(T,F,T)TTFF(T,F,F)TTTT(F,T,T)TTFF(F,T,F)TTTT(F,F,T)TFTT(F,F,F)TFFF例试求下列公式的成真解释和成假解释（PQ）（Q（RP））解:当P=T时,原式=(TQ)(Q(RT))=Q(Q(R))=