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

第一章命题逻辑的基本概念 作业 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 qp 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表示 “ （他） 很胖” ， 则句子 “他个子不高也不胖” 符号化为pq； (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 : Var0,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下的真值： pqrq rp (q r) 00100 (2). 使用如下表格计算A = (p r) ( q s)在真值赋值函数t下的真值： pqrsp r q( q s)A 00110110 (3). 使用如下表格计算A = ( p q r) (p q r)在真值赋值函数t下的真值： pqrsp q( p q)( p q r)(p q) r(p q r)A 001111110000 (4). 使用如下表格计算A = ( r s) (p q)在真值赋值函数t下的真值： pqrs 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)的真值表如下： pq p(p p)(p q)A 001100 011100 100000 110010 (2). 公式A = (p q) ( q p)的真值表如下： pqp q q p( q p)A 0011111 0110111 1001001 1110011 (3). 公式A = (p r) ( p q)的真值表如下： pqrp r p q p q)A 00001110 00101110 01001001 01101001 10000101 10110100 11000001 11110000 (4). 公式A = (p q) (q r) (p r)的真值表如下： pqr(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 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)(A B) (A B) (A B) 从而： (p (q r) p (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)是永真式，从而我们只要使用和构造出永真式即可，例如我们 将pp用仅含或的公式表示。 为此， 我们先考虑使用这两个联结词表示否定、 析取和合取联 结词， 不难看到： A A AA 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的真值表： pqrF备注 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) 点评：许多同学仍然在某个完备集表示公式的时候，没