《離散數(shù)學(xué)教程》配套教學(xué)課件

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

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

ADD(,,)表示“與的和等于”常用變元去填空位，如P(x)、QR(x,y)、ADD(x,y,z)n元謂詞：含有n個(gè)空位（或變元）的謂詞。當(dāng)謂詞的空位或變元處填以確定的對象后，便可判別其真假，即可得到一個(gè)命題。離散數(shù)學(xué)第0章準(zhǔn)備知識0.1.2命題與謂詞例0.3R(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)是真命題。離散數(shù)學(xué)第0章準(zhǔn)備知識謂詞填式：

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

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

，或?qū)ο笮蛄衪1,…,tn具有性質(zhì)P，或關(guān)系P。0.1.3集合的表示列舉法：將集合A中元素一一列舉在一個(gè)大括號中，或列出足夠多的元素以反映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è)集合。離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算0.1.3集合的表示例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+}離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算0.1.3集合的表示定義0.1

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

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

U={xxx}。定義0.2

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

。例0.5

{0,1}=2

Nn=n

＝0

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

(1)基礎(chǔ)條款：規(guī)定待定義集合以某些對象為其基本成員，集合的其它元素可以從它們出發(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中沒有別的對象。離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算0.1.3集合的表示字母表Σ上的字（用Σ+表示Σ上的字的集合）（1）基礎(chǔ)條款：ΣΣ+。（2）歸納條款：若ξΣ，wΣ+則ξwΣ+（3）終極條款：除有限次使用（l），（2）條款確定的元素外，Σ+中沒有別的對象。形式語言：用λ表示空字，令Σ+∪λ=Σ，如果LΣ，那么符號串集合L稱為Σ上的一個(gè)形式語言。離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算0.1.3集合的表示例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è)語言）離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算w的字頭:

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

w’,w’’Σ*），那么w’ξ也是w的字頭。（3）終極條款（略）。0.1.3集合的表示例0.8

“while程序集”的歸納定義（記為WP）（1）基礎(chǔ)條款：V←E在WP中。其中V為變元，E為算術(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）終極條款（略）。離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算0.1.4外延性原理與子集合外延性原理：集合A和集合B相等，當(dāng)且僅當(dāng)它們具有相同的元素。即對任意集合A,B，A=B當(dāng)且僅當(dāng)屬于A的元素也屬于

B；反之,屬于B的元素也屬于A。離散數(shù)學(xué)第0章準(zhǔn)備知識0.1集合、命題、謂詞和運(yùn)算例0.9

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

x＝1或x＝0}集合成員相異、無序，集合表示形式多樣0.1.4外延性原理與子集合定義1.3

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

或BA

A不是B的子集——AB離散數(shù)學(xué)第0章準(zhǔn)備知識{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集合、命題、謂詞和運(yùn)算0.1.4外延性原理與子集合定理0.1

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

B且B

A

。特別地，對任意集合A，A

A

。定理0.2

對任意集合A，AU。定理0.3

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

B,B

C，則A

C。定理0.4

對任何集合A，

A。定理0.5

空集是唯一的。離散數(shù)學(xué)第0章準(zhǔn)備知識定義0.4

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

B?！癆是B的真子集”記為AB?？占?/p>

是所有非空集合的真子集。0.1集合、命題、謂詞和運(yùn)算0.1.5運(yùn)算定義0.5

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

xy是集合A中唯一確定的成員。離散數(shù)學(xué)第0章準(zhǔ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)算對運(yùn)算滿足分配律，如果x(yz)=(xy)(xz)0.1.5運(yùn)算離散數(shù)學(xué)第0章準(zhǔ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)算對加運(yùn)算：滿足分配律;矩陣乘法：滿足結(jié)合律，不滿足交換律。0.1.5運(yùn)算定義0.7

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

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

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

=ox=o，稱元素o為集合A的關(guān)于運(yùn)算的零元。離散數(shù)學(xué)第0章準(zhǔ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)算。0.1.5運(yùn)算離散數(shù)學(xué)第0章準(zhǔ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)算

的零元是唯一的。0.1.5運(yùn)算定義0.9

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

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

。離散數(shù)學(xué)第0章準(zhǔ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í)，它的逆元是唯一的。0.2.1鴿籠原理基本形式通俗表述：當(dāng)多于鴿籠的鴿子飛進(jìn)籠子時(shí)，至少有兩只鴿子進(jìn)入同一個(gè)籠子。離散數(shù)學(xué)第0章準(zhǔn)備知識0.2鴿籠原理鴿籠原理基本形式一：如果把n+1（n是正整數(shù)）個(gè)對象放入n個(gè)盒子里，那么至少有一個(gè)盒子里放有兩個(gè)或兩個(gè)以上的對象。鴿籠原理基本形式二：

m個(gè)對象放入n個(gè)盒子里（m,n是正整數(shù)），那么有一個(gè)盒子至少放進(jìn)了個(gè)對象。0.2.1鴿籠原理基本形式例0.14

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

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

二維空間中有5個(gè)格點(diǎn)。證明在所有格點(diǎn)的連線的中點(diǎn)之中，至少有一個(gè)也是格點(diǎn)。離散數(shù)學(xué)第0章準(zhǔ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鴿籠原理0.2.1鴿籠原理基本形式例0.16從集合{1，2，…，200}中任選101個(gè)數(shù)。證明：無論怎樣選取，在選取的這些數(shù)中，必定存在兩個(gè)數(shù)，使得其中之一可以被另一個(gè)整除。證：任何正整數(shù)都可以寫成2k·a的形式，其中k是自然數(shù)，a是奇數(shù)。對于集合{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è)整除。離散數(shù)學(xué)第0章準(zhǔn)備知識0.2鴿籠原理0.2.1鴿籠原理基本形式例0.17

取黑白圍棋子21枚，黑白數(shù)目不限，排列成3行7列的長方形。求證：無論怎樣排放，都可以從中找到一個(gè)長方形，使該長方形的四個(gè)角的棋子同色。離散數(shù)學(xué)第0章準(zhǔn)備知識0.2鴿籠原理0.2.2鴿籠原理加強(qiáng)形式鴿籠原理的加強(qiáng)形式一：如果把q1+q2+……+qn-n+1（qi，n是正整數(shù)）個(gè)對象放入n個(gè)盒子里，那么或者第一個(gè)盒子里至少有q1個(gè)對象，或者第二個(gè)盒子里至少有個(gè)q2對象，……，或者第n個(gè)盒子里至少有qn個(gè)對象。離散數(shù)學(xué)第0章準(zhǔn)備知識0.2鴿籠原理證：如果第一個(gè)盒子里少于q1個(gè)對象，并且第二個(gè)盒子里少于q2個(gè)對象，……，并且第n個(gè)盒子里少于qn個(gè)對象，那么所有盒子里的對象的總數(shù)就不會超過(q1-1)+(q2-1)+……+(qn-1)=q1+q2+……+qn-n這與前提相沖突。0.2.2鴿籠原理加強(qiáng)形式鴿籠原理的加強(qiáng)形式二：如果把n(q-1)+1個(gè)對象放入n個(gè)盒子里，那么至少有一個(gè)盒子里放入了q個(gè)或多于q個(gè)的對象。

離散數(shù)學(xué)第0章準(zhǔn)備知識0.2鴿籠原理鴿籠原理的加強(qiáng)形式三：如果n個(gè)自然數(shù)q1,q2,…,qn的算術(shù)平均值(q1+q2+…+qn)/n大于（q-1）,那么q1,q2,…,qn中至少有一個(gè)大于或等于q

。0.2.2鴿籠原理加強(qiáng)形式例0.18

試證：nm+1個(gè)數(shù)組成的序列a1,a2,…,anm+1中或者有一個(gè)長度為n+1的遞增子序列，或者有一個(gè)長度為m+1的遞減子序列。離散數(shù)學(xué)第0章準(zhǔn)備知識0.2鴿籠原理例0.19

將兩個(gè)同心圓盤A，B分別劃分成200個(gè)全等的扇形。在A盤上任取100個(gè)扇形涂上紅色，其余100個(gè)扇形涂上蘭色。在B盤的200個(gè)扇形上隨意地涂紅色或蘭色（每個(gè)扇形只涂一種顏色）。現(xiàn)將兩盤中心對齊后疊在一起。證明：總可適當(dāng)?shù)剞D(zhuǎn)動B盤，使得兩盤上具有100或更多對的相同顏色的扇形相互重疊在一起。ThankYou!離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算第1章邏輯代數(shù)（上）：命題演算離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.2邏輯等價(jià)式和邏輯蘊(yùn)涵式

1.3范式1.4命題演算消解原理1.1.1邏輯聯(lián)結(jié)詞例1.1（1）雪不是白的（并非雪是白的）。（2）今晚我去商店或者去打球。（3）我看完了書，并且做完了作業(yè)。（4）他去了學(xué)校，又去了工廠。（5）你織布，我耕田。（逗號也是一種連接）（6）如果我有錢，那么我替你付學(xué)費(fèi)。（7）偶數(shù)a是質(zhì)數(shù)，當(dāng)且僅當(dāng)a=2（a是常數(shù)）。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式概念：邏輯聯(lián)結(jié)詞或命題聯(lián)結(jié)詞——聯(lián)接判斷的語言成分。原子命題或原子——不含邏輯聯(lián)接詞的命題。復(fù)合命題——原子命題和邏輯聯(lián)接詞共同組成的命題。1.1.1邏輯聯(lián)結(jié)詞否定詞：“并非”，用符號（或~）表示。

設(shè)p表示一命題，那么

p

表示命題p的否定。

p真時(shí)p假，而p假時(shí)p真。pp0110離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.2

p：雪是白的。

p：并非雪是白的、雪不是白的。（假）

p：整數(shù)都是自然數(shù)。

p：并非整數(shù)都是自然數(shù)（整數(shù)不都是自然數(shù)）。真值表：1.1.1邏輯聯(lián)結(jié)詞合取詞：“并且”，用符號∧表示。

設(shè)p，q表示兩命題，那么p∧q表示合取p和q所得的命題，即p和q同時(shí)為真時(shí)p∧q真，否則p∧q為假。pqp∧q001101010001離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.3

p：你去邊疆。

q：我去海島。

p∧q：你去邊疆并且我去海島。p：你織布。

q：我耕田。

p∧q：你織布，我耕田。真值表：1.1.1邏輯聯(lián)結(jié)詞析取詞：“或”，用符號∨表示。設(shè)p，q表示兩命題，那么p∨q表示p和q的析取，即當(dāng)p和q有一為真時(shí)，p∨q為真，只有當(dāng)p和q均假時(shí)p∨q為假。pqp∨q001101010111離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.4

p：今晚我看書。q：今晚我聽音樂。

p∨q：今晚我看書或者聽音樂。真值表：1.1.1邏輯聯(lián)結(jié)詞“不可兼或”，用符號表示。當(dāng)p和q都為真時(shí)pq卻為假。pqp

q001101010110離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.4

p：吃蛋糕。q：吃冰激凌。

pq：或者吃蛋糕，或者吃冰激凌。（只吃一種零食）真值表：1.1.1邏輯聯(lián)結(jié)詞蘊(yùn)涵詞：“如果…，那么…”，用符號→表示。設(shè)p，q表示兩命題，那么p→q表示命題“如果p，那么q”。其中的p稱為蘊(yùn)涵前件，q稱為蘊(yùn)涵后件。pqp→q001101011101離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.5

p：我有錢。q：我替你付學(xué)費(fèi)。

p→q：如果我有錢，那么我替你付學(xué)費(fèi)。真值表：1.1.1邏輯聯(lián)結(jié)詞實(shí)質(zhì)蘊(yùn)涵：不要求p→q中的p，q有什么關(guān)系，只要p，q為命題，

p→q就有意義。例如：“如果2+2=5，那么雪是黑的”是一個(gè)有意義的命題。實(shí)質(zhì)蘊(yùn)涵的數(shù)學(xué)應(yīng)用：證明對任何集合A，

A：因?yàn)闆]有任何對象x

，x(x為假)，故x蘊(yùn)涵xA為真，即

A真。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.1.1邏輯聯(lián)結(jié)詞雙向蘊(yùn)涵詞：“當(dāng)且僅當(dāng)”，用符號表示。設(shè)p，q為兩命題，那么pq表示命題“p當(dāng)且僅當(dāng)q”，“p與q等價(jià)”，即當(dāng)p與q同真值時(shí)pq為真，否則為假。pqp

q001101011001離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.6

p

：△ABC

≌△A'B'C'

q

：△ABC與△A'B'C'的三邊對應(yīng)相等。真值表：1.1.2命題公式符號化過程的最基本步驟：用拉丁字母p，q，r，s等表示具體命題，用f，t表示兩個(gè)特殊的常命題：常真命題和常假命題。命題常元：

p，q，r，s，f，t統(tǒng)稱為命題常元。命題變元：以“真、假”或“1，0”為取值范圍的變元，為簡單計(jì)，命題變元仍用p，q，r，s等表示。

(但不使用f，t)

離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.1.2命題公式定義1.1命題公式的歸納定義：

(1)

命題常元和命題變元是命題公式，也稱為原子公式或原子。(2)

如果A，B是命題公式，那么(A),(A∧B),(A∨B),(A→B)，(AB)也是命題公式。(3)

只有有限步引用條款(1)，(2)所組成的符號串是命題公式。命題公式簡稱公式，常用大寫字母A、B、C等表示。

子公式：如果B是公式A中的字母相互毗連的一部分，且B自身為一公式，則B稱為公式A的子公式。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.1.2命題公式約定：（1）公式最外層括號一律可省略。（2）聯(lián)結(jié)詞的結(jié)合能力強(qiáng)弱依次為

，(∧，∨)，→，結(jié)合能力平等的聯(lián)結(jié)詞采用左結(jié)合約定，當(dāng)運(yùn)算從左向右依次實(shí)施時(shí)，可省略其括號。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.7

（1）((p→(q∧r)))是命題公式，表示為(p→q∧r)。（2）p→q∨(r∧qs)表示((p)→(q∨((r∧q)s)))1.1.2命題公式定義1.2

設(shè)公式A含有命題變元p1，p2，…，pn，稱p1，p2，

…，pn每一取值狀況為一個(gè)指派，用希臘字母，等表示，當(dāng)A對取值狀況

為真時(shí)，稱指派弄真A，或

是A的弄真指派，記為(A)=1；反之稱指派弄假A，或是A的弄假指派，記為(A)=0。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.1.2命題公式

p

q

r

q∧r

p→(q∧r)(p→(q∧r))

00001111

00110011

01010101

000100011111000100001110離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式例1.8

作出公式(p→(q∧r))的真值表。1.1.3語句的形式化例1.9

將下列語句形式化，并表示為命題公式(1)

我和他既是弟兄又是同學(xué)。p∧q其中p：我和他是弟兄。q：我和他是同學(xué)。(2)

我和你之間至少有一個(gè)要去海島。

p∨q其中p：我去海島。q：你去海島。(3)

狗急跳墻。

p→q其中p：狗急了。q：狗跳墻。(4)

那只狗急了，跳墻了。

p∧q其中p：那只狗急了。q：那只狗跳墻了。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式形式化：用符號語言將自然語言語句符號化。1.1.3語句的形式化

(5)

除非他來，否則我不同他談判。

pq或(p→q)∧(p→q)其中p：他來。q：我與他談判。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式(6)

如果他沒來見你，那么他或者是生病了，或者是不想見你。

p→(q∨r)其中p：他來見你，q：他生病，

r：他想見你。(7)

如果袁翼和王虎不都是傻子，那么他們倆都不會去。

(p∧q)→(r∧s)其中p：袁翼是傻子，q：王虎是傻子，

r：袁翼會去，s：王虎會去。1.1.3語句的形式化

離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式(8)

因?yàn)樘煜掠?所以地皮濕。

p→q

其中p：天下雨，q：地皮濕。(9)只要認(rèn)真讀書，就能考出好成績；只有集中精力，才能認(rèn)真讀書。

(p→q)∧(p→r)

其中p：認(rèn)真讀書，q：考出好成績，r：集中精力。(10)

風(fēng)雨無阻，我去北京。

(p∧q→r)∧(p∧q→r)∧(p∧q→r)∧(p∧q→r)

其中p：天刮風(fēng)，q：天下雨，r：我去北京1.1.3語句的形式化語句形式化應(yīng)注意的問題：要善于確定原子命題，不要把一個(gè)概念硬拆成幾個(gè)概念。要注意語句的語用，不同的語用有不同的邏輯含義。要善于識別自然語言中的聯(lián)結(jié)詞(有時(shí)它們被省略)。否定詞的位置要放準(zhǔn)確。需要的括號不能省略;可以省略的括號，在需要提高公式可讀性時(shí)亦可不省略。注意“只要，就”“只有，才”的正確理解。

語句的形式化未必是唯一的。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.1.3語句的形式化例1.10

設(shè)p:“是偶數(shù)”，q:“是奇數(shù)”，r:“是質(zhì)數(shù)”，s:“=2”，那么，可如下理解各命題公式：(1)p∨q

(是偶數(shù)或是奇數(shù))(2)p∧r→s

(若是偶質(zhì)數(shù)，則=2)(3)p→(r→s)

(若是偶數(shù)，那么當(dāng)是質(zhì)數(shù)時(shí)，=2)(4)r∧s→q

(若是不等于2的質(zhì)數(shù)，則為奇數(shù))(5)q∧┐s→r(若不是奇數(shù)且2，則不是質(zhì)數(shù))(6)(q∨s)→r(若“是奇數(shù)與=2之一真”不成立，則非質(zhì)數(shù))(7)r→(q∨s)(若是質(zhì)數(shù)，則是奇數(shù)與=2之一真)(8)rq∨s(是質(zhì)數(shù)當(dāng)且僅當(dāng)是奇數(shù)或=2)離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.1邏輯聯(lián)結(jié)詞與命題公式1.2.1重言式定義1.3如果對命題公式A中命題變元的一切指派均弄真A，那么，稱A為重言式

；重言式又稱永真式；如果至少有一個(gè)這樣的指派弄真A，那么，稱A為可滿足式，否則稱A為不可滿足式或永假式、矛盾式。例1.11

對任何公式A，

A∨A是重言式,A∧A是矛盾式。對任何原子命題p，p與p都是可滿足式。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.1重言式可用真值表驗(yàn)證重言式、矛盾式、可滿足式。例1.12

用真值表證明(p∨q)∧p→q為重言式。證：建立待證公式的真值表

p

q

p∨q

p

(p∨q)∧p(p∨q)∧p→q

0011

0101

0111

110001001111離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算由表的最后一列可以看出，原式為重言式。1.2邏輯等價(jià)式和邏輯蘊(yùn)含式注意：用真值表驗(yàn)證重言式時(shí)，表中任何一列都不能省略。1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式定義1.4

當(dāng)命題公式AB為永真式時(shí)，稱A邏輯等價(jià)于B，記為A╞╡B，它又稱為邏輯等價(jià)式。A╞╡B的理解：（1）AB是重言式。（2）A，B等值。當(dāng)A真時(shí)B亦真，當(dāng)A假時(shí)B也假；由A真可推出B真，且由B真可推出A真。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式重要的邏輯等價(jià)式:E1

A╞╡A

雙重否定律E2

A∨A╞╡A

，A∧A╞╡A

冪等律E3

A∨B╞╡B∨A

，A∧B╞╡B∧A

交換律E4

(A∨B)∨C╞╡A∨(B∨C)結(jié)合律

(A∧B)∧C╞╡A∧(B∧C)結(jié)合律E5

A∧(B∨C)╞╡(A∧B)∨(A∧C)分配律

A∨(B∧C)╞╡(A∨B)∧(A∨C)離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式E6

(A∨B)╞╡A∧B

德摩根律

(A∧B)╞╡A∨B

E7

A∨(A∧B)╞╡A

吸收律

A∧(A∨B)╞╡A

E8

A→B╞╡A∨B

E9

A

B╞╡(A→B)∧(B→A)E10

A∨t╞╡t

，A∧f╞╡f離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式E11

A∨f╞╡A

，A∧t╞╡A

E12

A∨A╞╡t

，A∧A╞╡fE13

t╞╡f,f╞╡tE14

A∧B→C╞╡A→(B→C)E15

A∨B→C╞╡(A→C)∧(B→C)E16

A→B╞╡┐B→AE17

(A→B)∧(A→B)╞╡AE17

A

B╞╡(A∧B)∨(A∧B)離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式定義1.5當(dāng)命題公式A→B為永真式時(shí)，稱A邏輯蘊(yùn)涵B，記為A╞B，它又稱為邏輯蘊(yùn)涵式。A╞B的理解：（1）

A→B為永真式。（2）

弄真A的指派均弄真B；

“由A真可推得B真”或“由B假可推得A假”，但反之不然。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式重要的邏輯蘊(yùn)涵式：I1

A╞A∨B，B╞A∨B

I2

A∧B╞A，A∧B╞BI3

B╞A→B

I4

A∧(A→B)╞B

I5

(A→B)∧┐B╞┐A

I6

A∧(A∨B)╞B，B∧(A∨B)╞A

I7(A→B)∧(B→C)╞A→C

I8

(A→B)∧(C→D)╞(A∧C)→(B∧D)

I9(AB)∧(BC)╞AC

I10

A╞t;f╞A離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式定理1.1對任意命題公式A，B，C，A'，B'，

(1)A╞╡B當(dāng)且僅當(dāng)╞

AB(2)A╞B當(dāng)且僅當(dāng)╞

A→B(3)若A╞╡B，則B╞╡A(4)若A╞╡B，B╞╡C，則A╞╡C(5)若A╞B，則B╞A(6)若A╞B，B╞C，則A╞C(7)若A╞B，A╞╡A'，B╞╡B'，則A'╞B'離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式定理1.2(代入原理RS)

設(shè)A為永真式，p為A中命題變元，A(B/p)表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題公式(稱為A的一個(gè)代入實(shí)例)，那么A(B/p)亦為永真式。定理1.3(替換原理RR)

設(shè)A為一命題公式，C為A的子公式，且C╞╡D。若將A中子公式C的某些(未必全部)出現(xiàn)替換為D后得到的公式記為B，那么A╞╡B。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式RSRR使用對象任意永真式任一命題公式代換對象任一命題變元任一子公式代換物任一命題公式任一與代換對象等價(jià)的命題公式代換方式代換同一命題變元的所有出現(xiàn)代換子公式的某些出現(xiàn)代換結(jié)果仍為永真式與原公式等價(jià)離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算代入原理和替換原理的區(qū)別：1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式證明邏輯等價(jià)式及邏輯蘊(yùn)涵式的方法：（1）真值表法。

（2）對指派進(jìn)行討論。（3）利用已知的永真式、邏輯等價(jià)式、邏輯蘊(yùn)涵式以及代入、替換原理進(jìn)行推演。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式例1.13：試證對任意公式A，B，C，有

(A∨B)→C╞╡(A→C)∧(B→C)證1：先證(A∨B)→C╞(A→C)∧(B→C)。

設(shè)為弄真(A∨B)→C的任一指派，那么有以下兩種情況：

(a)(A∨B)=0。于是

(A)=(B)=0，從而

(A→C)=(B→C)=1，故

((A→C)∧(B→C))=1。

(b)

(C)=1且

(A∨B)=1。于是

(A→C)=

(B→C)=1，因而又有

((A→C)∧(B→C))=1

據(jù)(a)，(b)可知，必弄真(A→C)∧(B→C)，

因此，(A∨B)→C╞

(A→C)∧(B→C)得證。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式例1.13（續(xù)）：再證(A→C)∧(B→C)╞(A∨B)→C。

設(shè)為弄假(A∨B)→C的任一指派，那么

(A∨B)=1且

(C)=0。

(a)當(dāng)

(A)=1，

(C)=0時(shí)，

(A→C)=0，進(jìn)而有

((A→C)∧(B→C))=0；

(b)當(dāng)

(B)=1，

(C)=0時(shí)，

(B→C)=0，從而也有

((A→C)∧(B→C))=0，據(jù)(a)，(b)可知，弄假(A→C)∧(B→C)。

于是(A→C)∧(B→C)╞(A∨B)→C得證。所以，(A∨B)→C╞╡(A→C)∧(B→C)離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式例1.13（續(xù)）證2（利用代入、替換原理）

：

(A∨B)→C╞╡(A∨B)∨C

對E8用RS╞╡(A∧B)∨C

據(jù)E6用RR╞╡(A∨C)∧(B∨C)對E5用RS╞╡(A→C)∧(B∨C)據(jù)E8用RR╞╡(A→C)∧(B→C)據(jù)E8用RR

離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式例1.14

對任意公式A，B，C，證明：

A∧B

╞

A→(C→B)

證

A∧B╞

B

據(jù)I2

╞

C∨B

對I1用RS

╞

C→B

對E8用RS

╞

A∨(C→B)對I1用RS

╞

A→(C→B)對E8用RS離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.2邏輯等價(jià)式和邏輯蘊(yùn)涵式例1.15

證明下列推理是無效的：證令p表示“狗急”，q表示“狗跳墻”那么前提是pq和

p，結(jié)論是

q

。取指派，使得(p)=0,(q)=1。那么，(pq)=1，(p)=1,但(q)=0。因此，本推理無效。離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式1.2.3對偶原理離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式定義1.6

設(shè)公式A僅含聯(lián)結(jié)詞┐，∧，∨，A*為將A中符號∧，∨，t，f分別改換為∨，∧，f，t后所得的公式，那么稱A*為A的對偶。顯然，A與A*互為對偶，即(A*)*=A例1.16

p∨p

與p∧p

對偶

p∨q

與p∧q

對偶

(t∧p)∨q

與(f∨p)∧q對偶1.2.3對偶原理離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式定理1.4（對偶原理）設(shè)公式A中僅含命題變元p1,…,pn，及聯(lián)結(jié)詞┐，∧，∨，那么

A┝┥A*(p1／p1，…，pn／pn)

這里，A*(p1／p1，…，pn／pn)表示在A*中對p1,…,pn分別作代入p1,…,pn后所得的公式。例1.17

已知p∨q與p∧q互為對偶，在后者中用p，q代入p，q

，再取否定后得((p)∧(q))，容易驗(yàn)證它與p∨q邏輯等價(jià)。1.2.3對偶原理離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式定理1.5（對偶原理）設(shè)A，B為僅含聯(lián)結(jié)詞┐，∧，∨和命題變元

p1,…,pn的命題公式，且滿足A┝B，那么有B*┝A*。進(jìn)而當(dāng)A┝┥B時(shí)有A*┝┥B*。證據(jù)定理1.4及題設(shè)A┝B可知

A*(p1/p1,…,pn/pn)┝B*(p1/p1,…,

pn/pn)從而B*(

p1/p1,…,pn/pn)┝A*(p1/p1,…,pn/pn)

又據(jù)代入原理，有

B*(

p1/p1,…,pn/pn)(p1/p1,…,pn/pn)┝A*(p1/p1,…,pn/pn)(p1/p1,…,pn/pn)即B*(p1/p1,…,pn/pn)┝A*(p1/p1,…,pn/pn)據(jù)E1及替換原理即得B*┝A*。1.2.3對偶原理離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式定義1.7

B*┝A*，A*┝┥B*分別稱為A┝B和A┝┥B的對偶式。例1.18對偶式

A┝A∨B

與A∧B┝A

A∨(B∧C)┝┥(A∨B)∧(A∨C)與A∧(B∨C)┝┥(A∧B)∨(A∧C)當(dāng)已知(p∧q)∨(p∨(p∨q))┝┥p∨q時(shí)，可推得(p∨q)∧(p∧(p∧q))┝┥p∧q。1.2.4實(shí)用邏輯離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式例1.19

某倉庫失竊，甲、乙、丙、丁四人涉嫌被拘留審查。他們的口供筆錄如下：甲：丙是案犯。乙：案犯是丁無疑。丙：如果我作案，那么丁是主犯。?。鹤靼傅臎Q不是我。如果偵探得知四人中只有一個(gè)人說了假話，你能判定誰是案犯，誰說了假話嗎？1.2.4實(shí)用邏輯離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式例1.20

偵探調(diào)查了與案件相關(guān)的四個(gè)證人，分別是管家、廚師、園丁、清潔工。偵探經(jīng)調(diào)查得到以下結(jié)論：

（1）如果管家說的是真話，那么廚師說的也是真話。（2）廚師和園丁說的不可能都是真話。（3）園丁和清潔工沒有都說謊。（4）如果清潔工說的是真話，那么廚師在說謊。你能從中判定說真話和說謊的人嗎？1.2.4實(shí)用邏輯離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式解：

p，q，r，s分別是管家、廚師、園丁、清潔工說真話，上述結(jié)論的形式化表示為：

（1）pq

（如果管家說的是真話，那么廚師說的也是真話。）（2）(qr)（廚師和園丁說的不可能都是真話。）（3）(rs)（園丁和清潔工沒有都說謊。）（4）sq

（如果清潔工說的是真話，那么廚師在說謊。）結(jié)論：管家和廚師都說謊了，對園丁和清潔工是否說謊還無從考證。1.2.4實(shí)用邏輯離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式例1.21

有3個(gè)小孩在一起玩，在額頭上都弄上了泥巴。他們的父親對他們說：“你們中至少有一個(gè)人額頭上有泥巴?！苯又赣H問：“你們知道自己的額頭上有沒有泥巴？”三個(gè)孩子齊搖頭；父親又問同樣的問題，三個(gè)孩子又齊搖頭；可是當(dāng)父親第三次問同樣的問題時(shí)，三個(gè)孩子都回答“知道（自己的額頭上有泥巴）”。分析三個(gè)孩子最終能做出正確判斷的原因。1.2.4實(shí)用邏輯離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.2邏輯等價(jià)式和邏輯蘊(yùn)含式例1.22

A國只有兩種人，一種永遠(yuǎn)說真話，一種永遠(yuǎn)說假話。你來到A國，并在一個(gè)二叉路口不知如何走才能到達(dá)首都。守衛(wèi)路口的士兵只準(zhǔn)你問一個(gè)問題，而且他只答“是”或“不是”。你應(yīng)該如何發(fā)問，才能從士兵處獲知去首都的道路。1.3.1析取范式和合取范式離散數(shù)學(xué)第1章邏輯代數(shù)（上）：命題演算1.3范式文字：命題常元、變