復試2離散結(jié)構(gòu)2011

1離散數(shù)學2主要內(nèi)容數(shù)理邏輯集合論代數(shù)結(jié)構(gòu)圖論組合分析初步形式語言和自動機初步3教材與教學參考書教材：耿素云、屈婉玲、張立昂，離散數(shù)學（第四版），清華大學出版社,2008.教學參考書：屈婉玲、耿素云、張立昂，離散數(shù)學題解（第三版），清華大學出版社，2008.

4數(shù)理邏輯部分第1章命題邏輯第2章一階邏輯5第1章命題邏輯

1.1命題符號化及聯(lián)結(jié)詞1.2命題公式及分類1.3等值演算1.4聯(lián)結(jié)詞全功能集1.5對偶與范式1.6推理理論61.1

命題符號化及聯(lián)結(jié)詞

命題與真值原子命題復合命題命題常項命題變項聯(lián)結(jié)詞

7命題與真值

命題:判斷結(jié)果唯一的陳述句命題的真值:判斷的結(jié)果真值的取值:真與假真命題:真值為真的命題假命題:真值為假的命題注意:感嘆句、祈使句、疑問句都不是命題陳述句中的悖論以及判斷結(jié)果不唯一確定的也不是命題8

例

下列句子中那些是命題？

(1)

是無理數(shù).(2)2+5＝8.(3)x+5＞

3.(4)你有鉛筆嗎？

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

(6)請不要講話！

(7)我正在說謊話.真命題假命題真值不確定疑問句感嘆句祈使句悖論(3)~(7)都不是命題9簡單命題與復合命題簡單命題(原子命題):簡單陳述句構(gòu)成的命題簡單命題的符號化:用p,q,r,…,pi,qi,ri(i≥1)表示用“1”表示真，用“0”表示假復合命題:由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句

例如如果明天天氣好,我們就出去郊游設p:明天天氣好,q:我們出去郊游,如果p,則q

又如張三一面喝茶一面看報設p:張三喝茶,q:張三看報,p并且q10聯(lián)結(jié)詞否定聯(lián)結(jié)詞否定式p:非p(p的否定)

p

為真當且僅當p為假pp011011聯(lián)結(jié)詞(續(xù))合取聯(lián)結(jié)詞合取式pq:p并且q(p與q)pq為真當且僅當p與q同時為真pqpq00001010011112聯(lián)結(jié)詞(續(xù))析取聯(lián)結(jié)詞析取式pq:p或q

pq為假當且僅當p與q同時為假pqpq00001110111113聯(lián)結(jié)詞與復合命題定義1.1

設p為命題,復合命題“非p”(或“p的否定”)稱為p的否定式,記作p,符號稱作否定聯(lián)結(jié)詞,并規(guī)定p為真當且僅當p為假例如p:2是合數(shù),p:2不是合數(shù),p為假,p為真定義1.2

設p,q為二命題,復合命題“p并且q”(或“p與q”)稱為p與q的合取式,記作p∧q,∧稱作合取聯(lián)結(jié)詞,并規(guī)定

p∧q為真當且僅當p與q同時為真例如p:2是偶數(shù),q:2是素數(shù),p∧q:2是偶素數(shù),p為真,q為真,p∧q為真14聯(lián)結(jié)詞與復合命題(續(xù))定義1.3

設p,q為命題,復合命題“p或q”稱作p與q的析取式,記作p∨q,∨稱作析取聯(lián)結(jié)詞,并規(guī)定p∨q為假當且僅當p與q同時為假.例如張三和李四至少有一人會英語設p:張三會英語,q:李四會英語,符號化為p∨q相容或與排斥或例如這件事由張三和李四中的一人去做設p:張三做這件事,q:李四做這件事應符號化為(p∧q)∨(p∧q)15實例例2

將下列命題符號化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)

張輝與王麗都是三好生.(5)張輝與王麗是同學.解

記p:王曉用功,q:王曉聰明(1)p∧q(2)p∧q(3)q∧p(4)記r:張輝是三好生,s:王麗是三好生,r∧s(5)簡單命題,記

t:張輝與王麗是同學16實例例3

將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.解記p:2是素數(shù),q:3是素數(shù),r:4是素數(shù),s:6是素數(shù)(1)p∨r,(2)

p∨q,(3)r∨s,(4)記t:元元拿一個蘋果,u:元元拿一個梨真值:1真值:1真值:0(t∧u)∨(t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年(v∧w)∨(v∧w)又可形式化為v∨w17聯(lián)結(jié)詞(續(xù))蘊涵聯(lián)結(jié)詞蘊涵式pq:如果p,則qpq為假當且僅當p為真q為假pqpq00101110011118蘊涵式A:平時認真上課且完成作業(yè)B:期末得高分AB(1)001(2)011(3)100(4)111(1),(2),(4)推理正確(3)推理不正確(1)中B是A的邏輯結(jié)論,但B不是正確結(jié)論(2)和(4)中B既是Ａ的邏輯結(jié)論,Ｂ又是正確結(jié)論.19蘊涵式A:平時不認真學習B:期末得高分AB(1)001(2)011(3)100(4)111(1),(2),(4)推理正確(3)推理不正確(1)中B是A的邏輯結(jié)論,但B不是正確結(jié)論(2)和(4)中B既是Ａ的邏輯結(jié)論,Ｂ又是正確結(jié)論.20聯(lián)結(jié)詞與復合命題(續(xù))定義1.4

設p,q為二命題,復合命題“如果p,則q”稱作p與q的蘊涵式,記作pq,并稱p是蘊涵式的前件,q為蘊涵式的后件.稱作蘊涵聯(lián)結(jié)詞,并規(guī)定,pq為假當且僅當p為真且q為假.例如如果明天天氣好,我們就出去郊游設p:明天天氣好,q:我們出去郊游,形式化為pq21蘊涵聯(lián)結(jié)詞(續(xù))pq的邏輯關系:p為q的充分條件;q為p的必要條件“如果p,則q”的多種表述方式：若p,就q

只要p,就q

當p,則qp僅當q

只有q

才p

除非q,才p

除非q,否則非p當p為假時，pq為真(不管q為真,還是為假)22實例例4

設p:天冷,q:小王穿羽絨服，將下列命題符號化

(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.注意：

pq與qp

等值（真值相同）pqpqpqpqqp

qpqpqp23聯(lián)結(jié)詞與復合命題(續(xù))定義1.5

設p,q為命題,復合命題“p當且僅當q”稱作p與q的等價式,記作pq,稱作等價聯(lián)結(jié)詞.并規(guī)定pq為真當且僅當p與q同時為真或同時為假.

pq的邏輯關系:p與q互為充分必要條件例如這件事張三能做好,且只有張三能做好設p:張三做這件事,q:這件事做好了形式化為:pq24聯(lián)結(jié)詞(續(xù))等價聯(lián)結(jié)詞等價式pq:p當且僅當qpq為真當且僅當p與q同時為真或同時為假pqpq00101010011125實例例5

求下列復合命題的真值(1)2+2＝4當且僅當3+3＝6.(2)2+2＝4當且僅當3是偶數(shù).(3)2+2＝4當且僅當太陽從東方升起.(4)2+2＝5

當且僅當美國位于非洲.(5)f(x)在x0處可導的充要條件是它在

x0處連續(xù).1011026聯(lián)結(jié)詞與復合命題(續(xù))聯(lián)結(jié)詞優(yōu)先級:();;;

;;同級按從左到右的順序進行

pq

pp∧qp∨qpqpq0010011011011010001001101111基本復合命題的真值271.2命題公式及分類命題變項與合式公式公式的賦值真值表命題的分類重言式矛盾式可滿足式28合式公式命題常項:真值確定的簡單命題，一般用0或1表示；命題變項:真值變化的陳述句，一般用p,q,r或pi,qi,ri等表示。定義1.6

合式公式(命題公式,公式)遞歸定義如下：(1)單個命題常項或變項是合式公式,并稱作原子合式公式(2)若A是合式公式,則(A)也是合式公式(3)若A,B是合式公式,則(AB),(AB),(AB),(AB)也是合式公式(4)只有有限次地應用(1)~(3)形成的符號串才是合式公式說明:(1)元語言符號與對象語言符號

(2)在不影響運算順序時,括號可以省去

例如0,p,pq,(pq)(pr),pqr,(pq)r29合式公式的層次定義1.7(1)若公式A是單個命題變項,則稱A為0層公式(2)稱A是n+1(n≥0)層公式是指下面情況之一：(a)A=B,B是n層公式(b)A=BC,其中B,C分別為i層和j層公式,且

n=max(i,j)(c)A=BC,其中B,C的層次及n同(b)(d)A=BC,其中B,C的層次及n同(b)(e)A=BC,其中B,C的層次及n同(b)例如

p0層

p1層

pq2層(pq)r3層

((pq)r)(rs)4層30合式公式的層次(續(xù))

例如公式

p0層

p1層

pq2層(pq)r3層

((pq)r)(rs)4層31公式的賦值定義1.8設p1,p2,…,pn是出現(xiàn)在公式A中全部的命題變項,給p1,p2,…,pn指定一組真值,稱為對A的一個賦值或解釋.使公式為真的賦值稱作成真賦值,使公式為假的賦值稱作成假賦值說明:(1)賦值記作=12…n,i=0或1,

諸i之間不加標點符號(2)通常賦值與命題變項之間按下標或字母順序?qū)?即當A的全部命題變項為p1,p2,…,pn時,給A賦值12…n是指p1=1,p2=2,…,pn=n;當A的全部命題變項為p,q,r,…時,

給A賦值123…是指p=1,q=2,r=3,…32實例例6

公式A=(

p1

p2p3

)(p1

p2)000是成真賦值,001是成假賦值公式B=(pq)r000是成假賦值,001是成真賦值33真值表例8

給出公式的真值表(1)

(qp)qppqqp