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

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

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

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

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

5、;T ? F = F,作為狀態(tài)集的命題,一個命題值的真假完全由狀態(tài)決定。反過來，可以用命題描述狀態(tài)（集）。對于任何一個命題e，存在和這個命題對應的一個使該命題為真的狀態(tài)集，所以可用這個命題當作這個狀態(tài)集的描述。但是一個狀態(tài)集對應多個命題。即用命題描述狀態(tài)是不唯一的。,作為狀態(tài)集的命題,例：兩個狀態(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 謂詞邏輯,謂詞的描述將命題進行下面的擴展就成為謂詞：將命題中標識符由任何具有T和F值的表達式（如x<y）替代在命題中引進量詞?、?等。例((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)讀做：“至少存在一個整數(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),自由標識符和受約束標識符,(? i: m0)等價于 (x>0 ? m>0) ?(x<0 ? n<=0)即該謂詞的值依賴于m,n,x，而不依賴于i。事實上，i可以不在謂詞中出現(xiàn)，而將i

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

10、同時用e來代換而得到的表達式。為有效起見，代換必須產(chǎn)生一個語法正確的表達式。如果代換可能使e中的某個標識符變成受約束的，那么應在代換之前將E中的標識符做適當?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=,同時代換,定義2: 設x-表示一個不同標識符序列x1,x