pm講義-第2章-數(shù)理邏輯基礎(chǔ) (1)

1、第二章 數(shù)理邏輯基礎(chǔ),命題邏輯謂詞邏輯文本代換,2.1 命題邏輯,什么是命題？命題為具有確定真假意義的陳述句。命題必須具備二個(gè)條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義。,聯(lián)結(jié)詞,“?” 否定聯(lián)結(jié)詞P是命題，?P是P的否命題是由聯(lián)結(jié)詞 ? 和命題P組成的復(fù)合命題一元命題,聯(lián)結(jié)詞,“?” 合取聯(lián)結(jié)詞P?Q是命題P，Q的合取式是“?”和P，Q組成的復(fù)合命題“?”在語句中相當(dāng)于“不但…而且…”

2、P?Q取值1，當(dāng)且僅當(dāng)P，Q均取1P?Q取值為0，只要P，Q之一取0.,聯(lián)結(jié)詞,“?” 析取聯(lián)結(jié)詞P?Q是命題P，Q的析取式聯(lián)結(jié)詞“?” 表示相容或P?Q取值1，只要P，Q之一取值1，P?Q取值0，只有P，Q都取值0. “??” 不可兼析取(異或)聯(lián)結(jié)詞??表示不相容的或即“P??Q”?“?P?Q?P??Q”.,聯(lián)結(jié)詞,“?” 等價(jià)聯(lián)結(jié)詞P?Q是P，Q的等價(jià)式“?”在語句中相當(dāng)于“…當(dāng)且僅當(dāng)…”P?Q取

3、值1當(dāng)且僅當(dāng)P，Q取值相同.,聯(lián)結(jié)詞,“?” 蘊(yùn)含聯(lián)結(jié)詞“?”在語句中相當(dāng)于“如果P，那么Q”P?Q取值為0，只有P取值為1，Q取值為0時(shí)其余各種情況，均有P?Q取值為11?0的真值為00?1，1?1，0?0的真值均為1.,聯(lián)結(jié)詞運(yùn)算的優(yōu)先次序,?????,命題定律,,一種狀態(tài)下命題的值,定義1：狀態(tài)是標(biāo)識(shí)符集到值T和F上的一個(gè)函數(shù)。例：令狀態(tài)s是由{(a,F)，(b,T)，(c,T)}定義的函數(shù)s(a)=F,

4、 s(b)=T , s(c)=T定義2：如果命題e中的每個(gè)標(biāo)識(shí)符在狀態(tài)s下都有對(duì)應(yīng)的值T或F，則稱命題e在狀態(tài)s下是有意義的。,一種狀態(tài)下命題的值,定義3：設(shè)命題e在狀態(tài)s中是有意義的，那么在狀態(tài)s中命題e的值s(e)是這樣得到的：將命題e中的所有標(biāo)識(shí)符用它在狀態(tài)s中的值代入這樣就變成一個(gè)常量命題，由此計(jì)算出命題的值。例：令： s={(b,T)，(c,F)}, e= ¬b ? c 則：s(e)= ¬

5、;T ? F = F,作為狀態(tài)集的命題,一個(gè)命題值的真假完全由狀態(tài)決定。反過來，可以用命題描述狀態(tài)（集）。對(duì)于任何一個(gè)命題e，存在和這個(gè)命題對(duì)應(yīng)的一個(gè)使該命題為真的狀態(tài)集，所以可用這個(gè)命題當(dāng)作這個(gè)狀態(tài)集的描述。但是一個(gè)狀態(tài)集對(duì)應(yīng)多個(gè)命題。即用命題描述狀態(tài)是不唯一的。,作為狀態(tài)集的命題,例：兩個(gè)狀態(tài){(b,T),(c,T),(d,F)}和{(a,T),(b,F)}用命題(b ? c ? ¬ d) ? (a ? 

6、2; b)來表示。用命題T表示狀態(tài)集的全集用命題F表示空集,2.2 謂詞邏輯,謂詞的描述將命題進(jìn)行下面的擴(kuò)展就成為謂詞：將命題中標(biāo)識(shí)符由任何具有T和F值的表達(dá)式（如x<y）替代在命題中引進(jìn)量詞?、?等。例((x<=y) ?(y<z)) ? (x+y<z),謂詞的求值,例：令S={(x,1),(y,3),(z,5),(b,T)}e = ((x<=y) ?(y<z) ?(x+y<

7、z) ?b)則：S(e)= (1<=3) ?(3<5) ?(1+3<5) ?T)=T,量詞,存在量詞? （Existential Quantification）(?i: m<=i<n:Ei) ? (Em ?Em+1 ?… ?En-1)讀做：“至少存在一個(gè)整數(shù)i，滿足i在m和n-1之間，使得Ei成立”全稱量詞?（Universal Quantification）(? i: m<=i<

8、n:Ei) ? (Em ? Em+1 ? … ? En-1)(? i: m<=i<n:Ei) ? ¬(?i: m<=i<n: ¬ Ei),自由標(biāo)識(shí)符和受約束標(biāo)識(shí)符,(? i: m0)等價(jià)于 (x>0 ? m>0) ?(x<0 ? n<=0)即該謂詞的值依賴于m,n,x，而不依賴于i。事實(shí)上，i可以不在謂詞中出現(xiàn)，而將i

9、用j替換不會(huì)改變謂詞的值。即m，n，x和i所起的作用不同。我們把m,n,x,稱為自由標(biāo)識(shí)符，而像 i 這樣的標(biāo)識(shí)符稱為受約束的標(biāo)識(shí)符。,自由標(biāo)識(shí)符和受約束標(biāo)識(shí)符,在一個(gè)表達(dá)式中一個(gè)標(biāo)識(shí)符不可以既是受約束的又是自由的也不可以同時(shí)受到兩個(gè)不同的量詞的約束例：i>0 ?(? i: m0)(? i: m0) ? (? i: m0),2.3 文本代換,定義：設(shè)E和e是表達(dá)式，x是標(biāo)識(shí)符則記號(hào)Exe表示E中所有自由出現(xiàn)的x

10、同時(shí)用e來代換而得到的表達(dá)式。為有效起見，代換必須產(chǎn)生一個(gè)語法正確的表達(dá)式。如果代換可能使e中的某個(gè)標(biāo)識(shí)符變成受約束的，那么應(yīng)在代換之前將E中的標(biāo)識(shí)符做適當(dāng)?shù)母淖?，以免產(chǎn)生矛盾。,文本代換舉例,E = u*x<y and ?i:0<=i<n:b[i]<yE yx+y= E ua+b= E ik= E bc+1=,同時(shí)代換,定義2: 設(shè)x-表示一個(gè)不同標(biāo)識(shí)符序列x1,x