离散数学命题逻辑的基本概念

数理逻辑部分

第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日星期四

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

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

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

命题演算

? 命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

原始命题/原子命题 复合命题 逻辑连接词 否定/┐ 合取/∧ 析取/∨

条件/→（┐P∨Q）

双条件（不好意思，双向箭头字符未找到，(P∧Q)∨(┐P∧┐Q)） 真值表 命题公式/公式 命题变元 命题演算

等价（自反性、对称性、传递性，等价变换法俗称“少林派”） 结合律 交换律 分配律

德·摩根律/反演律 双重否定率 代换

蕴含（自反性、反对称性、传递性，蕴含推理法俗称“武当派”，传递法俗称“隔山打牛”） 对偶法则 对偶

不可兼析取（析取符上加一横，异或） 逆条件（条件符上加字母c） 与非/↑ 或非/↓

? ? ? ? ? ? ? ? ? ?

结合力（ ⑴┐⑵∧⑶∨、不可兼析取、↑、↓⑷→、逆条件⑸双条件 ） 析取范式 合取范式

主析取范式（∑=m∨…） 主合取范式（∏=M∧…） 直接推演 P规则 T规则

CP规则（俗称“北冥神功”） 间接推演/间接证明/反

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

【课题】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-

集合论部分

第三章、集合的基本概念和运算

3.1 集合的基本概念集合的定义与表示

集合与元素

集合 没有精确的数学定义

理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员 集合的表示

列元素法 A={ a, b, c, d }

谓词表示法 B={ x | P(x) }

B 由使得 P(x) 为真的 x 构成常用数集

N, Z, Q, R, C 分别表示自然数、整数、有理数、

实数和复数集合，注意 0 是自然数.

元素与集合的关系：隶属关系

属于 ，不属于

实例

A={ x | x R x2-1=0 }, A={-1,1}

1 A, 2 A

注意：对于任何集合 A 和元素 x (可以是集合)，

x A和 x A 两者成立其一，且仅成立其一.

集合之间的关系

包含（子集） A B x (x A x B)

不包含 A B x (x A x B)

相等 A = B A B B A

不相等 A B

真包含 A B A B A B

不真包含 A B

思考：