离散-1-2-命题逻辑(1).ppt

《离散-1-2-命题逻辑(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、永真公式公式的解释公式的真值表公式的分类代入规则（定理1.3.1）公式间的等价关系等价关系的5个基本性质基本逻辑恒等式对偶原理永真蕴含关系证明方法基本永真蕴涵式永真蕴涵关系的性质1§1.3永真式1.公式的解释定义1.3.1:设A(P1,…,Pn)是合式公式，对P1,…,Pn的一组真值赋值，称为对A的一个解释。例:设A(P1,P2),其解释有:00,01,10,11若B(Q1,Q2,Q3),则其解释有:000,001,……,111解释的个数与变元的关系：含n个变元的公式有2n种不同的解释。公式的真值表：例:构造(P∧Q)→R的真值表。2§1.3永真式2.公式的分类

2、定义:设A是合式公式,则（1）如果A在任何解释下均为真，则称A为永真式或重言式；（2）如果A在任何解释下均为假，则称A为永假式或矛盾式；（3）如果至少有一个解释使A为真，则称A为可满足式；例1：分析(P∧Q)→R和P∨┐P。代入规则（定理1.3.1):永真式的代入实例是永真式。例：分析P∨┐P3定理1.3.1：永真式的代入实例是永真式。证明：设A(P1,…,Pn)是永真式，A’是用Bi取代Pi(1≤i≤n)所得到的代入实例，对A’的任一解释I,∵A是永真式，∴A’在解释I下的真值为真，由I的任意性得：A’也是永真式。这个假使是否具有一般性？4§1.3永真式3.公

3、式间的等价关系(1)定义：设A、B是合式公式,若AB是永真式，则称A等价于B,记作AB（称为逻辑恒等式）。基本逻辑恒等式等价关系的性质：自反性(reflexivity)：对任意公式A,均有AA对称性(symmetry)：若AB,则BA传递性(transitivity)：若AB且BC,则AC若AB，则┐A┐B5例题验证吸收律P∨（P∧Q）PP∧（P∨Q）P证明列出真值表PQP∧QP∨（P∧Q）P∨QP∧（P∨Q）TTTTTTTFFTTTFTFFTFFFFFFF由表可知吸收律成立。6从真值表中可以看到，有些命题公式在分量的不同指派下，其对应的

4、真值与另一命题公式完全相同，如┐P∨Q与P→Q的对应真值相同，如下表所示。PQ┐P∨QP→QTTTTTFFFFTTTFFTT我们说┐P∨Q和P→Q是等价的，这在以后的推理中特别有用。7证明:∵C与D的不同仅在于C中A的一处或几处出现换成B,并且AB∴对C,D中变元的任一组真值赋值，C与D的真值相同，∴CD为永真式，即CD例：证明P(P∧Q)∨(P∧┐Q)证明:∵P基本恒等式»定理1.3.2:设A是C的子公式且AB，若用B替换C中A的一处或几处出现得到公式D,则CD.同一律P∧T补余律P∧(Q∨┐Q)分配律(P∧Q)∨(P∧┐Q)∴P(P∧Q)

5、∨(P∧┐Q)8§1.3永真式3.公式间的等价关系(2)例：证明（┐A→┐B)→(B→A)是永真式。证明:∵(┐A→┐B)→(B→A)蕴涵等值式┐(┐┐A∨┐B)∨(┐B∨A)基本恒等式»德·摩根律、双重否定律(┐A∧B)∨(┐B∨A)分配律(┐A∨┐B∨A)∧(B∨┐B∨A)交换律、结合律、补余律T∴（┐A→┐B)→(B→A)是永真式9§1.3永真式4.对偶原理（1）对偶式：设A是仅含┐、∧、∨的合式公式，在A中将∧和∨互换、T和F互换,所得到的公式A*称为A的对偶式。例：A:T∨(P∧┐Q)A*:F∧(P∨┐Q)对偶式的性质：定理1.3.3:设A(P

6、1,…,Pn)是仅含┐、∧、∨的合式公式，则┐A(P1,…,Pn)A*(┐P1,…,┐Pn)10定理:设A(P1,…,Pn)是仅含┐,∧,∨的公式，则┐A(P1,…,Pn)A*(┐P1,…,┐Pn)证明:①若A为P、T或F,则A*为P,F或T,此时有:┐P┐P,┐TF和┐FT,结论成立.②设对A1,A2结论成立,当A为┐A1,时，A*为┐A*1∴┐A┐(┐A1)┐(A*1(┐P1,…,┐Pn))A*(┐P1,…,┐Pn)若A为A1∧A2，则A*为A*1∨A*2∴┐A┐(A1∧A2)┐A1∨┐A2A*1(┐P1,…,┐Pn)∨A*2(┐P1

7、,…,┐Pn)A*1∨A*2(┐P1,…,┐Pn)A*(┐P1,…,┐Pn)同理可证当A为A1∨A2时，结论也成立11定理1.3.4(对偶定理)：设A为是仅含┐,∧,∨的合式公式,若AB，则A*B*(说明基本逻辑恒等式会成对出现)证明：设AB,则┐A┐B§1.3永真式4.对偶原理（2）∴┐A┐B是永真式。∵┐A┐BA*(┐P1,…,┐Pn)B*(┐P1,…,┐Pn)(定理1.3.3)∴A*(┐P1,…,┐Pn)B*(┐P1,…,┐Pn)--①也是永真式。用┐Pi取代Pi(1≤i≤n),得到①的一个代入实例：A*(P1,…,Pn)B*(P1

8、,…,Pn)由代入规则（