中国海洋大学《离散数学》课件-第4章 自然数

1离散数学信息科学与工程学院计算机科学与技术于彦伟yuyanwei@

1506675135012一月20232Ch4自然数后继，自然数的定义数学归纳法12一月20233例考虑空集的一系列后继。+

=∪{}={}

++

={}+={}∪{{}}={,{}}={,+}

+++

={,{}}+={,{}}∪{{,{}}}={,{},{,{}}}={,+,

++}

后继每个集合都是其后继的元素。每个集合都是其后继的子集。定义设A为集合，称A∪{A}为A的后继，记作A+，即A+=A∪{A}.12一月20234利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，即

0= 1=0+＝+

＝{}＝{0} 2=1+＝{}+

＝{}∪{{}}＝{,{}}＝{0,1} 3＝2+＝{,{}}+＝{,{},{,{}}}＝{0,1,2}

… n＝{0,1,…,n1} …自然数的定义如果定义1=，则自然数集从1开始。12一月20235Peano公理（自然数的定义）G.Peano公理自然数集合N={0,1,2,…}满足

(1)0∈N(0=) (2)如果n∈N，那么n+∈N（n+=n

∪{n}）

(3)如果一个子集S

N

具有性质

a)0∈S b)如果n∈S，那么n+∈S

则S=N。性质3称为极小性质，它指明了自然数系统的最小性。如果定义1=，则自然数集就从1开始。12一月20236定义设A为集合，如果满足下面的两个条件：（1）∈A（2）a(a∈A→a+∈A)

称A是归纳集。例如：下面的集合

{,+,++,+++,…} {,+,++,+++,…,a,a+,a++,a+++,…}

都是归纳集。归纳集

12一月20237定义自然数（1）一个自然数n是属于每一个归纳集的集合。（2）自然数集N是所有归纳集的交集。说明：根据上述定义得到的自然数集N恰好由,+,++,

+++,…等集合构成。而这些集合正是构造性方法所定义的全体自然数。例如：自然数都是集合，集合的运算对自然数都适用。2∪5＝{0,1}∪{0,1,2,3,4}＝{0,1,2,3,4}＝53∩4＝{0,1,2}∩{0,1,2,3}＝{0,1,2}＝34-2＝{0,1,2,3}-{0,1}={2,3}2×3＝{0,1}×{0,1,2}＝{<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}自然数n和自然数集N

的定义

12一月20238

P(1)＝P({0})＝{,{0}}＝{0,1}23＝{0,1}{0,1,2}＝{f|f：{0,1,2}→{0,1}}＝{f0,f1,…,f7}

其中f0＝{<0,0>,<1,0>,<2,0>}f1＝{<0,0>,<1,0>,<2,1>} f2＝{<0,0>,<1,1>,<2,0>} f3＝{<0,0>,<1,1>,<2,1>} f4＝{<0,1>,<1,0>,<2,0>} f5＝{<0,1>,<1,0>,<2,1>} f6＝{<0,1>,<1,1>,<2,0>} f7＝{<0,1>,<1,1>,<2,1>}举例

9第一编集合论相对补集(setdifference)相对补集:属于A而不属于B的全体元素,称为B对A的相对补,记作A-B.

A-B={x|x∈A∧x∉B}相对补运算的性质(1)补交转换律

AB=A∩~B(2)德摩根律(相对形式)

A(B∪C)=(AB)∩(AC)A(B∩C)=(AB)∪(AC)10第一编集合论11第一编集合论绝对补(complement)绝对补:~A=E-A,E是全集,A⊆E ~A={x|x∈E∧x∉A}12第一编集合论绝对补运算的性质(1)A=A(2)E=(3)=E(4)A∩A=(5)A∪A=E(6)德摩根律(绝对形式)

(B∪C)=B∩C

(B∩C)=B∪C13第一编集合论对称差(symmetricdifference)对称差:属于A而不属于B,或属于B而不属于A的全体元素,称为A与B的对称差,

记作A⊕B。

A⊕B={x|(x∈A∧x∉B)∨(x∉A∧x∈B)}A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)14第一编集合论容斥原理容斥原理(或包含排斥原理)

一个重要的组合计数原理，解决有限集合中具有某些性质或者不具有某些性质的元素的计数。15第一编集合论容斥原理设S为有穷集，P1,P2,…,Pn

是n种性质,Ai是S

中具有性质Pi

的元素构成的子集，i=1,2,…,n.则S

中具有性质P1

或

P2…或Pn的元素数为|A1∪A2|=|A1|+|A2|-|A1∩A2||A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|-|A2∩A3|-|A1∩A3|+|A1∩A2∩A3|16第一编集合论容斥原理(证明)n=2时的情况: |A∪B|=|A|+|B|-|A∩B|归纳证明:以n=3为例:|A∪B∪C|=|(A∪B)∪C|=|A∪B|+|C|-|(A∪B)∩C| =|A|+|B|-|A∩B|+|C|-|(A∩C)∪(B∩C)| =|A|+|B|-|A∩B|+|C| -(|A∩C|+|B∩C|-|(A∩C)∩(B∩C)|) =|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C| +|A∩B∩C|ABABC17第一编集合论容斥原理（续）推论S

中不具有性质P1,P2,…,Pn的元素数为18第一编集合论容斥原理(举例，续)例1求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？解：S={x|xZ,1≤

x≤1000},

如下定义S

的3个子集A,B,C：

A={x|xS,5|x}，

B={x|xS,6|x}，

C={x|xS,8|x}一.命题公式的赋值定义给公式A中的所有命题变元p1,p2,…,pn指定一组真值，称为对A的一个赋值或解释。成真赋值:

使公式为真的赋值成假赋值:使公式为假的赋值例如，公式p(q→r) 010,011都是成真赋值，

110是成假赋值。

（请自己写出所有的赋值情况）19二.真值表pqqp

(qp)q

(qp)qp

FFTTFTFTTFTTFFFTTTTT真值表:公式A在所有赋值下的取值情况列成的表.例1写出公式

A=(qp)qp

的真值表20二.真值表pqpqpqpq(pq)(pq)p↔qTTFFFTTTTFFTFFFFFTTFFFFFFFTTTFTT例2写出(pq)(pq)和p↔q

的真值表.(pq)(pq)和p↔q

的真值相同.21二.真值表说明：

n个命题变元，按照合式公式的规则，可以产生各种形式各异的公式。1.含n个命题变元的公式有2n个赋值，由n个命题变元确定的真值表个数为.2.从真值表可以看出，有的公式真值全为T，有的公式全为F，有的公式既有T又有F。3.不同形式的命题公式可能对应相同的真值表。22三.命题公式的分类定义设A为一个命题公式(1)若A在各种赋值下取值均为T,则称A为重言式(永真式).(2)若A在各种赋值下取值均为F,则称A为矛盾式(永假式).(3)若A不是矛盾式，则称A为可满足式.说明：(1)重言式是可满足式，但反之不真.(2)可满足式的等价定义是：A至少存在一个成真赋值.(3)可用真值表判断公式类型，求其成真(假)赋值.23三.命题公式的分类关于重言式的两个结论1.任何两个重言式的合取或析取，仍然是一个重言式。2.一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。

例如qq

((ps)r)((ps)r)24四.命题等值1.定义给定两个命题公式A和B，设p1,p2,…,pn为所有出现于A

和B中的命题变元，若对于p1,p2,…,pn任一组真值指派，A和B的真值都相同，即A与B构成的等价式A↔B是重言式，则称A和B是等价的或等值的或逻辑相等。记作AB。25四.命题等值说明：(1)

A,B,均为元语言符号,A或B中可能有哑元出现.

例如，在(pq)((pq)(rr))中，r为左边公式的哑元(r在左侧公式中未出现，即左侧公式的真

假与r无关).(2)用真值表可验证公式等值.(3)

区分，↔，=

A

BiffA↔

B为重言式。“=”是一般的等号。“”不是联结词，它是说明A与Ｂ等值（A↔

B为重言式）的一种记法，因此，“”是元语言符号。26四.命题等值pqpqpq(pq)pqTTTFFFFTFTFTFFFTTTFFFFFFTTTT2.用真值表判断公式等值例5

证明(pq)

pq27五.基本命题等值公式简单的等值公式容易用真值表验证，但是当命题变元较多时，这个过程就变得十分复杂。所以，可以先用真值表验证一组基本而又十分重要的等值公式，以此为基础进行公式演算，判断公式是否等值。28五.基本命题等值公式双重否定律PP1幂等律PPP,PPP2结合律(PQ)RP(QR)

(PQ)R

P(QR)3交换律PQQP,PQQP4分配律P(QR)(PQ)(PR)P(QR)(PQ)(PR)5吸收律P(PQ)P,P(PQ)P6德·摩根律(PQ)PQ,(PQ)PQ729五.基本命题等值公式同一律PF

P,PT

P8零律PFF,PTT9排中/矛盾律PP

T,PP

F10蕴含等值式PQPQ11等价等值式P↔Q(PQ)(QP)

12假言易位PQQP13等价否定等值式P↔QP↔Q14归谬论(PQ)(PQ)P1530六.等值演算与置换规则等值演算:由已知的等值式推演出新等值式的过程.置换规则:设(A)是含有公式A的合式公式,(B)是用公式B置换(A)中的A得到的合式公式.若AB,则(A)(B).等值演算的基础：

(1)基本等值式

(2)置换规则31六.等值演算与置换规则例6

证明q(p(pq))qp。【方法一】等价演算 设A:q(p(pq))

因为p(pq)p， 所以用p置换A中的p(pq)得到公式B:qp。故：AB32六.等值演算与置换规则pqpqp(pq)q(p(pq))qpTTTTTTTFFTTTFTFFFFFFFFTT例6证明q(p(pq))qp

【方法二】真值表33六.等值演算与置换规则例7证明(pq)(pq)p.证明：(pq)(pq)p(qq)分配律p1 排中律p

同一律34六.等值演算与置换规则例8证明p(qr)q(pr)r(qp).证明:p(qr)p(qr) //pqp∨qq(pr)//结合律、交换律q(pr).

p(qr)r(qp)//结合律、交换律r(qp)//q→pq∨p(r)(qp)//双重否定律r(qp).

故p(qr)q(pr)r(qp).35六.等值演算与置换规则例9证明:p(qr)(pq)r

用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到某赋值使一个成真,另一个成假.

方法一观察赋值法.容易看出000,010等是左边的成真赋值，同时是右边的成假赋值.

方法二用等值演算先化简两个公式，再观察.

左p(qr)， 右(pq)r

(pq)r

36六.等值演算与置换规则例10

用等值演算法判断下列公式的类型

(1)q(pq)

解q(pq)

q(pq)（条件等值式）

q(pq)（德摩根律）

p(qq)（交换律，结合律）

p0

（矛盾律）

0

（零律） 该式为矛盾式.37六.等值演算与置换规则(2)(pq)↔(qp) 例10(续)解(pq)↔(qp)

(pq)↔

(pq)（假言易位）

1该式为重言式.38六.等值演算与置换规则(3)((pq)(pq))r

例10(续)解((pq)(pq))r

(p(qq))r

（分配律）

p1r

（否定律）

pr

（同一律）这是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.演算步骤不唯一,应尽量使演算简洁.39判断公式等值的方法1.真值表2.命题公式的演算基本命题等值式；公式的等价代换；3.主范式(暂不讲)40作业习题2（P42）1，2，3，441重言式与蕴含式重言式与等值式的关系等值式与蕴含式的关系基本蕴含式蕴含式的证明42重言式与蕴含式学习要求1.理解重言式、等值式与蕴含式的关系2.熟悉基本蕴含式3.掌握PQ的证明方法43一.重言式与等值式定理设A,B为两个命题公式,AB当且仅当A↔B为一个重言式。例如证明(pq)(qp)证明:(pq)↔(qp)

(pq)↔(qp)（条件等价式）

(pq)↔(pq)（交换律）

1

因此(pq)(qp)44一.重言式与等值式AB

iff

A↔B为一个重言式,又A↔B(AB)(BA),故,A↔B为重言式(AB)为重言式且

(BA)为重言式。我们研究AB为重言式的情况。45二.蕴含式1.定义当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ。

PQ的逆换式：QP

反换式：PQ

逆反式：QP46二.蕴含式pqpqpqqpqppqTTFFTTTTTFFTFFTTFTTFTTFFFFTTTTTT它们之间的关系如下表所示从中看出：(pq)(qp)假言易位

(qp)(pq)47二.蕴含式2.证明PQ的方法(1)等值演算：证明P→Q

1(2)真值表法：列出P→Q的真值表(3)逻辑推证a）指定前件P的真值为1，若由此推出Q的真值亦为1，则PQ是重言式，即PQ成立；b）指定后件Q的真值为0，若由此推出P的真值亦为0，即证明了QP，故PQ成立。48二.蕴含式等价演算例1证明(pq)p证明(pq)→p(pq)p(pq)p149二.蕴含式例2推证q∧(pq)p逻辑推证【证法1】假定q∧(pq)为1.

则q为1，且(pq)为1.

由q为0,pq为1,所以必有p为0,故p为1。得证。【证法2】假定p为0,则p为1,讨论q的真值：若q为1,则pq为1,q为0,故q∧(pq)为0；若q为0,则pq为0,q为1,故q∧(pq)为0.50二.蕴含式3.用蕴含式表示等值式定理设P，Q为任意两个命题公式，PQ的充分 必要条件是PQ且QP。证明若PQ，则P↔Q为重言式， 因为P↔Q(PQ)∧(QP)1， 故PQ1,且QP1，即PQ，QP。反之，若PQ且QP，则PQ1且QP1,

因此P↔Q1，P↔Q是重言式，即PQ。51三.基本蕴含关系PQP1PQQ2PPQ3PPQ4QPQ5(PQ)P6(PQ)Q752三.基本蕴含关系P(PQ)Q8Q

(PQ)P9P

(PQ)Q10(PQ)(QR)PR11(PQ)(PR)(QR)R12(PQ)(RS)(PR)(QS)13(P↔

Q)(Q

↔

R)(P

↔

R)1453三.基本蕴含关系蕴含的性质1.设A,B,C为合式公式，若AB且A是重言式，则B必是重言式。2.若AB，BC，则AC，即蕴含关系是传递的.3.若AB，AC，则A