离散数学 郝晓燕 第1章逻辑

《离散数学 郝晓燕 第1章逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数理逻辑数理逻辑又称符号逻辑、数学逻辑,是用数学方法研究符号化、形式化的逻辑演绎规律的数学分支。数理逻辑的主要分支包括：逻辑演算(包括命题演算和谓词演算)、模型论、证明论、递归论和公理化集合论。数理逻辑简史数理逻辑是古典逻辑的发展,古典逻辑又称形式逻辑，从亚里士多德的三段论起已有2000多年的历史。古典逻辑分析语言所表达的逻辑维形式。但人们的语言中常有含糊不清不易判别的语句引起歧义，甚至争论。17世纪德国哲学家、数学家G.W.莱布尼兹提出用数学符号式的“通用语言”来进行思维演算，使人们能够证明思维的正确性，从而避免争论，这是数理逻辑最早的萌芽。数理逻辑简史到19世纪初英国数学家G.布尔终

2、于成功地构造了一种思维的代数，后来被称为布尔代数，初步实现了莱布尼兹的部分设想，又经过不少数学家的努力，布尔代数被发展为具有逻辑蕴涵式的命题演算，成为最简单的公理化的逻辑系统。布尔同时代的英国数学家A.德·摩根，采用符号表示命题中的谓词，使数学中的“关系”，“函数”都可以在逻辑命题中出现，加强了逻辑的表现力。经过G.弗雷格等数学家的改进，最终建立了公理化的谓词演算，成为数理逻辑的基础。第1章命题逻辑§1-1命题§1-1-1命题与真值定义1-1-1.1命题是能够判明真假的陈述句。判断的结果即命题的真值，真值只有“真”和“假”两种，真值为真时用“Ｔ”(或“１”)表示，真值为假时用“Ｆ”(或“

3、０”)表示。例1-1-1.1判断以下语句是否为命题，若是命题请给出命题的真值。（1）多美丽的景色呀！（2）你喜欢大学生活吗？（3）请不要在室内吸烟!（4）3+2=5（5）3+2=1（6）X+2=5（7）郑州是河北的省会。（8）中国承办二零零八年奥运会。（9）地球外的星球上也有人类。（10）我在说谎。§1-1-2原子命题与复合命题在例1-1-1.1中出现的命题，有一个共同的特点，即反映了对单一事物的真假判定，是简单的不能再分解的陈述句，这样的命题称之为原子命题或简单命题。原子命题通常用英文字母A、B、C、...P、Q、R、...A1、B2、C3、...Pi、Qi、Rk、...等表示。例如P

4、：郑州是河北的省会。R1：北京是中国的首都。原子命题之外，有很多命题是由一个或者多个命题组合而来的，例如:郑州不是河北的省会。郑州不是河北的省会并且北京是中国的首都。明天有雨或有雪。定义1-1-2.1原子命题通过逻辑联结词组合成的新命题是复合命题。思考的问题复合命题是用一些连接词将多个简单命题连接起来的复合句。那么1如何引进符号表示这些连接词？命题变元：用小写字母p,q,r,p1,q1等表示任意的是一个简单命题。命题变元是待定的简单命题，可以用具体的简单命题来代换，从而具有确定的真值。2哪些连接词要符号化？§1-2逻辑联结词§1-2-1否定联结词定义1-2-1.1设P为命题，复合命题“非

5、P”(或“P的否定”)称为P的否定式，记作P，符号称作否定联结词。规定P的真值为真当且仅当P的真值为假，否则P的真值为假。采用表格形式可以更直观清晰分析命题P与其否定命题P的逻辑关系，请你根据否定联接词的逻辑含义尝试画出表格。例1-2-1.199不是素数。解：令P：99是素数。则该命题可表示为P。§1-2-2合取联结词定义1-2-2.1设P,Q为两个命题，复合命题“P并且Q”称为P与Q的合取式，记作PQ，称作合取联结词。规定PQ的真值为真当且仅当P与Q的真值同时为真，否则PQ的真值为假。通常在自然语言中“并且”、“不但…而且...”、“既…又...”“又…还…”等均可

6、由合取联结词表示。请你根据合取联接词的逻辑含义尝试画出表格。例1-2-2.1小王能歌善舞。解：令P：小王会唱歌。Q：小王会跳舞。则该命题可表示为PQ。例1-2-2.2小王和小张是好朋友。解：该命题可表示为P。例1-2-2.3雪是白色的并且小王会唱歌。解：令P：雪是白色的。Q：小王会唱歌。则该命题可表示为PQ。§1-2-3析取联结词定义1-2-3.1设P,Q为两个命题，复合命题“P或者Q”称作P与Q的析取式，记作PQ，称作析取联结词.规定PQ的真值为假当且仅当P与Q的真值同时为假，否则PQ的真值为真。请你根据析取联接词的逻辑含义尝试画出表格。例1-2-3.1今天刮风或者下雨。解

7、:令P：今天刮风。Q：今天下雨。则该命题可表示为PQ例1-2-3.2第一节课上数学或者上英语。解:令P：第一节课上数学。Q：第一节课上英语。则该命题可表示为(QP)(PQ)。请你尝试画出例1-2-3.2的逻辑含义表格。§1-2-4蕴涵联结词定义1-2-4.1设P,Q为两个命题，复合命题“如果P那么Q”(或“若P则Q”)称为P与Q的蕴含式，记作PQ，称作蕴含联结词（也称为“单条件联结词”）。也说成P是PQ的前件，Q是