离散数学基础：数理逻辑导论

《数理逻辑》课程作业参考答案

周晓聪(isszxc@89d6bc01b52acfc789ebc917)

中山大学计算机科学系,广州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；

1

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

2

(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

3

作业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

4

根据上面的真值表，我们知道：

(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.有的同学没有判断公式的类型，有的同学乱写公式的类型，注意我们将公式的类型命名为三

类：矛盾式、永真式和非永真式的可满足式，永真式也可称为重言式。除这四个名字以外的名字都

是错误的。

5

第二章命题逻辑的等值演算

作业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//蕴涵等值式

6

点评：部分同学没有写注释；许多同学在演算时步骤不够详细。

作业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)化成与之等值的且仅含{↑}的公式，同样把该公式化成与之等值的且仅含{↓}的公式。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新外语学习离散数学基础：数理逻辑导论全文阅读和word下载服务。