緒論離散數學是研究離散量的結構及相互關系的學科，其研究對象一般是有限個或可數個元素。它充分描述了計算機科學離散性的特點，在計算機理論研究及軟、硬件開發的各個領域有著廣泛的應用。離散數學形成于七十年代初期，是現代數學的重要分支。1緒論離散數學在計算機科學中起著工具性的作用。離散數學與計算機科學中的數據結構、算法分析與設計、數據庫原理與設計、人工智能、操作系統、編譯原理、計算機網絡等課程聯系緊密。2本書的主要內容數理邏輯集合論圖論組合數學代數系統簡介3教學目的為計算機專業理論講授作好必要的知識準備;培養抽象思維和推理能力;培養解決實際問題的能力.4教材及參考書《離散數學》屈婉玲等編著高等教育出版社出版2019《離散數學》左孝凌上海科學技術文獻出版社《《離散數學及其應用》（中、英文版）KennethH.Rosen機械工業出版社mhhe/rosen5土耳其商人和帽子三個人：一個商人，兩個應試者A和B。五頂帽子，兩頂是紅色的，三頂是黑色的。兩個應試者看到商人頭上戴的是一頂紅帽子。過了一會兒，A喊道：“我知道我戴的帽子的顏色了”，請問他的帽子是什么顏色的？6數理邏輯邏輯學是一門研究思維形式及思維規律的科學。數理邏輯是用數學方法來研究推理的規律科學，就是引進一套符號體系的方法，所以又稱為符號邏輯。數理邏輯是現代計算機技術的基礎。7第一篇數理邏輯第一部分數理邏輯“我現在年紀大了,搞了這么多年軟件,錯誤不知犯了多少,現在覺悟了。我想假如我早年在數理邏輯上好好下點功夫的話,我就不會犯這么多的錯誤。不少東西邏輯學家早就說了,可我不知道。要是我能年輕20歲,我要回去學邏輯。”愛德斯格·維伯·迪克斯特拉（EdsgerWybeDijkstra）1930-20198數理邏輯莫紹揆中國數理邏輯學家（1917－）“事實上，它們（程序設計）或者就是數理邏輯，或者是用計算機語言書寫的數理邏輯，或者是數理邏輯在計算機上的應用。”9古典形式邏輯亞里士多德,古希臘人，是世界古代史上最偉大的哲學家、科學家和教育家之一。他在直言命題中引進了主謂項的變元，在此基礎上建立了直言三段論的理論。麥加拉學派和斯多阿學派發現了說謊者悖論，創立了命題邏輯,提出了相當于現代命題演算中的真值表。

在中世紀，形式邏輯作為一門獨

立的科學得到了發展。亞里士多德Aristotle公元前384—322

一個人說:“我正在說謊。”如果這個人說的是真話，那么根據他的話可以推知他說的是假話，矛盾。如果這個人說的是假話，既“我沒有說謊”，既他說的是真話，矛盾。說謊者悖論10第一篇數理邏輯數理邏輯創始人德國哲學家和數學家萊布尼茨是德國最重要的自然科學家、數學家、物理學家和哲學家，一個舉世罕見的科學天才，和牛頓同為微積分的創建人。萊布尼茨是現在公認的數理邏輯創始人，他的目的是建立一種“表意的符號語言”，其中把一切思維推理都化歸為計算。實際上這正是數理邏輯的總綱領。1eibniz1646—171611第一部分數理邏輯主要內容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算12第一章命題邏輯的基本概念命題與聯結詞

命題及其分類

聯結詞與復合命題命題公式及其賦值

命題變項與合式公式公式的賦值

131.1命題與聯結詞命題與真值命題：非真即假的陳述句命題的真值：判斷的結果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論不是命題14例1

下列句子中那些是命題？

(1)是有理數.(2)2+5=7.(3)x+5>3.(4)你去教室嗎？

(5)這個蘋果真大呀！

(6)請不要講話！

(7)2050年元旦下大雪.

(8)我正在說假話。

假命題命題概念

真命題不是命題不是命題不是命題不是命題

命題(真值現在未知）不是命題（悖論）15命題分類命題分類：簡單命題（也稱原子命題）：不能分解為更簡單的命題。復合命題：由簡單命題通過聯結詞聯結而成的命題。簡單命題符號化用小寫英文字母p,q,r,…,pi,qi,ri(i1)表示簡單命題。用“1”表示真，用“0”表示假。例如，令

p：π是有理數，則p的真值為0，

q：2+5=7，則q的真值為1。16實例將下面各命題中出現的原子命題符號化.是有理數是不對的。2是偶素數。2或4是素數。如果2是素數，則3是素數。2是素數當且僅當3是素數。p:是有理數

p:2是偶數，q:2是素數p:2是素數，q:4是素數p:2是偶數q:3是素數17否定聯結詞定義1.1

設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯結詞.規定p

為真當且僅當p為假.p01p1018合取聯結詞定義1.2

設p,q為兩個命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p

q,稱作合取聯結詞.規定p

q為真當且僅當p與q同時為真.pq00011011p

q0001同真則真19例2

將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但是不用功.(4)張輝與王麗都是三好生.

合取聯結詞的實例20解令p:吳穎用功,q:吳穎聰明

(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.

(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.

合取聯結詞的實例pqpqpqpq設p:張輝是三好生,q:王麗是三好生21合取聯結詞的實例p

：今天下雨q：明天下雨

p

q：今天下雨并且明天下雨 今天與明天都下雨這兩天都下雨p

：我們唱歌q：我們跳舞

p

q：我們一邊唱歌一邊跳舞22合取聯結詞的實例p

：他聰明q：他用功他既聰明又用功.

p

q他雖然聰明，但不用功。

p

q他不僅聰明，而且用功。

p

q他不是不聰明，而是不用功。(

p)q表示合取關系的常用詞：一邊…一邊…不僅…而且…既…又…雖然…但是…不是…而是…與、和、并且、都23合取聯結詞的實例注意：不要一看到與、和等聯結詞就用。張輝與王麗是同學。p:張輝與王麗是同學（簡單命題）注意：在數理邏輯中可以把兩個沒有內在聯系的命題用聯結詞連接起來。p：我去看電影q：房間里有十張桌子p

q

在邏輯學中允許24析取聯結詞定義1.3

設p,q為兩個命題，復合命題“p或q”稱作p與q的析取式，記作p

q，稱作析取聯結詞.規定p

q為假當且僅當p與q同時為假.pq00011011p

q0111同假則假25析取聯結詞實例他可能是100米或400米賽跑的冠軍.

p

q

用餐滿100元可以贈送免費湯或果盤.

（排斥或）

(p

q)(p

q)析取表示相容或.漢語中的“或”既可以表示“相容或”也可表示“排斥或”.26例3

將下列命題符號化(1)2或4是素數.(2)2或3是素數.(3)4或6是素數.(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.析取聯結詞的實例27例3

將下列命題符號化2或4是素數.(2)2或3是素數.(3)4或6是素數.析取聯結詞的實例令p:2是素數,q:4是素數,pq令p:2是素數,q:3是素數,pq令p:4是素數,q:6是素數,pq28析取聯結詞的實例(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.令p:小元元拿一個蘋果,q:小元元拿一個梨

(pq)(pq)(pq)(pq)或pq29蘊涵聯結詞定義1.4

設p,q為兩個命題，復合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯結詞.規定：pq為假當且僅當p為真q為假.pq00011011p

q1101前真后假則假30蘊涵聯結詞pq的邏輯關系：p為q的充分條件，

或者：q為p的必要條件。注意：當p為假時，pq恒為真。實例：如果天氣好，我就去游玩。

p→q如果我得到這本小說，我將讀完它。

p→

q如果雪是黑的，那么太陽從西方升起。

p→

q31蘊涵聯結詞的實例我將去旅游，僅當我有時間。p:我去旅游q:我有時間p

→

qp:不下雨q:我騎自行車上班只要不下雨，我就騎自行車上班

p

→

q只有不下雨，我才騎自行車上班。

q

→

p32蘊涵聯結詞的實例除非你努力，否則你不能成功。除非你努力，你才能成功。p:你努力q:你成功p

→

q或q

→

ppqpqqppq001111011000100111110011表示p

q的常用詞：p是q的充分條件q是p的必要條件如果（若）p，則q只要p，就q因為p所以qp僅當q只有q

才p除非q,才p除非q，否則非p33例4

設p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)

除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.蘊涵聯結詞的實例pqpqqp或pqqppq或qpqp或pqpq或qpqp34蘊涵聯結詞的實例如果今天是星期天，那么2+3=5.(永為真)如果今天是星期天，那么2+3=6.(除星期天外，天天真）在漢語中，“如果，則”是有因果關系的，但在命題邏輯中p→q總是有意義的．35等價聯結詞定義1.5

設p,q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價式，記作pq，稱作等價聯結詞.規定pq為真當且僅當p與q同時為真或同時為假.pq00011011p

q1001同則真不同則假pq的邏輯關系：p與q互為充分必要條件36等價聯結詞例5

求下列復合命題的真值(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連續.1001037等價聯結詞實例如果兩個三角形全等,則它們的三組對應邊相等；反之亦然.當王曉紅心情愉快時，她就唱歌；反之，當她唱歌時，一定心情愉快.表示p

q的常用詞：p當且僅當q.p是q的充要條件.如果p則q;反之亦然.38小結本小節中p,q,r,…均表示命題.聯結詞集為{,,,,}，p,pq,pq,pq,pq為基本復合命題.其中要特別注意理解pq的涵義.反復使用{,,,,}中的聯結詞組成更為復雜的復合命題.聯結詞的運算順序：（），,,,,,同級按先出現者先運算.391.2命題公式及其賦值命題變項與合式公式命題變項合式公式合式公式的層次公式的賦值公式賦值公式類型真值表40命題變項命題常項：一個命題標識符表示確定的命題，該標識符稱為命題常項。命題變項（命題變元）：命題標識符如僅是表示任意命題的位置標志，就稱為命題變項。常項與變項均用p,q,r,…,pi,qi,ri,…,等表示.41合式公式定義1.6合式公式（簡稱公式）的遞歸定義：(1)單個命題變項和命題常項是合式公式,稱作原子命題公式；(2)若A是合式公式，則(A)也是；(3)若A,B是合式公式，則(AB),(AB),

(AB),(AB)也是；(4)只有有限次地應用(1)—(3)形成的符號串才是合式公式。歸納或遞歸定義,元語言與對象語言,

外層括號可以省去。42合式公式的層次定義1.7(1)若公式A是單個命題變項，則稱A為0層公式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：

(a)A=B,B是n層公式；

(b)A=BC,其中B,C分別為i層和j層公式，且n=max(i,j)；

(c)A=BC,其中B,C的層次及n同(b)；

(d)A=BC,其中B,C的層次及n同(b)；

(e)A=BC,其中B,C的層次及n同(b).(3)若公式A的層次為k,則稱A為k層公式.43合式公式的層次例如：公式A=pB=pC=pqD=(pq)rE=((pq)r)(rs)0層1層2層3層4層44公式賦值定義1.8

設p1,p2,…,pn是出現在公式A中的全部命題變項,給p1,p2,…,pn各指定一個真值,稱為對A的一個賦值或解釋.若使A為1,則稱這組值為A的成真賦值;若使A為0,則稱這組值為A的成假賦值.45公式賦值幾點說明A中僅出現p1,p2,…,pn，給A賦值=12…n是指p1=1,p2=2,…,pn=n,i=0或1,i之間不加標點符號.

A中僅出現p,q,r,…,給A賦值123…是指p=1,q=2,r=3…含n個命題變項的公式有2n個賦值.如公式(pq)r000,010,101,110是成真賦值.001,011,100,111是成假賦值.46真值表定義1.9

將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加1,直至111為止.

(2)按從低到高的順序寫出公式的各個層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.47真值表例6

寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q48(1)A=(pq)r的真值表pqrpq

r

(pq)r000001010011100101110111001111111010101011101010成真賦值:000,001,010,100,110;成假賦值:011,101,11149(2)B＝(qp)qp的真值表p

q

qp(qp)q(qp)qp00011011101100011111成真賦值:00,01,10,11;無成假賦值50(3)C＝

(pq)q的真值表p

q

ppq(pq)(pq)q000110111100110100100000成假賦值:00,01,10,11;無成真賦值51公式的類型定義1.10(1)若A在它的任何賦值下均為真,則稱A為重言式或永真式;(2)若A在它的任何賦值下均為假,則稱A為矛盾式或永假式;(3)若A不是矛盾式,則稱A是可滿足式.52公式的類型由例1可知(pq)r為非重言式的可滿足式；(qp)qp是重言式

(pq)q是矛盾式.注意：重言式是可滿足式，但反之不真.真值表的用途:求出公式的全部成真賦值與成假賦值,判斷公式的類型53第一章習題課主要內容命題、真值、簡單命題與復合命題、命題符號化聯結詞,,,,及復合命題符號化命題公式及層次公式的類型真值表及應用54第一章習題課基本要求深刻理解各聯結詞的邏輯關系,熟練地將命題符號化會求復合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型55練習1判斷下列語句是否為命題：十是一個整數.北京是一個村莊.請勿吸煙!雪是黑色的.今天是7號.1+101=110.您吃飯了嗎?我學英語或法語.如果天氣好,我就去散步.我不給所有自己替自己理發的人理發，但卻給所有自己不替自己理發的人理發。是否是是是否是是否是56練習2將下列命題符號化

(1)豆沙包是由面粉和紅小豆做成的.(2)蘋果樹和梨樹都是落葉喬木.(3)王小紅或李大明是物理組成員.(4)王小紅或李大明中的一人是物理組成員.(5)由于交通阻塞，他遲到了.(6)如果交通不阻塞，他就不會遲到.(7)他沒遲到，所以交通沒阻塞.(8)除非交通阻塞，否則他不會遲到.(9)他遲到當且僅當交通阻塞.57練習2解答(1)豆沙包是由面粉和紅小豆做成的.(2)蘋果樹和梨樹都是落葉喬木.(3)王小紅或李大明是物理組成員.(4)王小紅或李大明中的一人是物理組成員.設p:交通阻塞，q:他遲到(5)由于交通阻塞，他遲到了.(6)如果交通不阻塞，他就不會遲到.(7)他沒遲到，所以交通沒阻塞.(8)除非交通阻塞，否則他不會遲到.(9)他遲到當且僅當交通阻塞.簡單命題合取式析取式排斥或pqpq或qpqp

或pqpq

或qppq

58練習3設p:2是素數