离散数学命题逻辑

数理逻辑部分

第1章 命题逻辑 1.1 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题

注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化

用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1）表示 简单命题

用“1”表示真，用“0”表示假

例如，令 p： 是有理数，则 p 的真值为 0

q：2 + 5 = 7，则 q 的真值为 1

联结词与复合命题 1.否定式与否定联结词“?”

定义 设p为命题，复合命题 “非p”（或 “p的否定”）称

为p的否定式，记作?p. 符号?称作否定联结词，并规定?p 为真当且仅当p为假.

2.合取式与合取联结词“∧”

定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真

注意：描述合取

第一部分

数理逻辑

2013年8月22日星期四

有一逻辑学家误入某部落，被拘于牢

狱，酋长欲放行，他对逻辑学家说： 逻辑学家手指一门问身旁一名战士说： 这扇门是死 今有两门，一为自由，一为死亡， 你可任意开启一门。为协助你脱逃， 今加派两名战士负责解答你所提的任 何问题。惟可虑者，此两战士中一名 天性诚实，一名说谎成性，今后生死 由你自己选择。 逻辑学家沉思片刻，

亡门，他(指另一名战士)将回答‘是’,对吗？

即向一战士发问，然后开门从容离去。

2013年8月22日星期四

P:被问战士是诚实人。 Q:被问战士的回答是 是 R:另一战士回答的是 是 S:这扇门是死亡门。

P T T F

Q T F F

R T F T

S F T F T

F T F 当被问人回答 是 时，此门是生门

当被问人回答 否 时，此门是死门

S (P∧ Q) ∨( P∧ Q)

(P∨ P) ∧ Q Q (S的真值总与Q的真值相反)

逻辑科学，它分为：

2013年8月22日星期四

逻辑，是研究思维形式及思维规律的科学,也把它称为研究推理的 概念是思维的基本单位 由一个或几个判断推出 通过概念对事物是否具有

辨证逻辑——是研究人的思维中的辩证法。

另一判断的思维形式， 某种属性进行肯定或否定

【课题】1．1命题逻辑

【教学目标】

知识目标：

（1）理解命题的概念．知道真命题与假命题的意义； （2）了解简单命题和复合命题的概念；

（3）掌握“且”、“或”、“非”、“如果?，那么?”、“当且仅当”等联结词． 能力目标：

通过简单命题和复合命题的学习，提高学生的数学思维能力.

【教学重点】

命题的真假．

【教学难点】

复合命题的真假．

【教学设计】

（1）通过日常生活、生产中的实例导入命题的概念； （2）引导学生认识命题、真命题和假命题的概念；

（3）通过概括、归纳的方法，让学生理解并掌握逻辑。联结词“且”、“或”、“非”的使用；

（4）通过分析例题，学会应用逻辑连接词的真值表判断命题的真假； （4）通过练习，巩固知识． （5）教学过程符合学生思维特点．

【教学备品】

教学课件．

【课时安排】

2课时．(90分钟)

【教学过程】

教 学 过 程 *第一章引言 我们经常说到一个词叫做“逻辑”,它指的是思维的规律.人们常说“说话要有条有理”,有条有理就是思路清晰,思路清晰就是思维逻辑合理.通常我们说的每一句话都需要合乎逻教师 学生 教学 时行为 行为 意图 间 介绍 说明 倾听 了解 引入教学内容 5

1. 设命题p1，p2的真值为1，p3，p4真值为0，求命题

(p1?(p2?(p3??p1)))?(p2??p4)的真值。

2. 给定3个命题：p：北京比天津人口多；q：2大于1；r：15是素数。 求复合命题：

(q?r)?(p??r)的真值。

3. 用等值演算法和真值表法判断公式A?((p?q)?(q?p))?(p?q)的类型。 4. 下列问题，若成立请证明，若不成立请举出反例：

已知p?r?q?r，问p?q成立吗？ 已知?p??q，问p?q成立吗？

5. 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。

问：若厂方拒绝增加工资，罢工刚开始，罢工是否能够停止。

6. 或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如

果许多学生喜欢逻辑，那么数学难学。

7. 用反证法证明(p?q),(p?r),(q?s)?s?r。

8. 用CP规则证明p?(q?r),r?(q?s)?p?(q?s)。 9. 用CP规则证明：(s?q)?r,?r?p10. p?q?r?s,s?t?u?p?u

,?p?s??q

离散逻辑学实验

班级：10电信实验班 学号：Q10600132 姓名：王彬彬 一、实验目的

熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。

二、实验内容

1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。（A）

2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C））

三、实验环境

C或C＋＋语言编程环境实现。

四、实验原理和实现过程（算法描述）

1.实验原理

（1）合取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P∧Q, 读作P、Q的合取, 也可读作P与Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = T时方可P∧Q =T, 而P、Q只要有一为F则P∧Q = F。这样看来，P∧Q可用来表示日常用语P与Q, 或P并且Q。

（2）析取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P∨Q, 读作P、Q的析取, 也可读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = F, Q = F时方可P∨Q =F, 而P、Q只要有一为T则P∨Q = T。这样看来，P∨Q可用

离散数学讲义

参考书

离散数学，左孝凌、李为鉴、刘永才编著， 上海科学技术文献出版社离散数学，陈莉、刘晓霞编著，高等教育 出版社 Discrete Mathematical Structures, Kolman, Busby and Ross

2013-5-26

第一篇 数理逻辑

第一章 命题逻辑 第二章 谓词逻辑

2013-5-26

第一章 命题逻辑1-1 命题及其表示法定义 1-1.1 命题(Proposition): 可以辨别真假的语句称为命题。 定义 1-1.2 真值： 命题总是具有一个“值”,称为真值。 真值只有“真”、“假”两种，记作 True(真)和False(假),分别用符号T和F 表示。2013-5-26 4

1-1 命题及其表示法例1: (1) 不在同一直线上的三点确定一个平面。 (T) (2) 煤是白的。 (F) (3) 我学英语，或者我学日语。 (4) 如果天气好，那么我去散步。 以上是命题，其中(3)、 (4) 是复合命题。

2013-5-26

1-1 命题及其表示法例2:别的星球上有生物。到目前为止，人们还不能判断别的星球 上是否有生物，但也许将来的人可以判断， 并且只能是别的星球上有生物或没有两种 情况之一。因此是命题。

2013-

第一篇 数理逻辑

数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，? 等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。

第1-1章 命题逻辑

学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。

表述客观世界的各种现象，表述人们的思想，表

第一篇 数理逻辑

数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，? 等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。

第1-1章 命题逻辑

学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。

表述客观世界的各种现象，表述人们的思想，表

第一篇 数理逻辑

数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，? 等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。

第1-1章 命题逻辑

学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。

表述客观世界的各种现象，表述人们的思想，表

1.1 命题符号化及联结词

[教学重点] 命题的概念和六个联结词的定义

[教学目的]1：使学生了解逻辑的框架，命题逻辑的基本要素是命题。 2：通过示例理解命题的概念。

3：通过示例理解合取、析取、异或、蕴涵、等价的含义，了解逻辑语言的精确性，为学习逻辑学打好基础。 4：学会命题符号化的方法。 [教学准备]

[教学方法]讲述法 [课时安排]二课时。 [教学过程] 讲述：

逻辑是解决推理方法的学科，中心是推理，基本要素是命题，称为命题逻辑。 数理逻辑则是用数学方法研究推理； 首先要理解命题是什么，然后了解怎样用数学方法描述命题，甚至逻辑推理。后者是命题符号化的问题。 板书：

第一章 命题基本概念 1.1 命题及其符号化 讲述： 首先讨论命题。 板书： 一 命题

A) 概念：

能判断真假的陈述句。 判断要点：

a 陈述句；b 或真或假，唯一真值； 讲述： 例：

(1) 地球是圆的； 真的陈述句，是命题 (2) 2+3=5； 真的陈述句，是命题 (3) 你知道命题逻辑吗？ 非陈述句，故非命题 (4) 3-x=5； 陈述句,但真假随x的变化而变