第一章命题逻辑的基本概念
作业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?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)
(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出差
点评：不少同学嫌烦，从而没有认真去扩展，也没有给出其他合适的方法来求解，可能是参考
别人的答案吧！有些同学使用真值表的方式进行求解，但列得不是很清晰。
离散数学形成性考核作业（四） 数理逻辑部分 本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。 第6章命题逻辑 1．判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题． （1）8能被4整除． （2）今天温度高吗？ （3）今天天气真好呀！ （4）6是整数当且仅当四边形有4条边． （5）地球是行星． （6）小王是学生，但小李是工人． （7）除非下雨，否则他不会去． （8）如果他不来，那么会议就不能准时开始． 解：此题即是教材P.184习题6（A）1 （1）、（4）、（5）、（6）、（7）、（8）是命题，（2）、（3）不是命题。 其中（1）、（5）是简单命题，（4）、（6）、（7）、（8）是复合命题。 2．翻译成命题公式 （1）他不会做此事． （2）他去旅游，仅当他有时间． （3）小王或小李都会解这个题． （4）如果你来，他就不回去． （5）没有人去看展览． （6）他们都是学生． （7）他没有去看电影，而是去观看了体育比赛． （8）如果下雨，那么他就会带伞． 解：此题即是教材P.184习题6（A）2
会带伞。 ：如果下雨，那么他就：他会带伞。 ：天下雨。）（。是去观看了体育比赛。：他没有去看电影，而。 ：他去观看了体育比赛：他去看电影。）（：他们都是学生。 ）（：没有人去看展览。 ：有人去看展览。）（去。 ：如果你来，他就不回：他回去。：你来。）（道题。：小王或小李都会解这：小李会解这道题。 ：小王会解这道题。）（时间。 ：他去旅游，仅当他有：他有时间。 ：他去游泳。）（：他不会做此事。：他会做此事。）（Q P Q P Q P Q P P P P Q P Q P Q P Q P Q P Q P P P →∧???→∧→?87654321 3．设P ，Q 的真值为1；R ，S 的真值为0，求命题公式(P ∨Q )∧R ∨S ∧Q 的真值． 解：此题即是教材P.184习题6（A ）4（2） (P ∨Q )真值为1，(P ∨Q )∧R 真值为0，S ∧Q 真值为0， 从而(P ∨Q )∧R ∨S ∧Q 真值为0。 4．试证明如下逻辑公式 （1） ┐（A ∧┐B ）∧（┐B ∨C ）∧┐C ? ┐（A ∨C ） （2） (P →Q )∧(Q →R )∧┐R ??P （此题即是教材P.185习题6（A ）5（1）、（4）） ) 7() () 8()6)(5()7()4)(2()6()4)(3()5()4()3()1() 2()() 1()(), (),(由由由由由证明：结论：前提：T B A T B A T A T B P C P C B T B A P B A B A C C B B A ∨??∧????∨?∨??∧?∨??∨??∧? ) 4)(3() 5()4()2)(1()3() 2() 1(), (),(由由证明：结论：前提：T P P R T R P P R Q P Q P P R R Q Q P ??→→→??→→
离散数学期末测试卷I及答案 第一部分、考试形式和时间 答题时限：120 分钟考试形式：闭卷笔试 第二部分、考试题型和得分构成 一、选择题：对每一道小题,从其4个备选答案中选择最适合的一项,每小题2分,共10 道小题,20分。 二、填空题：每空1分,共5道小题,10个空白处待填,10分。 三、判断题：每一道小题均以陈述语句描述,对的打√,错的打х。每小题1分,共10 道小题,10分。 四、综合题：每小题10分,共6道小题,60分。 第三部分、考试复习范围 一、选择题 1．含n个元素的集合A的幂集的元素个数为多少？ 答案：2n个。 2．数理逻辑的创始人是谁？
答案：莱布里茨。 3．设(R,+,?)是环,它有哪些特性？ 答案：1.(R,+)是阿贝尔群。2.(R,?)是半群。3.?对+可分配。 4．排中律满足哪些性质？ 答案：A ∧ 不成立。（不应同时否认一个命题（A ）及其否定（非A ）） x （F （x ）∨F （x ））对任何个体x 而言,x 有性质F 或没有性质F 。 5．什么是真命题？命题“如果雪是黑的,则1+1=0”是真命题吗？ 答案：真值为真的命题为真命题。命题“如果雪是黑的,则1+1=0”是真命题！ 解析：p:雪是黑的；q:1+1=0;如果雪是黑的,则1+1=0:p →q 。由于p 为假,所以无论的真值如何,“p →q ”的真值都为真。 6. 下列哪个等价公式有错？ A ．P Q Q P →?→； B ．P Q P Q →??∨； C ．P Q Q P →??∨； 答案：A 7. 设G 为4阶有向图,度数列为（3,4,2,3）,若它的入度列为（1,2,2,1）, 则出度列为哪项？ A ．（1,2,1,2）； B ．（2,2,0,2）； C ．（2,1,1,2）． 答案：B 解析：有向图中：度数=出度数+入度数。 8. 设{}{},3,4,S a φ=,则表示空元素属于S 怎样写？ 答案:?∈S 9. 什么是前束范式？下面哪个是前束范式？ A
第四章简单命题及其推理 一、下列命题是哪种直言命题？请指出命题的主项、谓项、联项、量项及主谓项的周延情况。 1．共产党员是无产阶级先进分子。答：这是个全称肯定命题（A），全称肯定量项省略；“共产党员”是主项；“是”为联项；“无产阶级先进分子”是谓项。主项周延，谓项不周延。 2．任何困难都不是不可克服的。答：这是个全称否定命题（E）。全称量项“任何”；主项“困难”；联项“不是”；谓项为负概念“不可克服的”。其主项、谓项都周延。 3．有些图书是线装书。答：这是特称肯定命题（I）。量项“有些”；主项“图书”；联项“是”；谓项“线装书”。其主项、谓项均不周延。 4．《女神》是郭沫若的诗集。答：这是个单称肯定命题。《女神》是主项；“是”是联项；“郭沫若的诗集”是谓项。其主项周延，谓项不周延。 5．有些学生不刻苦。答：这个命题一般理解为O命题：有些学生不是刻苦的。“学生”是主项；“刻苦的”是谓项；“不是”是联项；“有些”是量项。其主项不周延，谓项周延。 二、下列对当关系推理是否有效？为什么？ 1．由“有的植物不开花”真，推知“所有植物都开花”假。 答：正确。因为O与A是矛盾关系，由O真可推知A假。 2．由“凡环境污染都对人身体有害”真，推知“有的环境污染不对人身体有害”假。 答：正确。因为A与O是矛盾关系，由A真可推知O假。 3．由“有人生而知之”假，推知“有人不是生而知之”真。 答：正确。I与O是下反对关系，由I假可推知O真。 4．由“有的大学生是有理想的”真，推知“所有大学生都是有理想的”假。 答：不正确。I与A是从属（差等）关系，由I真推不出A假。 5．由“所有的古代散文都不押韵”假，推知“有的古代散文押韵”真。 答：正确。E与I是矛盾关系，由E假可推知I真。 6．由“所有的新诗都不押韵”假，推知“所有新诗都押韵”真。 答：不正确。E与A是反对关系，由E假推不出A真。 三、根据命题的对当关系，由已知下列命题的真假，断定同素材的其它三种命题的真 1．已知“某单位职工都买了电冰箱”为假。 答：这是个A命题。当A假时，同素材的E命题“某单位职工都没买电冰箱”真假不定；I命题“某单位职工有的买了电冰箱”真假不定；O命题“某单位有的职工没买电冰箱”为真。 2．已知“某班同学都不是会打桥牌的”为真。 答：这是个E命题。当E真时，A命题“某班同学都是会打桥牌的”为假；I命题“某班同学有的是会打桥牌的”为假；O命题“某班同学有的不是会打桥牌的”为真。 3．已知“有的科学家是自学成才的”为真。 答：这是个I命题。当I真时，A命题“所有的科学家是自学成才的”可真可假；E命题“所有的科学家不是自学成才的”为假；O命题“有的科学家不是自学成才的”可真可假。 4．已知“有的教授不是懂外语的”为假。 答：这是个O命题。当O假时，A命题“所有的教授都是懂外语的”为真；E命题“所有的教授都不是懂外语的”为假；I命题“有的教授是懂外语的”为真。 四、根据命题的对当关系，选择相应的命题来确定下列命题的虚假。 1．所有青年都是积极向上的。答：有的青年不是积极向上的。 2．有的理论是检验真理的标准。答：任何理论都不是检验真理的标准。
“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：((p q)((p q) (p q))) r （1）B：(p(q p)) (r q) （2）C：(p r) (q r) （3）E：p(p q r) （4）F：(q r) r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p q) q p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： ((p q) →s) p q) →(r s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。 解：p→((q∧r) ∧(p∨(q∧r)))p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。 解：((p→q)) (q→p) (p→q) (p→q) (p→q) p q M2.
第二篇集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作
暨 南 大 学 考 试 试 卷 一、填空题（共10小题，每小题2分，共20分） 1. 设命题 p ：罗素悖论的真值为假，q ：暨南大学的校训是信敏廉毅，r ：离散数学是计算机科学不可分割的一门基础课程，则复合命题: ()()()()() p q r q p r p ?∧?∨∧???→∨的真值 为 ; 2. 下列各式中为永真式的有： (1) Q Q P P →→∧))(( (2) Q Q P →→)( (3) )(Q P P ∨→ (3) Q Q P P →∨∧?))(( (5) )(Q P Q ∧→
3. A 是个10元集合，B 是个2元集合，则集合A B 中元素的个数为 4. 设M(x)：x 是人，C(x)：x 很聪明，则命题：“尽管有人很聪明，但未必一切人都聪明。”可符号化为： 5. 设R(x)：x 是实数；L(x, y)：x 小于y ，则谓词公式： (()(()(,)))x R x y R y L x y ?→?∧用自然语言表述就是： 6. 设个体域为A={a, b, c}，消去公式()()xP x xQ x ?→?中的量词得到的与之等值的谓词公式为： 7. P(A)表示集合A 的幂集，则((()))P P P ? = 8. ())(B A B B A ?-??= 9. 设D 为同一平面上直线的集合，并且 // 表示两直线的平行关系，⊥表示两直线间的垂直关系，则 20// ＝ ，21⊥＝ 10.设 {}c ,b ,a A =，{} ,,,A R a b b a I =<><>?是A 上的等价关系, 设自然映射,R /A A :g →,那么()=a g 二、简答题（共4小题，每小题6分，共24分） 1.(1)求公式()()?∨?→??P Q P Q 的主析取式（要有过程）；（4分） (2)根据主析取式直接写出该公式的主合取式；（2分）
一阶逻辑等值式与置换规则 1．设个体域D={a,b,c}，消去下列各式的量词： (1) x y(F(x)∧G(y)) (2) x y(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y)) 2．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。 (1) x(F(x)→G(x)) (2) x(F(x)∧G(x)) 3．给定解释I如下： (a) 个体域D={3,4}。 (b) (x)为(3)=4，(4)=3。 (c) (x,y)为(3,3)=(4,4)=0，(3,4)=(4,3)=1。 试求下列公式在I下的真值： (1) x yF(x,y) (2) x yF(x,y) (3) x y(F(x,y)→F(f(x),f(y))) 4．构造下面推理的证明： (1) 前提：x(F(x)→(G(a)∧R(x)))，xF(x)
结论：x(F(x)∧R(x)) (2) 前提：x(F(x)∨G(x))，┐xG(x) 结论：xF(x) (3) 前提：x(F(x)∨G(x))，x(┐G(x)∨┐R(x))，xR(x) 结论：xF(x) 5．证明下面推理： (1) 每个有理数都是实数，有的有理数是整数，因此有的实数是整数。 (2) 有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不 是无理数。 (3) 不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不 是无理数。
答案 1. (1) x y(F(x)∧G(y)) xF(x)∧yG(y) (F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c)) (2) x y(F(x)∨G(y)) xF(x)∨yG(y) (F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)) (3) xF(x)→yG(y) (F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c)) (4) x(F(x,y)→yG(y)) xF(x,y)→yG(y) (F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c)) 2.(1) I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真，所以 x(F(x)→G(x)) (F(1)→G(1)∧(F(2)→G(2))为真。 I2: F(x)同I1,G(x):x≤0 则F(1),F(2)均为真，而G(1),G(2)均为假， x(F(x)→G(x))为假。 (2)留给读者自己做。 3. (1) x yF(x,y)
玛 氏 食 品 ( 中国 ) 有 限 公 司 姓名：武英杰 性别：男 1-25 题均为选择题，只有一个正确答案。答案写在( ) 内 1-6 题根据下列数字规律，选择( )内应填数字： ( B ) 1、 2，9，16，23，30，（ ） A.35 B.37 C.39 D.41 ( C ) 2、 5，11，20，32，（ ） A ．43 B ．45 C ．47 D ．49 ( C )3、 1，2，3，5，（ ），13 A 9 B 11 C 8 D7 ( A )4、 5，7，（ ），19，31，50 A 12 B 13 C 10 D11 ( C )5、 8，4，2，2，（ ） A 、2 B 、3 C 、4 D 、5 ( C)6、 14，20，29，41，( ) A.45 B.49 C.56 D.72 ( A ) 7、. 15.025.053÷?的值是： A ．1 B ．1.5 C ．1.6 D ．2.0 ( C ) 8、 1994年第二季度全国共卖出汽车297600辆，与上年同期相比增长了 24%。上年同期卖出多少辆汽车?
A．714224 B．226176 C．240000 D．369024 ( D ) 9、甲、乙两地相距42公里，A、B两人分别同时从甲乙两地步行出发， A的步行速度为3公里/小时，B的步行速度为4公里/小时，问A、B步行几小时后相遇？ A. 3 B. 4 C. 5 D. 6 ( A)10、一根绳子长40米，将它对折剪断；再对剪断；第三次对折剪断，此时每根绳子长多少米？ A、5 B、10 C、15 D、20 ( B ) 11、如果一米远栽一棵树，则285米远可栽多少棵树？ A、285 B、286 C、287 D、284 (B ) 12、在一本300页的书中，数字“1”在书中出现了多少次？ A、140 B、160 C、180 D、120 ( D ) 13、自然数A、B、 C、 D的和为90，已知A加上2，B减去2，C乘以 2，D除以2之后所得结果相同，则B等于（） A、26 B、24 C、28 D、22 ( B ) 14、某人工作一年的报酬是18000元和一台全自动洗衣机,他干了7个月, 得到9500和一台全自动洗衣机,问这台洗衣机值多少元? A.8500元 B.2400元 C.2000元 D.1700元 ( B ) 15、橱窗：商品；相当于 A 电影：明星 B 书架：书籍 C 宇宙：星球 D 餐馆：厨师
浅谈数理逻辑在计算机科学中的应用 文章整理编辑---论文文库工作室（QQ1548927986） 摘要：数理逻辑是离散数学课程中研究推理的逻辑学科，它为确定一个给出的论证是否有效提供各种法则和技巧，在计算机科学里用来检验程序的正确性，也可以验证定理和推论，同时在计算机模型、计算机程序设计语言、计算机硬件系统等方面有着重要作用。研究数理逻辑在计算机科学领域中的应用，必须从研究数理逻辑的符号化开始讨论、加以分析、验证结论。 关键词：数理逻辑；命题逻辑；一阶逻辑；推理理论 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。其内容大致包含数理逻辑、集合论、代数结构、组合数学、图论和初等数论6部分，这6部分从不同的角度出发，研究各种离散量之间数与形的关系。本文主要研究数理逻辑部分在计算机科学领域中的应用。 1.为计算机的可计算性研究提供依据 数理逻辑分为命题逻辑和一阶逻辑两部分，命题逻辑是一阶逻辑的特例。在研究某些推理问题时，一阶逻辑比命题逻辑更准确。数理逻辑中的可计算谓词和计算模型中的可计算函数是等价的,互相可以转化，计算可以用函数演算来表达，也可以用逻辑系统来表达。 某些自然语言的论证看上去很简单，直接就可以得出结论，但是通过数理逻辑中的两种符号化表达的结果却截然不同，让人们很难理解，这就为计算机的可计算性研究埋下伏笔。下面举一个简单例子加以说明。 例1 凡是偶数都能被2整除。6是偶数，所以6能被2整除。 可见，一个复杂的命题或者公式可以利用符号的形式来说明含义，来判断正确性，这使得计算机科学中的通过复杂文字验证的推理过程变得简单、明了了。 2.为计算机硬件系统的设计提供依据 数理逻辑部分在计算机硬件设计中的应用尤为突出，数字逻辑作为计算机科学的一个重要理论，在很大程度上起源于数理逻辑中的布尔运算。计算机的各种运算是通过数字逻辑技术实现的，而代数和布尔代数是数字逻辑的理论基础，布尔代数在形式演算方面虽然使用了代数的方法，但其内容的实质仍然是逻辑。范式正是基于布尔运算和真值表给出的一个典型公式。 下面以计算机科学中比较典型的开关电路的设计为实例说明数理逻辑中布尔代数和范式的应用。整个开关电路从功能上可以看做是一个开关，把电路接通的状态记为1（即结果为真），把电路断开的状态记为0（即结果为假），开关电路中的开关也要么处于接通状态，要么处于断开状态，这两种状态也可以用二值布尔代数来描述，对应的函数为布尔函数，也叫线路的布尔表达式。接通条件相同的线路称为等效线路，找等效线路的目的是化简线路，使线路中包含的节点尽可能地少。利用布尔代数可设计一些具有指定的节点线路，数学上既是按给定的真值表构造相应的布尔表达式，理论上涉及到的是范式理论，但形式上并不难构造。 例2 关于选派参赛选手，赵，钱，孙三人的意见分别是：赵：如果不选派甲，那么不选派乙。钱：如果不选派乙，那么选派甲；孙：要么选甲，要么选乙。以下诸项中，同时满足赵，钱，孙三人意见的方案是什么？ 解答：把赵，钱，孙三个人的意见看做三条不同的线路，对三条线路化简得到接通状态
离散数学集合论部分测试题
离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
自主招生数学专题一：不等式 不等式是初等代数研究的问题之一，常见的考点包括未必局限于均值不等式（AM-GM不等式）、Cauchy不等式、排序不等式、Jensen不等式、三角不等式…某些求导才能求得函数最值的题也可以用卡尔松不等式、赫尔德不等式.还有一些常用的技巧还包括构造局部不等式、裂项、换元、线性规划、调整法等等.在不等式的凑配过程中我们还会用到因式分解、待定系数法、主元法等方法，还需要时刻注意不等式的取等条件. 近年来，有些同学跟我反映夏令营、自主招生的不等式题不会做，为了部分缓解(看来受生物实验毒害不浅)大家对不等式的恐惧,提升大家的能力,我整理了这个专题.在选题的过程中参考了《自招宝典》《自主招生直通车》《数学奥林匹克小丛书》以及一些竞赛或学科营中的题目，和之前在“高思教育”“北京数学学校”的课堂笔记，在此对他们表示感谢. 面对一道不等式,为什么有人能想到换元?为什么有人会这么凑系数?为什么会想到如此放缩?巧夺天工的证明往往蕴含了自然而优美的逻辑.希望通过对以下例题的探讨等够带大家初步领略不等式的妙处，提升大家对不等式的感觉. 【知识梳理】 1证明均值不等式 2用不包括向量法在内的三种方法证明Cauchy不等式 3证明排序不等式
【重要例题】 1(2015北大体验营)1=++c b a 求) 1)(1)(1(c b a abc ---的最大值 21=++c b a 求证:1)9111≥++c b a 2)3 1 222≥++c b a 3)127≤abc 4)3≤++c b a 5)3311 1 ≥+ + c b a 6)63115≤+∑a 7)(2011江西预赛)最大值求32c ab 3(2016清华自主招生)12 ==∑∑x x 求xyz 最值(原题为不定项选择题) 4设0,,>c b a ,求证2≥+++c b c b a a c 5(2008南开)5262 +=+++a bc ac ab ,0,,>c b a 求c b a 23++的最小值 6(2009清华自招)设0,,>z y x ,a,b,c 是x,y,z 的一个排列，求证3 ≥++z c y b x a 7求2 211x y y x -+-的最大值 8(2010浙大),,11 +=∈=∑R x x i n i i 求证41 3 >-∑ i i x x
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
数理逻辑的心得 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧 1数理逻辑的发展前期 ·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论 ·初创时期——逻辑代数时期（17世纪末） ·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。 ·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。 ·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想： ·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。 ·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。 ·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。 数理逻辑的奠基时期 ·弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。 ·皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。 ·罗素(Bertrand Russell, 1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。 ·逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。 ·各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。 ·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。 ·布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。 ·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将
离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
數理邏輯與集合論作業二 1. 解：該題應該理解為此列表中每一句都是形如“i: 在這個列表中，恰有i條語句為假”的形式。 a)思路：考慮這100句裡可能有幾句為真。是否可能沒有一句為真？是否可能 祗有一句為真，是哪一句？是否可能多餘等於兩句為真？ b)思路：“至少i+1句為假”蘊含“至少i句為假”，若第i句為真，則1…… i-1句都為真，所以第 100, 99, 98, ……句都為假，一直到第50句為真 c) 思路同上，但是…… 2. 解答：如果我說右邊的路通往遺跡你將回答“是”，對嗎？ 3.
解答： ))))a q p b p q c q p d q p →∧→?→? 4. 也就是上述描述是否自相矛盾？ 5. 解答： 条件符号化 ::::(1)(2)(C G)(3)(G W)G W (4)G W G W S C G W S C G W S C C G W C C S C S →?∧=?∨???∧?=∨→?????男管家廚師園丁雜役假設為真，則由（2）得：再由（1）得：但無法判定的真假 假設為假，則由（3）得：再由（4）得：由（1）得：綜上所述：和說了假話，，的話真假未知 6. 四个朋友被认定为非法进入某计算机系统的嫌疑人。他们已对调查员作了陈述。
艾丽斯说“卡罗斯干的” 约翰说“我没幹。” 卡罗斯说“戴安娜干的。” 戴安娜说“卡罗斯说是我幹的，他说谎。” a）如果调查员知道四个嫌疑人中恰有一人说真话，那么准幹的？解释你的推理。 b）如果调查员知道恰有一人说谎，谁干的？解释你的推理。 解：前提符號化為 （1）A: C （2）J: ? J （3）C: D （4）D: ? (C: D) a) 祗有一句話為真，而（3）（4）有且僅有一句為真，分別討論（3）（4）為真的情況。 b）分析步驟同上。 7. 用真值表證明德摩根律和吸收律。 解答略 8. 使用等值演算證明下列命題公式為永真式（不得用真值表） 解答： a
《离散数学》试题及答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式?x((A(x)?B(y，x))??z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死
7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（4）Q P→ ? P? Q→ ?（2）Q P? →（3）Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)?Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能 答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。 答：?P ，Q→P 14、谓词公式?x(P(x)??yR(y))→Q(x)中量词?x的辖域是（）。 答：P(x)??yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
逻辑推理题常用的解法与解题思路 “逻辑思路”，主要是指遵循逻辑的四大基本规律来分析推理的思路。 【同一律思路】同一律的形式是：“甲是甲”，或“如果甲，那么甲”。它的基本内容是，在同一思维过程中，同一个概念或同一个思想对象，必须保持前后一致性，亦即保持确定性。这是逻辑推理的一条重要思维规律。运用这一规律来解题，我们把它叫同一律思路。 例1. 某公安人员需查清甲、乙、丙三人谁先进办公室，三人口供如下：甲：丙第二个进去，乙第三个进去。乙：甲第三个进去，丙第一个进去。丙：甲第一个进去，乙第三个进去。三人口供每人仅对一半，究竟谁第一个进办公室？ 分析（用同一律思路推理）；这一类问题具有非此即彼的特点。比如甲是否是第一个进办公室只有两种可能：是或非。我们用1表示“是”，0表示“非”，则可把口供列表处理。（1）若甲第一，则依据丙的口供见左表，这个表与甲的口供仅对一半相矛盾；（2）若甲非第一，则依据丙的口供，乙第三个进去，进行列表处理如右表，与“三人口供仅对一半”相符。从而可以判定，丙最先进入办公室。这个问题也可以不列表而用同一律推理。甲的话第一句对，第二句错，则丙第二，乙不是第三，又不是第二，自然乙第一，甲第二，这个结论与丙说的话“半对半错”不符。因此，有甲的第一句错，第二句对。即乙第三个进去，丙不是第二个，自然是第一个。这个结论与乙的话“半对半错”相符：甲不是第三，丙是第一。并且这个结论与丙的话“半对半错”也相符：甲不是第一，乙是第三。在整个思维过程中，我们对三人的话“半对半错”进行了一一验证，直到都符合题目给定的条件为止。 例2. 从前一个国家里住着两种居民，一个叫宝宝族，他们永远说真话；另一个叫毛毛族，他们永远说假话。一个外地人来到这个国家，碰见三位居民，他问第一个人：“请问你是哪个民族的人？”“匹兹乌图。”那个人回答。外地人听不懂，就问其他两个人：“他说的是什么意？”第二个人回答：“他说他是宝宝族的。”第三个人回答：“他说他是毛毛族的。” 请问，第一个人说的话是什么意思？第二个人和第三个人各属于哪个民族？ 分析（用同一律思路思考）：如果第一个人是宝宝族的，他说真话，那么他说的是“我是宝宝族的”。如果这个人是毛毛族的，他说假话，他说的还是“我是宝宝族的”。这就是说，第一个人不管是什么民族的，那句话的意思都是：“我是宝宝族的”。根据这一推理，那么第二个人回答“他说他是宝宝族的”这句话是真的，而从条件可知，说真话的是宝宝族人，因此可以判断第二个人是宝宝族人。不管第一个人是什么民族的，根据前面推理已知他说的话是“我是宝宝族的”，而第三个人回答“他说他是毛毛族的”显然是错的，而说假话的是毛毛族人，因此可以断定第三个人是毛毛族人 我们在分析本题时，始终保持了思维前后的一致性，这就是同一律思路的具体运用。 【不矛盾律思路】不矛盾律的形式是“甲不是非甲”。它的基本内容是：同一对象，在同一时间内和同一关系下，不能具有两种互相矛盾的性质，它是逻辑推理的又一重要规律，运用不矛盾律来推理、思考某些问题的解答，这种思路我们把它叫做不矛盾律思路。 例1.有三个和尚，一个讲真话，一个讲假话，另外一个有时讲真话，有时讲假话。一天，一位智者遇到这三个和尚，他先问左边的那个和尚：“你旁边的是哪一位？”和尚回答说