《数理逻辑课本答案》由会员分享，可在线阅读，更多相关《数理逻辑课本答案（45页珍藏版）》请在金锄头文库上搜索。
1、第一章命题逻辑的基本概念作业 1.1 判断下列语句是否是命题， 并对命题确定其真值：(1) 火星上有生命存在.(2) 12是质数。(3) 香山比华山高。(4) x + y = 2。(5) 这盆茉莉花真香！(6) 结果对吗？(7) 这句话是错的。(8) 假如明天是星期天， 那么学校放假。解答：(1) “火星上有生命存在”是命题， 但现在不能确定其真值；(2) “12是质数”是命题， 其真值为假；(3) “香山比华山高”是命题， 其真值为假；(4) “x + y = 2”不是命题， 因为含有公认是变量的东西， 从而不具有确定的真值；(5) “这盆茉莉花真香！ ”是感叹句， 因而不是命题；(6) “
2、结果对吗？ ”是疑问句， 因而不是命题；(7) “这句话是错的”是语义悖论， 因而不是命题；(8) “假如明天是星期天， 那么学校放假”是命题， 其真值为真。点评：实际上，确定一个具体命题的真值不是数理逻辑研究的内容，但是不能说一个命题没有真值。作业 1.2 令p表示今天很冷， q表示正在下雪， 将下列命题符号化：(1) 如果正在下雪， 那么今天很冷。(2) 今天很冷当且仅当正在下雪。(3) 正在下雪的必要条件是今天很冷。用自然语言叙述下列公式：(p q) p qp q p q p p q解答：(1) “如果那么”是典型的表蕴涵的连词，因此句子“如果正在下雪，那么今天很冷”符号化为q p；1(
3、2) “当且仅当”是典型的表等价的连词，因此句子“今天很冷当且仅当正在下雪”符号化为p q；(3) “正在下雪的必要条件是今天很冷”相当于“只有今天很冷，（才）正在下雪” ，也即“如果正在下雪， 那么意味着今天很冷” ， 因此应该符号化为q p。对于公式的自然语言叙述， 我们有：(1) 公式(p q)的自然语言叙述可以是：“并非今天很冷且正在下雪”；(2) 公式 p q的自然语言叙述可以是：“并非今天很冷或者并非正在下雪” ， 或者 “今天不很冷或者没有正在下雪”；(3) 公式p q的自然语言叙述可以是：“如果今天很冷， 那么正在下雪”；(4) 公式 p q的自然语言叙述可以是：“今天不很冷或
4、者正在下雪”；(5) 公式 p的自然语言叙述可以是：“并非今天不很冷”；(6) 公式 p q的自然语言叙述可以是：“今天不很冷当且仅当正在下雪” 。点评：1. 当然这种题目的答案不惟一，但是有些同学的自然叙述十分不符合汉语习惯。另外，从汉语语义来说，p通常不应该理解为“今天不冷” ，而应正确理解为“并非今天很冷” ，或者“今天不很冷” 。 通常，“不很冷” 与 “不冷” 的含义并不相同。 第1个公式有许多人叙述为 “今天不是很冷而且没有正在下雪” ， 这是错误的。2. 另外，对于上面将自然语言命题的符号化，不少同学将第3小题符号化为p q，这是由于粗心所犯的错误。作业 1.3 将下列命题符号化
5、：(1) 他个子高且很胖。(2) 他个子高但不很胖。(3) 并非他个子高或很胖。(4) 他个子不高也不胖。(5) 他个子高或者他个子矮而很胖。(6) 他个子矮或他不很胖都是不对的。(7) 如果水是清的， 那么或者张三能见到池底或者他是个近视眼。(8) 如果嫦娥是虚构的， 而如果圣诞老人也是虚构的， 那么许多孩子受骗了。解答：(1) 令p表示“他个子高” ， q表示“ （他）很胖” ， 则句子“他个子高且很胖”符号化为p q；(2) 令p表示“他个子高” ， q表示“ （他）很胖” ， 则句子“他个子高但不很胖”符号化为p q；(3) 令p表示“他个子高” ，q表示“ （他）很胖” ，则句子“并
6、非他个子高或很胖”符号化为(p q)， 注意， 按照我对自然语言的理解， 并非通常是否定后面整个句子， 而非只是否定“他个子高”；(4) 令p表示 “他个子高” ， q表示 “ （他） 很胖” ， 则句子 “他个子不高也不胖” 符号化为pq；(5) 令p表示“他个子高” ， q表示“他个子矮” ， r表示“ （他）很胖” ， 则句子“他个子高或者他个子矮而很胖”符号化为p (q r)， 按照我对自然语言的理解：(i).“他个子矮”不等于“并非他个子高” ，因为日常生活中还常说某个人不高也不矮呢！所以我建议用不同的符号来表示这两个原子命题； (ii). 句子的结构是“或者而” ， 按我的理解，
7、在自然语言中“而”的优先级也比“或”高。(6) 令p表示 “他个子矮” ， q表示 “ （他） 很胖” ， 则句子 “他个子矮或他不很胖都是不对的” 符号化为(p q)。2(7) 令p表示“水是清的” ，q表示“张三能见到池底” ，r表示“他是个近视眼” ，则句子“如果水是清的， 那么或者张三能见到池底或者他是个近视眼”符号化为p (q r)；(8) 令p表示“嫦娥是虚构的” ，q表示“圣诞老人是虚构的” ，r表示“许多孩子受骗了” ，则句子“如果嫦娥是虚构的， 而如果圣诞老人也是虚构的， 那么许多孩子受骗了”符号化为(p q) r作业 1.4 针对严格符合定义的公式， 使用归纳法证明公式中左
8、园括号的数目与公式中联结词的数目相同， 同样右园括号的数目也与公式中联结词的数目相同。证明对任意的公式A， 按照A的结构实施归纳法：(1) 归纳基：若公式A是命题变量p，则其左园括号数目等于右园括号数目等于联结词数目等于0；(2) 归纳步：若公式A具有形式(B)，则按照归纳假设，B的左园括号数目等于右园括号数目等于联结词数目，则公式A比B多一个左园括号，一个右园括号以及一个联结词，因此公式A的左园括号数目也等于右园括号数目也等于联结词数目。类似地，若公式A具有形式(B C)，其中是,之一，则按照归纳假设，公式B和C都满足其左园括号数目等于右园括号数目等于联结词数目，而公式A的左园括号数是B和C
9、中左园括号数目之和加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
10、 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)A00110110(3). 使用如下表格计算A = ( p q r) (p q r)在真值赋值函数t下的真值：pqrsp q( p q)( p q r)(p q) r(p q r)A001111110000(4). 使用如下表格计算A = ( r s) (p q)在真值赋值函数t下的真值：pqrs r( r s) q(p q)A0011
11、001013作业 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)A001100011100100000110010(2). 公式A = (p q) ( q p)的真值表如下：pqp q q p( q p)A00111110
12、11011110010011110011(3). 公式A = (p r) ( p q)的真值表如下：pqrp r p q p q)A0000111000101110010010010110100110000101101101001100000111110000(4). 公式A = (p q) (q r) (p r)的真值表如下：pqr(p q)(q r)(p q) (q r)(p r)A00011111001111110101001101111111100010011010101111010001111111114根据上面的真值表， 我们知道：(1) 公式(p p) (p q)是矛盾式；(2)
13、 公式(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,1
14、11。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/ 德摩根
