薄荷少年解答：
(1)将公式(p→(q∧r))∨p化成与之等值的且仅含?和∧的公式，可利用等值式：
(A∨B)??(?A∧?B)(A→B)?(A→B)??(A∧?B)
从而：
(p→(q∧r))∨p?(?(∧?(q∧r)))∨p//(?A∨B)??(A∧?B)
??((p∧?(q∧r))∧?p)//(A∨B)??(?A∧?B)
当然，我们也可先将原来的公式在某种程度上进行化简，然后再利用上述等值式：
(p→(q∧r))∨p?(?p∨(q∧r))∨p//蕴涵等值式
?(?p∨p)∨(q∧r)//结合律
?1∨(q∧r)//排中律
?1//零律
?(?p∨p)//排中律
??(p∧?p)//(A∨B)??(?A∧?B)
7
(2)我们先将公式(p→(q∧?p))∧q∧r作适当地化简，然后利用下面的等值式：
(A∧B)??(?A∨?B)(A→B)?(?A∨B)
将该公式化成与之等值的且仅含?和∨的公式：
(p→(q∧?p))∧q∧r?(?p∨(q∧?p))∧q∧r//蕴涵等值式
??p∧q∧r//吸收律
??(p∨?q∨?r)//(A∧B)??(?A∨?B)
(3)上面已经将公式(p→(q∧?p))∧q∧r适当地化简了，在化简的基础上，并利用下面等值式：
(A∧B)??(?A∨?B)??(A→?B)(A∨B)?(?A→B)
将该公式化成与之等值的且仅含?和→的公式：
(p→(q∧?p))∧q∧r??(p∨?q∨?r)//上一小题
??(r→(p∨?q))//蕴涵等值式
??(r→(q→p))//蕴涵等值式
(4)我们先将公式p→(?p→q)化简：
p→(?p→q)??p∨(p∨q)?1
也即公式p→(?p→q)是永真式，从而我们只要使用{↑}和{↓}构造出永真式即可，例如我们将p∨?p用仅含{↑}或{↓}的公式表示。为此，我们先考虑使用这两个联结词表示否定、析取和合取联结词，不难看到：
?A?A↑A?A?A↓A
从而由A↑B??(A∧B)有：
A∧B??(A↑B)?(A↑B)↑(A↑B)
而由A∨B??(?A∧?B)有：
A∨B??(?A∧?B)??A↑?B?(A↑A)↑(B↑B)
类似地，由A↓B??(A∨B)有：
A∨B??(A↓B)?(A↓B)↓(A↓B)
而由A∧B??(?A∨?B)有：
A∧B??(?A∨?B)??A↓?B?(A↓A)↓(B↓B)
从而有：
p→(?p→q)?p∨?p?p∨(p↑p)?(p↑p)↑((p↑p)↑(p↑p))
?p∨?p?p∨(p↓p)?(p↓(p↓p))↓(p↓(p↓p))
通过上面的分析，我们看到↑和↓满足交换律，但不满足幂等律和结合律。
8
点评：大多数同学都做得过于复杂，没有将原公式先化简；有些同学没有做第4小题，有些同学在第4小题中出现0和1,严格说这是不对的。最后，非常奇怪的是，许多人在等值演算中都认为1∨q等值于q，而正确的答案是等值于1。
作业2.4使用等值演算方法求与下面公式等值的析取范式和合取范式（请注意写清楚等值演算中所用的基本等值式）：
(1)(p∧q)∨?(p∧q)
(2)p→(?p∧q∧r)
(3)?(p∨?q)∧(s→t)
解：
(1)
(p∧q)∨?(p∧q)?(p∧q)∨(?p∨?q)//德摩根律
?(p∨?p∨?q)∧(q∨?p∨?q)//分配律
?p∨?p//排中律、同一律
因此(p∧q)∨?(p∧q)是永真式，与它等值的析取范式和合取范式都可取公式p∨?p。
(2)
p→(?p∧q∧r)??p∨(?p∧q∧r)//蕴涵等值式
??p//吸收律
因此与p→(?p∧q∧r)等值的合取范式和析取范式都可取公式?p。
(3)
?(p∨?q)∧(s→t)??(p∨?q)∧(?s∨t)//蕴涵等值式
?(?p∧q)∧(?s∨t)//德摩根律
?(?p∧q∧?s)∨(?p∧q∧t)//分配律
因此与?(p∨?q)∧(s→t)等值的析取范式是：
(?p∧q∧?s)∨(?p∧q∧t)
而与它等值的合取范式是?p∧q∧(?s∨t)。
作业2.5使用等值演算方法或构造真值表法求与下面公式等值的主析取范式和主合取范式（请注意，如使用等值演算法请写清楚所用的基本等值式，如使用构造真值表法请列出构造过程中的子公式）：
(1)(?p∨?q)→(p?q)
(2)(p→(q∧r))∧(?p→(?q∧?r))
(3)p→((q∧r)→s)
解：
9
(1)
(?p∨?q)→(p?q)?(?p∨?q)→((?p∨q)∧(?q∨p))//等价等值式
??(?p∨?q)∨((?p∨q)∧(?q∨p))//蕴涵等值式
?(p∧q)∨((?p∨q)∧(?q∨p))//德摩根律
?(p∧q)∨(?p∧?q)∨(p∧q)//分配律、排中律、同一律
?(?p∧?q)∨(p∧q)//幂等律、交换律
?m0∨m3
因此与公式(?p∨?q)→(p?q)等值的主析取范式是m0∨m3，而主合取范式是M1∧M2。
(2)
(p→(q∧r))∧(?p→(?q∧?r))?(?p∨(q∧r))∧(p∨(?q∧?r))//蕴涵等值式
?(?p∨q)∧(?p∨r)∧(p∨?q)∧(p∨?r)//分配律
上式已经是合取范式，我们对其进行扩展以得到主合取范式：
?p∨q?(?p∨q∨r)∧(?p∨q∨?r)?M4∧M5
?p∨r?(?p∨q∨r)∧(?p∨?q∨r)?M4∧M6
p∨?q?(p∨?q∨r)∧(p∨?q∨?r)?M2∧M3
p∨?r?(p∨q∨?r)∧(p∨?q∨?r)?M1∧M3
因此与公式(p→(q∧r))∧(?p→(?q∧?r))等值的主合取范式是：
(p→(q∧r))∧(?p→(?q∧?r))?M1∧M2∧M3∧M4∧M5∧M6
从而与之等值的主析取范式是m0∨m7。
(3)
p→((q∧r)→s)??p∨((q∧r)→s)//蕴涵等值式
??p∨(?(q∧r)∨s)//蕴涵等值式
??p∨(?q∨?r)∨s//德摩根律
?M14
上式已经是一个极大项，也就是说已经是一个主合取范式，从而与上述公式等值的主析取范式是：m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7∨m8∨m9∨m10∨m11∨m12∨m13∨m15
点评：有几个常见问题：1)不少同学在做这一题的时候不能正确判断是使用真值表还是使用等值演算，例如最后一小题，实际上它的主合取范式很容易得到，有的同学列真值表花了不少时间；2)还是有同学不明白主合取范式与主析取范式之间的关系，本来只要求其中一个主范式则可得到另外一个主范式，但却做了多余的工作，两次使用等值演算分别求了主合取范式和主析取范式；4)许多同学在给出主范式的时候不是给出极小项和极大项的编码，也有同学用错编码的大小写，甚至有的同学搞错极小项和极大项的二进制编码，例如只有两个变量时却出现m4。
10
作业2.6某电路有一个灯泡和三个开关A,B,C。已知在且仅在下述四种情况下灯亮：
(a)C的扳键向上，A,B的扳键向下；
(b)A的扳键向上，B,C的扳键向下；
(c)B,C的扳键向上，A的扳键向下；
(d)A,B的扳键向上，C的扳键向下。
设F为1表示灯亮，p,q,r分别表示A,B,C的扳键向上（也即?p,?q,?r分别表示A,B,C的扳键向下）。
(1)求F的主析取范式；
(2)在联结词完备集{?,∧}上构造F；
(3)在联结词的完备集{?,→}上构造F。
解：
(1)为求F的主析取范式，我们根据题意列出F的真值表：
p q r F备注
0000
0011C的扳键向上，A,B的扳键向下
0100
0111B,C的扳键向上，A的扳键向下
1001A的扳键向上，B,C的扳键向下
1010
1101A,B的扳键向上，C的扳键向下
1110
从而可写出F的主析取范式：
F?m1∨m3∨m4∨m6?(?p∧?q∧r)∨(?p∧q∧r)∨(p∧?q∧?r)∨(p∧q∧?r)
(2)为在联结词完备集{?,∧}上构造F，我们对F作进一步的化简：
F?(?p∧r)∨(p∧?r)??(?(?p∧r)∧?(p∧?r))
(3)类似地，我们有：
F?(?p∧r)∨(p∧?r)??(p∨?r)∨?(?p∨r)?(r→p)→?(p→r)
点评：许多同学仍然在某个完备集表示公式的时候，没有先讲公式化简，从而使得答案非常复杂。
作业2.7A,B,C,D四人要派两个人出差，按下述三个条件有几种派法？如何派？
(a)若A去，则C和D中要去且仅去一人；
(b)B和C不能都去；
(c)若C去，则D不能去。
解：设：(i)用p表示派A出差；(ii)用q表示派B出差；(iii)用r表示派C出差；(iv)用s表示派D出差。从而上述条件符号化为：
(a)若A去，则C和D中要去且仅去一人，符号化为：
p→((r∧?s)∨(s∧?r))??p∨((r∨s)∧(?s∨?r))?(?p∨r∨s)∧(?p∨?s∨?r)
11
(b)B和C不能都去，符号化为：
?(q∧r)??q∨?r
(c)若C去，则D不能去，符号化为：
r→?s??r∨?s
也即选派方案必须满足的条件是：
F?(?p∨r∨s)∧(?p∨?r∨?s)∧(?q∨?r)∧(?r∨?s)
上述公式是合取范式，我们使用编码方式将上式扩展为主合取范式。
(1)公式?p∨r∨s的编码为1?00，它扩展出的极大项编码应该是1000和1100，即M8和M12；
(2)公式?p∨?r∨?s的编码为1?11，它扩展出的极大项编码应该是1011和1111，即M11和M15；
(3)公式?q∨?r的编码为?11?，它扩展出的极大项编码应该是0110,0111,1110和1111，即M6,M7,M14,M15；
(4)公式?r∨?s的编码为??11，它扩展出的极大项编码应该是0011,0111,1011和1111，
即M3,M7,M11,M15。
因此F的主合取范式是：
F?M3∧M6∧M7∧M8∧M11∧M12∧M14∧M15
从而F的主析取范式是：
F?m0∨m1∨m2∨m4∨m5∨m9∨m10∨m13
对应的成真赋值分别是0000,0001,0010,0100,0101,1001,1010,1101，进一步根据题意要派两个人出
差，因此真正的成真赋值只能取0101,1001,1010，即q,t为真，或p,t为真，或者p,s为真，即选派方案
有三个：
派B和D出差或者派A和D出差或者派A和C出差
点评：不少同学嫌烦，从而没有认真去扩展，也没有给出其他合适的方法来求解，可能是参考
别人的答案吧！有些同学使用真值表的方式进行求解，但列得不是很清晰。
12
第三章命题逻辑的自然推理
作业3.1试仿照否定引入规则正确性的证明，证明析取消除规则
Γ A∨BΓ,A CΓ,B C
Γ C
的正确性。
证明设Γ={A1,A2,···,A n}，D=A1∧A2∧···∧A n。要证明上述规则的正确性，根据规则正确性的定义即要证明，对任意的真值赋值函数t:Var→{0,1}有：如果t(D→A∨B)= 1，t(D∧A→C)=1以及t(D∧B→C)=1，则有t(D→C)=1。由于t(D→C)=0当且仅当t(D)=1而t(C)=0，因此我们分两种情况讨论：
1.如果t(D)=0，则总有t(D→C)=1；
2.如果t(D)=1，则根据蕴涵联结词的定义，由t(D→A∨B)=1可得t(A∨B)=1，则t(A)=1或t(B)=1：
(i).如果t(A)=1，则t(D∧A)=1，从而由t(D∧A→C)=1必有t(C)=1，从而t(D→C)=1；
(ii).若t(B)=1，则t(D∧B)=1，从而由t(D∧B→C)=1必有t(C)=1，从而t(D→C)=1。
总之，无论何种情况，对任意的真值赋值函数，当t(D→A∨B)=1，t(D∧A→C)=1以及t(D∧B→C)=1时，总有t(D→C)=1，这就表明上述规则是正确的。
作业3.2试给出证明破坏性二难推理规则
Γ ?C∨?DΓ A→CΓ B→D
Γ ?A∨?B
正确性的证明序列。
解答：验证上述派生规则正确的证明序列如下：
(1)Γ A→C//前提引入
(2)Γ,?C A→C//(1)弱化规则
(3)Γ,?C ?C//前提引入
(4)Γ,?C ?A//(2),(3)假言易位
(5)Γ,?C ?A∨?B//(4)析取引入
(6)Γ B→D//前提引入
(7)Γ,?D B→D//(6)弱化规则
(8)Γ,?D ?D//前提引入
(9)Γ,?D ?B//(7),(8)假言易位
13
(10)Γ,?D ?A∨?B//(9)析取引入
(11)Γ ?C∨?D//前提引入
(12)Γ ?A∨?B//(5),(10),(11)析取消除
作业3.3试根据推理有效性的含义及派生规则正确性的含义证明：对任意的前提集Γ和公
式A1,A2,···,A n，若A1,A2,···,A n A是有效的推理，则下述派生规则
Γ A1Γ A2···Γ A n
Γ A
是正确的。
证明设Γ={B1,B2,···,B m}，D=B1∧B2∧···∧B m,E=A1∧A2∧···∧A n。根据规则正确性的定义，要证明上述派生规则的正确，则要证明对任意的真值赋值函数t:Var→{0,1}，如果对
任意的1≤i≤n，t(D→A i)=1，则有t(D→A)=1。同样，我们可分两种情况讨论：
(1).如果t(D)=0，则总有t(D→A)=1；
(2).如果t(D)=1，则因为对任意的1≤i≤n都有t(D→A i)=1，从而对任意的1≤i≤n都有t(A i)=1，从而有
t(E)=t(A1∧A2∧···∧A n)=1
由于推理A1,A2,···,A n A是有效推理，根据推理有效性的定义，这意味着对任意的真值赋值函数t都有t(E→A)=1，而现在t(E)=1，那么必有t(A)=1，从而我们得到t(D→A)=1。
因此无论何种情况都有t(D→A)=1，这表明上述派生规则是正确的。
作业3.4在自然推理系统中验证下述推理的有效性：
(1)q→p,q?s,s?t,t∧r p∧q；
(2)(p∨q)→(r∧s),(s∨t)→u p→u；
(3)p→?q,?r∨q,r∧?s ?p；
(4)p→(q→r),r→?r,s→p,t→q s→?t。
