【正文】 命題邏輯語義 ? 語義的特殊公式 （ 1）公式 A為永真式，重言式 tautologies，如果對一切賦值 ， AA （ 2） A為永假式，矛盾式 contradictions，如果對一切賦值 ， ~A^A v 1?VAv 0?VA 96 命題邏輯語義 ?語義的特殊公式 （ 3） A， B為邏輯等價的，如果對于一切賦值 ， ，記做 A╞B(A├|B) T(A)=T(B),對于任意 T （ 4）可滿足的，公式 A為可滿足的，如果至少存在一個賦值 ， v VV BA ?v 1?VA 97 命題邏輯語義 ? 真值計算 有了賦值映射，我們可以計算任意公式的真值。通常真值計算的方法有：真值表計算方法和二叉樹計算方法等。 1）真值表 真值表是計算真值的簡單工具。利用這個工具可以計算任意公式的真值。 98 命題邏輯語義 ?實例 公式 的真值表如下： )( rqp ???0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 )( rqp ???rqp 99 命題邏輯語義 2） 利用二叉樹，可視化地計算公式的真值。例如：計算下面公式的真值，并給出它是否是重言式。 100 ))(()( rqqpA ?????A1?p 0?prq ?? )( ))(( rqq ???1?q 0?q 1?q 0?q0 r 0 11?r 0?r1 0 A故 A不為重言式，是可滿足的。 101 邏輯推論（邏輯演算） ?有了公式的真值以后，對于一些公式我們可以比較公式的真值得大小。從而可以討論公式真值之間的關系。 ?討論公式之間真值關系就是我們在語義上進行演算的主要內容。 102 邏輯推論（邏輯演算） ?基本概念 （ 1）邏輯推論：設 是一個 FSPC上的公式集合， A是 FSPC上的任一公式。 A為 的邏輯結果，記做 ╞A，當且僅當對任何賦值映射 v，如果 ＝ 1時，則 。 ╞讀作邏輯蘊涵。 ???v? 1?vA 103 邏輯推論（邏輯演算） ?基本概念 （ 2）邏輯等價：設公式 A和公式 B分別為FSPC上的兩個公式。 A和 B為邏輯等價的，記做 A╞| B，當且僅當 A╞B和 B╞A同時成立。 （ 3）永真式：如果 A為永真式，則公式集合 為空集，即 ╞A。 ? 104 邏輯推論（邏輯演算） ?邏輯推論的主要方法 （ 1）代入原理（ principle of substitution） 設 A(P)為一含有命題變元 P的永真式，那么將A中 P的每一次出現(xiàn)代換為公式 B，所得公式 A(B)仍為永真式。 （ 2）替換原理（ principle of replacement） 設命題公式 A含有子公式 C（ C為命題公式），如果 C╞│D，那么將 A中子公式 C提換為命題公式D，所得公式 B滿足 A╞│B。 A(BA)=A(~BUA) 105 邏輯推論（邏輯演算） ? 邏輯推論的主要方法 （ 3）邏輯等價性：邏輯等價且有自反性、對稱性和傳遞性。 T(A)=T(B),T(B)=T(C)。T(A)=T(C)。 Y(A)=YA),Y(A)=Y(B),則 Y(B)=Y(A), Y(A)=Y(B),Y(B)=Y(C),則 Y(A)=Y(C) 106 邏輯推論（邏輯演算） ? 邏輯推論的主要方法 （ 4）對偶原理 設 A是原子公式和聯(lián)結符號組成的公式，并且在 A中交換以原子公式與其否定互換得到的公式 A′,稱 A′為 A的對偶； A╞│ A′ ? 107 邏輯推論（邏輯演算） ? 邏輯推論的主要方法 （ 5）演繹定理 設 為 FSPC的公式集合， A和 B分別為 FSPC上的公式。 ╞ 成立的充分必要條件是： ╞ 。 ?? BA?A,? B 108 邏輯推論性質 ?公理為重言式 A1 ╞ v A2 ╞v A3 ╞v )( ABA ??))()(())(( CABACBA ??????)()( ABBA ????? 109 邏輯推論性質 ?推理規(guī)則保真性 設 A和 B為 FSPC上的公式；如果 ╞A且 ╞ 成立，則 ╞ 成立。 ?重要永真式 BA? BPPPP ??? ,)(),( QPPP ????PPQP ???? ,)()()( RPRP ?????)()()( RPRP ????? 110 邏輯推論性質 ?重要等價式 E1 ╞│ E2 ╞│ ╞│ （等冪律） E3 ╞│ ╞│ (交換律 ) E4 ╞│ E5 ╞│ （分配律） E6 ╞│ （德摩根定律） ╞│ )( P?? PPP? PPP ?,QP? QPPQ ?? , PQ?)( RQP ?? )()( RPQP ???)( RQP ?? )()( RPQP ???)( QP ?? )()( QP ???)( QP ?? )()( QP ??? 111 邏輯推論性質 ?重要等價式 E7 ╞│ E8 ╞│ E9 ╞│ E10 ╞│ E11 ╞│ E12 ╞│ ╞│ （吸收律） QP ?? )( QP ?QP ? )()( PQ ???)( RQP ?? RQP ?? )(QP ? )()( PP ???QP ? ))()(()( QPQP ?????)( QPP ?? P)( QPP ?? P 112 公式化簡 ?基本概念 有了賦值規(guī)則和上述的等價公式后，我們就可以將公式進行等價形式的轉化。轉換的目標是獲得一個標準的公式形式，從而使公式計算更簡單，同時使計算機能夠進行基于符號的演算和推理過程。范式是常用的公式的標準形式。 113 公式化簡 ?范式 設 A和 B為 FSPC上的兩個公式，稱公式 B為公式 A的析取（合?。┓妒?，如果 B╞│A，并且 B型如： 其中， 稱為 B的子句（ Clause），子句型如： 其中， 為原子公式或其否定式，被稱為文字。 )( 321321 mm CCCCCCCC ???????? ??),3,2,1( miC i ??)( 321321 nn LLLLLLLL ???????? ??),3,2,1( njL j ?? 114 公式化簡 ?對于 FSPC上的任意公式 A，存在一個析?。ê先。┓妒脚c其邏輯等值。 115 公式化簡 116 元理論與元語言 元理論是數(shù)理邏輯研究的主要內容之一，元理論主要包含以下內容： （ 1）語法構成研究（ Syntax）：主要是關于形式系統(tǒng)語言構成規(guī)律的研究。研究符號串的推演規(guī)律（重寫規(guī)則）。 （ 2）語義研究（ Semantics）：在這類研究中，符號被賦予一定的意義。研究在這種意義下，對公式作出各種解釋的性質，特別是真值性質的研究。 （ 3）語法與語義關系：這種關系主要研究，語法演算與語義推理之間的性質。主要研究語法與語義之間能否具有一致性關系。 117 命題邏輯元理論 118 4. 經(jīng)典一階邏輯 ? 基本概念 ? 數(shù)理邏輯的發(fā)展過程 ? 數(shù)理邏輯學科的發(fā)展 ? 數(shù)理邏輯與其他科學 ? 課程內容 119 4. 經(jīng)典一階邏輯 120 主要內容 ? 預備知識 ? 形式系統(tǒng) ? 命題邏輯形式系統(tǒng) ? 一階謂詞邏輯形式系統(tǒng) ? 歸結原理 121 主要內容 ? 預備知識 ? 形式系統(tǒng) ? 命題邏輯形式系統(tǒng) ? 一階謂詞邏輯形式系統(tǒng) ? 歸結原理 122 5. 歸結原理 ? 基本概念 ? 數(shù)理邏輯的發(fā)展過程 ? 數(shù)理邏輯學科的發(fā)展 ? 數(shù)理邏輯與其他科學 123 124 125 126 127 128 129 130 131