離散數(shù)學(xué)-第一章邏輯與證明

主講：檀曉紅上課形式、點(diǎn)播、 ，多種方式混合學(xué)習(xí)多用

、答疑中心、郵件溝通交流、

提問鍛煉和培養(yǎng)自主學(xué)習(xí)的能力，順利完成網(wǎng)絡(luò)教育的課業(yè)考核方式平時(shí)作業(yè)15%考勤15%期末考試（閉卷）70%2內(nèi)容：

離散數(shù)學(xué)預(yù)備知識(shí)：

數(shù)學(xué)計(jì)算機(jī)34邏輯、證明、數(shù)學(xué)歸納法集合、函數(shù)、數(shù)列計(jì)數(shù)、鴿巢原理、排列組合高級(jí)計(jì)數(shù)問題：遞推關(guān)系、容斥原理關(guān)系、等價(jià)關(guān)系圖，哈米爾頓回路，歐拉回路，平面圖樹，樹的遍歷、最小生成樹邏輯研究

推理關(guān)注

推理過程是否正確研究

命題之間的聯(lián)系6邏輯（logic）是研究推理的，關(guān)注推理的正確性，重點(diǎn)研究命題之間的關(guān)系，而不是一個(gè)具體命題的內(nèi)容?？紤]下面的論斷：所有的數(shù)學(xué)家都穿涼鞋。任何一個(gè)穿涼鞋的人都是代數(shù)學(xué)家。因此，所有的數(shù)學(xué)家都是代數(shù)學(xué)家。邏輯并不能幫助確定這些命題是否為真；然而，如果前兩個(gè)命題為真，邏輯可以保證命題所有的數(shù)學(xué)家都是代數(shù)學(xué)家。也為真。邏輯在數(shù)學(xué)上一般用來證明定理，在計(jì)算機(jī)科學(xué)中一般用來證明程序?qū)崿F(xiàn)了要求它完成的任務(wù)。本章將

采用邏輯方法來證明邏輯命題，這種邏輯命題可能是形式化的或非形式化的，但卻是必不可少的。7命題是一個(gè)陳述句，或真或假，不可以既真又假。命題是邏輯的基本構(gòu)成單元下列句子(a)

~(e)哪個(gè)為真，哪個(gè)為假（不能既真又假）能整除7

的正整數(shù)只有1

和7

本身。多倫多是

的首都。對(duì)于每個(gè)正整數(shù)n，存在一個(gè)大于n

的素?cái)?shù)。地球是宇宙中惟一存在生命的星球。買兩張星期五去“大劇院”音樂會(huì)的票。(a)真

(b)假

(c)真(d)不知真假，但一定是非真即假。因此是命題(e)不是命題89用變量來表示命題（如p、q

和r）。p:1+1=3定義p

是命題1+1=3。p

pTFFTp為一個(gè)命題，則p的否定表示為p，是命題not

p?

p

寫做“p

的說法是不正確的”。如：p：巴黎是英國的首都?

p：巴黎是英國的首都的說法是不正確的簡言之：?

p：巴黎不是英國的首都11兩個(gè)連接命題的連接詞：“與”（and）“或”（or）定義2:

p,

q

的合取表示成

p∧q即“p

and

q”“p并且q”定義3：

p,

q的析取表示成

p∨q即“p or

q”,

“

p或q”12復(fù)合命題的真值可以由真值表來表達(dá)。用T

代表真，F(xiàn)

代表假。復(fù)合命題p∧q，p

∨q的真值由下列真值表pqp∧qTTTTFFFTFFFFpqp

∨

qTTTTFTFTTFFF13p∧q:p∨q:天正在下雨并且天很冷天正在下雨或者天很冷例如：命題“天正在下雨”與“天很冷”可以連接成單一命題形式“天正在下雨與天很冷”?！芭c”和“或”的形式化定義。p:天正在下雨 q:

天很冷p:

3<5q:巴黎是英國的首府則p,q皆為假，析取p∨q表示：3<5或巴黎是英國的首府假題（如p

∨q）在一般的語言中，組合起來通常

的是有關(guān)聯(lián)的內(nèi)容，但在邏輯中并不關(guān)心每個(gè)命題的內(nèi)容是否相關(guān)，只關(guān)心命題真值之間的關(guān)系。1415定義4：異或p⊕q，當(dāng)p和q中只有一個(gè)為真時(shí)，命題為真，否則為假pqp

⊕qTTFTFTFTTFFF某參與競選的宣布：如果我當(dāng)選了，那么我將會(huì)減稅?！獥l件命題16定義4：如果p和q是命題，那么命題：

“若p則q”稱為條件命題，并表為p

→

q命題p稱為假設(shè)（或前提、前項(xiàng)）命題q稱為結(jié)論（或推論）條件語句又稱“蘊(yùn)含”p：如果我當(dāng)選了q：我將減稅假設(shè)是“這位結(jié)論是“這位當(dāng)選了”，會(huì)減稅”。17如何確定命題的真值？先假設(shè)“這位若他減稅，當(dāng)選了”：題顯然為真。（p

→q

為真）反之，他沒有減稅，則

題為假。（p

→q

為假。）再假設(shè)“這位

沒有當(dāng)選”：減了或沒減，此時(shí)與題為

結(jié)論。這時(shí)能得出當(dāng)這位沒有當(dāng)選時(shí)，無論無關(guān)，當(dāng)然也不怎樣，

的命題都為真。1819條件命題的真值表pqp

→

qTTTTFFFTTFFT：“如果今天天晴，那么去海灘”時(shí)，這個(gè)只有

天天晴，而我們不去海灘命題為假，否則上述命題成立。：“如果今天是星期五，那么2+3=5”該命題總是成立，因?yàn)?+3=5總是為真“如果今天是星期五，那么2+3=6”該命題 天不是星期五 時(shí)，成立20一下命題：對(duì)于所有的實(shí)數(shù)x，若x>0，則x2

>0

為真。令p

：x

>0，令q

：x2>0?，F(xiàn)在考慮當(dāng)p

為

情況。若x

=-2，則p

為假，但q

為真。為了在這種情況下使命題為真，必須把p

→q在p

為假且q

為真時(shí)定義為真。若x=0，則p和q

都為假。為了在這種情況下使命題為真，必須把p→q

在p和q

都為假時(shí)定義為真。2122條件命題：p

→

q逆：

q→

p反（否）：

p

→

q倒置（逆否）：

q

→

p例：命題“每當(dāng)下雨時(shí)，主隊(duì)就能獲勝”原命題p

→

q：如果下雨，那么主隊(duì)就能獲勝逆q

→

p

：如果主隊(duì)獲勝，那么下雨了倒置

q→

p：如果主隊(duì)沒有獲勝，那么沒有下雨反

p

→

q

：如果沒有下雨，那么主隊(duì)沒有獲勝23優(yōu)先級(jí):

(

)

假設(shè)：p真q假r真，給出下面每個(gè)命題的真值(p

q)

r(p

q)

rp

(q

r)p

(q

r)24構(gòu)造真值表

(p

q)

(p

q)pq

qp

qp

q(p

q)

(p

q)TTFTTTTFTTFFFTFFFTFFTTFF新生，才可以從校園網(wǎng)訪“只有你主修計(jì)算機(jī)科學(xué)問因特網(wǎng)”設(shè)：a:你可以從校園網(wǎng)c:你主修計(jì)算機(jī)科學(xué)因特網(wǎng)f:你是個(gè)新生問題：該語句的等價(jià)說法（

）：A“如果你主修計(jì)算機(jī)科學(xué)，或者你不是新生，那么你可以從校園網(wǎng) 因特網(wǎng)”B“如果你可以從校園網(wǎng) 因特網(wǎng)，那么你主修了計(jì)算機(jī)科學(xué)，或者你不是新生”所以，形式化表示為：

a

(c

f)25（a）如果Mary努力學(xué)習(xí)，她將成為一名好學(xué)生。僅當(dāng)John是大二、大三或大四的學(xué)生時(shí)，他才學(xué)習(xí)微積分。你一唱歌，

耳朵就難受。Cubs獲得世界職業(yè)棒球大賽冠軍的必要條件是他們有一個(gè)右手的替補(bǔ)投手。Maria

法國的充分條件是Maria

到達(dá)了埃菲爾鐵塔。2627僅當(dāng)John

是大二、大三或大四的學(xué)生時(shí)，他才學(xué)習(xí)微積分(b)這個(gè)句子的意思是如果John

要學(xué)習(xí)微積分，則他必須是大二、大三或大四的學(xué)生。如果他是大一的學(xué)生，則不能學(xué)習(xí)微積分。所以，如果John學(xué)習(xí)微積分，那么他一定是大二、大三或大四的學(xué)生。這個(gè)句子等價(jià)于如果John學(xué)習(xí)微積分，則他是大二、大三或大四的學(xué)生。而不等價(jià)于如果John是大二、大三或大四的學(xué)生，則他學(xué)習(xí)微積分。如果John

是大二、大三或大四的學(xué)生，他可能學(xué)習(xí)微積分，也可能不學(xué)習(xí)微積分。（具有學(xué)習(xí)微積分的條件，但可能不打算學(xué)。）“如果p，則q”強(qiáng)調(diào)前提，“p

僅當(dāng)q”強(qiáng)調(diào)結(jié)論，兩者只有形式上的區(qū)別。28(d)Cubs獲得世界職業(yè)棒球大賽冠軍的必要條件是他們有一個(gè)右手的替補(bǔ)投手。注意：必要條件成立時(shí)并不確保結(jié)果成立；但是，若必要條件不成立，則結(jié)果一定不成立。上面的句子的含義為：如果Cubs獲得世界職業(yè)棒球大賽的冠軍，可以肯定他們有一個(gè)右手的替補(bǔ)投手，因?yàn)槿绻麤]有這個(gè)投手，則他們不可能獲得世界職業(yè)棒球大賽的冠軍。所以這個(gè)句子的等價(jià)形式為如果Cubs

獲得世界職業(yè)棒球大賽的冠軍，則他們有一個(gè)右手的替補(bǔ)投手。注意如果Cubs

他們有一個(gè)右手的替補(bǔ)投手，則他們獲得世界職業(yè)棒球大賽的冠軍。不是這個(gè)句子的等價(jià)形式。有一個(gè)右手的替補(bǔ)投手并不能保證他們獲得世界職業(yè)棒球大賽的冠軍。然而，如果沒有一個(gè)右手的替補(bǔ)投手，則他們肯定不能獲得世界職業(yè)棒球大賽的冠軍。如果充分條件不成立，則結(jié)果可能成立也可能不成立；但如果條件成立，則可以保證結(jié)果成立。在

Maria

法國的充分條件是Maria到達(dá)了埃菲爾塔。中，如果Maria

到達(dá)了埃菲爾鐵塔，則保證一定到了法國。（當(dāng)然，通過其他方法也可以

法國，比如去里昂。）于是，上面的句子的等價(jià)形式為如果Maria

到達(dá)了埃菲爾鐵塔，則Maria

了法國。注意如果Maria

法國，則Maria

到達(dá)了埃菲爾鐵塔。不是上面的句子的等價(jià)形式。前面已經(jīng)提到過，不去埃菲爾鐵塔，到達(dá)其他地方也可以 法國。29例：當(dāng)文件系統(tǒng)滿時(shí)，自動(dòng)應(yīng)答不能夠發(fā)出p:自動(dòng)應(yīng)答系統(tǒng)能夠發(fā)出q:文件系統(tǒng)滿了p:自動(dòng)應(yīng)答系統(tǒng)不能夠發(fā)出規(guī)范說明表示為：q

p系統(tǒng)規(guī)范說明應(yīng)該一致，無 的需求30確定下列系統(tǒng)規(guī)范說明是否一致消息 在緩沖區(qū)中或者被重傳消息沒有緩存在緩沖區(qū)中消息被重傳如果

消息

在緩沖區(qū)中，那么它被重傳解：p:

消息 在緩沖區(qū)中q:p

qpp

q一致的。pq

pp

qp

qTTFTTTFFTFFTTTTFFTFT大多數(shù)網(wǎng)上搜索引擎支持布爾檢索技術(shù)，以找到有關(guān)特定 的網(wǎng)頁例：用布爾檢索找出關(guān)于新墨西哥州(NewMexico)各大學(xué)的網(wǎng)頁New

and

Mexico

and

University找出與新墨西哥州或亞利桑那州的大學(xué)有關(guān)網(wǎng)頁(New

and

Mexico

Or

Arizona)

and

University找出有關(guān)墨西哥的大學(xué)的網(wǎng)頁(Mexico

and

University)

Not

New32一個(gè)島上居住著兩類人——騎士和 。騎士說的都是真話，而 總是說謊?，F(xiàn)在碰到了島上的兩個(gè)人A和B，如果A說“B是騎士”，B說“我們兩人不是一類人”。請判斷A、B的

。解：每個(gè)人要么是騎士，要么是

。假設(shè)A是騎士，那么他說的是真話，即B也是騎士，那么B應(yīng)當(dāng)說真話，但B所說并非如此，所以A不是騎士假設(shè)A是 ，那么他說的是謊話，則B也是 ，那么B也應(yīng)當(dāng)說謊話，與題目所給的條件一致。所以A和B都是

。331.

條件命題？條件命題如何表示？2.給出條件命題的真值表。3.在條件命題中，4.在條件命題中，前提？結(jié)論？.必要條件？充分條件？p

→q

的逆命題？雙條件命題？9.P

和Q

邏輯等價(jià)的含義是什么？10.

p

→q

的逆否命題？34Joey將通過離散數(shù)學(xué)考試,如果他學(xué)習(xí)努力。Rosa可以畢業(yè),如果她獲得160學(xué)分。Fernando

一臺(tái)計(jì)算機(jī)的必要條件是他得到2000美圓。Katrina選修算法課的充分條件是她學(xué)過離散數(shù)學(xué)。當(dāng)可以制造出更好的汽車時(shí)，Buick會(huì)制造它們。當(dāng)

講

，聽眾會(huì)睡覺。僅當(dāng)程序具有良好的結(jié)構(gòu)，才是可讀的。1.

如果Joey學(xué)習(xí)努力，則他將通過離散數(shù)學(xué)考試。4.

如果Katrina通過離散數(shù)學(xué)考試，則她將修算法課。7.

如果程序是可讀的，則它具有良好的結(jié)構(gòu)。8.

（對(duì)于練

）如果Joey通過離散數(shù)學(xué)考試，則他學(xué)習(xí)努力。351.

如果Joey學(xué)習(xí)努力，則他將通過離散數(shù)學(xué)考試。２.如Rosa

獲得160學(xué)分，她可以畢業(yè)。３、如果Fernando

了一臺(tái)計(jì)算機(jī)，那么他一定得到了2000美圓4.

如果Katrina通過離散數(shù)學(xué)考試，則她將修算法課。５、如果可以制造出更好的汽車，Buick會(huì)去制造的６、如果 講課，聽眾會(huì)睡覺7.

如果程序是可讀的，則它具有良好的結(jié)構(gòu)。8.

（對(duì)于練

）如果Joey通過離散數(shù)學(xué)考試，則他學(xué)習(xí)努力。36定義1復(fù)合命題的永真式（重言式）：無論其中題的真值是什么，該復(fù)合命題的真值總是真。：真值

是

復(fù)合命題?？赡苁剑杭炔挥勒嬗植?/p>

題例：p

pp

pp

∧pTFTFFTTF3738pq

（p∨q）p∧qTTFFTFFFFTFFFFTT任何情況下都有相同真值的兩個(gè)復(fù)合命題稱為邏輯等價(jià)定義：如果p?q是永真式，那么命題p，q是邏輯等價(jià)，記為p

≡q判斷方法之一：真值表德摩根定律（p∨q）≡

p∧

q（p∧q）≡

p

∨

qpqp

q(p

q

)(q

p)p

pTTTTTTTFFFTFFTFTFFFFTTTT3940證明命題:

p∨(q

∧

r)與

(p∨q)

∧(p∨r)

等價(jià)pqrq

∧

rp∨(q

∧

r)p∨qp∨r(p∨q)

∧(p∨r)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTTFTFFFTFFFFTFFFTTFFFFFFFF41證明:?

(p

→q)≡p∧?

q解：?

(p

→q)≡?

(?

p∨q)≡

?

(?

p)

∧

?

q≡p∧

?

q證明:(p

∧q)→(p

∨q)永真證明：?

(p

∨

(?

p

∧

q)

)≡

?

p∧

?

q證明:?

(p

→q)≡p

∧?

q證：通過寫出P

=?

(p

→q)和Q=p∧?

q的真值表來驗(yàn)證對(duì)于任意給定的p

和q的真值，或者P

和Q都為真，或者P

和Q都為假。42用德摩根律表達(dá)“麥克有一部 和一臺(tái)電腦”的否定解：p麥克有一部

，q麥克有一臺(tái)電腦那么原命題表示為：p

∧q則其否定（p∧q）等價(jià)于

p

∨

q即：“麥克沒有一部

或沒有一臺(tái)電腦”用德摩根律表達(dá)“John或者Jessi將去看 ”的否定解：p:John去看

，q：Jessi去看那么原命題表示為：p∨q則其否定（p

∨q）等價(jià)于

p

∧

q即：“John和Jessi都不去看

”4344句子p:n是一個(gè)奇數(shù)p

不是一個(gè)命題句子p

不是命題，因?yàn)閜

的真假取決于n

的值。例如，當(dāng)n

=103

時(shí)p

為真，當(dāng)n

=8

時(shí)p

為假。因?yàn)閿?shù)學(xué)和計(jì)算機(jī)科學(xué)中的多數(shù)句子使用變元，所以必須擴(kuò)展邏輯系統(tǒng)使之包括這樣的句子?！^詞邏輯含變量的語句：x

>3，即“x

大于3”主語

謂詞令P(x)表示x

>3，其中P表示謂詞“大于3”,x是變量命題函數(shù)P

(x)，表示P在x的值。如：令p(x)表示x

>3，則p(4),p(2)的真值分別為T和F如：Q(x,y)表示語句“x=y+3”,則Q(1,2)和Q(3,0)的真值是什么？4546P(n)

：n

是一個(gè)奇數(shù)D

正整數(shù)集合P

是一個(gè)命題函數(shù)例如，如果n

=1，得到命題P(1):１是一個(gè)奇數(shù)（命題為真）。如果n

=2，得到命題P(2):2

是一個(gè)奇數(shù)（命題為假）。47命題函數(shù)P本身既不為真也不為假。然而，對(duì)于命題論域中的每一個(gè)x，P(x)是一個(gè)命題，所以它或者為真或者為假。可以把命題函數(shù)當(dāng)成一個(gè)命題類，論域中的每個(gè)元素對(duì)應(yīng)一個(gè)命題。例如，如果P是一個(gè)命題函數(shù)，其論域是正整數(shù)集合，便得到命題類P(1),

P(2),...每個(gè)P(1),P(2),...或者為真，或者為假。下面所述的都是命題函數(shù)。n2+2n是奇數(shù)（

域是正整數(shù)集合）A(c,n)：計(jì)算機(jī)c被連接到網(wǎng)絡(luò)nA(x):

計(jì)算機(jī)x正被一個(gè)

者命題函數(shù)，本身既不為真，也不為假，而對(duì)于每個(gè)

x,

p(x)是一個(gè)命題4849量化：謂詞在一定范圍內(nèi)的取值謂詞演算：處理謂詞和量詞的邏輯領(lǐng)域全稱量詞：P(x)的全稱量化表示語句“P(x)對(duì)x在其論域中的所有值都為真”存在量詞：P(x)的存在量化表示語句“論域中至少有一個(gè)值滿足P(x)為真”量詞命題何時(shí)為真何時(shí)為假全稱量詞??xP(x)對(duì)每一個(gè)x，P(x)都為真有一個(gè)x，使得P(x)為假存在量詞??xP(x)有一個(gè)x，使得P(x)為真對(duì)每一個(gè)x，P(x)為假對(duì)于全稱量詞語句

x

(x2

≥

0)論域是實(shí)數(shù)集合。這個(gè)句子為真。對(duì)于全稱量詞語句

x

(x2

-

1

>0)論域是實(shí)數(shù)集合。這個(gè)句子為假，因?yàn)楫?dāng)x

=1

時(shí)，命題12

-

1>

0為假。所以1

是語句

x(x2

-

1

>

0)

的一個(gè)反例。雖然x取某些值時(shí)命題函數(shù)為真，但一個(gè)反例就可以使全稱量詞語句為假。51例：P(x)表示語句“x2＞0”，論域?yàn)椴怀^4的真整數(shù)，?xP(x)的真值是什么？解：論域?yàn)閧1，2，3，4}，P(1),P(2),P(3)為真。52唯一量詞??。捍嬖谖ㄒ坏膞使?x

P(x)為真53x<0

(x2>0)y≠0

(y3

≠

0)x(x<0

→x2>0)y(y≠0

→y3

≠

0)全稱量詞的約束等價(jià)于一個(gè)條件語句的全稱量化?z>0

(z2=2)

?z(z>0

∧(z2=2)存在量詞的約束等價(jià)于一個(gè)合取的存在量化54量詞比所有命題演算的邏輯運(yùn)算符的優(yōu)先級(jí)高如語句xP(x)

∨

Q(x)等價(jià)于（

A

）？A.

(xP(x))

∨

Q(x)B.

(xP(x)

∨

Q(x))綁定&當(dāng)量詞作用于變量x時(shí)，x是綁定的沒有被量詞綁定的變量是

的例：?x(x+y=1)其中x

是綁定變量，y是 變量5556考慮語句的否定：“班里每個(gè)學(xué)生都學(xué)過微積分”即xP(x)其中P(x)：x學(xué)過離散數(shù)學(xué)其否定：“并非班里每個(gè)學(xué)生都學(xué)過微積分”也就是：“班里有學(xué)生沒有學(xué)過微積分”，即?

xP(x)等價(jià)關(guān)系：xP(x)

≡?

xP(x)57再考慮“班里有個(gè)學(xué)生學(xué)過離散數(shù)學(xué)”即?xP(x)其中P(x)：x學(xué)過離散數(shù)學(xué)否定：“并非班里有學(xué)生學(xué)過微積分”也就是：“班里沒有學(xué)生學(xué)過微積分”即“班里每個(gè)學(xué)生都沒有學(xué)過微積分”P(x)：x學(xué)過離散數(shù)學(xué)x

P(x)等價(jià)關(guān)系：

?

xP(x)

≡

x

P(x)量詞否定的規(guī)則：量詞的德摩根定律否定等價(jià)語句何時(shí)為真何時(shí)為假

?

xP(x)?xP(x)對(duì)每個(gè)x，P(x)都為假有x，使得P(x)為真?xP(x)?xP(x)有x，使得P(x)為假對(duì)每一個(gè)x，P(x)為真例：“有的

誠實(shí)”的否定是：解：H(x):x是誠實(shí)的，?xH(x)，則

?xH(x)≡?xH(x)表示：每個(gè)都不誠實(shí)。例：“所有 人都吃干酪漢堡包”的否定：解：設(shè)C(x):

x吃干酪漢堡包，

?xC(x)?xC(x)

≡

?

xC(x),

即：有些

人不吃。。。5859用謂詞和量詞表達(dá)：“這個(gè)班上某個(gè)學(xué)生去過墨西哥”引入量詞x,表示某個(gè)學(xué)生x，論域是這個(gè)班級(jí)引入謂詞M(x)，表示x

去過墨西哥（1）

x

M(x)引入變量x，表示某個(gè)人x,論域是所有人引入謂詞S(x)，表示x是這個(gè)班上的一個(gè)學(xué)生則：x(S(x)∧M(x))表示某個(gè)人，他是這個(gè)班級(jí)的學(xué)生，并且他去過墨西哥，或者去過用謂詞和量詞表示“這個(gè)班上每個(gè)學(xué)生或者去過墨西哥”C(x)表示x去過

，M(x)表示x去過墨西哥（1）如果x的論域是這個(gè)班級(jí)的學(xué)生，則表示為：x

(C(x)∨M(x))（2）如果x的論域是所有人則表示為：x

(S(x)

(C(x)∨M(x))表示語句“對(duì)于每一個(gè)人，如果他是這個(gè)班級(jí)的學(xué)生，那么他去過

或去過墨西哥”6061用謂詞與量詞表達(dá)系統(tǒng)說明：每封大于1MB的郵件將被壓縮令S(m,y)表示“郵件m大于yMB”C(m)表示“郵件m被壓縮”其中m的論域是所有郵件，y的論域是正實(shí)數(shù)則：：x(S(m,1)

C(m))62如果用戶處于活動(dòng)狀態(tài)，那么至少有一個(gè)網(wǎng)絡(luò)連接有效令A(yù)(u)表示“用戶u處于活動(dòng)狀態(tài)”，u的論域是所有用戶S(n,x)表示“網(wǎng)絡(luò)連接n處于x狀態(tài)其中n的論域時(shí)所有的網(wǎng)絡(luò)連接，x的論域是（available,

unavailable）u

A(u)

n

S(n,

available)63論證：前幾句是前提，最后一句是結(jié)論。例：“所有獅子都是兇猛的”“有些獅子不喝咖啡”“有些兇猛的動(dòng)物不喝咖啡”引入量詞x,表示所有動(dòng)物引入謂詞P(x)——“x是獅子”Q(x)——“x是兇猛的”R(x)——“x喝咖啡”則這些語句可以表示為右表的形式：x(

P(x)

Q(x))x

(

P(x)

∧

R(x))x

(Q(x)

∧

R(x))64例：“所有蜂鳥都是五彩斑斕的”“沒有大鳥以蜜為生”“不以蜜為生的鳥都色彩單調(diào)”“蜂鳥是小鳥”引入量詞x,表示所有鳥的集合引入謂詞：P(x)：x是只蜂鳥Q(x)：x是大的

R(x)：x以蜜為生

S(x):x是五彩斑斕的則這些語句可以表示為：x(

P(x)

S(x))

x(Q(x)

∧

R(x))x(

R(x)

S(x))x(

P(x)

Q(x)).5.命題函數(shù)？論域？全稱量詞語句？反例？存在量詞語句？敘述一般化的De

Morgan

邏輯定律。解釋如何證明全稱量詞語句為真。解釋如何證明存在量詞語句為真。解釋如何證明全稱量詞語句為假。解釋如何證明存在量詞語句為假。6566考慮用符號(hào)表示句子任意兩個(gè)正實(shí)數(shù)的和為正。如果要表示這個(gè)句子，首先需要為這兩個(gè)正實(shí)數(shù)分別選擇一個(gè)變量，記做x

和y。這個(gè)句子可以寫做：如果x

>0

與y

>0，則x

+y

>0。句子中提到任意的兩個(gè)正實(shí)數(shù)的和都是正數(shù)，所以需要兩個(gè)全稱量詞。xy((x

>

0)∧(y

>

0)→(x

+

y>

0))67例：P(x,y):“x+y=y+x”,量化語句：xyP(x,y)

與yxP(x,y)的真值都為真例：Q(x,y)：“x+y=0”

yx

P(x,y)表示“有個(gè)實(shí)數(shù)y，對(duì)任意實(shí)數(shù)x，