析取——或者，或许，可能。 蕴涵——若…则…，假如…那么…，既然 …那就…，倘若…就…。 等价——当且仅当，充分必要，相同，一样。
2013-6-24
7、运算顺序 逻辑联结词也称逻辑运算符，以上五种最基本 的联结词组成了一个集合 {, , , , } ，称为 一个联结词集。规定优先级的顺序为, , , , ，若有括号时，先进行括号内运算。 例如： P (Q P ) (Q R ) Q 设P真值为1 ，Q真值为0，R真值为1
真值表：
P Q
0 0 0 1
PQ
1 0 0 1
1
1
0
1
2013-6-24
例1.16、春天到了，燕子南飞。 解： P : 春天到了; Q : 燕子南飞
PQ
2013-6-24
6、逻辑联结词与自然语言中联结词的关系。
否定——不是，没有，非，不。 合取——并且，同时，和，既…又…，不但 …而且…，虽然…但是…。
原子命题 例：4是合数。 例：4是合数，并且3是素数。 复合命题 例：4是合数，并且3是素数，但1既不是素数也 不是合数。 复合命题
2013-6-24
例： 2是有理数是不对的；2是偶素数；
2或4是素数；如果2是素数，则3也是 素数；2是素数当且仅当3也是素数。
解： : 2是有理数 P
Q : 2是素数
R : 2是偶数
S : 3是素数 T : 4是素数
“非 P”；“ Q 并且 R”；“ Q 或 T ”； “如果 Q ，则 S”；“ Q 当且仅当 S” .
2013-6-24
二、逻辑联结词。
常用的联结词有 , , , , 这五种
2013-6-24
P 1、“非 ”称为 p 的否定式，记作 P
例2、将下面命题符号化。 (1)小丽既聪明又用功。 (2)小丽聪明，但不用功。
(3)小丽不但聪明，而且用功。
PQ
P Q
PQ
(4) 小丽不是不聪明，是不用功。 (P ) Q
(5)小刚与小丽都是三好学生。 (6)小刚与王丽是同学。
RS
2013-6-24
T 解：设 P ：小丽聪明， Q ：小丽用功。 R:小刚是三好学生， S :小丽是三好学生。 T:小刚与王丽是同学
2013-6-24
例7、P：北京比天津人口多，
Q：2+2=4
R：乌鸦是白色的。求下列复合命题的真值。 (1).((P Q ) ( P Q )) R
(2).(Q R ) ( P R ) (3).(P R ) ( P R )
解：P,Q,R的真值分别为1，1，0，所以
PQ
(3) 因为天下雨，所以我在室内活动。 P Q (4) 除非天下雨，否则我不在室内活动。 Q P (5) 如果天不下雨，我就不在室内活动。P Q (6) 仅当天下雨，我才在室内活动。
2013-6-24
QP
5、“P 当且仅当 Q ”称 P, Q的等价式，记作 P Q 。
Q P 是 Q 的充要条件，也是 P 的充要条件。
2013-6-24
数理逻辑的研究内容
现代数理逻辑：逻辑演算、证明论、公理集 合论、递归论和模型论。 逻辑演算是数理逻辑中最成熟的部分，在计 算机科学中应用最为广泛，其中命题逻辑是 数理逻辑的最基础部分，谓词逻辑是在它的 基础上发展起来的，本门课研究命题逻辑与 谓词逻辑。

2013-6-24
第一章 命题逻辑 Proposition Logic

命题变元：真值可以变化的陈述句，也用 P,Q,R,…等表示。命题变元已不在是命题。
2013-6-24
2、命题公式(或合式公式)
定义1.1 通俗地说，命题公式是由命题变元，联结词，
圆括号按一定逻辑关系联结起来的字符串。 (1)单个命题变元是命题公式,并称为原子公式. (2)若A是命题公式,则￢A也称为命题公式. (3)若A，B是命题公式,则(A∧B), (A∨B), (A→B), (A B) 也是命题公式. (4)只有有限次地应用(1)～ (3)形成的符号串才是合式 公式.
真值表
P
0 1
P
1
0
例如： ：11是素数； P ：11不是素数 P
P 取值1， P 取值0。
2013-6-24
2、“ 并且Q ”称为 P, Q的合取式，记作 P Q 。 P 真值表
P Q
0 0 1 1 0 1 0 1
PQ
0 0ቤተ መጻሕፍቲ ባይዱ0 1
例1.1，小刚和小明都是大学生
解： ：小刚是大学生， P

2013-6-24
命题的记法
命题的符号化：P,Q,R,…,Pi, ,Qi ,Ri,… 真值的符号化：1/T表真，0/F表假 例：P: 2是素数，Q:雪是黑色的
2013-6-24
命题的分类
简单命题(原子命题）——不能再分解成更简单的命题 命题 复合命题——由简单命题用联结词联结而成的命题
P 3、“ 或者 Q ”称 P, Q的析取式，记作 P Q 。
真值表
P Q
0 0 1 1 0 1 0 1
PQ
0 1 1 1
例1.5，今晚我在家看电视或听音乐。
解： ：今晚我在家看电视， P
Q ：今晚我在家听音乐
2013-6-24
命题符号化为：
PQ
注意：
①“∨”的逻辑关系是明确的。即P、Q二命题中至少有
2013-6-24
离散数学的内容十分丰富，最重要，最 核心的是：数理逻辑、集合论、代数系统 和图论。本课程主要讲授以上四个方面的 内容。
2013-6-24
数理逻辑简介
2013-6-24
数理逻辑是用数学方法来研究推 理的形式结构和推理规律的数学学 科，这里所指的数学方法就是引进 一套符号体系的方法，所以数理逻 辑又称符号逻辑。它与数学的其它 分支、计算机科学、人工智能、语 言学等学科均有密切的联系。
2013-6-24
例3、将下列命题符号化
⑴张晓静爱唱歌或爱听音乐； 解：P：张晓静爱唱歌；Q:张晓静爱听音乐 符号化为P∨Q
(2)张晓静是江西人或安徽人； 解：R：张晓静是江西人；S:张晓静是安徽人 可符号化为(R∧￢ S)∨(S ∧￢ R)
(3)张晓静20多岁或30来岁. 解：这里的或是一个模糊的数据。
2013-6-24

2 、 用P表示命题“天下雪”， Q表示命题 “我将去镇上”，R表示命题“我有时间”。 以符号形式写出下列命题:
(a)如果天不下雪和我有时间,那么我将去镇上. (b)我将去镇上，仅当我有时间.
(c)天不下雪 (d)天下雪,那么我不去镇上
2013-6-24
第1.2节 命题公式及真值表
（1）的真值为1， （2）的真值为1， （3）的真值为0。
2013-6-24
习题解析

1、指出下列语句哪些是命题，哪些不是命题， 如果是命题指出真值 a) 离散数学是计算机科学系的一门必修课 b) Π>2 吗？ c) 明天我去看电影 d) 请勿随地吐痰 ！ e) 不存在最大质数
2013-6-24
f) 如果我掌握了英语，法语，那么学习其他欧 洲的语言就容易多了 g) 9+5<12 h) x<3 i) 月球上有水
②数理逻辑中的联结词是对日常语言中的联结词的
一种逻辑抽象，自然语言中联结词所联结的句子 之间是有一定内在联系的，但在数理逻辑中，联 结词所联结的命题可以毫无关系。
2013-6-24
例、
P ：天下雨，Q ：我在室内活动。
(1) 如果天下雨，那么我在室内活动。 P Q
(2) 只要天下雨，我就在室内活动。
第1.1节 命题及联结词
2013-6-24
内容：命题，逻辑联结词，命题符号化 重点： (1)掌握命题概念 (2)掌握联结词含义及真值表 (3)掌握命题符号化方法
2013-6-24
一、命题的概念
命题是研究思维规律的科学中的一项基本要素， 它是一个判断的语言表达。 命题：能判断真假的陈述句。 说明：一切没有判断内容的句子，无所谓是非的 命题真值：命题所表达的判断结果。 句子，如感叹句、疑问句、祈使句等都不是命题。
2013-6-24
内容：命题公式，24组重要等值式，命题公式的类型
重点：(1) 掌握命题公式的定义及公式的真值表。 (2) 掌握两公式等值的定义；掌握24个重要 等值式，并能利用其进行等值演算。 (3) 掌握重言式和矛盾式的定义及使用真 值表进行判断。
2013-6-24
一、命题公式
1、命题常元、命题变元 命题常元：简单命题。
计算机软件 离散数学
Discrete Mathematics
主讲教师：任美睿
2013-6-24
离散数学是现代数学的一个重要分支。 是计算机科学中基础理论的核心课程，为 计算机科学提供了有力的理论基础和工具。 离散数学的基本思想、概念和方法广泛地 渗透到计算机科学与技术发展的各个领域， 而且其基本理论和研究成果更是全面而系 统地影响和推动着其发展。
(6) 地球外的星球上也有人。
2013-6-24
例1、判断下列句子中哪些是命题。 (7) 明天有课吗？ (9) 我正在说假话。
× √?
(8) 小明和小林都是三好生。 (10) 2020年春节是晴天。
×悖论,无法判断真值
√?
2013-6-24
命题的判断
判断一个语句是否为命题，关键： ①首先看是否为陈述句； ②再看其真值是否唯一。 要注意两点： ①一个陈述句在客观上能判断真假，而不受人的知识 范围的限制； ②一个陈述句暂时不能确定真值，但到了一定时候就 可以确定，与一个陈述句的真值不能唯一确定是不 结论:1、命题一定是陈述句，陈述句未必是命题。 同的。 2、命题的真值有时可以明确给出，但有时还需要依靠 环境、条件和实际环境时间才能确定其真值。