数理逻辑与集合论前两章作业答案.pdf

第一章命题逻辑的基本概念作业 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表示今天1)如果正在下雪，那2)今天很冷当且仅3)正在下雪的必要用自然语言叙述下列 p q)解答：1)“如果那么”q p；是否是命题.，那么学校放”是命题，其真值为命题，其真题，因为含”是感叹句问句，因而语义悖论，那么学校具体命题冷，q表示今天很冷。正在下雪。件是今天很式：p q典型的表蕴对命题确定其真值。在不能确定其真值假；认是变量的东西，而不是命题；命题；不是命题；”是命题，其真值值不是数理逻辑研下雪，将下列命题符p q p q的连词，因此句子“1不具有确定的真。内容，但是不能化：p p q果正在下雪，那么句，并：在！天假在但现；题假；是值为命有公从而值；！，因疑不是是因而天放假为真一个的真究的说一个命题没有真值很正在号么当条冷。公是涵如今天很冷”符号化为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通常不应该理解为“今天不冷”，冷”。通常，“不很冷”与“不冷”的含义并不相同有正在下雪”，这是错误的。2.另外，对于上面将自然语言命题的符号化心所犯的错误。作业 1.3 将下列命题符号化：1)他个子高且很胖。2)他个子高但不很胖。3)并非他个子高或很胖。4)他个子不高也不胖。5)他个子高或者他个子矮而很胖。6)他个子矮或他不很胖都是不对的。7)如果水是清的，那么或者张三能见到池8)如果嫦娥是虚构的，而如果圣诞老人也解答：1)令p表示“他个子高”，q表示“（他）很胖2)令p表示“他个子高”，q表示“（他）很胖3)令p表示“他个子高”，q表示“（他）很胖q)，注意，按照我对自然语言的理解，并非通常是4)令p表示“他个子高”，q表示“（他）很胖5)令p表示“他个子高”，q表示“他个子矮子矮而很胖”符号化为p q r)，按照我对自然高”，因为日常生活中还常说某个人不高也不矮题；ii).句子的结构是“或者而”，按我的6)令p表示“他个子矮”，q表示“（他）很胖化为 p q)。不很冷或者正在下雪”；天不很冷”；天不很冷当且仅当正在下雪学的自然叙述十分不符合汉应正确理解为“并非今天第1个公式有许多人叙述为不少同学将第3小题符号化或者他是个近视眼。虚构的，那么许多孩子受骗，则句子“他个子高且很胖，则句子“他个子高但不很”，则句子“并非他个子高否定后面整个句子，而非只，则句子“他个子不高也不，r表示“（他）很胖”，则句言的理解：i).“他个子矮！所以我建议用不同的符解，在自然语言中“而”的，则句子“他个子矮或他不2。习惯。另外，从汉语冷”，或者“今天不很今天不是很冷而且没为p q，这是由于粗。符号化为p q；”符号化为p q；很胖”符号化为 p 否定“他个子高”；”符号化为pq；“他个子高或者他个不等于“并非他个子来表示这两个原子命先级也比“或”高。胖都是不对的”符号天今今”语而很。“，底是了”胖或是”胖”子语”呢号理优”很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)3)p q r)p q r)解答：1).使用如下表格计算p q r)在真值赋值函数t下的真值：p0q0r1q r0p q r)02)p r)q s)4)r s)p q)2).使用如下表格计算A=p r)q s)在真值赋值函数t下的真值：p0q0r1s1p r0 q1 q s)1A03).使用如下表格计算A=p q r)p q r)在真值赋值函数t下的真值：p0q0r1s1p1 q1 p q)1 p q r)1p q)0 r0p q r)0A04).使用如下表格计算A=r s)p q)在真值赋值函数t下的真值：p0q0r1s1 r0 r s)03 q1p q)0A1作业 1.6 构造下列公式的真值表，并判断该公式的类型（永真式、非永真式的可满足式还是矛盾式），注意在列真值表时，行要按二进制编码顺序，前几列要按命题变量的字母顺序，并要给出需要计算的子公式：1)p p)p q)3)p r)p q)解答：1).公式A=p p)p q)的真值表如下：p0011q0101 p1100p p)1100p q)0001A00002)p q)q p)4)p q)q r)p r)2).公式A=p q)q p)的真值表如下：p0011q0101p q1101 q1010 p1100 q p)1101A11113).公式A=p r)p q)的真值表如下：p00001111q00110011r01010101p r00000101 p11110000 q11001100 p q)11000000A001110104).公式A=p q)q r)p r)的真值表如下：p00001111q00110011r01010101p q)11110011q r)110111014p q)q r)11010001p r)11110101A11111111根据上面的真值表，我们知道：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)真值表的列应该给出所有需要计算的子公式的真值；3)行应该按照二进制编码顺序，两个变量2.有的同学没有判断公式的类型，有的同：矛盾式、永真式和非永真式的可满足式，永错误的。公式的真值，但有些同学00,01,10,11，三个变量乱写公式的类型，注意我真式也可称为重言式。除5愿意列出p或q这样的000,001,010,011,100,101,110,111将公式的类型命名为三四个名字以外的名字都按不子时是是。学们类这是第二章命题逻辑的等值演算作业 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)r4)p q)r)q s r)q s p)r解答p q p)p q p)p q p p p q p p q)p p q)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)p q r)p q r p q)r p q)r p q)rp q)r)q s r)p q)r)q s r)p q)q s)rp q)q s)r q p s)r q p s)r q p s)r q s p)r6式/值）：1)2)蕴涵等值式蕴涵等值式交换律蕴涵等值式蕴涵等值式等价等值式蕴涵等值式德摩根律德摩根律分配律3)4)排中律、同一律蕴涵等值式双重否定律德摩根律蕴涵等值式蕴涵等值式分配律德摩根律分配律德摩根律德摩根律蕴涵等值式点评：部分同学没有写注释；许多同学在演算时步骤不够详细。作业 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 C。点评：许多同学做得过于复杂，有些同学试图利用真值表进行求解，但不是表达得很清楚；而有些同学利用等值演算，得到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)从而：p q r)p p q r)p p q r)p)/A B)A B)/A B)A B)A B)A B)A B)当然，我们也可先将原来的公式在某种程度上进行化简，然后再利用上述等值式：p q r)p p q r)p p p)q r)1 q r)1 p p)p p)7/蕴涵等值式/结合律/排中律/零律/排中律/A B)A B)2)我们先将公式 p q p)q r作适当地化简，然后利用下面的等值式：A B)A B)将该公式化成与之等值的且仅含和的公式：p q p)q r p q p)q r p q r p q r)/蕴涵等值式/吸收律/A B)A B)A B)A B)3)上面已经将公式 p q p)q r适当地化简了，在化简的基础上，并利用下面等值式：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)是永真式，从而我们只要使用和构造出永真式即可，例如我们将pp用仅含或的公式表示。为此，我们先考虑使用这两个联结词表示否定、析取和合取联结词，不难看到：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)通过上面的分析，我们看到和满足交换律，但不满足幂等律和结合律。8A A A/上一小题/蕴涵等值式/蕴涵等值式A B)A B)点评：大多数同学都做得过于复杂，没有将原公式先化简；有些同学没有做第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)是永真式，与它等值的析取范式和合取范式都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/德摩根律/分配律/排中律、同一律取公式p p。/蕴涵等值式/吸收律/蕴涵等值式/德摩根律/分配律主析取范式和主合取范式（请值表法请列出构造过程中的子可的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)m m3因此与公式 p q)p q)等值的主析取范式是m 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 M5p r p q r)p q r)M4 M6p q p q r)p q r)M2 M3p 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从而与之等值的主析取范式是m m7。3)p q r)s)p q r)s)p q r)s)p q r)s M14上式已经是一个极大项，也就是说已经是一个主合取范式，从而与上述公式等值的主析取范式是：m m1 m2 m3 m4 m5 m6 m7 m8 m9 m1 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的真值表：p00001111从而可写出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.7 A,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)11q00110011r01010101F01011010A,B的扳键向上，C的扳键向下B,C的扳键向上，A的扳键向下A的扳键向上，B,C的扳键向下C的扳键向上，A,B的扳键向下备注b)B和C不能都去，符号化为：q r)q rc)若C去，则D不能去，符号化为：r s r s也即选派方案必须满足的条件是：F p r s)p r s)q r)r s)上述公式是合取范式，我们使用编码方式将上式扩展为主合取范式。1)公式p r s的编码为100，它扩展出的极大项编码应该是1000和1100，即M8和M12；2)公式prs的编码为111，它扩展出的极大项编码应该是1011和1111，即M11和M15；3)公式qr的编码为 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 m m1 m2 m4 m5 m9 m1 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