離散數(shù)學(xué)2省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

離散數(shù)學(xué)DiscreteMathematics1/309/13/20231DiscreteMath.,huangliujia第一部分?jǐn)?shù)理邏輯PartOneMathematicslogic2/309/13/20232DiscreteMath.,huangliujia邏輯學(xué):

研究人思維形式和規(guī)律科學(xué)．因為研究對象和方法各有側(cè)重而又分為形式邏輯、辯證邏輯和數(shù)理邏輯．?dāng)?shù)理邏輯是用數(shù)學(xué)方法來研究推理形式結(jié)構(gòu)和推理規(guī)律數(shù)學(xué)學(xué)科。這里所指數(shù)學(xué)方法就是引進(jìn)一套符號體系方法。所以數(shù)理邏輯又稱符號邏輯，它是從量側(cè)面來研究思維規(guī)律。當(dāng)代數(shù)理邏輯可分為邏輯演算、證實論、公理集合論、遞歸論和模型論。本部分僅介紹計算機(jī)科學(xué)領(lǐng)域中所必需數(shù)理邏輯基礎(chǔ)知識：命題邏輯和謂詞邏輯（一階邏輯）。3/309/13/20233DiscreteMath.,huangliujia第一章命題邏輯ChapterOneFoundationsofPropositionLogic4/309/13/20234DiscreteMath.,huangliujia1.1命題與聯(lián)結(jié)詞1.2命題公式及其賦值命題與真值命題符號化聯(lián)結(jié)詞及其邏輯關(guān)系復(fù)合命題命題常項與變項命題公式及其賦值命題公式類型公式類型判斷方法5/309/13/20235DiscreteMath.,huangliujia一、命題

命題：能判斷真假(非真即假)陳說句。

命題真值：命題判斷結(jié)果?！?.1命題與聯(lián)結(jié)詞它只有兩種可能：真或假，分別用1和0來表示。真值為1命題稱為真命題；真值為0命題稱為假命題。判斷一個句子是否為命題：首先判斷它是否為陳說句;其次判斷它是否有唯一真值。定義一個命題若不能被分解成更簡單陳說句，則稱為簡單命題或原子命題；若一個命題是由幾個簡單陳說句經(jīng)過聯(lián)結(jié)詞聯(lián)結(jié)而成，則稱為復(fù)合命題。例命題“因為3>2,所以3

2.”組成。6/309/13/20236DiscreteMath.,huangliujia（1）

4是素數(shù)。例1.1判斷以下句子是否為命題注：通慣用小寫字母p,q,r

等來表示命題。（9）

我正在說假話。（8）

這朵花真漂亮?。。?）

請不要吸煙！（6）

π大于嗎？（5）

2050年元旦是晴天。（4）

火星上有水。（3）

x大于y,其中x和y是任意兩個數(shù)。（2）

是無理數(shù)。√√√√×××××7/309/13/20237DiscreteMath.,huangliujia定義1.1設(shè)p為命題，復(fù)合命題“非p”(即“p否定”)稱為p否定式，記為┐p。符號┐稱為否定聯(lián)結(jié)詞。要求：┐p為真當(dāng)且僅當(dāng)p為假。二．聯(lián)結(jié)詞與復(fù)合命題則:(1)┐p；(2)┐q.例符號化：（1）張偉不是三好學(xué)生;（2）不是有理數(shù)。解：記p：張偉是三好學(xué)生。q：是有理數(shù)。例1.2將以下命題符號化。(1)是有理數(shù)是不正確.（2）2是偶素數(shù).(3)2或4是偶素數(shù).(4)假如2是素數(shù)，則3也是素數(shù).(5)2是素數(shù)當(dāng)且僅當(dāng)3是素數(shù).解：記p：是有理數(shù).q：2是素數(shù).r：2是偶數(shù).s：3是素數(shù).

t：4是偶數(shù).則各語句表述為：非p;(2)q與r;(3)p或t;(4)假如q,則s；(5)q當(dāng)且僅當(dāng)s.8/309/13/20238DiscreteMath.,huangliujia定義1.2設(shè)p,q為兩個命題。復(fù)合命題“p與q”即“p而且q”稱為p與q合取式，記為p∧q。符號∧稱為合取聯(lián)結(jié)詞。要求：p∧q為真當(dāng)且僅當(dāng)p與q同時為真。注：自然語言中“與”,“和”,“且”,“既.…又…”,“不但…而且…”,“即使…不過…”,“一面…一面…”等聯(lián)結(jié)詞都能夠符號化為∧；但并不是全部“與”、“和”等都能用聯(lián)結(jié)詞∧替換。9/309/13/20239DiscreteMath.,huangliujia(1)

吳穎既用功又聰明.(2)

吳穎不但用功而且聰明.(3)

吳穎即使聰明，但不用功.(4)

張輝和王麗都是三好學(xué)生.(5)

張輝和王麗是同學(xué).例1.3將以下命題符號化p∧q;p∧q;q∧┐p；r∧s。(5)是原子命題,符號化為t:張輝和王麗是同學(xué)。則符號化分別為：解:(1)、(2)、(3)、(4)：令p:吳穎用功；q:吳穎聰明，r:張偉是三好學(xué)生；s:王輝是三好學(xué)生.10/309/13/202310DiscreteMath.,huangliujia定義1.3設(shè)p,q為兩個命題,復(fù)合命題“p或q”稱為p與q析取式,記為p∨q。符號∨稱為析取聯(lián)結(jié)詞。要求：p∨q為假當(dāng)且僅當(dāng)p與q同時為假。注:自然語言中“或”聯(lián)結(jié)兩個命題能夠含有相容性，也能夠含有排斥性。前者稱為相容或，后者稱為排斥或。析取聯(lián)結(jié)詞∨指是“相容或”。11/309/13/202311DiscreteMath.,huangliujia（1）張曉靜愛唱歌或愛聽音樂。（2）張曉靜只能挑選202房或203房。（3）張曉靜是江西人或安徽人。解：(1)令p:張曉靜愛唱歌；q:張曉靜愛聽音樂，則：例1.4將以下命題符號化p∨q;(2)令r:張曉靜住202房；s:張曉靜住203房，則:(r∧┐s)∨(┐r∧s);(3)令t:張曉靜是江西人；u:張曉靜是安徽人，則：(t∧┐u)∨(┐t∧u).12/309/13/202312DiscreteMath.,huangliujia

定義1.4設(shè)p,q為兩個命題。復(fù)合命題“假如p,則q

”稱為p與q蘊涵式，記作p→q。符號→稱為蘊涵聯(lián)結(jié)詞，稱p是蘊涵式前件，q是蘊涵式后件，q是p必要條件。要求：p→q為假當(dāng)且僅當(dāng)p

為真q為假。

注：1.在自然語言中，“假如p,則q”這種命題還有其它敘述方式，比如：“只要p,就q”，“因為p，所以q”,“p僅當(dāng)q”,“只有q才p”，“除非q才p”,“除非q，不然非p

”等等，它們都可符號化為p→q。2.在數(shù)學(xué)或其它自然科學(xué)中，“假如p,則q”往往表示是前件p為真，后件q也為真推理關(guān)系。但在數(shù)理邏輯中，作為一個要求，當(dāng)p為假時，不論q是真是假，p→q均為真（因為考慮整個語句）。3.在自然語言中，“假如p,則q”中前件p和后件q往往含有某種內(nèi)在聯(lián)絡(luò)，而在數(shù)理邏輯中，p與q能夠無任何內(nèi)在聯(lián)絡(luò)。13/309/13/202313DiscreteMath.,huangliujia(1)

假如3+3=6,則雪是白色。(2)

假如3+3≠6,則雪是白色。(3)

假如3+3=6,則雪不是白色。(4)

假如3+3≠6,則雪不是白色。(5)

只要a能被４整除，則a一定能被２整除。(6)

a能被４整除，僅當(dāng)a能被２整除。(7)

除非a能被２整除，a才能被４整除。(8)

除非a能被２整除，不然a不能被４整除。(9)

只有a能被２整除，a才能被４整除。(10)只有a能被４整除，a才能被２整除。(a是一個給定正整數(shù)）。例1.5將以下命題符號化，并指出各復(fù)合命題真值。解：令p：3+3=6；q：雪是白色。則(1)到(4)符號化形式分別為：令r：a能被４整除；s:

a能被２整除。(5)到(9)都可符號化為:p→q；┐p→q；p→┐q；┐p→┐q。它們真值分別為：１,１,０,１。(10)可符號化為r→s,真值為１。s→r，真值視a

值而定。14/309/13/202314DiscreteMath.,huangliujia定義1.5設(shè)p,q是兩個命題，復(fù)合命題“p

當(dāng)且僅當(dāng)

q”稱為p與q等價式，記為p?q。符號?稱為等價聯(lián)結(jié)詞。要求：

p?q為真當(dāng)且僅當(dāng)p與q

同時為真或同時為假。注：p?q可了解為“q與p互為充分必要條件”；它與(p→q)∧(q→p)邏輯關(guān)系完全一致。15/309/13/202315DiscreteMath.,huangliujia(1)

√3是無理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。(2)

2+3=5充要條件是√3是無理數(shù)。(3)

若兩圓面積相等,則它們半徑相等,反之亦然。(4)

當(dāng)王小紅心情愉快時,她就唱歌,反之,當(dāng)她唱歌時,一定心情愉快。解：(1)令p:√3是無理數(shù)；q:加拿大位于亞洲，則符號化為(4)令x:王小紅心情愉快；y:王小紅唱歌，則符號化為p?q,真值為0。(2)令r:2+3=5；令p:√3是無理數(shù)，則符號化為r?p,真值為1。(3)令s:兩圓面積相等；t:兩圓半徑相等，則符號化為x?y,真值由詳細(xì)情況而定。s?t,真值為1。例1.6將以下命題符號化，并討論它們真值。16/309/13/202316DiscreteMath.,huangliujia以上定義五種最基本聯(lián)結(jié)詞組成一個聯(lián)結(jié)詞集{┐，∧，∨，→，?}。由其中某個聯(lián)結(jié)詞聯(lián)結(jié)兩個原子命題（┐聯(lián)結(jié)一個原子命題）所形成復(fù)合命題稱為基本復(fù)合命題，它們真值情況以下表。pq┐pp∧qp∨qp→qp?q小結(jié)110000010111110110010001101117/309/13/202317DiscreteMath.,huangliujia屢次使用聯(lián)結(jié)詞集中聯(lián)結(jié)詞，可組成更為復(fù)雜復(fù)合命題。求復(fù)雜復(fù)合命題真值時，可依據(jù)上述真值表逐次求取。但運算過程中應(yīng)注意聯(lián)結(jié)詞優(yōu)先次序(包含括號)：(),┐,∧,∨,→，?。對同一優(yōu)先級聯(lián)結(jié)詞，按出現(xiàn)先后次序運算。例1.7令：p：北京比天津人口多；q：2+2=4；r：烏鴉是白色。求以下命題真值：(1)((┐p∧q)∨(p∧┐q))→r;(2)(q∨r)→(p→┐r);(3)(┐p∨r)?(p∧┐r).解：∵p,q,r真值分別為1,1,0，∴按照真值表及命題式，(1),(2),(3)真值分別為1,1,0。18/309/13/202318DiscreteMath.,huangliujia定義1.6簡單命題（原子命題）稱為命題常項，而稱真值能夠改變陳說句為命題變項。命題變項普通也用小寫字母p,q,r,…來表示。將命題變項用聯(lián)結(jié)詞和括號按一定邏輯關(guān)系聯(lián)結(jié)起來符號串稱為合式公式或命題公式。詳細(xì)地說,合式公式定義以下:(1)

單個命題變項是合式公式,稱為原子命題公式.(2)

若A是合式公式,則(┐A)也是合式公式.(3)

若A,B是合式公式,則(A∧B),(A∨B),(A→B),(A?B)也是合式公式.(4)

只有有限次地應(yīng)用(1)～(3)形成符號串才是合式公式.設(shè)A是合式公式,B是中一部分,若B是合式公式,則稱B為A子公式.比如:p,(p∨q)∨(┐r),(p→q)∧(q?r),(p∧q)∧┐r,p∧(q∨┐r)都是命題公式。說明：元語言與對象語言,外層括號能夠省去§1.2命題公式及其賦值19/309/13/202319DiscreteMath.,huangliujia定義1.7(1)若命題公式A是單個命題變項，則稱A為0層公式。(2)稱命題A是n+1(n≥0)層公式，只要A是以下情況之一：(a)A=┐B,B是n層公式;(b)A=B∧C,B,C分別為i層和j層公式，且max(i,j)=n。(c)A=B∨C,B,C分別為i層和j層公式，且max(i,j)=n。(d)A=B→C,B,C分別為i層和j層公式，且max(i,j)=n。(e)A=B?C,B,C分別為i層和j層公式，且max(i,j)=n。比如:(┐p∧q)→r,(┐(p→┐q))∧((r∨s)?┐p)分別為3層和4層公式。20/309/13/202320DiscreteMath.,huangliujia因為命題公式中含有命題變項，故其真值普通是不確定。當(dāng)公式中全部命題變項都解釋成詳細(xì)命題后，命題公式就成了真值確定命題了。比如，命題公式(p∨q)→r:則命題公式(p∨q)→r就被解釋成了一個真命題。若將p解釋成:2是素數(shù),q解釋成:3是偶數(shù),r解釋成：是無理數(shù)。則(p∨q)→r就被解釋成了一個假命題。另外，假如p,q解釋不變，而將r解釋成：是有理數(shù)，21/309/13/202321DiscreteMath.,huangliujia定義1.8設(shè)在命題公式A中出現(xiàn)全部命題變項為p1

,

p2,

…

pn

，給它們各指定一個真值，稱為對公式A一個賦值(或解釋)。若一個賦值使A真值為1，則稱該賦值為A成真賦值，不然稱為A成假賦值。注：設(shè)A中變項為p1

,

p2

,

…,

pn

，給A賦值a1

,

a2

,

…

an是指p1=a1,p2

=a2,…,pn=an，其中ai

為0或1,(i=1,2,…,n)。比如：公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，000(即p1

=0,p2

=0,

p3=0)和110都是而001(即p1=0,p2=0,p3=1)和011都是成真賦值；成假賦值。賦值22/309/13/202322DiscreteMath.,huangliujia

定義1.9將命題公式A在全部賦值下取值情況列成表，稱為A真值表。含n個命題變項公式共有2n個不一樣賦值。結(jié)構(gòu)真值表普通步驟以下：列出命題公式中全部命題變項p1,

p2,

…

pn，(無下標(biāo)時按字典序排列)。列出這些變項全部2n個賦值。普通從00…0開始，按二進(jìn)制加法依次列到11…1為止。(2)

按從低到高次序依次列出公式各個層。(3)對應(yīng)于變項2n個賦值分別計算出各層真值，直至算出公式真值。真值表23/309/13/202323DiscreteMath.,huangliujia例1.8

寫出以下公式真值表，并求它們成真、成假賦值。(1)(┐p∧q)→┐r;(2)(p∧┐p)?(q∧┐q);(3)┐(p→q)∧q∧rpqr┐p┐r┐p∧q(┐p∧q)→┐r解：

(┐p∧q)→┐r真值表

1111000000000101001110010111011110101010001100001110111124/309/13/202324DiscreteMath.,huangliujia(p∧┐p)?(q∧┐q)真值表pq┐p┐qp∧┐pq∧┐q(p∧┐p)?(q∧┐q)00011011┐(p→q)∧q∧r真值表pqrp→q┐(p→q)┐(p→q)∧q┐(p→q)∧q∧r000001010011100101110111111111001010000000001111001100001100000000000000000025/309/13/202325DiscreteMath.,huangliujia定義1.10設(shè)A是一個命題公式。若A在各種賦值下取值總為1，則稱A是永真式或重言式。(2)若A在各種賦值下取值總為0，則稱A是永假式或矛盾式。(3)若A不是矛盾式，則稱A為可滿足式。

注：A是可滿足式當(dāng)且僅當(dāng)A最少存在一個成真賦值。1.重言式必是可滿足式，但反之不真。2.可用真值表來判斷公式類型：若真值表最終一列全為1，則公式為重言式；(2)若真值表最終一列全為0，則公式為矛盾式；(3)若真值表最終一列最少有一個1，則公式為可滿足式。公式分類26/309/13/202326DiscreteMath.,huangliujia給定n個命題變項，使用聯(lián)結(jié)詞和括號，可組成無窮多個命題公式。

ｎ個命題變項共有2n

個可能賦值，而在每個賦值下公式只能取值０或1。所以含ｎ個命題變項公式其真值表只有22ｎ種可能情況。從而必有沒有窮多個公式含有相同真值表。27/309/13/202327DiscreteMath.,huangliujia例1.9以下公式中哪些含有相同真值表？(1)ｐ→ｑ；(2)ｐ?ｑ