《離散數(shù)學(xué)教程》第0章 準(zhǔn)備知識(shí)

離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1集合、命題、謂詞和運(yùn)算0.2鴿籠原理第0章準(zhǔn)備知識(shí)離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.1（1）北京大學(xué)全體學(xué)生（2）全體正整數(shù)（3）本書中所有漢字（4）獲1921年諾貝爾物理學(xué)獎(jiǎng)的科學(xué)家（5）上海市市東中學(xué)所有班級(jí)（6）好書的全體（7）方程x(x2-2x+1)=0的所有根（8）方程x2+x+1=0的根（9）滿足方程x2+y2=1的平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)（10）滿足方程x2+y2=1的平面直角坐標(biāo)系中的點(diǎn)的坐標(biāo)0.1.1集合集合：由確定的、互相區(qū)別的、并作整體識(shí)別的一些對(duì)象組成的總體。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1.1集合對(duì)象：稱元素或成員具體的或抽象的客體單一的客體或客體的序列。集合族：所有成員均為集合的集合表示：集合——大寫字母A，B，C等元素——小寫字母a,b,c等當(dāng)對(duì)象a是集合A的成員時(shí)，稱a屬于A，記為aA當(dāng)對(duì)象a不是集合A的成員時(shí)，稱a不屬于A，記為aA正規(guī)原理：集合理論約定，對(duì)任何對(duì)象、集合A,AA。0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1.2命題與謂詞命題：對(duì)確定事物作出判斷的陳述句。真值：當(dāng)判斷正確或符合客觀實(shí)際時(shí)，稱該命題真（true），否則稱該命題假（false）。真值“真、假”常用數(shù)字“1、0”來表示。排中律：命題或真、或假，但不能兼而有之。0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.2（1）雪是白的。（2）2+2=5（3）陳勝、吳廣起義的那天杭州下雨。（4）第30屆奧林匹克運(yùn)動(dòng)會(huì)開幕時(shí)倫敦天晴。（5）大于2的偶數(shù)均可分解為兩個(gè)質(zhì)數(shù)的和（哥德巴赫猜想）。（6）火星上有生物。（7）好痛快?。。?）您身體好嗎？（9）我說的這句話（例0.2之（9））假。（10）x≤00.1.2命題與謂詞離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)斷言：？？謂詞：斷言中關(guān)于對(duì)象基本性質(zhì)或相互關(guān)系的語言成分。表示：帶有空位的大寫拉丁字母（或字母串）。如：P()表示“小于等于零”

QR(,)表示“與的平方和等于1”

ADD(,,)表示“與的和等于”常用變?cè)ヌ羁瘴唬鏟(x)、QR(x,y)、ADD(x,y,z)n元謂詞：含有n個(gè)空位（或變?cè)┑闹^詞。當(dāng)謂詞的空位或變?cè)幪钜源_定的對(duì)象后，便可判別其真假，即可得到一個(gè)命題。0.1.2命題與謂詞離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.3

R(x)：x是實(shí)數(shù)R(3)是真命題。

L(x,y)：x小于y

L(3,2)是假命題。

B(x,y)：x生于y

B(董青，青島)真假是確定的。ADD(x,y,z)：x+y=z

ADD(3,5,8)是真命題。0.1.2命題與謂詞謂詞填式：

n元謂詞P(x1,…,xn)

填滿對(duì)象后的表達(dá)式P(t1,…,tn)，表示對(duì)象序列t1,…,tn滿足n元謂詞P(x1,…,xn)

，或?qū)ο笮蛄衪1,…,tn具有性質(zhì)P，或關(guān)系P。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1.3集合的表示列舉法：將集合A中元素一一列舉在一個(gè)大括號(hào)中，或列出足夠多的元素以反映A中成員的特征，形如

A＝｛a1,a2,…,an｝或A=｛a1,a2,a3,…｝描述法：將集合A中元素的特征用一個(gè)謂詞來描述，形如

A=｛x

P(x)｝或A=｛x

：P(x)｝

B=｛<x1,x2,…,xn>

Q(x1,x2,…,xn)｝或B=｛<x1,x2,…,xn>:Q(x1,x2,…,xn)｝

概括原理：每一個(gè)謂詞確定一個(gè)集合。0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.4

常用集合及其表示：（1）{0,l}＝{xTV(x)}（2）自然數(shù)集合N={0,1,2,3,…}={xNN(x)}正整數(shù)集合I+={1,2,3,…}={xIN(x)}（3）整數(shù)集合I＝{…,-2,-l,0,l,2,…}=｛xINTEG(x)｝（4）前n個(gè)自然數(shù)的集合

Nn＝{0,1,2,…,n-1}={xNN(x)且xn}（5）前n個(gè)自然數(shù)集合的集合={{0},{0,1},{0,1,2},…}={Nnn

I+}0.1.3集合的表示0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)定義0.1

沒有任何元素的特定集合稱為空集，記為，即

＝{}={xxx}由研究對(duì)象全體組成的集合稱為全集，記為

U={xxx}。定義0.2

空集和只含有有限多個(gè)元素的集合稱為有限集，否則稱為無限集。有限集合中成員的個(gè)數(shù)稱為集合的基數(shù)。集合A的基數(shù)表示為A

。例0.5

{0,1}=2

Nn=n

＝0

{}=1。0.1.3集合的表示0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)歸納法（歸納定義）：

(1)基礎(chǔ)條款：規(guī)定待定義集合以某些對(duì)象為其基本成員，集合的其它元素可以從它們出發(fā)逐步確定。

(2)歸納條款：規(guī)定由已確定的集合成員去進(jìn)一步確定其它成員的規(guī)則。

(3)終極條款：規(guī)定待定義集合只含有(1)，(2)條款所確定的成員。

例0.6

偶數(shù)集E：

(1)基礎(chǔ)條款：0

E。

(2)歸納條款：若xE，則x+2E，x2E。

(3)終極條款：除有限次使用(1)，(2)條款確定的元素外，E中沒有別的對(duì)象。0.1.3集合的表示0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)字母表Σ上的字（用Σ+表示Σ上的字的集合）（1）基礎(chǔ)條款：ΣΣ+。（2）歸納條款：若ξΣ，wΣ+則ξwΣ+（3）終極條款：除有限次使用（l），（2）條款確定的元素外，Σ+中沒有別的對(duì)象。形式語言：用λ表示空字，令Σ+∪λ=Σ，如果LΣ，那么符號(hào)串集合L稱為Σ上的一個(gè)形式語言。0.1.3集合的表示0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.7

設(shè)Σ為數(shù)字集D＝{0,l,2,…,9}，則Σ+＝D+為全體自然數(shù)的集合。當(dāng)Σ＝{a,b}時(shí)，Σ={λ,a,b

，aa，ab，ba，bb，…}。

L＝{λ，ab，aabb，aaabbb，…}Σ

（L為Σ上的一個(gè)語言）0.1.3集合的表示0.1集合、命題、謂詞和運(yùn)算w的字頭:

（1）基礎(chǔ)條款：λ是w的字頭。（2）歸納條款：若w’為w的字頭，w=w’ξw’’（其中ξΣ,

w’,w’’Σ*），那么w’ξ也是w的字頭。（3）終極條款（略）。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.8

“while程序集”的歸納定義（記為WP）（1）基礎(chǔ)條款：V←E在WP中。其中V為變?cè)珽為算術(shù)表達(dá)式。（2）歸納條款：（2.l）若C為條件語句，P1，P2為while程序，則ifCthenP1elseP2endif

在WP中。（2.2）若C為條件語句，P為while程序，則whileCdoPendwhile在WP中。（2.3）若P1,P2為whlile程序，則P1;P2在WP中。（3）終極條款（略）。0.1.3集合的表示0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1.4外延性原理與子集合外延性原理：集合A和集合B相等，當(dāng)且僅當(dāng)它們具有相同的元素。即對(duì)任意集合A,B，A=B當(dāng)且僅當(dāng)屬于A的元素也屬于

B；反之,屬于B的元素也屬于A。0.1集合、命題、謂詞和運(yùn)算例0.9

{0,l}＝{l,0}＝{x∣x(x2-2x＋l)＝0}={x

x＝1或x＝0}集合成員相異、無序，集合表示形式多樣離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)定義1.3

集合A稱為集合B的子集合（或子集），如果A的每一個(gè)元素都是B的元素，即，若元素x屬于A，那么x也屬于B。表示：A是B的子集——AB

或BA

A不是B的子集——AB{a，b}{a，c，b，d}{a，b，c}{a，b，c}{a}{a，b}a{a，b}a{a，b}{1}{1，{1}}{1}{1，{1}}例0.100.1.4外延性原理與子集合0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)定理0.1

對(duì)任意集合A，B，A＝B當(dāng)且僅當(dāng)A

B且B

A

。特別地，對(duì)任意集合A，A

A

。定理0.2

對(duì)任意集合A，AU。定理0.3

設(shè)A，B，C為任意集合，若A

B,B

C，則A

C。定理0.4

對(duì)任何集合A，

A。定理0.5

空集是唯一的。定義0.4

集合A稱為集合B的真子集，如果AB且A

B。“A是B的真子集”記為AB。空集

是所有非空集合的真子集。0.1.4外延性原理與子集合0.1集合、命題、謂詞和運(yùn)算離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)定義0.5

分別稱，為集合A上的一元、二元運(yùn)算，如果，分別是對(duì)單元素和序偶的操作，并且對(duì)任意x,yA，其結(jié)果(x)，

xy是集合A中唯一確定的成員。0.1.5運(yùn)算0.1集合、命題、謂詞和運(yùn)算定義0.6

設(shè)，為集合A上的二元運(yùn)算，x,y.z是A中的任意元素

(1)稱運(yùn)算滿足結(jié)合律，如果x(yz)=(xy)z

(2)稱運(yùn)算滿足交換律，如果xy=yx

(3)稱運(yùn)算對(duì)運(yùn)算滿足分配律，如果x(yz)=(xy)(xz)離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1.5運(yùn)算0.1集合、命題、謂詞和運(yùn)算例0.11

求相反數(shù)運(yùn)算：實(shí)數(shù)集合上的一元運(yùn)算加運(yùn)算、乘運(yùn)算：實(shí)數(shù)集合上的二元運(yùn)算實(shí)數(shù)和多項(xiàng)式的加運(yùn)算、乘運(yùn)算：都滿足結(jié)合律和交換律；乘運(yùn)算對(duì)加運(yùn)算：滿足分配律;矩陣乘法：滿足結(jié)合律，不滿足交換律。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)定義0.7

設(shè)為集合A上的二元運(yùn)算，如果eA且對(duì)任意元素xA有

xe=ex=x，稱元素e為集合A的關(guān)于運(yùn)算的幺元。定義0.8

設(shè)為集合A上的二元運(yùn)算，如果oA且對(duì)任意xA有xo

=ox=o，稱元素o為集合A的關(guān)于運(yùn)算的零元。0.1.5運(yùn)算0.1集合、命題、謂詞和運(yùn)算例0.120是實(shí)數(shù)集合上加運(yùn)算的幺元、關(guān)于乘運(yùn)算的零元；1是實(shí)數(shù)集合上關(guān)于乘運(yùn)算的幺元。零矩陣是關(guān)于矩陣加法的幺元、關(guān)于矩陣乘法的零元；單位矩陣是關(guān)于矩陣乘法的幺元。注意：某元素是否是所在集合的幺元或零元，不僅取決于所在的集合，還取決于所關(guān)注的運(yùn)算。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.1.5運(yùn)算0.1集合、命題、謂詞和運(yùn)算定理0.6

設(shè)為集合A上的二元運(yùn)算，那么集合A的關(guān)于運(yùn)算的幺元是唯一的。定理0.7

設(shè)

為集合A上的二元運(yùn)算，那么集合A的關(guān)于運(yùn)算

的零元是唯一的。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)定義0.9

設(shè)為集合A上的二元運(yùn)算，e為幺元，x,y為A中元素，若

xy＝y(tǒng)x＝e那么稱x(y)為y(x)的逆元。x的逆元通常記為x-1

。0.1.5運(yùn)算0.1集合、命題、謂詞和運(yùn)算例0.13

非零實(shí)數(shù)集合上：1是乘法的幺元每一個(gè)實(shí)數(shù)x都有自己的乘法逆元x-1實(shí)數(shù)集合上：0是加法的幺元每一個(gè)實(shí)數(shù)x都有自己的加法逆元x。定理0.8

設(shè)為集合A上的二元運(yùn)算，e為幺元，且運(yùn)算滿足結(jié)合律，那么當(dāng)A中元素x有逆元時(shí)，它的逆元是唯一的。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.2.1鴿籠原理基本形式0.2鴿籠原理通俗表述：當(dāng)多于鴿籠的鴿子飛進(jìn)籠子時(shí)，至少有兩只鴿子進(jìn)入同一個(gè)籠子。鴿籠原理基本形式一：如果把n+1（n是正整數(shù)）個(gè)對(duì)象放入n個(gè)盒子里，那么至少有一個(gè)盒子里放有兩個(gè)或兩個(gè)以上的對(duì)象。鴿籠原理基本形式二：

m個(gè)對(duì)象放入n個(gè)盒子里（m,n是正整數(shù)），那么有一個(gè)盒子至少放進(jìn)了個(gè)對(duì)象。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)0.2.1鴿籠原理基本形式0.2鴿籠原理例0.14

13個(gè)人組成的集合中，至少有兩個(gè)人生日的月份相同。

60個(gè)人組成的集合中，至少有個(gè)人生日的月份相同。離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.15

二維空間中有5個(gè)格點(diǎn)。證明在所有格點(diǎn)的連線的中點(diǎn)之中，至少有一個(gè)也是格點(diǎn)。證：格點(diǎn)的二個(gè)坐標(biāo)的奇(1)偶(0)狀況只有4個(gè)：(0,0),(0,1),(1,0),(1,1)。因此，根據(jù)鴿籠原理基本形式一，5個(gè)格點(diǎn)中至少有兩個(gè)格點(diǎn)的坐標(biāo)的奇、偶狀況相同。設(shè)這兩個(gè)格點(diǎn)的坐標(biāo)是(a,b)和(a’,b’)，于是，它們之間連線的中點(diǎn)的坐標(biāo)是((a+a’)/2,(b+b’)/2,由于(a,b)和(a’,b’)的奇、偶狀況相同，((a+a’)/2,(b+b’)/2中各坐標(biāo)均為整數(shù)，故該點(diǎn)是一個(gè)格點(diǎn)。0.2.1鴿籠原理基本形式0.2鴿籠原理離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.16從集合{1，2，…，200}中任選101個(gè)數(shù)。證明：無論怎樣選取，在選取的這些數(shù)中，必定存在兩個(gè)數(shù)，使得其中之一可以被另一個(gè)整除。證：任何正整數(shù)都可以寫成2k·a的形式，其中k是自然數(shù)，a是奇數(shù)。對(duì)于集合{1，2，…，200}中的數(shù)，a只能是1，3，5，…，199這100個(gè)數(shù)中的一個(gè)。根據(jù)鴿籠原理基本形式一，在選取的101個(gè)數(shù)中，有兩個(gè)數(shù)的上述表示形式中的a是相同的。即分別是2k·a

，2j·a

，它們之中自然有一個(gè)可以被另一個(gè)整除。0.2.1鴿籠原理基本形式0.2鴿籠原理離散數(shù)學(xué)第0章準(zhǔn)備知識(shí)例0.17

取黑白圍棋子21枚，黑白數(shù)目不限，排列成3行7列的長方形。求證：無論怎樣排放，都可以從中找到一個(gè)長方形，使該長方形的四個(gè)角的棋子同色。0.2鴿籠原理0