离散数学 课件1.1命题与命题联结词

离

散

数

学主讲人：王素霞1数理逻辑

命题逻辑

一阶逻辑2集合论3二元关系4图论主要内容离散数学的起源与发展脉络1古代萌芽(公元前)

•

逻辑学：古希腊哲学家亚里士多德(Aristotle)奠定了形式逻辑的基础，提出了三段论，这是离散结构中逻辑推理的雏形。

•

组合数学：古印度和阿拉伯的学者研究排列组合问问题，如《吠陀》文献中的诗歌排列，以及犹太经典《密西拿》对组合规则的探讨。217-18世纪：奠基阶段

•

数论与组合：费马(Fermat)，欧拉(Euler)和高斯(Gauss)在数论中研究整数性质，欧拉还解决了"哥尼斯堡七桥问题"，开创了图论。

•

逻辑代数化：莱布尼茨(Leibniz)提出用符号表示逻辑关系，为后来的布尔代数埋下伏笔。319世纪：关键突破

•

布尔代数：乔治。布尔(GeorgeBoole)在《逻辑的数学分析》(1847)中建立布尔代数，将逻辑转化为代数运算。

•

集合论：康托尔(Cantor)在1870年代创立集合论，为离散结构提供了统一语言。

•

图论成形：柯尼斯堡问题后，图论在凯莱(Cayley)等人的工作中应用于化学和树结构研究。420世纪：系统化与计算机推动

•

数理逻辑：弗雷格(Frege)，罗素(Russell)和希尔伯特(Hilbert)完善了命题逻辑与谓词逻辑。

•

算法与计算理论：图灵(Turing)和丘奇(Churclh)在1930年代提出计算模型，奠定计算机科学理论基础。

•

组合爆炸：随着计算机发展，组合数学，图论和离散优化在算法设计中变得至关重要。定义

非真即假的陈述句称为命题。将真和假称为命题的真值，常用T或1表示真，F或0表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。定义由真能推出假，由假能推出真，即自相矛盾的陈述称为悖论。注意:感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不唯一确定的也不是命题

1.1命题与命题联结词命题与真值

判断下列句子是否为命题。（1）济南是安徽的省会。（2）请勿高空抛物！（3）太阳从西方升起。（4）明天补课吗？（5）博物馆里的人真多啊！（6）图灵和德摩根都是英国数学家。（7）别的星球上有生物。（8）2058年春节会下雪。（9）我正在说慌话。真命题假命题疑问句感叹句祈使句悖论假命题命题命题注：作为命题，是否知道它的真假是不重要的，重要的是它有确切的真假。简单命题(原子命题)：能再分解成更简单的陈述句的命题复合命题：由简单命题与联结词按一定规则复合而成的命题注：用小写英文字母

p,q,r,…,pi,qi,ri

(i≥1）表示简单命题例

判断下列命题是简单命题还是复合命题，（1）2不是整数。（2）2是整数并且太阳从西方升起

。（3）2是整数或者太阳从西方升起

。（4）如果2是整数，则太阳从西方升起。（5）2是整数当且仅当太阳从西方升起。

（1）2不是整数。（2）2是整数并且太阳从西方升起

。（3）2是整数或者太阳从西方升起

。（4）如果2是整数，则太阳从西方升起。（5）2是整数当且仅当太阳从西方升起。判断下列命题是简单命题还是复合命题（1）可以分解出“2是整数”这个简单命题，（2）—（5）均可以分解出“2是整数”、“太阳从西方升起”两个简单命题，因而都是复合命题。联结词与复合命题

1.否定式与否定联结词“

”定义:设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作

p.符号

称作否定联结词，并规

定

p

为真当且仅当p为假.2.合取式与合取联结词“∧”定义:

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

p∧q为真当且仅当p与q同时为真.注意：描述合取式的灵活性与多样性

例

将下列命题符号化.(1)王为既用功又聪明.(2)王为不仅聪明，而且用功.(3)王为虽然聪明，但不用功.(4)

张辉与王丽都是三好生.(5)张辉与王丽是同学.

解

令

p：王为用功，q：王为聪明，则

(1)p∧q(2)p∧q(3)p∧

q.令

r:张辉是三好学生，s:王丽是三好学生

(4)r∧s.(5)令

t:张辉与王丽是同学，t是简单命题

.3.析取式与析取联结词“∨”

定义设p,

q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q.∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例

将下列命题符号化

(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.

解

令p:2是素数,q:3是素数,r:4是素数,s:6是素数,

则(1),(2),(3)均为相容或.

分别符号化为:p∨r,p∨q,r∨s,

它们的真值分别为1,1,0.

(4),(5)为排斥或.

令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为

(t∧

u)∨(

t∧u).

令v:王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧

w)∨(

v∧w),又可符号化为v∨w.

4.蕴涵式与蕴涵联结词“

”

定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作p

q，并称p是蕴涵式的前件，q为蕴涵式的后件.

称作蕴涵联结词，并规定，p

q为假当且仅当p为真q为假.

p是q的充分条件，q是p的必要条件.pqp

q111001011100

注：作为推理“如果,则”的形式化当前件为真、后件为真时，显然为真；当前件为真、后件为假时，显然为假。当前件为假时，无论后件是真是假，均为真，这就是“善意推定”。

例如“如果太阳从西边出来，今天就不下雨。”实际上，不管今天是否下雨，这句话都是真命题，因为太阳不可能从西边出来。也就是说，前件“太阳从西边出来”为假，不论后件“今天不下雨”是真是假，这句话都是真命题。例

p：土壤缺少水分q：植物会死亡

命题：“如果p，则q”

当p为真，q为真时，p

q为真

当p为真，q为假时，p

q为假

当p为假时，不管植物是否死亡，“如果p，则q”都是真命题，即前件为假时，不论后件是真是假，p

q都是真命题。p

q的逻辑关系：q为p的必要条件“如果p，则q”的不同的等价表述法很多：

若p，就q

只要

p，就q

因为

p，所以

q

p仅当q

只有q

才p

除非q,才p

或除非q,否则非p.当p为假时，p

q为真如果太阳从西边升起，我就不姓张这句话永远是对的常出现的错误：不分充分与必要条件例

设p:天冷，q:小王穿羽绒服，将下列命题符号化

(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.

q

p

(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.

(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.

p

q(8)小王穿羽绒服仅当天冷的时候.p

qp

qp

qq

p

q

pp

qq

pq

p注意：

p

q与

q

p

等值（真值相同）(6)除非小王穿羽绒服，否则天不冷.如果小王没穿羽绒服，则天不冷如果天冷，则小王穿羽绒服例：p：天气好。 q：我去公园。 1

如果天气好，我就去公园。p

q2

只要天气好，我就去公园。p

q

3

天气好，我就去公园。p

q4

仅当天气好，我才去公园。q

p

5

只有天气好，我才去公园。q

p

6

我去公园，仅当天气好。q

p5.等价式与等价联结词“

”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p

q.

称作等价联结词.并规定p

q为真当且仅当p与q同时为真或同时为假.说明:(1)p

q的逻辑关系:p与q互为充分必要条件

(2)p

q为真当且仅当p与q同真或同假例

求下列复合命题的真值

(1)2+2＝

4当且仅当3+3＝

6.(2)2+2＝

4当且仅当3是偶数.(3)2+2＝

4当且仅当太阳从东方升起.(4)2+2＝

4当且仅当美国位于非洲.(5)函数

f(x)在x0

可导的充要条件是它在

x0连续.11000例