可有：左边=右边得证

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)个合取组

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

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

合取式也取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，QR

如果P=>Q，Q=>R；对于PQ，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…，GnG}出发可演绎出公式(RR)。其中R为任意公式

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

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

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)

于是将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)