数理逻辑1.3.ppt

《数理逻辑1.3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.3命题公式间的逻辑等价关系1.3.1基本概念1.3.2替换定理1.3.3代入定理1.3.4逻辑等价变换1.3.5联结词归约与范式1.3.1基本概念定义1设,是两个命题公式。如果对于与的合成变元组(即这两个公式所有不同命题变元合在一起)的任意指派，均有()=()则称与逻辑等价，也称永真等价或同真假。记为。判断两个命题公式逻辑等价的第一种方法是使用真值表。先将与的合成变元组的各种指派和与在各种指派下的真假值写在同一张表上，然后检验与的相应位置上的真值是否相同。例如，利用真值表即可验证命题公式PQ与命题公式P(PQ)逻

2、辑等价。PP双重否定律PPP,PPP幂等律(PQ)RP(QR)(PQ)RP(QR)结合律PQQP,PQQP交换律P(QR)(PQ)(PR)P(QR)(PQ)(PR)分配律(PQ)PQ(PQ)PQDeMorgan律PFP,PTP同一律PTT,PFF零律PPT,PPF否定律PQPQPQ(PQ)(QP)联结词归约基本逻辑等价式请用真值表验证各个逻辑等价公式研究两个命题公式之间逻辑等价关系的方法之二是利用命题公式的永真性。定理1设

3、,为命题公式，当且仅当为永真公式。命题公式间的逻辑等价关系具有：1)自反性：；2)对称性：若，则；3)传递性：若且，则。应当指出的是，两个命题公式逻辑等价与两个命题公式相等是有所区别的。前者是指结果相同，后者是指形式相同(当然结果必相同)。因此相等比逻辑等价的要求更高。以后仍用“＝”表示相等。1.3.2替换定理定义2设命题公式，是命题公式的一部分且是命题公式，则称是的子命题公式。定义3设是命题公式，若将的子命题公式用另一命题公式替换，则称替换后产生的命题公式是关于替换为的结果。利用替换

4、，可以将原有的命题公式改造成新的命题公式。例如，命题公式P(P(PQ))关于P(PQ)替换为PQ的结果为P(PQ)。替换定理设是关于替换为的结果。如果，则。引理设1,2,1,2均为命题公式。若11,22,则1)112)12123)12124)12125)1212证：3）设1,2,1,2的合成变元组为(P1,P2,…,Pn)。对于该合成变元组的任一指派，由条件11,22有1()=1()2()=2()于是

5、有1()2()=1()2()由于(12)()=1()2()(12)()=1()2()于是有(12)()=(12)()由指派的任意性和逻辑等价的定义知有1212。替换定理设是关于替换为的结果。如果，则。证：对中除之外的联结词个数k进行归纳证明。当k=0时，为下述两种形式之一。1)=P(P是命题变元)，2)=对于1)根据的定义可知，此时=P。于是有==P，当然有。对于2)有==。设当k

6、立。事实上，按照命题公式的定义可知，必呈下述形式之一。1,12,12,12,12仅以12为例进行证明。由于是关于替换为的结果，而且只是对中以外的联结词进行归纳，即12中的不是中的联结词。因此，必呈12的形式，其中1,2分别是1,2关于替换为的结果。又由于1,2中除之外的联结词的个数必然小于n。于是按照归纳假设可知，有1122再由引理知，有1212,即。1.3.3代入定理代入是通过已有的永真公式推出更多的永真公式的一种有效途径。例如，是否可由PP是

7、永真公式而直接推断出PQPQ是永真公式。这就是代入定理所要回答的问题。定义4设为命题公式，P是中的命题变元，是任一命题公式。如果将中P的所有出现均用命题公式代替，则称代替后所得到的命题公式为关于P代入为的结果，简称的代入实例，记为[/P]。例=(P(PQ))Q，=PQ，代入P后则有[/P]=((PQ)((PQ)Q))Q代入定理设为命题公式，P是中的命题变元。如果是永真公式，那么对任意命题公式，有[/P]为永真公式。证令=[/P]。设的变元组为(P1,P2,…,Pn)，的变元组为(Q1,Q2,

8、…,Qm)。于是的变元