中國海洋大學《離散數(shù)學》課件-第4章 自然數(shù)

1離散數(shù)學信息科學與工程學院計算機科學與技術于彥偉yuyanwei@

1506675135012一月20232Ch4自然數(shù)后繼，自然數(shù)的定義數(shù)學歸納法12一月20233例考慮空集的一系列后繼。+

=∪{}={}

++

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

+++

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

++}

后繼每個集合都是其后繼的元素。每個集合都是其后繼的子集。定義設A為集合，稱A∪{A}為A的后繼，記作A+，即A+=A∪{A}.12一月20234利用后繼的性質(zhì)，可以考慮以構造性的方法用集合來給出自然數(shù)的定義，即

0= 1=0+＝+

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

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

… n＝{0,1,…,n1} …自然數(shù)的定義如果定義1=，則自然數(shù)集從1開始。12一月20235Peano公理（自然數(shù)的定義）G.Peano公理自然數(shù)集合N={0,1,2,…}滿足

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

∪{n}）

(3)如果一個子集S

N

具有性質(zhì)

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

則S=N。性質(zhì)3稱為極小性質(zhì)，它指明了自然數(shù)系統(tǒng)的最小性。如果定義1=，則自然數(shù)集就從1開始。12一月20236定義設A為集合，如果滿足下面的兩個條件：（1）∈A（2）a(a∈A→a+∈A)

稱A是歸納集。例如：下面的集合

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

都是歸納集。歸納集

12一月20237定義自然數(shù)（1）一個自然數(shù)n是屬于每一個歸納集的集合。（2）自然數(shù)集N是所有歸納集的交集。說明：根據(jù)上述定義得到的自然數(shù)集N恰好由,+,++,

+++,…等集合構成。而這些集合正是構造性方法所定義的全體自然數(shù)。例如：自然數(shù)都是集合，集合的運算對自然數(shù)都適用。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>}自然數(shù)n和自然數(shù)集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}相對補運算的性質(zhì)(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第一編集合論絕對補運算的性質(zhì)(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,或?qū)儆贐而不屬于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第一編集合論容斥原理容斥原理(或包含排斥原理)

一個重要的組合計數(shù)原理，解決有限集合中具有某些性質(zhì)或者不具有某些性質(zhì)的元素的計數(shù)。15第一編集合論容斥原理設S為有窮集，P1,P2,…,Pn

是n種性質(zhì),Ai是S

中具有性質(zhì)Pi

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

中具有性質(zhì)P1

或

P2…或Pn的元素數(shù)為|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第一編集合論容斥原理（續(xù)）推論S

中不具有性質(zhì)P1,P2,…,Pn的元素數(shù)為18第一編集合論容斥原理(舉例，續(xù))例1求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個？解：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個命題變元，按照合式公式的規(guī)則，可以產(chǎn)生各種形式各異的公式。1.含n個命題變元的公式有2n個賦值，由n個命題變元確定的真值表個數(shù)為.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為所有出現(xiàn)于A

和B中的命題變元，若對于p1,p2,…,pn任一組真值指派，A和B的真值都相同，即A與B構成的等價式A?B是重言式，則稱A和B是等價的或等值的或邏輯相等。記作AB。25四.命題等值說明：(1)

A,B,均為元語言符號,A或B中可能有啞元出現(xiàn).

例如，在(pq)((pq)(rr))中，r為左邊公式的啞元(r在左側公式中未出現(xiàn)，即左側公式的真

假與r無關).(2)用真值表可驗證公式等值.(3)

區(qū)分，?，=

A

BiffA?

B為重言式?！?”是一般的等號?！啊辈皇锹?lián)結詞，它是說明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六.等值演算與置換規(guī)則等值演算:由已知的等值式推演出新等值式的過程.置換規(guī)則:設(A)是含有公式A的合式公式,(B)是用公式B置換(A)中的A得到的合式公式.若AB,則(A)(B).等值演算的基礎：

(1)基本等值式

(2)置換規(guī)則31六.等值演算與置換規(guī)則例6

證明q(p(pq))qp?！痉椒ㄒ弧康葍r演算 設A:q(p(pq))

因為p(pq)p， 所以用p置換A中的p(pq)得到公式B:qp。故：AB32六.等值演算與置換規(guī)則pqpqp(pq)q(p(pq))qpTTTTTTTFFTTTFTFFFFFFFFTT例6證明q(p(pq))qp

【方法二】真值表33六.等值演算與置換規(guī)則例7證明(pq)(pq)p.證明：(pq)(pq)p(qq)分配律p1 排中律p

同一律34六.等值演算與置換規(guī)則例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六.等值演算與置換規(guī)則例9證明:p(qr)(pq)r

用等值演算不能直接證明兩個公式不等值,證明兩個公式不等值的基本思想是找到某賦值使一個成真,另一個成假.

方法一觀察賦值法.容易看出000,010等是左邊的成真賦值，同時是右邊的成假賦值.

方法二用等值演算先化簡兩個公式，再觀察.

左p(qr)， 右(pq)r

(pq)r

36六.等值演算與置換規(guī)則例10

用等值演算法判斷下列公式的類型

(1)q(pq)

解q(pq)

q(pq)（條件等值式）

q(pq)（德摩根律）

p(qq)（交換律，結合律）

p0

（矛盾律）

0

（零律） 該式為矛盾式.37六.等值演算與置換規(guī)則(2)(pq)?(qp) 例10(續(xù))解(pq)?(qp)

(pq)?

(pq)（假言易位）

1該式為重言式.38六.等值演算與置換規(guī)則(3)((pq)(pq))r

例10(續(xù))解((pq)(pq))r

(p(qq))r

（分配律）

p1r

（否定律）

pr

（同一律）這是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.演算步驟不唯一,應盡量使演算簡潔.39判斷公式等值的方法1.真值表2.命題公式的演算基本命題等值式；公式的等價代換；3.主范式(暫不講)40作業(yè)習題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。得證?！咀C法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三.基本蘊含關系蘊含的性質(zhì)1.設A,B,C為合式公式，若AB且A是重言式，則B必是重言式。2.若AB，BC，則AC，即蘊含關系是傳遞的.3.若AB，AC，則A