經(jīng)典命題邏輯命題：具有唯一真值的陳述句。聯(lián)結(jié)詞（命題運(yùn)算符）否定—”不”析取—”或”合取—”與”條件—”若…，則…”雙條件—”…當(dāng)且僅當(dāng)…”復(fù)合命題&簡(jiǎn)單命題在命題邏輯中，邏輯形式由聯(lián)結(jié)詞決定命題語言Lp命題語言Lp是經(jīng)典命題邏輯的形式語言命題語言Lp是符號(hào)的集合命題符號(hào)：pqr…聯(lián)結(jié)符號(hào)：標(biāo)點(diǎn)符號(hào)：（）命題語言Lp的含義本質(zhì)上不涉及語義，而只有語法。表達(dá)式表達(dá)式：Lp中有限個(gè)符號(hào)組成的字符串表達(dá)式的長(zhǎng)度：表達(dá)式中的符號(hào)數(shù)目空表達(dá)式：長(zhǎng)度為0的表達(dá)式，記為表達(dá)式相等：U=Viff表達(dá)式U和V中符號(hào)依次相同表達(dá)式U和V依次并列形成新的表達(dá)式UV，且若表達(dá)式U=W1VW2，則V是U的段。若V是U的段且V和U不相等，則V是U的真段。初始段、結(jié)尾段、真初始段、真結(jié)尾段公式集的歸納定義并不是所有表達(dá)式都是研究對(duì)象研究對(duì)象必須符合語法原子公式集Atom(Lp)={U|U是由單個(gè)命題符號(hào)構(gòu)成的表達(dá)式}合式公式集Form(Lp)i）Atom(Lp)?Form(Lp)ii）若A∈Form(Lp)，則(﹁A)∈Form(Lp)iii）若A，B∈Form(Lp)，則(A*B)∈Form(Lp)。其中*表示∧，∨，→，?中的任何一個(gè)iv）A是能由有限次應(yīng)用i）—iii）形成的表達(dá)式iffA∈Form(Lp)公式集的歸納定義合式公式集Form(Lp)是滿足的以下i）—iii）的S中的最小集i）Atom(Lp)?Sii）若A∈S，則(﹁A)∈Siii）若A，B∈S，則(A*B)∈S。其中*表示∧，∨，→，?中的任何一個(gè)公式集的歸納證明定理：設(shè)R是一個(gè)性質(zhì)，若

i）對(duì)于任何p∈Atom(Lp)，R(p)；

ii）對(duì)于任何A∈Form(Lp)，若R(A)，則R((﹁A))；

iii）對(duì)于任何A，B∈Form(Lp)，若R(A)且R(B)，則R((A*B))。其中*表示∧，∨，→，?中的任何一個(gè)；則對(duì)于任何A∈Form(Lp)，R(A)。公式結(jié)構(gòu)引理：對(duì)于任何A∈Form(Lp)，有A為不空的表達(dá)式。A中的左括號(hào)與右括號(hào)的數(shù)目相同。A的任何不空的真初始段中，左括號(hào)的數(shù)目比右括號(hào)的數(shù)目多；A的任何不空的真結(jié)尾段中，左括號(hào)的數(shù)目比右括號(hào)的數(shù)目少。定理：Lp的每一公式恰好具有以下6種形式之一：原子公式，(﹁A)，(A∧B)，(A∨B)，(A→B)，(A?B)；并且在各種情形公式所具有的那種形式是唯一的。公式的語法分類原子公式復(fù)合公式設(shè)A，B為公式，則否定式(?A)合取式(A∧B)析取式(A∨B)蘊(yùn)含式(A→B)，其中A為前件，B為后件。等值式(A?B)轄域設(shè)A，B，C為公式若(﹁A)是C的段，則稱A為它左方的﹁在C中的轄域若(A*B)是C的段，則稱A和B分別為它們之間的*在C中的左轄域和右轄域。其中*表示∧，∨，→，?中的任何一個(gè)定理：任何A中的任何﹁（如果有）有唯一的轄域；任何A中的任何*（如果有）有唯一的左轄域和右轄域定理：若A是(﹁B)的段，則A=(﹁B)或A是B的段；若A是(B*C)的段，則A=(B*C)或A是B的段或A是C的段語義函數(shù)v：{Lp中所有命題符號(hào)}→{1，0}，被稱為一個(gè)真假賦值。真假賦值v給公式A指派的真假值，記為Av。其定義為：(i)pv∈{1,0}。(ii)若Av=0，則(﹁A)v=1；否則，(﹁A)v=0。(iii)若Av=Bv=1，則(A∧B)v=1；否則，(A∧B)v=0。(iv)若Av=Bv=0，則(A∨B)v=0；否則，(A∨B)v=1。(v)若Av=1并且Bv=0，則(A→B)v=0；否則，(A→B)v=1。(vi)若Av=Bv，則(A?B)v=1；否則，(A?B)v=0。這是一個(gè)遞歸定義函數(shù)。對(duì)于一個(gè)公式，列出所有真假賦值指派的真假值，就形成了該公式真值表。例子p∨q→?q∧rpqrp∨q→?q∧r1111110010111011100100101110110111001100100001101100101010011001000010001101100000011000公式的語義分類若對(duì)于所有B∈∑，Bv=1，則∑v=1；否則，∑v=0?！剖强蓾M足的，當(dāng)且僅當(dāng)存在真假賦值v，使得∑v=1。特別的，若{A}是可滿足的，則稱A為可滿足式。A是重言式，當(dāng)且僅當(dāng)對(duì)于任何的真假賦值v，Av=1。A是矛盾式，當(dāng)且僅當(dāng)對(duì)于任何的真假賦值v，Av=0。邏輯推論設(shè)∑?Form(Lp)，A∈Form(Lp)。A是∑的邏輯推論，記作∑╞A，當(dāng)且僅當(dāng)對(duì)于任何真假賦值v，∑v=1蘊(yùn)涵Av=1（Av=0蘊(yùn)涵∑v=0）。Φ╞A表示A為重言式。╞不是Lp中符號(hào)?！屁bA不是公式。A╞╡B表示“A╞B并且B╞A”，并稱A和B是邏輯等值的。證明：A→B，B→C╞A→C

。證(1)：對(duì)于任何真假賦值v，若{A→B，B→C}v=1?？傻茫?/p>

(A→B)v=1(i)，

(B→C)v=1(ii)。若Av=1，則由(i)可得，Bv=1。再由(ii)可得，Cv=1。所以，(A→C)v=1。若Av=0，則(A→C)v=1。證明：A→B，B→C╞A→C

。證(2)：設(shè)任何真假賦值v，若(A→C)v=0

可得，

Av=1(i)，

Cv=0(ii)。若Bv=1，則由(ii)可得，(B→C)v=0。所以，{A→B，B→C}v=0。若Bv=0，則由(ii)可得，(A→B)v=0。所以，{A→B，B→C}v=0。定理（等值公式替換）如果B╞╡C，且A中將B的某些出現(xiàn)替換為C而得到A’，則A╞╡A’。（對(duì)偶性）設(shè)A為L(zhǎng)p的原子公式和聯(lián)結(jié)符號(hào)?，∧，∨使用相關(guān)規(guī)則而形成的公式。若對(duì)A中的∧與∨，原子公式與它的否定式進(jìn)行交換而得到A’（稱為A的對(duì)偶），則?A╞╡A’。形式可推演用∑表示任何公式集，即∑?Form(Lp)。∑∪{A}可以記為∑，A?！啤取啤梢杂洖椤?，∑’。若∑={A1,A2,A3,…}，則∑可以記為A1,A2,A3,…?！譬繟表示A由∑形式可推演（形式可證明）的。其中，∑為前提，A為結(jié)論。├不是Lp中符號(hào)?！譬繟不是公式。A├┤B表示“A├B并且B├A”，并稱A和B是語法等值的。命題邏輯的推演規(guī)則共11條，A，B，C為公式(Ref)A├A(+)若∑├A， 則∑，∑’├A(﹁-)若∑，﹁A

├B，

∑，﹁A

├﹁B，則∑├A(→-)若∑├A→B，

∑├A，則∑├B(→+)若∑，A├B，

則∑├A→B(∧-)若∑├A∧B，則∑├A，∑├B

(∧+)若∑├A

，

∑├B

，則∑├A∧B

(∨-)若∑，A├C，∑，B├C，則∑，A∨B├C(∨+)若∑├A

，則∑├A∨B，

∑├B∨A(?-)若∑├A?B，∑├A，則∑├B

若∑├A?B，∑├B，則∑├A(?+)若∑，A├B，∑，B├A，則∑├A?B

形式推演的定義A是在命題邏輯中由∑形式可推演（形式可證明）的，記為∑├A，當(dāng)且僅當(dāng)∑├A能有限次使用形式推演規(guī)則生成。這是一個(gè)歸納定義。定義了以下集合

{∑├A|∑?Form(Lp)且A∈Form(Lp)}關(guān)于歸納證明（定理2.6.2）一個(gè)有限序列∑1├A1，∑2├A2，…，∑n├An被稱為∑n├An的形式證明。其中，∑k├Ak（1≤k≤n）由使用某一推演規(guī)則而生成。∈規(guī)則證明：A，∑├A。證：

(1)A├A(Ref)(2)A，∑├A(+)(1)例子證明：﹁A→B├﹁B→A證：

(1)﹁A→B，﹁B，﹁A├﹁A→B(∈)(2)﹁A→B，﹁B，﹁A├﹁A(∈)(3)﹁A→B，﹁B，﹁A├B(→-)(1)(2)(4)﹁A→B，﹁B，﹁A├﹁B(∈)(5)﹁A→B，﹁B├A(﹁-)(3)(4)(6)﹁A→B├﹁B→A(→+)(5)Tr規(guī)則證明：若∑├∑’，∑’├A，則∑├A證：

(1)∑’├A(前提)(2)A1，A2，…，An├A(定理2.6.2)(1)

其中A1，A2，…，An∈∑’

(3)∑，A1，A2，…，An├A(+)(2)(4)∑，A1，A2，…，An-1├An→A(→+)(3)(5)∑├An(前提)(6)∑，A1，A2，…，An-1├

A(→-)(4)(5)(7)∑├

A(同理(6))證明：A→B，B→C├A→C

。證：

(1)A→B，B→C，A├A→B(∈)(2)A→B，B→C，A├A

(∈)(3)A→B，B→C，A├B

(→-)(1)(2)(4)A→B，B→C，A├B→C(∈)(5)A→B，B→C，A├C

(→-)(4)(3)(6)A→B，B→C├

A→C(→+)(5)證明：A→(B→C)，A→B├A→C

。證：

(1)A→(B→C)，A→B，A├A→(B→C)(∈)(2)A→(B→C)，A→B，A├A

(∈)(3)A→(B→C)，A→B，A├B→C(→-)(1)(2)(4)A→(B→C)，A→B，A├A→B(∈)(5)A→(B→C)，A→B，A├B(→-)(4)(2)(6)A→(B→C)，A→B，A├C(→-)(3)(5)(7)A→(B→C)，A→B├A→C(→+)(6)證明：﹁﹁A├A證：

(1)﹁﹁A，﹁A├﹁A(∈)(2)﹁﹁A，﹁A├﹁﹁A(∈)(3)﹁﹁A├A(﹁-)(1)(2)(﹁+)歸謬律證明：(﹁+)若∑，A

├B，

∑，A

├﹁B，則∑├﹁A證：(1)∑，﹁﹁A├∑(∈)(2)﹁﹁A├A(已證)(3)∑，﹁﹁A├A(+)(2)(4)∑，A

├B(前提)(5)∑，﹁﹁A├B(Tr)(1)(3)(4)(6)∑，A

├﹁B(前提)(7)∑，﹁﹁A├﹁B(Tr)(1)(3)(6)

(8)∑├﹁A

(﹁-)(5)(7)證明：A├﹁﹁A證：

(1)A，﹁A├A(∈)(2)A，﹁A├﹁A(∈)(3)A├﹁﹁A(﹁+)(1)(2)范式單式原子公式和原子公式的否定稱為單式。析（合）取子式以單式為析（合）取項(xiàng)的析（合）取式稱為析（合）取子式。析取范式以合取子式為析取項(xiàng)的析取式稱為析取范式。合取范式以析取子式為合取項(xiàng)的合取式稱為合取范式。主析取范式和主合取范式例子求(p→q)∧r的析取范式和合取范式解：(p→q)∧r╞╡(?p∨q)∧r╞╡(?p∧r)∨(q∧r)╞╡(?p∨q)∧(r∨q)∧(?p∧r)∧r翻譯符號(hào)化下列命題，并進(jìn)行推理。公安人員審查一件盜竊案，事實(shí)如下：張平或王磊盜竊了機(jī)房的計(jì)算機(jī)一臺(tái)；若張平盜竊了計(jì)算機(jī)，則作案時(shí)間不可能發(fā)生在午夜之前；若王磊的證詞正確，則午夜時(shí)機(jī)房里的燈未滅；若王磊的證詞不正確，則作案時(shí)間發(fā)生在午夜之前；午夜時(shí)機(jī)房的燈光滅了。問：誰盜竊了該臺(tái)計(jì)算機(jī)。p：張平盜竊了機(jī)房的計(jì)算機(jī)一臺(tái)。q：王磊盜竊了機(jī)房的計(jì)算機(jī)一臺(tái)。r：作案時(shí)間發(fā)生在午夜之前。s：王磊的證詞正確。t：午夜時(shí)機(jī)房的燈光滅了。p∨q，p→?r，s→?t，?s→r，t├？(1)p，?q├p(∈)(2)q，?q

，?p

├?q(∈)(3)q，?q

，?p

├q(∈)(4)q，?q

├p(?-)(2)(3)(5)p∨q，?q├p