《数理逻辑》课程作业参考答案
周晓聪(isszxc@https://www.doczj.com/doc/2619218668.html,)
中山大学计算机科学系,广州510275
2010年1月11日
第一章命题逻辑的基本概念
作业1.1判断下列语句是否是命题，并对命题确定其真值：
(1)火星上有生命存在.
(2)12是质数。
(3)香山比华山高。
(4)x+y=2。
(5)这盆茉莉花真香！
(6)结果对吗？
(7)这句话是错的。
(8)假如明天是星期天，那么学校放假。
解答：
(1)“火星上有生命存在”是命题，但现在不能确定其真值；
(2)“12是质数”是命题，其真值为假；
(3)“香山比华山高”是命题，其真值为假；
(4)“x+y=2”不是命题，因为含有公认是变量的东西，从而不具有确定的真值；
(5)“这盆茉莉花真香！”是感叹句，因而不是命题；
(6)“结果对吗？”是疑问句，因而不是命题；
(7)“这句话是错的”是语义悖论，因而不是命题；
(8)“假如明天是星期天，那么学校放假”是命题，其真值为真。
点评：实际上，确定一个具体命题的真值不是数理逻辑研究的内容，但是不能说一个命题没有真值。
作业1.2令p表示今天很冷，q表示正在下雪，将下列命题符号化：
(1)如果正在下雪，那么今天很冷。
(2)今天很冷当且仅当正在下雪。
(3)正在下雪的必要条件是今天很冷。
用自然语言叙述下列公式：
?(p∧q)?p∨?q p→q?p∨q??p?p?q
解答：
(1)“如果…那么…”是典型的表蕴涵的连词，因此句子“如果正在下雪，那么今天很冷”符号化为q→p；
(2)“当且仅当”是典型的表等价的连词，因此句子“今天很冷当且仅当正在下雪”符号化为p?q；
(3)“正在下雪的必要条件是今天很冷”相当于“只有今天很冷，（才）正在下雪”，也即“如果正在下雪，那么意味着今天很冷”，因此应该符号化为q→p。
对于公式的自然语言叙述，我们有：
(1)公式?(p∧q)的自然语言叙述可以是：“并非今天很冷且正在下雪”；
(2)公式?p∨?q的自然语言叙述可以是：“并非今天很冷或者并非正在下雪”，或者“今天不很冷或者没有正在下雪”；
(3)公式p→q的自然语言叙述可以是：“如果今天很冷，那么正在下雪”；
(4)公式?p∨q的自然语言叙述可以是：“今天不很冷或者正在下雪”；
(5)公式??p的自然语言叙述可以是：“并非今天不很冷”；
(6)公式?p?q的自然语言叙述可以是：“今天不很冷当且仅当正在下雪”。
点评：
1.当然这种题目的答案不惟一，但是有些同学的自然叙述十分不符合汉语习惯。另外，从汉语语义来说，?p通常不应该理解为“今天不冷”，而应正确理解为“并非今天很冷”，或者“今天不很冷”。通常，“不很冷”与“不冷”的含义并不相同。第1个公式有许多人叙述为“今天不是很冷而且没有正在下雪”，这是错误的。
2.另外，对于上面将自然语言命题的符号化，不少同学将第3小题符号化为p→q，这是由于粗心所犯的错误。
作业1.3将下列命题符号化：
(1)他个子高且很胖。
(2)他个子高但不很胖。
(3)并非他个子高或很胖。
(4)他个子不高也不胖。
(5)他个子高或者他个子矮而很胖。
(6)他个子矮或他不很胖都是不对的。
(7)如果水是清的，那么或者张三能见到池底或者他是个近视眼。
(8)如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那么许多孩子受骗了。
解答：
(1)令p表示“他个子高”，q表示“（他）很胖”，则句子“他个子高且很胖”符号化为p∧q；
(2)令p表示“他个子高”，q表示“（他）很胖”，则句子“他个子高但不很胖”符号化为p∧?q；
(3)令p表示“他个子高”，q表示“（他）很胖”，则句子“并非他个子高或很胖”符号化为?(p∨q)，注意，按照我对自然语言的理解，并非通常是否定后面整个句子，而非只是否定“他个子高”；
(4)令p表示“他个子高”，q表示“（他）很胖”，则句子“他个子不高也不胖”符号化为?p∧?q；
(5)令p表示“他个子高”，q表示“他个子矮”，r表示“（他）很胖”，则句子“他个子高或者他个子矮而很胖”符号化为p∨(q∧r)，按照我对自然语言的理解：(i).“他个子矮”不等于“并非他个子高”，因为日常生活中还常说某个人不高也不矮呢！所以我建议用不同的符号来表示这两个原子命题；(ii).句子的结构是“…或者…而…”，按我的理解，在自然语言中“而”的优先级也比“或”高。
(6)令p表示“他个子矮”，q表示“（他）很胖”，则句子“他个子矮或他不很胖都是不对的”符号化为?(p∨?q)。
(7)令p表示“水是清的”，q表示“张三能见到池底”，r表示“他是个近视眼”，则句子“如果水是清的，那么或者张三能见到池底或者他是个近视眼”符号化为p→(q∨r)；
(8)令p表示“嫦娥是虚构的”，q表示“圣诞老人是虚构的”，r表示“许多孩子受骗了”，则句子“如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那么许多孩子受骗了”符号化为(p∧q)→r
作业1.4针对严格符合定义的公式，使用归纳法证明公式中左园括号的数目与公式中联结词的数目相同，同样右园括号的数目也与公式中联结词的数目相同。
证明对任意的公式A，按照A的结构实施归纳法：
(1)归纳基：若公式A是命题变量p，则其左园括号数目等于右园括号数目等于联结词数目等于0；
(2)归纳步：若公式A具有形式(?B)，则按照归纳假设，B的左园括号数目等于右园括号数目等于联结词数目，则公式A比B多一个左园括号，一个右园括号以及一个联结词，因此公式A的左园括号数目也等于右园括号数目也等于联结词数目。类似地，若公式A具有形式(B⊕C)，其中⊕是∧,∨,→,?之一，则按照归纳假设，公式B和C都满足其左园括号数目等于右园括号数目等于联结词数目，而公式A的左园括号数是B和C中左园括号数目之和加1，公式A的右园括号数也是B和C中右左园括号数目之和加1，公式A的联结词数也是B和C中联结词数目之和加1，因此公式A的左园括号数目也等于右园括号数目也等于联结词数目。
点评：许多数同学都没有做对，其关键错误在于在归纳步时，没有理解归纳假设到底是什么！另外，这一题对联结词个数进行归纳不是很妥，需要对公式的形式进行归纳。
作业1.5给定真值赋值函数t:Var→{0,1}，其中t(p)=t(q)=0,t(r)=t(s)=1，确定下列公式在真值赋值函数t下的真值：
(1).p∨(q∧r)(2).(p?r)∧(?q∨s)
(3).(?p∧?q∧r)?(p∧q∧?r)(4).(?r∧s)→(p∧?q)
解答：
(1).使用如下表格计算p∨(q∧r)在真值赋值函数t下的真值：
p q r q∧r p∨(q∧r)
00100
(2).使用如下表格计算A=(p?r)∧(?q∨s)在真值赋值函数t下的真值：
p q r s p?r?q(?q∨s)A
00110110
(3).使用如下表格计算A=(?p∧?q∧r)?(p∧q∧?r)在真值赋值函数t下的真值：
p q r s?p?q(?p∧?q)(?p∧?q∧r)(p∧q)?r(p∧q∧?r)A
001111110000
(4).使用如下表格计算A=(?r∧s)→(p∧?q)在真值赋值函数t下的真值：
p q r s?r(?r∧s)?q(p∧?q)A
001100101
作业1.6构造下列公式的真值表，并判断该公式的类型（永真式、非永真式的可满足式还是矛盾式），注意在列真值表时，行要按二进制编码顺序，前几列要按命题变量的字母顺序，并要给出需要计算的子公式：
(1).(p→?p)∧(p∧q)(2).(p→q)→(?q→?p)
(3).(p∧r)?(?p∧?q)(4).((p→q)∧(q→r))→(p→r)
解答：
(1).公式A=(p→?p)∧(p∧q)的真值表如下：
p q?p(p→?p)(p∧q)A
001100
011100
100000
110010
(2).公式A=(p→q)→(?q→?p)的真值表如下：
p q p→q?q?p(?q→?p)A
0011111
0110111
1001001
1110011
(3).公式A=(p∧r)?(?p∧?q)的真值表如下：
p q r p∧r?p?q?p∧?q)A
00001110
00101110
01001001
01101001
10000101
10110100
11000001
11110000
(4).公式A=((p→q)∧(q→r))→(p→r)的真值表如下：
p q r(p→q)(q→r)((p→q)∧(q→r))(p→r)A
00011111
00111111
01010011
01111111
10001001
10101011
11010001
11111111
根据上面的真值表，我们知道：
(1)公式(p→?p)∧(p∧q)是矛盾式；
(2)公式(p→q)→(?q→?p)是永真式；
(3)公式(p∧r)?(?p∧?q)是非永真式的可满足式；
(4)公式A=((p→q)∧(q→r))→(p→r)是永真式。
点评：在以上两题计算公式真值和构造公式真值表的题目中
1.少数同学仍未遵守讲稿所说的注意事项：
(1)前几列应该给出公式的所有命题变量，并应按命题变量的字母顺序排列，但有些同学
按p,r,q排列；
(2)真值表的列应该给出所有需要计算的子公式的真值，但有些同学不愿意列出?p或?q这样的
子公式的真值；
(3)行应该按照二进制编码顺序，两个变量时是00,01,10,11，三个变量是000,001,010,011,100,101,110,111。
2.有的同学没有判断公式的类型，有的同学乱写公式的类型，注意我们将公式的类型命名为三
类：矛盾式、永真式和非永真式的可满足式，永真式也可称为重言式。除这四个名字以外的名字都
是错误的。
第二章命题逻辑的等值演算
作业2.1使用等值演算方法证明下列等值式（注意写清楚所使用的基本等值式）：
(1)p→(q→p)??p→(p→?q)
(2)?(p?q)?(p∨q)∧?(p∧q)?(p∧?q)∨(?p∧q)
(3)(p→(q∨r))?(p∧?q)→r
(4)((p∧q)→r)∧(q→(s∨r))?(q∧(s→p))→r
解答
(1)p→(q→p)?p→(?q∨p)//蕴涵等值式
??p∨?q∨p//蕴涵等值式
?p∨?p∨?q//交换律
?p∨(p→?q)//蕴涵等值式
??p→(p→?q)//蕴涵等值式(2)?(p?q)??((p→q)∧(q→p))//等价等值式
??((?p∨q)∧(?q∨p))//蕴涵等值式
??(?p∨q)∨?(?q∨p)//德摩根律
?(p∧?q)∨(q∧?p)//德摩根律
?(p∨q)∧(p∨?p)∧(?q∨q)∧(?q∨?p)//分配律
?(p∨q)∧(?q∨?p)//排中律、同一律(3)(p→(q∨r))??p∨q∨r//蕴涵等值式
???(?p∨q)∨r//双重否定律
??(p∧?q)∨r//德摩根律
?(p∧?q)→r//蕴涵等值式(4)((p∧q)→r)∧(q→(s∨r))?(?(p∧q)∨r)∧(?q∨s∨r))//蕴涵等值式
?(?(p∧q)∧(?q∨s))∨r//分配律
?((?p∨?q)∧(?q∨s))∨r//德摩根律
?(?q∨(?p∧s))∨r//分配律
?(?q∨?(p∨?s))∨r//德摩根律
??(q∧(p∨?s))∨r//德摩根律
?(q∧(s→p))→r//蕴涵等值式
点评：部分同学没有写注释；许多同学在演算时步骤不够详细。
作业2.2对任意的公式A,B,C，如果A∨C?B∨C，是否有A?B？如果A∧C?B∧C是否有A?B？如果?A??B，是否有A?B？为什么？
解答：
(1).当C是一个永真式，即C的真值恒为1时，A∨C和B∨C的真值都恒为1，也即这时A∨C?B∨C，但显然这时A不一定与B等值；
(2).类似地，当C是一个矛盾式，即C的真值恒为0时，A∧C和B∧C的真值都恒为0，也即这时A∧C?B∧C，但显然这时A不一定与B等值；
(3).若?A??B，则按公式等值的定义有，对任意的真值赋值函数t，都有t(?A)=t(?B)，而根据否定联结词的定义，t(A)=1当且仅当t(?A)=0，这就说明，对任意的真值赋值函数t，也都有t(A)=t(B)，因此A?B。
点评：许多同学做得过于复杂，有些同学试图利用真值表进行求解，但不是表达得很清楚；而有些同学利用等值演算，得到A∨C?B∨C等值于(A?B)∨C，而A∧C?B∧C等值于(A?B)∨?C，这两个结果好像是对的，但过程比较复杂。
作业2.3求解下面有关联结词完备集的问题：
(1)将公式(p→(q∧r))∨p化成与之等值的且仅含?和∧的公式；
(2)将公式(p→(q∧?p))∧q∧r化成与之等值的且仅含?和∨的公式；
(3)将公式(p→(q∧?p))∧q∧r化成与之等值的且仅含?和→的公式；
(4)定义联结词“与非”↑和“或非”↓：对任意的公式A和B，
A↑B??(A∧B)A↓B??(A∨B)
在数字逻辑电路设计中经常使用与非门和或非门，不难证明{↑}是联结词的完备集，而且{↓}也是联结词的完备集。试将公式p→(?p→q)化成与之等值的且仅含{↑}的公式，同样把该公式化成与之等值的且仅含{↓}的公式。
解答：
(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)
(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))
通过上面的分析，我们看到↑和↓满足交换律，但不满足幂等律和结合律。
点评：大多数同学都做得过于复杂，没有将原公式先化简；有些同学没有做第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)
解：
(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。
作业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)
(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出差
点评：不少同学嫌烦，从而没有认真去扩展，也没有给出其他合适的方法来求解，可能是参考
别人的答案吧！有些同学使用真值表的方式进行求解，但列得不是很清晰。
第三章命题逻辑的自然推理
作业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)假言易位
(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。
解答：
(1)令Γ={q→p,q?s,s?t,t∧r}，验证Γ p∧q的证明序列为：
(1)Γ s?t//前提引入
(2)Γ t→s//(1)等价消除
(3)Γ q?s//前提引入
(4)Γ s→q//(3)等价消除
(5)Γ t→q//(2),(4)传递规则
(6)Γ t∧r//前提引入
(7)Γ t//(6)合取消除
(8)Γ q//(5),(7)蕴涵消除
(9)Γ q→p//前提引入
(10)Γ t→p//(5),(9)传递规则
(11)Γ p//(7),(10)蕴涵消除
(12)Γ p∧q//(8),(11)合取引入
(2)令Γ={(p∨q)→(r∧s),(s∨t)→u}，验证Γ p→u的证明序列如下：
(1)Γ,p p//前提引入
(2)Γ,p p∨q//(1)析取引入
(3)Γ,p (p∨q)→(r∧s)//前提引入
(4)Γ,p r∧s//(2),(3)蕴涵消除
(5)Γ,p s//(4)合取消除
(6)Γ,p s∨t//(5)析取引入
(7)Γ,p (s∨t)→u//前提引入
(8)Γ,p u//(6),(7)蕴涵消除
(9)Γ p→u//(8)蕴涵引入(3)令Γ={p→?q,?r∨q,r∧?s}，验证Γ ?p的证明序列如下：
(1)Γ,p p//前提引入
(2)Γ,p p→?q//前提引入
(3)Γ,p ?q//(1),(2)蕴涵消除
(4)Γ,p ?r∨q//前提引入
(5)Γ,p ?r//(3),(4)析取三段论
(6)Γ,p r∧?s//前提引入
(7)Γ,p r//(6)合取消除
(8)Γ ?p//(5),(7)归谬律
(4)令Γ={p→(q→r),r→?r,s→p,t→q}，验证Γ s→?t的证明如下：
(1)Γ,s,t s//前提引入
(2)Γ,s,t s→p//前提引入
(3)Γ,s,t p//(1),(2)蕴涵消除
(4)Γ,s,t p→(q→r)//前提引入
(5)Γ,s,t q→r//(3),(4)蕴涵消除
(6)Γ,s,t t//前提引入
(7)Γ,s,t t→q//前提引入
(8)Γ,s,t q//(6),(7)蕴涵消除
(9)Γ,s,t r//(5),(8)蕴涵消除
(10)Γ,s,t r→?r//前提引入
(11)Γ,s,t ?r//(9),(10)蕴涵消除
(12)Γ,s ?t//(9),(11)归谬律
(13)Γ s→?t//(12)蕴涵引入
作业3.5在自然推理系统中验证下述推理的有效性：
(1)只要张三曾到过受害者房间并且11点以前没有离开，则张三犯了谋杀罪。张三曾到过受害者房间。如果张三在11点以前离开，则看门人会看见他。看门人没有看见他。所以，张三犯了谋杀罪。
(2)在大城市球赛中，如果北京队第三，那么上海队第二意味者天津队第四。沈阳队不是第一或北京队第三。上海队第二。因此，如果沈阳队第一，则天津队第四。
(3)如果法官是公正严明的，则就应当宣判张大侠有罪，除非现有的证据尚不充分。如果法官是公正严明的，则不会不认定现有的证据是充分的，除非这些证据有假。证据都没有假。因此，如果法官是公正严明的，就应当宣判张大侠有最。
(1).通读句子，我们可发现有如下原子命题：
p:张三曾到过受害者房间q:张三11点以前离开
r:张三犯了谋杀罪s:看门人看见张三
而句子“只要张三曾到过受害者房间并且11点以前没有离开，则张三犯了谋杀罪”符号化为：
(p∧?q)→r
而句子“如果张三在11点以前离开，则看门人会看见他”符号化为q→s。因此我们要验证的推理是：
(p∧?q)→r,p,q→s,?s r
验证上述推理的证明序列如下：令Γ={(p∧q)→r,p,q→s,?s}，
(1)Γ ?s//前提引入
(2)Γ q→s//前提引入
(3)Γ ?q//(1),(2)假言易位
(4)Γ p//前提引入
(5)Γ p∧?q//(3),(4)合取引入
(6)Γ (p∧?q)→r//前提引入
(7)Γ r//(5),(6)蕴涵消除
(2).通读句子，我们可发现有如下原子命题：
p:北京队第三q:上海队第二
r:天津队第四s:沈阳队第一
而句子“如果北京队第三，那么上海队第二意味者天津队第四”符号化为：
p→(q→r)
句子“沈阳队不是第一或北京队第三”符号化为：
?s∨p
而推理结论“如果沈阳队第一，则天津队第四”符号化为：s→r，因此要验证的推理是：
p→(q→r),?s∨p,q s→r
验证上述推理的证明序列如下：令Γ={p→(q→r),?s∨p,q}，
(1)Γ,s s//前提引入
(2)Γ,s ?s∨p//前提引入
(3)Γ,s p//(1),(2)析取三段论
(4)Γ,s p→(q→r)//前提引入
(5)Γ,s q→r//(3),(4)蕴涵消除
(6)Γ,s q//前提引入
(7)Γ,s r//(5),(6)蕴涵消除
(8)Γ s→r//(7)蕴涵引入
(3).通读句子，我们可发现有如下原子命题：
p:法官是公正严明的q:法官应当宣判张大侠有罪
r:现有的证据是充分的s:证据有假
而句子“如果法官是公正严明的，则就应当宣判张大侠有罪，除非现有的证据尚不充分”的含义是“如果法官是公正严明的，则只有在现有的证据尚不充分时，法官才不会宣判张大侠有罪”，也即“如果法官是公正严明的，则法官不宣判张大侠有罪意味着现有的证据尚不充分”，从而应该符号化为：
p→(?q→?r)
类似的，句子“如果法官是公正严明的，则不会不认定现有的证据是充分的，除非这些证据有假”的含义是“如果法官是公正严明的，则只有当这些证据有假时，法官才不会认定现有的证据是充分的”，也即“如果法官是公正严明的，则它不认定现有的证据是充分的，意味着这些证据有假”，因此应该符号化为：
p→(?r→s)
句子“证明都没有假”符号化为?s，而“如果法官是公正严明的，就应当宣判张大侠有罪”则应符号化为：
p→q
从而我们要验证的推理是：
p→(?q→?r),p→(?r→s),?s p→q
验证上述推理的证明序列如下：令Γ={p→(?q→?r),p→(?r→s),?s}，
(1)Γ,p p→(?r→s)//前提引入
(2)Γ,p p//前提引入
(3)Γ,p ?r→s//(1),(2)蕴涵消除
(4)Γ,p ?s//前提引入
(5)Γ,p r//(3),(4)假言易位
(6)Γ,p p→(?q→?r)//前提引入
(7)Γ,p ?q→?r//(2),(6)蕴涵消除
(8)Γ,p q//(5),(7)假言易位
(9)Γ p→q//(8)蕴涵引入
作业3.6我们在自然推理系统中验证一些基本等值式：
1.p∨q q∨p
(1)p∨q,p p//前提引入
(2)p∨q,p q∨p//(1)析取引入
(3)p∨q,q q//前提引入
(4)p∨q,q q∨p//(3)析取引入
(5)p∨q p∨q//前提引入
(6)p∨q q∨p//(2),(4),(5)析取消除
2.(p∨q)∨r p∨(q∨r)
(1)(p∨q)∨r,p∨q,p p//前提引入
(2)(p∨q)∨r,p∨q,p p∨(q∨r)//(1)析取引入
(3)(p∨q)∨r,p∨q,q q//前提引入
(4)(p∨q)∨r,p∨q,q q∨r//(3)析取引入
(5)(p∨q)∨r,p∨q,q p∨(q∨r)//(4)析取引入
(6)(p∨q)∨r,p∨q p∨q//前提引入
(7)(p∨q)∨r,p∨q p∨(q∨r)//(2),(5),(6)析取消除
(8)(p∨q)∨r,r r//前提引入
(9)(p∨q)∨r,r q∨r//(8)析取引入
(10)(p∨q)∨r,r p∨(q∨r)//(9)析取引入
(11)(p∨q)∨r (p∨q)∨r//前提引入
(12)(p∨q)∨r p∨(q∨r)//(7),(10),(11)析取消除
3.p∧(q∨r) (p∧q)∨(p∧r)
(1)p∧(q∨r),q p∧(q∨r)//前提引入
(2)p∧(q∨r),q p//(1)合取消除
(3)p∧(q∨r),q q//前提引入
(4)p∧(q∨r),q p∧q//(2),(3)合取引入
(5)p∧(q∨r),q (p∧q)∨(p∧r)//(4)析取引入
(6)p∧(q∨r),r p∧(q∨r)//前提引入
(7)p∧(q∨r),r p//(6)合取消除
(8)p∧(q∨r),r r//前提引入
(9)p∧(q∨r),r p∧r//(7),(8)合取引入
(10)p∧(q∨r),r (p∧q)∨(p∧r)//(9)析取引入
(11)p∧(q∨r) p∧(q∨r)//前提引入
(12)p∧(q∨r) q∨r//(11)合取消除
(13)(p∨q)∨r (p∧q)∨(p∧r)//(5),(10),(12)析取消除4.p∨(p∧q) p
(1)p∨(p∧q),p∧q p∧q//前提引入
(2)p∨(p∧q),p∧q p//(1)合取消除
(3)p∨(p∧q),p p//前提引入
(4)p∨(p∧q) p∨(p∧q)//前提引入
(5)p∨(p∧q) p//(2),(3),(4)析取消除
5.?(p∧q) (?p∨?q)
(1)?(p∧q),?(?p∨?q),?p ?p//前提引入
(2)?(p∧q),?(?p∨?q),?p ?p∨?q//(1)析取引入
(3)?(p∧q),?(?p∨?q),?p ?(?p∨?q)//前提引入
(4)?(p∧q),?(?p∨?q) p//(2),(3)否定消除
(5)?(p∧q),?(?p∨?q),?q ?q//前提引入
(6)?(p∧q),?(?p∨?q),?q ?p∨?q//(5)析取引入
(7)?(p∧q),?(?p∨?q),?q ?(?p∨?q)//前提引入
(8)?(p∧q),?(?p∨?q) q//(6),(7)否定消除
(9)?(p∧q),?(?p∨?q) p∧q//(4),(8)合取引入
(10)?(p∧q),?(?p∨?q) ?(p∧q)//前提引入
(11)?(p∧q) ?p∨?q//(9),(10)否定消除