吉林大学离散数学课后习题

第二章命题逻辑§2.2主要解题方法证明命题公式恒真或恒假主要有以下方法：方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的全部讲解下都是真，所以是恒真的；若表中对应公式所在列的每一取值全为0，这说明该公式在它的全部讲解下都为假，所以是恒假的。真值表法比较烦杂，但只要仔细仔细，不会出错。例说明G=(PQR)(PQ)(PR)是恒真、恒假还是可满足。解：该公式的真值表以下：PQRPQP(PQPRGRQR)(PQ)0001111100111111010111110111111110010011101100111100100111111111表由于表中对应公式G所在列的每一取值全为1，故G恒真。方法二.以基本等价式为基础，经过屡次对一个公式的等价代换，使之最后转变为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。例说明G=((PR)R)((QP)是恒真、恒假还是可满足。解：由(PR)R=

P

R

R=1，以及(Q

P)

P=

（QP）

P=Q

PP=0知，((PR)R)((QP)P)=0，故G恒假。方法三.取式包含全部取式包含全部

设命题公式G含n个原子，若求得nn2个极大项，则G是恒假的。

G的主析G的主合方法四.对任给要判断的命题公式G，设其中有原子P1，P2，，Pn，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，，Pn，再令P1取0值，求G真值，这样连续，到最后只含0或1为止，若最后结果全为1，则公式G恒真，若最后结果全为0，则公式G恒假，若最后结果有1，有0，则是可满足的。例子拜会书中例。方法五.注意到公式G蕴涵公式H的充要条件是：公式H是恒真的；公式G，H等价的充要条件是：公式GH是恒真的，所以，若是待观察公式是GH型的，可将证明GH是恒真的转变为证明G蕴涵H；若是待观察公式是GH型的，可将证明GH是恒真的转变为证明G和H相互相蕴涵。例证明G=(PR)((QR)((PQ)R))恒真。证明：要证明(P恒真，只要证明(P我们使用形式演绎法。

R)((QR)((PQ)R))R)((QR)((PQ)R))。（1）PR规则1（2）QR附加前提（3）PR规则2，依照（1）（4）QR规则2，依照（2）（5）（PR）（QR）规则2，依照（3）、（4）（6）（PQ）R规则2，依照（5）（7）（PQ）R规则2，依照（6）（8）（PQ）R规则2，依照（7）（9）(QR)((PQ)R)规则3，依照（2）、8）公式蕴涵的证明方法主要有以下方法：给出两个公式A，B，证明A蕴涵B，我们有以下几种方法：方法一.真值表法。将公式A和公式B同列在一真值表中，扫描公式A所对应的列，考据该列真值为行家上相应公式B所对应列上的每一项必为A蕴涵B。

1

的每一项，它所1（真），则公式例设A=(PQR)(PQ)，B=(PR)，证明：B。证明：PQRPQPABRQ00011110011111010111101111111001001101100111001001111111表由表能够看出，使A为真的讲解均使B亦为真，所以，AB。方法二.证明AB是恒真公式。由例知，(PQR)(PQ)马上可获得例中的结论：(P(PR)，即AB。

(P

R)恒真，所以，QR)(PQ)例设A、B和C为命题公式，且AB。请分别阐述（必定或否定）以下关系式的正确性。（1）(AC)(BC)；（2）(AC)(BC)。解：由AB知，AB是恒真公式，故A=1时，B不能能为0。真值表以下：ABCAB(AC)(AC)(BC)(BC)000111001111010110011111110111111111表从真值表能够看出，(AC)(BC)(A不是恒真公式，所以，

(AC)(A

C)(BC)

(BC)是恒真公式，所以，C)正确；(AC)(BC)(BC)不正确。例设A=(R

P)Q，B=PB

Q，证明

A蕴涵

B。(

((RP

Q)

P)Q)

(

P

Q)=

(

(

RP)

Q)=((

RP)

Q)(

PQ)=(

R

Q)(P

Q)(P

Q)=1方法三.利用一些基本等价式及蕴涵式进行推导。关于例，由基本等价式可得：A=(R=(

P)

QRP)

Q=(R

P)Q=(R=(R由教材中基本蕴涵式2.P(PQ)，即A蕴涵B。

Q)(PQ)Q)(PQ)QQ可知，(R

Q)

(P

Q)方法四.任取讲解I，若I满足A，往证I满足B。例设A=PQ，B=(RQ)（（PR）Q），证明A蕴涵B。证明：任取讲解I，若I满足A，则有以下两种状况：1）在讲解I下，P为假，这时，B等价于(RQ)RQ），所以，I亦满足B。（2）在讲解I下，P为真，Q为真，所以，PRQ为真，故B为真，即，I满足B。综上，I满足B，所以，A蕴涵B。方法五.反证法，设结论假，往证前提假。关于例，证明(RP)Q蕴涵PQ，若使用方法三，是很烦杂的，而使用方法四，就很简单。假设存在解释I使PQ为假，则只有一种状况，P在I下为真，且Q在I下为假，这时RP在I下为真，故I弄假Q。所以，(RP)Q蕴涵PQ。

(R

P)方法六.分别将公式A和公式B转变为它们各自的主析取式或主合取式。若公式A的主析取式所包含的全部极小项也包含在公式B的主析取式中；也许，公式B的主合取式中所包含的极大项均包含在公式A的主合取式中，则公式A蕴涵公式B。使用这种方法需要注意，当公式A和公式B中包含的原子不完好同样时，在求两公式的极小项或极大项时，要考虑该两公式包含命题原子的并集中的全部原子。在例中，A和B的主析取式分别为：A=(PQR)(PQR)(PQR)(PQR)(PB=(PQR)(PQR)

QR)，(PQ

R)(

PQ

R)

(P

Q

R)

(P

QR)，可见，AB。A和

B的主合取式分别为：A=(P

QR)

(

PQ

R)

(

PQ

R),B=(

PQ

R)

(

PQ

R)可见，

A

B。别的若给出前提会集S={G1，，Gk}，公式G，证明有以下两种方法：1.G1GkG

S

G形式演绎法：依照一些基本等价式和基本蕴涵式，从S出发，演绎出G。教材中已经给出了这方面的例子，在此不再赘述。求主合取式和主析取式极小项与极大项的性质以3个原子为例，则对应极小项和极大项的表为：PQR极小项极大项000m0=PM0=PQRQR0011QR1m=PM=PQR010m2=PQRM2=PQR011m=PQRM=PQR33100m4=PQRM4=PQR101m5=PQRM5=PQR110m=PQRM=PQR66111m=PQRM=PQR77表由表可知，对n个命题原子P1，，Pn，极小项有以下性质：1）n个命题原子P1，，Pn有2n个不同样的讲解，每个讲解对应P1，，Pn的一个极小项。（2）对P1，，Pn的任意一个极小项m，有且只有一个讲解使m取1值，若使极小项取1的讲解对应的二进制数为i，则m记为mi，于是关于P1，，Pn的全部极小项为m0，m1，，m2n1。（3）任意两个不同样的极小项的合取式恒假：mimj=0，≠j。2n1（4）全部极小项的析取式恒真：mi=1。i0极大项有以下性质：（1）n个命题原子P1，，Pn有2n个不同样的讲解，每个解释对应P1，，Pn的一个极大项。（2）对

P1，，

Pn

的任意一个极大项

M，有且只有一个讲解使M取0值，若使极大项取0的讲解对应的二进制数为i，则M记为Mi，于是关于P1，，Pn的全部极大项为M0，M1，，M2n1。（3）任意两个不同样的极大项的析取式恒真：MiMj=1，i≠j。2n1（4）全部极大项的合取式恒假：Mi=0。i0主合取式与主析取式之间的关系由极小项和极大项的定义可知，二者有以下关系：mi=Mi，Mi=mi由此可知，若PQR为一公式G的主合取式，则G=G=M0=(M1M2M6)=MMM126=m1m2m6为G的主析取式。若（PQ）（PQ）（PQ）为一公式的主析取式，则H=H=(（PQ）（PQ）（PQ）)=

（（m0

m1

m3））(m2)=M2=PQ为H的主合取式。一般地，若公式A中含n个命题原子，且A的主析取式中含有k个极小项：mi1,...,mik，则A的主析取式中必含有其余的2n-k个极小项，不如设为：mj1,...,mjn，即2kA=mj1...mj2nk。所以，A=A=（mj1...mj2nk）=mj1...mj2nk=Mj1...Mjn。2k由此可知，从一公式A的主析取式求其主合取式的步骤以下：1）求出A的主析取式中没有包含的全部极小项。2）求出与（1）中极小项下标同样的极大项。（3）将（2）求出的全部极大项合取起来，即得式。

A的主合取近似地，从一公式A的主合取式求其主析取式的步骤为：1）求出A的主合取式中没有包含的全部极大项。2）求出与（1）中极大项下标同样的极小项。（3）将（2）求出的全部极小项析取起来，即得A的主析取式。求主合取式和主析取式的方法方法一.真值表法。主析取式恰好是使得公式为真的讲解所对应的极小项的析取组成，主合取式恰好是使得公式为假的讲解所对应的极大项的合取组成。方法二.公式推导法。设命题公式G中全部不同样原子为P1，，Pn，则G的主析取式的求法以下：将公式G化为析取式。删去析取式中全部恒假的短语。用等幂律将短语中重复出现的同一文字化简为一次出现，如，PP=P。关于全部不是关于P1，，Pn的极小项的短语使用同一律，补进短语中未出现的全部命题原子，并使用分配律张开，即，若是短语Gi’不是关于P1，，Pn的极小项，则Gi’中必然缺少原子，不如设为Pj1，，Pjk，于是Gi’=Gi’(Pj1Pj1)(PjkPjk)=mi1...mik2这样，就将非极小项Gi’化成了一些极小项之析取。将同样的短语的多次出现化为一次出现，就获得了给定公式的主析取式。主合取式的求法近似，留给读者作为练习。由上面谈论可知，只要求出一种式，可马上获得别的一种式。例求公式G=P→(Q→R)的主析取式与主合取式。解：（1）使用真值表法。见表。PQRP→(Q→R)00010011010101111001101111001111表依照真值表中使得公式为真的讲解，所对应的极小项的析取即为其主析取式：G=(

P

QR)PQ

(R)

P

QR)

((

PQ

R)

(P

QR)

(P

QR)=m

(P0

QR)m1m2

m3

m4

m5

m7依照真值表中使得公式为假的讲解，所对应的极大项的合取即为其主合取式：G=PQR=M6（2）公式推导法G=P→(Q→R)=

P

QR=（

P（Q

Q）

（R

R））（Q（P

P）

（R

R））（R

（P

P）

（Q

Q））=(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)=m0m1m2m3m4m5m7G=P→(Q→R)=PQRM6主合取式与主析取式的应用1）由可知，利用主合取式与主析取式可求解判断问题。2）证明等价式成立。由于任意公式的主式是唯一的，所以能够分别求出两个给定的公式的主式，若二者主式相同，则给定的两公式是等价的，否则，给定的两公式不等价。求（

例判断P→(Q→R)与（PQ）→R可否等价。证明：我们利用求主合取式的方法来判断。由例知，P→(Q→R)的主合取式为：M6。下面PQ）→R的主合取式。（PQ）→R=（PQ）R=

（

P

Q）

R=

（PR）

（QR）=

（P（

Q

Q）

R）（（P

P）

QR）=（PQR）（PQR）（PQR）=M2M4M6二者的主合取式不同样，所以，这两个公式不等价。联系词的转变和全功能集关于联系词的转变和全功能集方面一般有以下题型：（1）要求只用几个联系词表示某个命题公式，见例。2）给出一个新的联系词的定义，要求证明其是全功能集，并用其表示某个命题公式。这种题目的做法以下：由于不难证明出{，}，{，}，{，→}，{}，{}都是全功能联系词会集，所以，若要证明新定义的联系词是全功能集，只要证明上面某个全功能会集（比方{，}）中的每个联系词（如，和）都能够用新联系词表示。若想用其表示某个命题公式，能够先将基本联系词（，，）用给定的新联系词表示，尔后按要求把原命题公式转变为用新联系词表示的形式。见例。3）证明一个联系词会集不是全功能集。一般用归纳法，证明在有限步，用这个联系词结合不能能表示全部的命题。见例。应该说明的是，追求最少联系词的全功能联系词会集，主要不是个理论问题，而是为了满足工程实践的需要。但是，一般状况下，为了不至于由于联系词的减少而使得公式的形式变得复杂，我们仍常采用“，，，→，”这5个联系词。例将公式（P→（QR））（PQ）用仅含联系词和的公式等价表示。解：（P→（QR））（PQ）=（P（QR））（PQ）=（P（PQ））（（QR）（PQ））=（PQ）（Q（PQ））（R（PQ））=（PQ）（PQ）（（PQ）R）=PQ=（PQ）例定义三元联系词如表。e1e2e3f(e1,e2,e3)00010011010001101001101111011110表三元联系词f(e1,e2,e3)的真值表（1）试证明{f}是齐全的，即，联系词会集{，}或{，}可由该联系词表示。2）用该联系词表示公式：（P→R）Q。1）证明：由于所以联系词会集{而联系词会集

{

，}可由该三元联系词，}是齐全的，所以，

Q)f表示。{f}是齐全的。（2）解：由于PQ=f(P,P,Q)，所以P→Q=PQ=f(P,P,Q).又由PQ=

(

P=

Q)=(f(P,P,Q)=

Q

P)f(Q,Q,P).所以（P→R）Q=f(P,P,R)Q=f(Q,Q,f(P,P,R))=f(Q,Q,f(P,P,f(R,R,R)))=f(f(Q,Q,f(P,P,f(R,R,R))),P,f(R,R,R))),f(Q,Q,f(P,P,f(R,R,R))))

f(Q,。

Q,f(P,例2.2.12{，→}是否是联系词的全功能会集？证明你的结论。在证明此题从前，我们先直观解析一下。考虑和→这两个联系词的特点：当一个命题公式中只含有联系词和→时，则当公式中出现的全部命题原子都取真值1时，公式也必然取真值

1。这就是说，仅含

和→的公式不能够表示全部的命题公式，比方恒假式：

A

A。所以，联系词会集

{

，→}不是全功能集。证明：下面证明{，→}不是联系词的全功能集。对公式中出现的联系词个数使用数学归纳法来证明下面的结论：当一个命题公式中只含有联系词和→时，则当公式中出现的全部命题原子都取真值1时，公式也必然取真值1。n=0时，即公式中不含任何联系词时，公式为原子，结论显然。假设n≤k时，命题成立，即，若是一个公式中含有n个联系词，→，则当公式的全部原子真值取1时，公式也取真值1。当n=k+1时，设任一含k+1个联系词的公式为A，则存在公式B和C，使得：A=B→C或

A=B

C，且B和

C中的联系词个数均≤

k。由归纳假设知，当全部原子取真值1时，B和C在该讲解下的真值均为1，所以，A在该讲解下的真值亦为1。归纳完成。由该结论知，若是一个命题公式中只含有联系词和→，那么最少存在一个讲解满足该公式。所以，只含有联系词和→的公式必定不能够表示恒假公式。所以，{，→}不是联结词的全功能集。综合应用题综合题主若是先符号化，再使用上面的知识进行联系词的转变、或求主合取式、主析取式、利用基本等价式化简、或进行逻辑推理来论证或做逻辑判断等。例一个排队线路，输入为A，B，C，其输出分别为FA,FB,FC。在同一时间只能有一个信号经过。假好像时有两个或两个以上信号经过时，则按A，B，C的序次输出。比方，A，B，C同时输入时，只能A有输出。写出FA,FB,FC的逻辑表达式，并化成全功能集{}中的表达式。解：先将已知事实中的各简单命题符号化，设：：A输入；：B输入；：C输入。尔后依照已知条件，写出FA,FB,FC的真值表如表。PQRFAFBFC000000001001010010011010100100101100110100111100表于是，(P

Q=

FA=(PR)(P（（P

QQR)Q）

（

R)R

(PR））

（（P

QR)Q（

RR））=

（P

Q）

（P

Q）=P

（QQ）=P=

(P

P)===(P

FB=(=(

(PP)((PP)P)PQPQ)

(P

(PP))P).R)(PQ（RR）

R)PQ=(=(P

PQ)Q)=P=PFC=

P

Q(Q

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

(PQR)Q)(R)(PQ))(PQ))Q)(P

(

(R)Q))

R)

(R

R)例一一个公安人员审查一件盗窃案，已知的事实以下：1）A或B盗窃了x2）若A盗窃了x，则作案时间不能够发生在子夜前3）若B证词正确，则在子夜时屋里灯光未灭4）若B证词不正确，则作案时间发生在子夜前5）子夜时屋里灯光灭了6）A其实不丰饶试用演绎法找出盗窃犯。解：先将已知事实中的各简单命题符号化，设：P：A盗窃了xQ：B盗窃了xR：作案时间发生在子夜前S：B证词正确T：在子夜时屋里灯光未灭U：A其实不丰饶再将各前提写出：G1：P∨QG2：P→RG3：S→TG4：：S→RG5：TG6：U演绎过程为：（1）S→T（规则１）（2）T（规则１）（3）S（规则2）（4）S→R（规则１）（5）R（规则2）（6）P→R（规则１）（7）P（规则2）（8）P∨Q（规则１）（9）Q（规则2）所以，是B盗窃了x。例一甲、乙、丙、丁四个人有且仅有两个人参加围棋优胜比赛。关于谁参加比赛，下面四种判断都是正确的：1）甲和乙只有一人参加；2）丙参加，丁必参加；3）乙或丁至多参加一人；4）丁不参加，甲也不会参加。请推断出哪两个人参加了围棋比赛。解：先将已知事实中的各简单命题符号化，设：P：甲参加了比赛；Q：乙参加了比赛；R：丙参加了比赛；S：丁参加了比赛.依已知条件（1）--（4）有：（1）(PQ)(PQ)2）R→S3）（QS）4）S→P将（1）-（4）式合取起来有：（(PQ)(PQ)）（R→S）（QS）S→P）=（(Q

(PS)(S

Q)P)

(P

Q)）

（RS）=(P

Q

RS)

(P

QS)

(

PQR

S)依照已知，甲、乙、丙、丁四个人有且仅有两个人参加比赛，知，

PQ

R

S为假，所以只有

(P

QRS)

(P

QS)

为真，即甲和丁参加了比赛。§2.3第二章习题解答习题2.1解答设P是命题“天下雪”；Q是命题“我上街”；R是命题“我有时间”。（1）用逻辑符号写出以下命题：a．如天不下雪并且我有时间，那么我上街。b．我去上街，仅当我有时间。c．天不下雪。d．天正在下雪，我也没去上街。解：a可表示为：(PR)Q；b可表示为：QR；c可表示为：P；d可表示为：PQ。2）对下述命题用中文写出语句。a．Q（RP）．RQ．（QR）（RQ）．（RQ）解：a为：我上街当且仅当我有时间并且天不下雪；为：我有时间并且上街了；为：我上街了当且仅当我有时间；为：我每时间又没上街。说出下述每一命题的抗命题和逆否命题：（1）若是天下雨，我将不去。（2）仅当你去我将逗留。（3）若是n是大于2的正整数，则方程xn+yn=zn无正整数解。（4）若是我不获得更多帮助，我不能够完成这个任务。解：（1）抗命题为：若是我不去，那么天下雨；逆否命题为：若是我去，那么天不下雨。（2）抗命题为：仅当我将逗留你去；逆否命题为：你不去我将不断留。（3）抗命题为：若是方程xn+yn=zn无正整数解，则n是大于2的正整数；逆否命题为：如nnn有正整数解，则n是不大于2的正整数。果方程x+y=z抗命题为：我不能够完成这个任务，由于我没有获得更多帮助。逆否命题：若是我完成了任务，则我获得了更多帮助。给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：a)(P(QR))((PQ)(RS))b)((PQ)R)(((PQ)R)S)c)((PQ)R)((QP)(RS))d)(P(Q(RP)))(QS)解：a)令G=(P(QR))((PQ)(RS))则：TI(G)=(1(10))((11)(00))=00=1b)令G=((PQ)R)(((PQ)R)S)则：TI(G)=((11)0)(((11)0)0)=10=1c)令G=((PQ)R)((QP)(RS))=((PQ)R)(((QP)(PQ))(RS))=(PQR)((QP)(PQ)(RS))则：TI(G)=(110)((11)(11)(00))=11=1d)令G=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=((P(Q(RP)))(QS))((QS)(P(Q(RP))))=(P(Q(RP)))(QS))((QS)(P(Q(RP))))TI(G)=(1(1(01)))(10))((10)(1(1(01))))=11=1习题2.1解答组成以下公式的真值表：Q（PQ）P（PQR）（PQ）（PR）(3)(PQQR）PR(4)（（PPQ）R）QR解：（1）设G=Q（PQ）P，其真值表以下：PQG001010101111（2）设G=（PQR）（PQ）（PR），其真值表以下：PQRGPQRG00001001001010100100110101101110（3）设G=(PQQR)PR，其真值表以下：PQRGPQRG00001001001010110101110101101110（4）设G=（（PPQ）R）QR，其真值表以下：PQRGPQRG00011001001010100101110101111111指出以下公式哪些是恒真的哪些是恒假的：(1)P（PQ）Q（PQ）（PQ）(3)（PQ）（QR）（PR）(4)（PQ）（PQPQ）解：（1）是恒真的，（2）是恒真的，（3）是恒真的，（4）是可满足的。3.对

P和

Q的全部值，证明

P

Q与

PQ有同样的真值。证明（

P

Q）

（

PQ）是恒真的。解：对PQ的任意讲解I，若I使PQ为真，则I使P为假或I使P为假，则使P，此时PQ为真，若I使P和Q同时为真，则为真，也就是说PQ为真时PQ为真。若I使PQ为假，则I时PQ为假，也就是说PQ为假时PQ为假。综上知PQ与定义知（PQ）（PQ）是恒真的。

P和Q同时为真，若Q为真，此时PQ使P为真Q为假，此PQ同真同假，由判断以下公式是恒真？恒假？可满足？a)(P(QR))(P(QR))；b)P(P(QP))；c)(QP)(PQ)；d)(PQ)(PQ)。解：（1）设G=(P(QR))(P(QR))=(P(QR))(P(QR))=(((P(QR))P)((P(QR))QR)=((PP)(PQR))((P(QR))QR)=((PP)(PQR))((PQ)(PR)QR)=((PP)(PQR))(((PQ)Q)((PR)R))=(PQR)(PQR)，其真值表以下：PQRGPQRG00011000001010100100110001101111所以G是可满足的。（2）设G=P(P(QP))=P(P(QP))PP=T其真值表以下：PQG001011101111G(3)G=(QP)=(QP)=(PQ)

(

(

PQ)PQ)(PQ)=F其真值表以下：PQG000010100110所以G是恒假的。(4)G=(PQ)(PQ)=(PQ)((PQ)(QP))=(PQ)((PQ)(QP))=(PQ)(PQ)(PQ)其真值表以下：PQG000011101111所以G是可满足的。习题2.3解答证明下面的等价式：(1)(P(QR))(QR)(PR)=R(2)P(QP)=P(PQ)(3)P(QR)=(PQ)(PR)(4)(PQ)(RQ)=(PR)Q(1)证明：(P(QR))(QR)(PR)=(((P(QR))Q)((P(QR))=((((PQ)(RQ))((PR)R))=((PQ)(RQ)R)(PR)=((PQ)R)(PR)=(PR)(QR)(PR)=R(PP)(QR)=R得证。(2)证明：左边=P(QP)=P(QP)=PQP=PPQ=T右边=P(PQ)=PPQ=T

R))(P

R)

(P

R)可有：左边=右边，得证(3)证明：左边=PQR右边=PQPR=PQR可有：左边=右边，得证(4)证明：左边=(PQ)(RQ)=(PR)Q=(PR)Q=(P

R)

Q=右边得证2设

S={G1，，

Gn}

是命题公式会集。试求出在不增加新原子的状况下从

S出发演绎出的全部命题公式。提示：考虑G1Gn的主合取式。解：任设一公式G’为从S出发演绎出来的公式。则可知G’为G=G1Gn的一个逻辑结果。而G有唯一一个与其等价的主合取式，设为G’’。可设G’’共有m个极大项，则能够知道令G’’取1的讲解使这m个极大项也取1。则从S出发的演绎出来的的全部命题公式正是从这m个极大项中任取n(0≤n≤m)个合取组m设H为由若干极大项组成的合取公式。现在证明：1)S=>H，即G=>H。从定义出发，设有一讲解I使G=G1Gn取1值，必使G的主合取式也取1值。即使每一个极大项都取1值。从而使由若干极大项合取组成的公式H也取1值，则有S=>H。任意设公式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矛盾。证明：两个公式之间的蕴涵关系拥有反身性，反对称性和传达性。证明：a)任意设一公式P,由于PP是恒真的，则有P=>P即蕴涵关系有反身性。任取两个命题公式P，Q若是P=>Q并且Q=>P，则有PQ恒真，QP恒真，则（PQ）那么有PQ恒真，得出P=Q，所以蕴涵关系有反对称性。c)任取命题公式P，Q，R若是P=>Q，Q=>R；关于P，Q，R的任意一个讲解I。若是I满足若I满足Q则I满足R。则有I满足P时，也满足R，故有P=>R。所以蕴涵关系有传达性。

（QP）恒真，P则I也满足Q，证明：若前提会集S中的公式都是恒真的，G是从S出发的一个演绎的逻辑结果，则G必是恒真公式。证明：设S是由

G1，，Gn组成的，则

G1，，Gn是恒真的，那么

G1

Gn是恒真的，而由已知有：G1Gn=>G，所以由蕴涵定义有G必为恒真公式。设G1，，Gn是公式。证明：从{G1，，Gn}出发可演绎出公式G的充要条件是从{G1，，Gn，G}出发可演绎出公式(RR)。其中R为任意公式。证明：充分性，即{G1，，G，G}=>(RR)，可有nGGnG=>(RR)，因(RR)恒假，则GGnG恒假。那么有11（GG）G恒真，即（GG）G恒真，则有(G1G)=>G，所以有1n1nn{G1，，Gn}蕴涵G。必要性，即已知：{G，，G}=>G，有（GG）G恒真，即（G1n1n1Gn）G恒真，那么对上式取非有G1GnG恒假，也就是(G1GnG)(RR)恒真，其中R为任意一个公式，则有(G1GnG)=>(RR)，即从{G1，，Gn，G}出发可演绎出公式(RR)。命题得证。证明以下蕴涵式：(1)(PQ)(PQ)证明：要证上式成马上证则：(PQ)(PQ)=(PQ)(=(PQ)(=PQQ

(PQ)PQ)PQ)

(P

Q)恒真，=T即：(P

Q)(P

Q)恒真命题得证。

(或从PQ

Q，Q(P

Q))(2)P

(Q

P)证明：同

a)，P(Q

P)=P

(

QP)=P

P

Q=T命题得证。(或从P(3)(P(QR))(PQ)证明：(P(QR))=(PQR)

(

(P(P

QP)出发)R)Q)(P(PQ

R)R)=T得证。(4)P

QP

(P

Q)证明:若P(PQ)为假，则PQ为假，

P为真。所以有

Q为假，则PQ为假，

(后件假推出前件假等价于前件真推出后件真

)得证。(5)(P

Q)QPQ证明：(PQ)Q=(PQ)Q=(PQ)Q=(PQ)(QQ)=>(PQ)(基本蕴涵式)(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)(RS)}共同蕴涵RS。证明：1)CD规则12)(CD)H规则13)H规则2，依照1),2)4)H(AB)规则15)(AB)规则2，依照3),4)6)(AB)(RS)规则17)RS规则2，依照5),6)8.证明{PQ，QR，PM，M}共同蕴涵R(PQ)。证明：1)PM规则12)MP规则2，依照1)3)M规则14)P规则2，依照2),3)5)PQ规则16)PQ规则2，依照5)7)Q规则2，依照4),6)8)QR规则19)R规则2，依照7),8)10)R(PQ)规则2，依照5),9)9.证明{PQ，QR，RS}共同蕴涵PS。证明：1)PQ规则12)P规则3（附加前提）3)Q规则2，依照1),2)4)QR规则15)R规则2，依照3),4)6)RS规则17)S规则2，依照5),6)8)PS规则3，依照2),7)习题2.4解答试证明公式：((PQ)(P(QR)))(PQ)(PR)是恒真公式。证明：原式=((PQ)(P(QR)))(PQ)(PR)=((PQ)(P(QR)))(PQ)(PR)=((PQ)(PQ)(PR))(PQ)(PR)=(P(QR))(P(QR))=T模拟主析取式的看法，引进主合取式的看法。并证明：对任意命题公式，存在唯一一个与其等价的主合取式。第一引进极大项看法：定义6：设P，，P是n个不同样原子，一个子句若是恰好包含全部这n个原子或其否1n定，且其排列序次与P1，，Pn的序次