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

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

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

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

第7頁，共25頁，2022年，5月20日，14點52分，星期五8

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

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

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

(6)請不要講話！

(7)我正在說謊話.真命題假命題真值不確定疑問句感嘆句祈使句悖論(3)—(7)都不是命題第8頁，共25頁，2022年，5月20日，14點52分，星期五9命題的分類簡單命題(原子命題)：簡單陳述句構(gòu)成的命題.

復(fù)合命題：由簡單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題.第9頁，共25頁，2022年，5月20日，14點52分，星期五10例如p

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

的真值為

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

：2+5=7，則q

的真值為0第10頁，共25頁，2022年，5月20日，14點52分，星期五11聯(lián)結(jié)詞與復(fù)合命題

1.否定式與否定聯(lián)結(jié)詞“”定義設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作p，符號稱作否定聯(lián)結(jié)詞，并規(guī)定p

為真當(dāng)且僅當(dāng)p為假.例如：p：10是素數(shù)，則p：10不是素數(shù).第11頁，共25頁，2022年，5月20日，14點52分，星期五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

同時為真.描述合取式的靈活性與多樣性，分清簡單命題與復(fù)合命題.注意:第12頁，共25頁，2022年，5月20日，14點52分，星期五13

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

：丁楠聰明，q

：丁楠用功，則

(1)p∧q(2)

p∧q

(3)

p∧q

(4)

()p∧(q).第13頁，共25頁，2022年，5月20日，14點52分，星期五14

例1.3(續(xù))

令r

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

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

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

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

的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時為假.例1.4將下列命題符號化:(1)2或4是素數(shù)；(2)2或3是素數(shù)；(3)4或6是素數(shù)；(4)小元元只能拿一個蘋果或一個梨；(5)王曉紅生于1989年或1990年.3.析取式與析取聯(lián)結(jié)詞“∨”第15頁，共25頁，2022年，5月20日，14點52分，星期五16解：令p

:2是素數(shù),q

:3是素數(shù),

r:4是素數(shù),

s

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

:小元元拿一個蘋果，u

:小元元拿一個梨，則(4)符號化為(t∧u)∨(t∧u).令v:王曉紅生于1989年,w:王曉紅生于1990年,則(5)既可符號化為(v∧w)∨(v∧w),又可符號化為v∨w,Why?第16頁，共25頁，2022年，5月20日，14點52分，星期五17定義設(shè)p,q為二命題，復(fù)合命題“如果p,則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件.稱作蘊涵聯(lián)結(jié)詞，并規(guī)定，pq為假當(dāng)且僅當(dāng)p為真q為假.4.蘊涵式與蘊涵聯(lián)結(jié)詞“”第17頁，共25頁，2022年，5月20日，14點52分，星期五18pq

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

為p

的必要條件“如果

p，則

q”的不同表述法很多：

若p，就

q

只要

p，就

q

p

僅當(dāng)

q

只有

q

才p

除非

q,才

p

或除非

q,否則非

p，當(dāng)p為假時，pq為真常出現(xiàn)的錯誤：分不清充分條件與必要條件！第18頁，共25頁，2022年，5月20日，14點52分，星期五19例1.5設(shè)p

:天冷，q

:小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.

注意：pq

與qp

等值（真值相同）pqpqqppqqp

qppqqp第19頁，共25頁，2022年，5月20日，14點52分，星期五20定義設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結(jié)詞.并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時為真或同時為假.5.等價式與等價聯(lián)結(jié)詞“”說明:(1)pq

的邏輯關(guān)系:p與q互為充分必要條件,(2)pq為真當(dāng)且僅當(dāng)p與q同真或同假.第20頁，共25頁，2022年，5月20日，14點52分，星期五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)太陽從東方升起.(4)2+2＝4當(dāng)且僅當(dāng)美國位于非洲.(5)函數(shù)f(x)在x0可導(dǎo)的充要條件是它在x0連續(xù).10100第21頁，共25頁，2022年，5月20日，14點52分，星期五22以上給出了5個聯(lián)結(jié)詞：,,,,，組成一個聯(lián)結(jié)詞集合{,,,,}，聯(lián)結(jié)詞的優(yōu)先順序為：,,,,;

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