(3)证明：左边= P QR

右边= P QP R =P QR

可有：左边=右边，得证

(4)证明：左边= (P Q) ( R Q) =(P R) Q = (P R) Q =(P R) Q=右边 得证

2设S={G1，…，Gn}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。

提示：考虑G1…Gn的主合取式。

解：任设一公式G’为从S出发演绎出来的公式。则可知G’

为G= G1…Gn的一个逻辑结果。而G有唯一一个与其等价的主合取式，设为G’’。

可设G’’共有m个极大项，则可以知道令G’’取1的解释使这m 个极大项也取1。则从S出发的演绎出来的的所有命题公式正是从这m个极大项中任取n(0≤n≤m)个合取组

m

成，共有2个，其中包括恒真公式这里用1表示。

设H为由若干极大项构成的合取公式。现在证明：

1) S=>H，即G=>H。从定义出发，设有一解释I使G=G1…Gn 取1值，必使G的主

合取式也取1值。即使每一个极大项都取1值。从而使由若干极大项合取组成的公式H也取1值，则有S=>H。

2) 任意设公式H是S的一个逻辑结果，H是一些极大项的合取。现在要证组成H的极

大项都在G的主合取式G”中。

反证法：若不然，假设H中有一个极大项mk不在G的主合取式中。则取使mk为0的解释I，可有解释I使H取0值。而I使所有不等于mk的极大项都为1，则可有G的主合取式G’’在I下取1值，即G在I下取1值，这与G=>H矛盾。

3.证明：两个公式之间的蕴涵关系具有反身性，反对称性和传递性。 证明：a)任意设一公式P,

由于PP是恒真的，则有P=>P 即蕴涵关系有反身性。 b)任取两个命题公式P，Q

如果P=>Q 并且Q=>P，则有PQ恒真，QP恒真，则（PQ）（QP）恒真，那么有PQ恒真，得出P=Q，所以蕴涵关系有反对称性。 c)任取命题公式P，Q，R

如果P=>Q，Q=>R；对于P，Q，R的任意一个解释I。如果I满足P则I也满足Q，若I满足Q则I满足R。

则有I满足P时，也满足R，故有P=>R。 因此蕴涵关系有传递性。

4.证明：若前提集合S中的公式都是恒真的，G是从S出发的一个演绎的逻辑结果，则G必是恒真公式。

证明：设S是由G1，…，Gn构成的，则G1，…，Gn是恒真的，那么G1… Gn是恒真的，

而由已知有：

G1… Gn=>G，因此由蕴涵定义有G必为恒真公式。

5.设G1，…，Gn是公式。证明：从{G1，…，Gn}出发可演绎出公式G的充要条件是从{G1，…，Gn，G}出发可演绎出公式(RR)。其中R为任意公式。

证明： 充分性，即{G1，…，Gn，G}=>(RR)，可有 G1… GnG=>(RR)，因(RR)恒假，则G1… GnG恒假。那么有

（G1… Gn）G恒真，即（G1… Gn）G恒真，则有(G1… Gn )=>G，因此有{G1，…，Gn}蕴涵G。

必要性，即已知：{G1，…，Gn}=>G，有（G1… Gn）G恒真，即（G1…

Gn ） G恒真，那么对上式取非有G1… GnG恒假，也就是(G1… GnG) (RR)恒真，其中R为任意一个公式，则有(G1… GnG) => (RR)，即从{G1，…，Gn，G}出发可演绎出公式(RR)。

命题得证。

6.证明下列蕴涵式： (1)(PQ)(PQ)

证明：要证上式成立即证(PQ) (PQ)恒真， 则：(PQ) (PQ)

= (PQ) (PQ)

=(P Q) (PQ) =P QQ =T

即：(PQ) (PQ)恒真

命题得证。(或从PQQ，Q(PQ)) (2)P(QP)

证明：同a)， P (QP)

=P (QP) =P PQ =T

命题得证。(或从P (QP)出发) (3) (P(QR))(PQ)(PR)

证明：(P(QR)) (PQ)(PR)

=(PQR) (PQR) =T

得证。

(4) PQP(PQ)

证明:若P(PQ)为假，则PQ为假，P为真。因而有Q为假，则PQ为假，(后件假推出前件假等价于前件真推出后件真)得证。 (5) (PQ)QPQ

证明：(PQ)Q

= (P Q) Q =(P Q) Q

=(P Q) (Q Q) =>(P Q) (基本蕴涵式)

(6) ((PP)Q)((PP)R)(QR)

证明：若(QR)为假，则R为假，Q为真，则(PP)R为假，而(PP)Q为真，则有((PP)Q)((PP)R)为假，得证。 （用PQ证明也可） (7) (Q(PP))(R(PP))(RQ)

证明：若(RQ)为假，则Q为假，R为真，则 R(PP)为假，而Q(PP)为真。有(Q(PP))(R(PP))为假，得证。

7.证明{CD，(CD)H，H(AB)，(AB)证明：1) CD 规则1

2) (CD)H 规则1

3) H 规则2，根据1),2) 4) H(AB) 规则1 5) (AB) 规则2，根据3),4) 6) (AB)(RS) 规则1

7) RS 规则2，根据5),6)

8.证明{PQ，QR，PM，M}共同蕴涵R(PQ)。 证明：1) PM 规则1

2) M P 规则2，根据1) 3) M 规则1

4) P 规则2，根据2),3) 5) PQ 规则1

6) PQ 规则2，根据5) 7) Q 规则2，根据4),6) 8) QR 规则1

9) R 规则2，根据7),8) 10) R(PQ) 规则2，根据5),9)

9.证明{PQ，QR，RS}共同蕴涵PS。 证明：1) PQ 规则1

2) P 规则3（附加前提） 3)Q 规则2，根据1),2) 4) QR 规则1

5)R 规则2，根据3),4) 6) RS 规则1

7)S 规则2，根据5),6) 8) PS 规则3，根据2),7)

2.3.4 习题2.4解答

S)}共同蕴涵RS。 (R1.试证明公式： ((PQ)(P(QR)))(PQ)(PR) 是恒真公式。

证明： 原式=((PQ)(P(QR)))(PQ)(PR) =((PQ) (P (QR))) (PQ)(PR) =((PQ) (P Q)( P R)) (PQ) ( PR)

=( P (Q R)) ( P (Q R)) =T

2.模仿主析取式的概念，引进主合取式的概念。 并证明： 对任意命题公式，存在唯一一个与其等价的主合取式。

首先引进极大项概念：

定义6：设P1，…，Pn是n个不同原子，一个子句如果恰好包含所有这n个原子或其否定，且其排列顺序与P1，…，Pn的顺序一致，则称此子句为关于P1，…，Pn的一个极大项。 定义7：设命题公式G中所有不同原子为P1，…，Pn，如果G的某个合取式G’中的每一个子句，都是关于P1，…，Pn的一个极大项，则称G’为G的主合取式。

证明：（对任意命题公式，存在唯一一个与其等价的主合取式。）

由定理1知对于命题公式G，存在与它等价的合取式G’,设G中的不同原子为P1，…，Pn。

对于G’中的每一个子句G’i进行检查，如果G’i不是关于P1，…，Pn的极大项，则G’i必然缺少原子Pj1,…Pjk。则可以通过如下方式扩展G’i G’i= G’i (Pj1 Pj1) …( Pjk Pjk)

k

=Mi1…Mi2

于是将G’中的非极大项G’i化成了一些极大项的合取。 对其它非极大项也做同样处理，得到等价于G的主合取式G’’。

现在证唯一性，也就是证明对任意两个关于P1，…，Pn的主合取式，如果公式不完全相同，则G与H不等价。

任意取两个命题公式G、H是关于P1，…，Pn的两个主合取式。若G和H不完全相同。则必然存在一个极大项Mi在G’中而不在H中（或相反），则取一解释I使Mi取0值，即使公式G取0值。由定义可知I使非Mi的极大项都为1，从而有I使H取1值。所以G与H不等价。

从而有对任意命题公式，存在唯一一个与其等价的主合取式。

3. 证明： 命题公式G是恒真的当且仅当在等价于它的合取式中，每个子句均至少包含一个原子及其否定。

证明：设公式G的合取式为：G’=G1G2…Gn

若公式G恒真，则G’恒真，即子句Gi；i=1,2,…n恒真 为其充要条件。

Gi恒真则其必然有一个原子和它的否定同时出现在Gi中，也就是说无论一个解释I使这个原子为1或0 ，Gi都取1值。

若不然，假设Gi恒真，但每个原子和其否定都不同时出现在Gi中。则可以给定一个

解释I，使带否定号的原子为1，不带否定号的原子为0，那么Gi在解释I下的取值为0。这与Gi恒真矛盾。

因此，公式G是恒真的当且仅当在等价于它的合取式中，每个子句均至少包含一个

原子及其否定。

4. 试将下列公式化为析取式和合取式： a) P(PQ)

b) (PQ)(PQ)

解：a)P(PQ)

=P(PQ) (合取式) =(PP) (PQ) (析取式)

=PQ (合取、析取式) b) (PQ)(PQ)

=( (PQ) (PQ)) ((PQ) (PQ)) =((PQ) ( PQ)) ((PQ) (PQ)) =(PQ ( PQ)) (PQ (PQ)) =(PQ) (PQ) (合取式) =((PQ) P) ((PQ) Q)

=( P Q) (P Q) (析取式)

5. 试将下列公式化为主析取式和主合取式： (1) P((PQ)(QP))； (2) P(P(Q(QR)))。

解：(1) P((PQ)(QP)) =P((PQ) QP)

=P(QP) =(P (QQ)) (QP) =(P Q) (PQ) (QP) (主析取式) =P(QP)

=(PQ) (PP)

=PQ （主合取式） (2) P(P(Q(QR))) =P(P(Q(QR))) =P(PQR)

=PQR （主合取式） =(P(Q Q) (RR)) (Q(P P) (RR)) (R(P P) (QQ)) =(PQR)(PQR) (PQR) (PQR) (QPR) (QPR) (QPR) (QP (RPQ) (RPQ) (RPQ) (RP=(PQR)(PQR) (PQR) (PQR) (QPR) (QPR) (RPQ) =(PQR)(PQR) (PQR) (PQR) (PQR) (PQR) (PQ R) (主析取式)

R) Q)