下载文档原格式
第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。
十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。
冯·诺意曼，图灵，克林，…等人研究了逻辑与计算的关系。
基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。
除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。
不仅有演绎逻辑，也还有归纳逻辑。
计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。
现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。
第1-1章命题逻辑学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。
表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。
本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。
§1-1-1 命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。
例1-1-1.1人总是要死的。
例1-1-1.2苏格拉底是人。
例1-1-1.3苏格拉底是要死的。
例1-1-1.4中国人民是勤劳和勇敢的。
例1-1-1.5鸵鸟是鸟。
例1-1-1.6 1是质（素）数。
《离散数学》资料库第一章数理逻辑1、数理逻辑的历史。
逻辑是研究人类思维学科，最早是由古希腊学者亚里士多德创建的，他的《工具论》奠定了逻辑学的理论基础。
中国最早的一部逻辑专著--《墨经》也创造了一个比较完整的逻辑体系。
b5E2RGbCAP 根据所研究的对象和方法的不同，逻辑学可分为形式逻辑、辩证逻辑和数理逻辑。
数理逻辑得用数学方法研究推理，利用符号体系研究推理过程中前提和结论之间的关系，因此也叫符号逻辑。
plEanqFDPw从十七世纪开始，就有一些学者试图用数学的方法来研究逻辑。
德国的哲学家的数学家莱布尼兹&".10让血2＞被公认为是数理逻辑的创始人。
他认为数学之所以能发展如此迅速，数学知识之所以能如此有效，就是因为数学使用了特别的符号语言。
这种符号语言为表达思想和进行推理提供了非常良好的条件。
因此他提出了用一种象数学一样的表意符号体系来研究思维形式和规律，能简洁地表达出各种的推理的逻辑关系，使得推理过程就象数学一样可以利用公式来进行计算，以便用计算来解决争论。
DXDiTa9E3d1847年，英国数学家、逻辑学家布尔（G.Boole＞发表了《逻辑的数学分析》（The mathematical Analysis of Logic＞，建立了“布尔代数”（Boolean Algebra＞，并创造一套符号系统，利用符号来表示逻辑中的各种概念。
布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。
RTCrpUDGiT十九世纪七十年代末至二十世纪初，为了理解数学命题的性质和数学思维规律，德国的弗雷格（G.Frege＞、意大利的皮亚诺（G.Peano ＞和英国的罗素（B.Russell＞建立了古典逻辑演算、命题演算和谓词演算。
数理逻辑突破了古典形式逻辑的局限，形成了一个完整的逻辑体系.5PCzVD7HxA而德国的希尔伯特（D.Hilbert^D哥德尔（K.Godel＞的研究努力又使数理逻辑成为一门内容丰富的独立学科。
第一章基础：逻辑和证明1内容提要◦逻辑（logic）：思维的规律和规则，是研究推理的科学公元前四世纪由希腊哲学家亚里士多德首创◦数理逻辑：用数学方法研究逻辑，又称符号逻辑十七世纪由德国数学家莱布尼兹提出2内容提要命题逻辑数理逻辑谓词逻辑34日常使用的自然语言，往往易产生二义性：•冬天，能穿多少穿多少；夏天，能穿多少穿多少。
•中国足球，谁也打不赢；中国乒乓球，谁也打不赢。
引入形式符号体系5本节摘要◦命题（离散对象）◦命题逻辑（离散对象之间的关系）◦命题逻辑的应用6命题◦命题是一个陈述语句，可判定真假◦举例：◦月亮是绿色奶酪做的。
◦1+0=1◦别的星球有生物。
◦坐下！◦几点了？◦X+1=2。
◦我正在说谎。
7命题非命题说明：◦只有具有确定真值的陈述句才是命题。
一切没有判断内容的句子，无所谓是非的句子，如：感叹句、祈使句、疑问句等，都不是命题。
◦命题只有两种真值，“命题逻辑”又称“二值逻辑”。
◦“具有确定真值”指客观上的具有，与我们是否知道它的真值是两回事。
8命题逻辑◦命题变量：表示命题的变量，习惯上用p, q, r, s, ...表示；真命题用T表示，假命题用F表示◦命题逻辑：涉及命题的逻辑领域研究对象：复合命题由已知命题用逻辑运算符（联结词）组合而来只有成绩好和竞赛获奖的同学才能保研操作符：逻辑联结词包括[否定，合取，析取，异或，条件，双条件]9复合命题：否定联结词◦令p为一命题，则p的否定记为 p，读作“非p”，一元运算符。
命题之否定的真值表T FF T“非”放在命题最前面表意更清晰。
p：地球是圆的；p：并非地球是圆的。
p：咱们班上都是男同学；p：咱们班上都不是男同学(×)or 咱们班上不都是男同学(√)。
10◦令p 和q 为命题，p 和q 的合取（conjunction ）记作pq 。
11复合命题：合取联结词T T T T F F F T F F F F两命题析取的真值表阳光灿烂，但是正在下雨= 阳光灿烂正在下雨我在吃饭我女朋友在吃饭我和女朋友一起吃饭= 我和女朋友都在吃饭复合命题：析取联结词◦令p和q为命题，p和q的析取（disjunction）记作p q。
第1章命题逻辑基本概念主要内容1. 命题与真值（或真假值）。
2. 简单命题与复合命题。
3. 联结词：否定联结词┐，合取联结词∧，析取联结词∨，蕴涵联结词→，等价联结词。
4. 命题公式（简称公式）。
5. 命题公式的层次和公式的赋值。
6. 真值表。
7. 公式的类型（重言式（或永真式），矛盾式（或永假式），可满足式）。
学习要求1. 在5种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：① p→q的逻辑关系② p→q的真值③ p→q的灵活的叙述方法2. 写真值表要特别仔细认真，否则会出错误。
3. 深刻理解各联结词的逻辑含义。
4. 熟练地将复合命题符号化。
6. 会用真值表求公式的成真赋值和成假赋值。
1.1 命题与联结词 (2)一、命题的概念 (2)二、复合命题与联结词 (2)三、复合命题真假值 (5)1.2 命题公式及其赋值 (6)一、命题公式的定义 (6)二、公式的层次 (6)三、公式的赋值 (6)四、真值表 (7)五、公式的真假值分类 (8)1.1 命题与联结词一、命题的概念引言中的例子就是要对“我戴的是黑帽子”进行判断。
这样的陈述句称为命题。
作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
真命题表达的判断正确，假命题表达的判断错误。
任何命题的真值都是唯一的。
判断给定句子是否为命题，应该分两步：首先判定它是否为陈述句，其次判断它是否有唯一的真值。
例1.1 判断下列句子是否为命题。
(1) 4是素数。
(2) 是无理数。
(3) x大于y。
(4) 月球上有冰。
(5) 2100年元旦是晴天。
(6) π大于吗？(7) 请不要吸烟！(8) 这朵花真美丽啊！(9) 我正在说假话。
解:本题的(9)个句子中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因而这3个句子都不是命题。
剩下的6个句子都是陈述句，但(3)无确定的真值，根据x,y的不同取值情况它可真可假，即无唯一的真值，因而不是命题。
第一部分数理逻辑
先看著名物理学家爱因斯坦出过的一道题：
一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。
”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。
这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。
”
请问这个人说得对吗？他是怎么推导出来的呢？
要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。
这又需要经历如下过程：
(1) 什么是前提？有哪些前提？
(2) 结论是什么？
(3) 根据什么进行推理？
(4) 怎么进行推理？
下面的第一章，第二章回答第一个问题。
第三章回答第二、三个问题。
下图给出了逻辑部分的知识体系。
