吉林大学离散数学课后习题答案 下载本文

(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)