離散數(shù)學(xué)第一張講義

1、1,2,主要內(nèi)容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理,第一部分 數(shù)理邏輯,3,第一章 命題邏輯的基本概念,主要內(nèi)容命題與聯(lián)結(jié)詞 命題及其分類 聯(lián)結(jié)詞與復(fù)合命題命題公式及其賦值,4,命題與真值 數(shù)理邏輯是研究推理的數(shù)學(xué)分支，推理由一系列的陳述句組成 命題：判斷結(jié)果惟一（非真即假）的陳述句 命題的真值：判斷的結(jié)果 真值的取值：真與假 真命

2、題（真值為真的命題）與假命題（真值為假的命題）,1.1 命題與聯(lián)結(jié)詞,注意：感嘆句、祈使句、疑問(wèn)句都不是命題陳述句中的悖論，判斷結(jié)果不惟一確定的不是命題判定給定句子是否為命題，分兩步：首先判定它是否為陳述句，其次判斷它是否有唯一的真值,5,6,例1 下列句子中那些是命題？ (1) 是有理數(shù). (2) 2 + 5 = 7. (3) x + 5 > 3. (4) 你去教室嗎？ (5) 這個(gè)蘋果真大呀

3、！ (6) 請(qǐng)不要講話！ (7) 2050年元旦下大雪. (8) 我正在說(shuō)假話,假命題,命題概念,真命題,不是命題,不是命題,不是命題,不是命題,命題，但真值現(xiàn)在不知道,悖論，不是命題,7,命題分類：簡(jiǎn)單命題（不能被分解成更簡(jiǎn)單的命題稱作簡(jiǎn)單命題，也稱原子命題）與復(fù)合命題（由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的命題，稱作復(fù)合命題）簡(jiǎn)單命題符號(hào)化用小寫英文字母 p, q, r, …, pi, qi, ri (i?1)表示簡(jiǎn)單命題用”

4、1”表示真，用”0”表示假 例如，令 p： 是有理數(shù)，則 p 的真值為0， q：2 + 5 = 7，則 q 的真值為1,命題分類,,例1.2 先將下面各個(gè)陳述句中出現(xiàn)的原子命題符號(hào)化，并指出它們的真值，然后再寫出這些陳述1） 是有理數(shù)是不對(duì)的2）2是偶素?cái)?shù)3）2或4是素?cái)?shù)4）如果2是素?cái)?shù)，則3也是素?cái)?shù)5）2是素?cái)?shù)當(dāng)且僅當(dāng)3 也是素?cái)?shù)原子命題：p: 是有理數(shù) q

5、：2是素?cái)?shù) r: 2是偶數(shù) s: 3是素?cái)?shù) t: 4是素?cái)?shù),8,9,否定、合取、析取聯(lián)結(jié)詞,定義1.3 設(shè)p, q為兩個(gè)命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞. 規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假.,定義1.1 設(shè) p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作?p，符號(hào)?稱作否定聯(lián)結(jié)詞. 規(guī)定?p 為真當(dāng)且僅當(dāng)p為假.,定義1.2 設(shè)p,q為兩

6、個(gè)命題，復(fù)合命題“p并且q”(或“p與 q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞. 規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真.,10,例2 將下列命題符號(hào)化. (1) 吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明. (3) 吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學(xué).,合取聯(lián)結(jié)詞的實(shí)例,11,解 令p:吳穎用功, q:吳穎聰明 (1) p?q (2) p?

7、q (3) ?p?q (4) 設(shè)p:張輝是三好生, q:王麗是三好生 p?q (5) p:張輝與王麗是同學(xué)(1)—(3) 說(shuō)明描述合取式的靈活性與多樣性(4)—(5) 要求分清 “與” 所聯(lián)結(jié)的成分,合取聯(lián)結(jié)詞的實(shí)例,12,例3 將下列命題符號(hào)化(1) 2 或 4 是素?cái)?shù).(2) 2 或 3 是素?cái)?shù).(3) 4 或 6 是素?cái)?shù).(4) 小元元只能拿一個(gè)蘋果或一個(gè)梨.(5) 王小紅生于 1975 年

8、或 1976 年.,析取聯(lián)結(jié)詞的實(shí)例,13,解 (1) 令p:2是素?cái)?shù), q:4是素?cái)?shù), p?q(2) 令p:2是素?cái)?shù), q:3是素?cái)?shù), p?q(3) 令p:4是素?cái)?shù), q:6是素?cái)?shù), p?q(4) 令p:小元元挑選 202房間, q:小元元挑選203房間 (p??q)?(?p?q)(5) p:王小紅生于 1975 年, q:王小紅生于1976 年, (p??q)?(?p?q

9、) 或 p?q(1)—(3) 為相容或, ?聯(lián)結(jié)的兩個(gè)命題可以同時(shí)為真(4)—(5) 為排斥或, 只有當(dāng)一個(gè)為真另一個(gè)為假時(shí)，才為真，符號(hào)化時(shí)(5)可有兩種形式，而(4)則不能,析取聯(lián)結(jié)詞的實(shí)例,14,定義1.4 設(shè)p, q為兩個(gè)命題，復(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為假.,蘊(yùn)涵聯(lián)結(jié)詞,(1) p?q 的

10、邏輯關(guān)系：q為 p 的必要條件(2) “如果 p, 則 q” 有很多不同的表述方法： 若p，就q 只要p，就q p僅當(dāng)q 只有q 才p 除非q, 才p 或 除非q，否則非p，…． (3) 當(dāng) p 為假時(shí)，p?q恒為真，稱為空證明 (4) 常出現(xiàn)的錯(cuò)誤：不分充分與必要條件,15,例4 設(shè) p：天冷，q：小王穿羽絨服，將下列命題符號(hào)化(1) 只要天冷，

11、小王就穿羽絨服.(2) 因?yàn)樘炖?，所以小王穿羽絨服.(3) 若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服僅當(dāng)天冷的時(shí)候.,蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例,p?q,注意： p?q 與 ?q??p 等值（真值相同）,p?q,p?q,q?p,q?p,p?q,q?p,q?p,16,定義1.5 設(shè) p

12、, q為兩個(gè)命題，復(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í)為假.p?q 的邏輯關(guān)系：p與q互為充分必要條件,等價(jià)聯(lián)結(jié)詞,例5 求下列復(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) 美

13、國(guó)位于非洲.(5) 是無(wú)理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲,1,0,0,1,0,,例1.7 令 p：北京比天津人口多 q：2+2=4 r：烏鴉是白色的求下列復(fù)合命題的真值(1) ((?p ?q) ?(p ? ?q)) ?r (q ?r) ?(p ? ?r) (?p ?r) ?(p ? ?r),1

14、7,18,本小節(jié)中p, q, r, … 均表示命題.,聯(lián)結(jié)詞集為{?, ?, ?, ?, ?}，?p, p?q, p?q, p?q, p?q為基本復(fù)合命題. 其中要特別注意理解p?q的涵義. 反復(fù)使用{?, ?, ?, ?, ?}中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.設(shè) p: 是無(wú)理數(shù)，q: 3是奇數(shù)， r: 蘋果是方的， s: 太陽(yáng)繞地球轉(zhuǎn) 則復(fù)合命題 (p?q) ? ((r??s) ??p) 是

15、假命題.,小　結(jié),聯(lián)結(jié)詞的運(yùn)算順序: ( ), ?, ?, ?, ?, ?, 同級(jí)按先出現(xiàn)者先運(yùn)算.,19,1.2 命題公式及其賦值,命題變項(xiàng)與合式公式命題變項(xiàng)合式公式合式公式的層次公式的賦值公式賦值公式類型真值表,20,命題變項(xiàng)與合式公式,命題常項(xiàng): 簡(jiǎn)單命題是命題邏輯中最基本的研究單位，其真值是確定的，稱作命題常項(xiàng)或命題常元 命題變項(xiàng)（命題變?cè)喝≈?（真）或0（假）的變?cè)Q作命題變項(xiàng)或命題變?cè)?

16、命題變項(xiàng)不是命題，命題變項(xiàng)與命題常項(xiàng)的關(guān)系如同初等數(shù)學(xué)中變量與常量的關(guān)系 常項(xiàng)與變項(xiàng)均用 p, q, r, …, pi, qi, ri, …, 等表示.,?r,21,命題變項(xiàng)與合式公式,定義1.6 將命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按照一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串稱作合式公式，合式公式（簡(jiǎn)稱公式）的遞歸定義： (1) 單個(gè)命題變項(xiàng)和命題常項(xiàng)是合式公式, 稱作原子命題公式 (2) 若A是合式公式，則 (?A)也是 (3) 若A,

17、 B是合式公式，則(A?B), (A?B), (A?B), (A?B)也是 (4) 只有有限次地應(yīng)用(1)—(3) 形成的符號(hào)串才是合式公式合式公式也稱作命題公式或命題形式，簡(jiǎn)稱為公式,22,命題變項(xiàng)與合式公式,幾點(diǎn)說(shuō)明： 定義1.6給出的合式公式的定義方式是歸納或遞歸定義定義中引進(jìn)的A、B等符號(hào)，用它們表示任意的何時(shí)公式，稱為元語(yǔ)言符號(hào)，而某個(gè)具體的公式，如：p、 p ?q、p ?q， (p ?q)?r 稱作對(duì)象語(yǔ)

18、言符號(hào)，所謂對(duì)象語(yǔ)言是指用來(lái)描述研究對(duì)象的語(yǔ)言，而元語(yǔ)言是用來(lái)描述對(duì)象語(yǔ)言的語(yǔ)言為方便起見(jiàn)，當(dāng)(p ?q)， (?A)等公式單獨(dú)出現(xiàn)時(shí)或者公式中的括號(hào)不影響運(yùn)算次序時(shí)，外層括號(hào)可以省去,23,合式公式的層次,定義1.7(1) 若公式A是單個(gè)命題變項(xiàng)，則稱A為0層公式.(2) 稱 A 是 n+1(n≥0) 層公式是指下面情況之一： (a) A=?B, B 是 n 層公式； (b) A=B?C, 其

19、中B,C 分別為 i 層和 j 層公式， 且 n=max(i,j)； (c) A=B?C, 其中 B,C 的層次及 n 同(b)； (d) A=B?C, 其中B,C 的層次及 n 同(b)； (e) A=B?C, 其中B,C 的層次及 n 同(b). (3) 若公式A的層次為k, 則稱A為k層公式.例如 公式 A=p, B=?p, C=?p?q,

20、 D=?(p?q)?r, E=((?p?q) ?r) ?(?r?s) 分別為0層，1層，2層，3層，4層公式.,在命題公式中，由于有命題變項(xiàng)的出現(xiàn)，因而真值是不確定的。用命題常項(xiàng)替換公式中的命題變項(xiàng)稱作解釋。在將公示中出現(xiàn)的全部命題變項(xiàng)都解釋成具體的命題常項(xiàng)之后，公式就成了真值確定的命題。如： (p ? q) ?r, 當(dāng)命題變?cè)忉尦刹煌拿}常項(xiàng)，則可得到不同真值的

21、命題,24,公式賦值,25,定義1.8 設(shè)p1, p2, … , pn是出現(xiàn)在公式A中的全部命題變項(xiàng), 給p1, p2, … , pn各指定一個(gè)真值, 稱為對(duì)A的一個(gè)賦值或解釋. 若使A為1, 則稱這組值為A的成真賦值; 若使A為0, 則稱這組值為A的成假賦值.幾點(diǎn)說(shuō)明：A中僅出現(xiàn) p1, p2, … , pn，給A賦值?=?1?2…?n是指 p1=?1, p2=?2, …, pn=?n, ?i=0或1, ?i

22、之間不加標(biāo)點(diǎn)符號(hào) A中僅出現(xiàn) p, q, r, …, 給A賦值?1?2?3…是指 p=?1, q=?2 , r=?3 …含n個(gè)命題變項(xiàng)的公式有2n個(gè)賦值. 如 000, 010, 101, 110是?(p?q)?r的成真賦值 001, 011, 100, 111是成假賦值.,公式賦值,26,定義1.9 將命題公式A在所有賦值下取值的情況列成表, 稱作A的真值表.構(gòu)造真值表的步驟:

23、(1) 找出公式中所含的全部命題變項(xiàng)p1, p2, … , pn(若無(wú)下角標(biāo) 則按字母順序排列), 列出2n個(gè)全部賦值, 從00?0開(kāi)始, 按 二進(jìn)制加法, 每次加1, 直至11?1為止. (2) 按從低到高的順序?qū)懗龉降母鱾€(gè)層次.(3) 對(duì)每個(gè)賦值依次計(jì)算各層次的真值, 直到最后計(jì)算出公式 的真值為止.,真值表,27,例6 寫出下列公式的真值表, 并求它們的成真賦值和成假 賦值:

24、 (1) (p?q) ??r (2) (q?p) ?q?p (3) ? (?p?q) ?q,真值表,28,(1) A = (p?q) ??r,成真賦值:000,001,010,100,110; 成假賦值:011,101,111,真值表1,29,(2) B＝(q?p)?q?p,成真賦值:00,01,10,11; 無(wú)成假賦值,真值表2,30,(3) C＝? (?p?q)?q的真值表,成假賦值:00,01,10,11

25、; 無(wú)成真賦值,真值表3,31,如果兩個(gè)公式A與B的真值表對(duì)所有賦值最后一列都相同，即最后結(jié)果都相同，則稱這兩個(gè)真值表相同。,32,公式的類型,根據(jù)公式在各種賦值下的取值情況，可以按照下述定義將命題公式進(jìn)行分類：定義1.10 設(shè)A為任一命題公式 (1) 若A在它的任何賦值下均為真, 則稱A為重言式或永真式;(2) 若A在它的任何賦值下均為假, 則稱A為矛盾式或永假式;(3) 若A不是矛盾式, 則稱A是可滿足式.,真值表的用

26、途: 求出公式的全部成真賦值與成假賦值, 判斷公式的類型,33,公式的類型,從定義不難看出以下幾點(diǎn)：1、A是可滿足式的等價(jià)定義是：A至少存在一個(gè)成真賦值2、重言式一定是可滿足式，但反之不真。若公式A是可滿足式，且它至少存在一個(gè)成假賦值，則稱A為非重言式的可滿足式。3、真值表可以用來(lái)判斷公式的類型。 最后一列全為1（重言式），全為0（矛盾式），至少有一個(gè)為1（可滿足式）由例1可知, (p?q) ??r,

27、(q?p) ?q?p, ? (?p?q) ?q 分別為非重言式的可滿足式, 重言式, 矛盾式.,34,從定義不難看出以下幾點(diǎn)：給定n個(gè)命題變項(xiàng)，按照合式公式的形成規(guī)則，可以形成無(wú)窮多種形式各異的公式，但這些公式的真值表不是無(wú)窮多種，而是22n種不同的情況例1.9 下列各公式均含兩個(gè)命題變項(xiàng)p或q，計(jì)算看它們中哪些具有相同的真值表（1） p?q （2） p ?q（3） ?（p ? ?q）（

28、4） （p?q） ?（ q?p ）（5） ?q ?p,35,設(shè)公式A、B中共含有命題變項(xiàng)p1, p2, … , pn，而A或B不全含這些命題變項(xiàng)，如A中不含pi+1, pi+2, … , pn ，i>=2, 稱這些命題變項(xiàng)為A的啞元，A的取值與啞元無(wú)關(guān)，如此在討論A與B是否有相同的真值表時(shí)，可以將A，B都看成含p1, p2, … , pn的命題公式例1.10 下列公式中，哪些具有相同的真值表（1） p?q （2）?q ?

29、r（3）(?p ?q) ?((p ? r) ?p)（4） (q?r) ?(p?p),36,第一章 習(xí)題課,主要內(nèi)容命題、真值、簡(jiǎn)單命題與復(fù)合命題、命題符號(hào)化聯(lián)結(jié)詞?, ?, ?, ?, ?及復(fù)合命題符號(hào)化命題公式及層次公式的類型真值表及應(yīng)用基本要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將命題符號(hào)化會(huì)求復(fù)合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等概念熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值

30、及判斷公式類型,37,1. 將下列命題符號(hào)化 (1) 豆沙包是由面粉和紅小豆做成的. (2) 蘋果樹(shù)和梨樹(shù)都是落葉喬木. (3) 王小紅或李大明是物理組成員. (4) 王小紅或李大明中的一人是物理組成員. (5) 由于交通阻塞，他遲到了. (6) 如果交通不阻塞，他就不會(huì)遲到. (7) 他沒(méi)遲到，所以交通沒(méi)阻塞. (8) 除非交通阻塞，否則他不會(huì)遲到. (9) 他遲到當(dāng)且僅當(dāng)交通阻塞.,練習(xí)1,38,

31、提示：分清復(fù)合命題與簡(jiǎn)單命題分清相容或與排斥或分清必要與充分條件及充分必要條件答案: (1) 是簡(jiǎn)單命題 (2) 是合取式 (3) 是析取式（相容或）(4) 是析取式（排斥或）設(shè) p: 交通阻塞，q: 他遲到 (5) p?q, (6) ?p??q或q?p

32、(7) ?q??p 或p?q, (8) q?p或?p??q (9) p?q 或?p??q可見(jiàn)(5)與(7)，(6)與(8) 相同（等值）,練習(xí)1解答,39,2. 設(shè) p : 2是素?cái)?shù) q : 北京比天津人口多 r : 美國(guó)的首都是舊金山 求下面命題的真值 (1) (p?q)?r (2) (q?r)?(p??r) (3

33、) (q?r)?(p??r) (4) (q?p)?((p??r)?(?r??q)),0,練習(xí)2,1,0,0,40,3. 用真值表判斷下面公式的類型 (1) p?r??(q?p) (2) ((p?q) ?(?q??p)) ?r (3) (p?q) ?(p?r),練習(xí)3,41,練習(xí)3解答,(1) p?r??(q?p),矛盾式,42,練習(xí)3解答,(2) ((p?q) ?(?q??p)) ?r,永真式,43,練