经典命题逻辑

经典命题逻辑命题：具有唯一真值的陈述句。联结词（命题运算符）否定—”不”析取—”或”合取—”与”条件—”若…，则…”双条件—”…当且仅当…”复合命题&简单命题在命题逻辑中，逻辑形式由联结词决定命题语言Lp命题语言Lp是经典命题逻辑的形式语言命题语言Lp是符号的集合命题符号：pqr…联结符号：标点符号：（）命题语言Lp的含义本质上不涉及语义，而只有语法。表达式表达式：Lp中有限个符号组成的字符串表达式的长度：表达式中的符号数目空表达式：长度为0的表达式，记为表达式相等：U=Viff表达式U和V中符号依次相同表达式U和V依次并列形成新的表达式UV，且若表达式U=W1VW2，则V是U的段。若V是U的段且V和U不相等，则V是U的真段。初始段、结尾段、真初始段、真结尾段公式集的归纳定义并不是所有表达式都是研究对象研究对象必须符合语法原子公式集Atom(Lp)={U|U是由单个命题符号构成的表达式}合式公式集Form(Lp)i）Atom(Lp)⊆Form(Lp)ii）若A∈Form(Lp)，则(﹁A)∈Form(Lp)iii）若A，B∈Form(Lp)，则(A*B)∈Form(Lp)。其中*表示∧，∨，→，↔中的任何一个iv）A是能由有限次应用i）—iii）形成的表达式iffA∈Form(Lp)公式集的归纳定义合式公式集Form(Lp)是满足的以下i）—iii）的S中的最小集i）Atom(Lp)⊆Sii）若A∈S，则(﹁A)∈Siii）若A，B∈S，则(A*B)∈S。其中*表示∧，∨，→，↔中的任何一个公式集的归纳证明定理：设R是一个性质，若

i）对于任何p∈Atom(Lp)，R(p)；

ii）对于任何A∈Form(Lp)，若R(A)，则R((﹁A))；

iii）对于任何A，B∈Form(Lp)，若R(A)且R(B)，则R((A*B))。其中*表示∧，∨，→，↔中的任何一个；则对于任何A∈Form(Lp)，R(A)。公式结构引理：对于任何A∈Form(Lp)，有A为不空的表达式。A中的左括号与右括号的数目相同。A的任何不空的真初始段中，左括号的数目比右括号的数目多；A的任何不空的真结尾段中，左括号的数目比右括号的数目少。定理：Lp的每一公式恰好具有以下6种形式之一：原子公式，(﹁A)，(A∧B)，(A∨B)，(A→B)，(A↔B)；并且在各种情形公式所具有的那种形式是唯一的。公式的语法分类原子公式复合公式设A，B为公式，则否定式(¬A)合取式(A∧B)析取式(A∨B)蕴含式(A→B)，其中A为前件，B为后件。等值式(A↔B)辖域设A，B，C为公式若(﹁A)是C的段，则称A为它左方的﹁在C中的辖域若(A*B)是C的段，则称A和B分别为它们之间的*在C中的左辖域和右辖域。其中*表示∧，∨，→，↔中的任何一个定理：任何A中的任何﹁（如果有）有唯一的辖域；任何A中的任何*（如果有）有唯一的左辖域和右辖域定理：若A是(﹁B)的段，则A=(﹁B)或A是B的段；若A是(B*C)的段，则A=(B*C)或A是B的段或A是C的段语义函数v：{Lp中所有命题符号}→{1，0}，被称为一个真假赋值。真假赋值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。这是一个递归定义函数。对于一个公式，列出所有真假赋值指派的真假值，就形成了该公式真值表。例子p∨q→¬q∧rpqrp∨q→¬q∧r1111110010111011100100101110110111001100100001101100101010011001000010001101100000011000公式的语义分类若对于所有B∈∑，Bv=1，则∑v=1；否则，∑v=0。∑是可满足的，当且仅当存在真假赋值v，使得∑v=1。特别的，若{A}是可满足的，则称A为可满足式。A是重言式，当且仅当对于任何的真假赋值v，Av=1。A是矛盾式，当且仅当对于任何的真假赋值v，Av=0。逻辑推论设∑⊆Form(Lp)，A∈Form(Lp)。A是∑的逻辑推论，记作∑╞A，当且仅当对于任何真假赋值v，∑v=1蕴涵Av=1（Av=0蕴涵∑v=0）。Φ╞A表示A为重言式。╞不是Lp中符号。∑╞A不是公式。A╞╡B表示“A╞B并且B╞A”，并称A和B是逻辑等值的。证明：A→B，B→C╞A→C

。证(1)：对于任何真假赋值v，若{A→B，B→C}v=1。可得，

(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)：设任何真假赋值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的某些出现替换为C而得到A’，则A╞╡A’。（对偶性）设A为Lp的原子公式和联结符号¬，∧，∨使用相关规则而形成的公式。若对A中的∧与∨，原子公式与它的否定式进行交换而得到A’（称为A的对偶），则¬A╞╡A’。形式可推演用∑表示任何公式集，即∑⊆Form(Lp)。∑∪{A}可以记为∑，A。∑∪∑’可以记为∑，∑’。若∑={A1,A2,A3,…}，则∑可以记为A1,A2,A3,…。∑├A表示A由∑形式可推演（形式可证明）的。其中，∑为前提，A为结论。├不是Lp中符号。∑├A不是公式。A├┤B表示“A├B并且B├A”，并称A和B是语法等值的。命题逻辑的推演规则共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，当且仅当∑├A能有限次使用形式推演规则生成。这是一个归纳定义。定义了以下集合

{∑├A|∑⊆Form(Lp)且A∈Form(Lp)}关于归纳证明（定理2.6.2）一个有限序列∑1├A1，∑2├A2，…，∑n├An被称为∑n├An的形式证明。其中，∑k├Ak（1≤k≤n）由使用某一推演规则而生成。∈规则证明：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规则证明：若∑├∑’，∑’├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)范式单式原子公式和原子公式的否定称为单式。析（合）取子式以单式为析（合）取项的析（合）取式称为析（合）取子式。析取范式以合取子式为析取项的析取式称为析取范式。合取范式以析取子式为合取项的合取式称为合取范式。主析取范式和主合取范式例子求(p→q)∧r的析取范式和合取范式解：(p→q)∧r╞╡(¬p∨q)∧r╞╡(¬p∧r)∨(q∧r)╞╡(¬p∨q)∧(r∨q)∧(¬p∧r)∧r翻译符号化下列命题，并进行推理。公安人员审查一件盗窃案，事实如下：张平或王磊盗窃了机房的计算机一台；若张平盗窃了计算机，则作案时间不可能发生在午夜之前；若王磊的证词正确，则午夜时机房里的灯未灭；若王磊的证词不正确，则作案时间发生在午夜之前；午夜时机房的灯光灭了。问：谁盗窃了该台计算机。p：张平盗窃了机房的计算机一台。q：王磊盗窃了机房的计算机一台。r：作案时间发生在午夜之前。s：王磊的证词正确。t：午夜时机房的灯光灭了。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