離散數(shù)學(xué)命題與聯(lián)結(jié)詞

關(guān)于離散數(shù)學(xué)命題與聯(lián)結(jié)詞2第一章命題邏輯邏輯：研究推理，關(guān)注推理的正確性數(shù)學(xué)上，證明定理；計(jì)算機(jī)科學(xué)中，證明程序?qū)崿F(xiàn)了要求它完成的任務(wù)。邏輯重點(diǎn)研究命題之間的關(guān)系，而不是一個(gè)具體命題內(nèi)容在自然語(yǔ)言中的意義.第2頁(yè),共25頁(yè)，2024年2月25日，星期天3例如，軟工專業(yè)的學(xué)生都喜歡看宮廷劇《延禧攻略》.任何一個(gè)喜歡看《延禧攻略》的學(xué)生都是軟工1701班的.軟工專業(yè)的學(xué)生都是軟工1701班的.真真真從邏輯的角度從語(yǔ)義的角度假第3頁(yè),共25頁(yè)，2024年2月25日，星期天41.1命題與聯(lián)結(jié)詞1.2命題公式與賦值1.3等值演算1.4析取范式與合取范式1.5命題邏輯的推理理論本章內(nèi)容第4頁(yè),共25頁(yè)，2024年2月25日，星期天51.1命題與聯(lián)結(jié)詞命題與真值原子命題復(fù)合命題命題常項(xiàng)命題變項(xiàng)聯(lián)結(jié)詞第5頁(yè),共25頁(yè)，2024年2月25日，星期天6命題與真值命題:判斷結(jié)果惟一的陳述句.命題的真值:判斷的結(jié)果.真值的取值:真與假.真命題:真值為真的命題.假命題:真值為假的命題.

感嘆句、祈使句、疑問(wèn)句都不是命題！陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題！注意:

理發(fā)師悖論第6頁(yè),共25頁(yè)，2024年2月25日，星期天7理發(fā)師悖論：在某個(gè)城市中有一位理發(fā)師，他的廣告詞是這樣寫(xiě)的：“本人的理發(fā)技藝十分高超，譽(yù)滿全城。我將為本城所有不給自己刮臉的人刮臉，我也只給這些人刮臉。我對(duì)各位表示熱誠(chéng)歡迎！”來(lái)找他刮臉的人絡(luò)繹不絕，自然都是那些不給自己刮臉的人?？墒?，有一天，這位理發(fā)師從鏡子里看見(jiàn)自己的胡子長(zhǎng)了，他本能地抓起了剃刀，你們看他能不能給他自己刮臉呢？如果他不給自己刮臉，他就屬于“不給自己刮臉的人”，他就要給自己刮臉，而如果他給自己刮臉呢？他又屬于“給自己刮臉的人”，他就不該給自己刮臉。

第7頁(yè),共25頁(yè)，2024年2月25日，星期天8

例1.1下列句子中哪些是命題？

(1)是無(wú)理數(shù).(2)2+5＝8.(3)x+5＞3.(4)你有鉛筆嗎？

(5)這只兔子跑得真快呀！

(6)請(qǐng)不要講話！

(7)我正在說(shuō)謊話.真命題假命題真值不確定疑問(wèn)句感嘆句祈使句悖論(3)—(7)都不是命題第8頁(yè),共25頁(yè)，2024年2月25日，星期天9命題的分類簡(jiǎn)單命題(原子命題)：簡(jiǎn)單陳述句構(gòu)成的命題.

復(fù)合命題：由簡(jiǎn)單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題.第9頁(yè),共25頁(yè)，2024年2月25日，星期天10例如p

：是有理數(shù)，則p

的真值為

用小寫(xiě)英文字母p,q,r,…,pi,qi,ri(i≥1）表示簡(jiǎn)單命題，簡(jiǎn)單命題符號(hào)化用“1”表示真，用“0”表示假.1q

：2+5=7，則q

的真值為0第10頁(yè),共25頁(yè)，2024年2月25日，星期天11聯(lián)結(jié)詞與復(fù)合命題

1.否定式與否定聯(lián)結(jié)詞“

”定義設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作

p，符號(hào)

稱作否定聯(lián)結(jié)詞，并規(guī)定

p

為真當(dāng)且僅當(dāng)p為假.例如：p：10是素?cái)?shù)，則

p：10不是素?cái)?shù).第11頁(yè),共25頁(yè)，2024年2月25日，星期天122.合取式與合取聯(lián)結(jié)詞“∧”

定義設(shè)p,q為二命題,復(fù)合命題“p并且q

”(或“p與q

”)稱為p與q

的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞，并規(guī)定

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

q

同時(shí)為真.描述合取式的靈活性與多樣性，分清簡(jiǎn)單命題與復(fù)合命題.注意:第12頁(yè),共25頁(yè)，2024年2月25日，星期天13

例1.3將下列命題符號(hào)化.(1)丁楠既聰明又用功.(2)丁楠不僅聰明，而且用功.(3)丁楠雖然聰明，但不用功.(4)丁楠不是不聰明，而是不用功.(5)凌道恒與鞠奕明都是三好學(xué)生.(6)凌道恒與鞠奕明是同學(xué).解：令p

：丁楠聰明，q

：丁楠用功，則

(1)p∧q(2)

p∧q

(3)

p∧

q

(4)

()p∧(

q).第13頁(yè),共25頁(yè)，2024年2月25日，星期天14

例1.3(續(xù))

令r

:凌道恒是三好學(xué)生，s

:鞠奕明是三好學(xué)生(5)r∧s.(6)令t

:凌道恒與鞠奕明是同學(xué)，t

是簡(jiǎn)單命題.(1)—(5)說(shuō)明描述合取式的靈活性與多樣性.(6)中“與”聯(lián)結(jié)的是句子的主語(yǔ)成分，因而(6)中句子是簡(jiǎn)單命題.說(shuō)明第14頁(yè),共25頁(yè)，2024年2月25日，星期天15定義設(shè)p,q為二命題，復(fù)合命題“p或q”稱作p與q

的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假.例1.4

將下列命題符號(hào)化:(1)2或4是素?cái)?shù)；(2)2或3是素?cái)?shù)；(3)4或6是素?cái)?shù)；(4)小元元只能拿一個(gè)蘋(píng)果或一個(gè)梨；(5)王曉紅生于1989年或1990年.3.析取式與析取聯(lián)結(jié)詞“∨”第15頁(yè),共25頁(yè)，2024年2月25日，星期天16解：令p

:2是素?cái)?shù),q

:3是素?cái)?shù),

r:4是素?cái)?shù),

s

:6是素?cái)?shù),則(1),(2),(3)均為相容或.分別符號(hào)化為:p∨r,p∨q,r∨s,它們的真值分別為1,1,0.而(4),(5)為排斥或.令t

:小元元拿一個(gè)蘋(píng)果，u

:小元元拿一個(gè)梨，則(4)符號(hào)化為(t∧

u)∨(

t∧u).令v:王曉紅生于1989年,w:王曉紅生于1990年,則(5)既可符號(hào)化為(v∧

w)∨(

v∧w),又可符號(hào)化為v∨w,Why?第16頁(yè),共25頁(yè)，2024年2月25日，星期天17定義設(shè)p,q為二命題，復(fù)合命題“如果p,則q”稱作p與q的蘊(yùn)涵式，記作p

q，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件.

稱作蘊(yùn)涵聯(lián)結(jié)詞，并規(guī)定，p

q為假當(dāng)且僅當(dāng)p為真q為假.4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“

”第17頁(yè),共25頁(yè)，2024年2月25日，星期天18p

q

的邏輯關(guān)系：q

為p

的必要條件“如果

p，則

q”的不同表述法很多：

若p，就

q

只要

p，就

q

p

僅當(dāng)

q

只有

q

才p

除非

q,才

p

或除非

q,否則非

p，當(dāng)p為假時(shí)，p

q為真常出現(xiàn)的錯(cuò)誤：分不清充分條件與必要條件！第18頁(yè),共25頁(yè)，2024年2月25日，星期天19例1.5設(shè)p

:天冷，q

:小王穿羽絨服，將下列命題符號(hào)化(1)只要天冷，小王就穿羽絨服.(2)因?yàn)樘炖洌孕⊥醮┯鸾q服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時(shí)候.

注意：p

q

與

q

p

等值（真值相同）p

qp

q

q

pp

qq

p

q

p

p

qq

p第19頁(yè),共25頁(yè)，2024年2月25日，星期天20定義設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作p

q，

稱作等價(jià)聯(lián)結(jié)詞.并規(guī)定p

q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假.5.等價(jià)式與等價(jià)聯(lián)結(jié)詞“

”說(shuō)明:(1)p

q

的邏輯關(guān)系:p與q互為充分必要條件,(2)p

q為真當(dāng)且僅當(dāng)p與q同真或同假.第20頁(yè),共25頁(yè)，2024年2月25日，星期天21例1.6求下列復(fù)合命題的真值(1)2+2＝4當(dāng)且僅當(dāng)3+3＝6.(2)2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).(3)2+2＝4當(dāng)且僅當(dāng)太陽(yáng)從東方升起.(4)2+2＝4當(dāng)且僅當(dāng)美國(guó)位于非洲.(5)函數(shù)f(x)在x0可導(dǎo)的充要條件是它在x0連續(xù).10100第21頁(yè),共25頁(yè)，2024年2月25日，星期天22以上給出了5個(gè)聯(lián)結(jié)詞：

,

,

,

,

，組成一個(gè)聯(lián)結(jié)詞集合{

,

,

,

,

}，聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋?/p>

,

,

,

,;

如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無(wú)括號(hào)時(shí)，則按從左到右的順序運(yùn)算;若遇有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算.本書(shū)中使用的括號(hào)全為圓括號(hào).注意:①②③第22頁(yè),共25頁(yè)，2024年2月25日，星期天23邏輯聯(lián)結(jié)詞真值表小結(jié)第23頁(yè),共25頁(yè)，2024年2月25日，星期天24例1.7將下列命題符號(hào)化并求其真值.(1)如果3是合數(shù)，則4是素?cái)?shù)，并且如果4是素?cái)?shù)，則它不能被2整除；(2)如果當(dāng)且僅當(dāng)5是合數(shù)，則和都是有理數(shù).解:(1)設(shè)p:3是合數(shù)，