数理逻辑-命题逻辑

第一章命题逻辑1.2命题公式与分类11.命题常元与命题变元命题常元：表示一个具体的简单命题的符号。命题常元的真值是确定不变的，不是为1，就是为0。命题变元：没有赋予具体内容的原子命题。该命题变量无具体的真值，它的只域是集合{T，F}(或{0，1})。命题公式是由命题常元、命题变元、联结词、括号等组成的符号串，但并不是由这些符号任意组成的符号串都是命题公式。22.命题公式的定义由以下形成规则生成的公式叫命题公式

(简称公式)：

(1)命题变元和命题常元是命题公式。

(2)如果A、B是命题公式,则(┒A),(A∧B),(A∨B),(A→B),(A↔

B)是合式公式。

(3)只有有限次地使用(1)和(2)所得到的符号串才是命题公式。3例如：以下字符串就不是命题公式,因为它们不符合形成规则：

∧Q，(P→Q，P→∧Q，((PQ)∧R)

为了减少圆括号的使用,以后书写命题公式时，可按约定省略公式中的部分圆括号。4例用定义说明(P→(P∨Q))是命题公式。解：(i)P是命题公式 根据(1)(ii)Q是命题公式 根据(1)(iii)(P∨Q)是命题公式 根据(i)(ii)和(2)

(iv)(P→(P∨Q))是命题公式根据(i)(iii)和(2)

53.公式的赋值或解释（指派）如果一个命题公式含有命题变元，则它的真值是不确定的。只有对它的每个命题变元用指定的真值后，命题公式才变成命题，其真值才能唯一确定。定义设A为一个命题公式，P1,P2,…,Pn

为出现该公式中的所有的命题变元。分别给P1,P2,…,Pn

指定一个真值，则称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称这组值为A的成真赋值，若使A的值为假，则称这组值为A的成假赋值。6例

设命题公式A=p∧q→r则

110（p=1,q=1,r=0）为A的成假赋值。

111(p=1,q=1,r=1)是A的成真赋值。

011是A的成真赋值010是A的成真赋值。74.公式的真值表含n个命题变元的命题公式，共有2n组赋值。将命题公式在所有赋值下取值的情况列成表，称为命题公式的真值表。构造真值表的具体步骤如下：

(1)找出命题公式中所含的所有命题变元p1,p2,…,pn(若无下角标就按字典顺序给出)，列出所有可能的赋值(2n个)；—按二进制加法进行。

(2)按从低到高的顺序对命题公式进行分解；

(3)对应每个赋值，计算各列的值，直到最后计算出命题公式的值。8例(a)构造命题公式((P∨Q)∧P)和┒((P∨Q)∧P)

的真值表。解：该公式的真值表如下：9

(b)构造公式P↔Q与P∧Q∨┒P∧┒Q

的真值表。

两个命题公式，

如果有相同的真值，则称它们是逻辑等价命题。以上两个命题因后两列的真假值完全一致，

所以它们是逻辑等价命题。解：

P↔Q的真值表如下：10课堂练习构造下列命题公式的真值表。

(1)

┐q∨r(2)(q→r)∧(p→p)115.命题公式的分类根据在各种赋值下的取值情况，可将命题公式分为3类：定义设A为一个命题公式。

(1)若A在它的各种赋值下取值均为真，则称A为重言式或永真式。

(2)若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式。

(3)若A至少存在一组赋值是使A为真，则A是可满足式。由定义可知，重言式一定是可满足式，但反之不成立。12命题逻辑的重点是对重言式的研究，它在数理逻辑中起着重要作用。因为它有以下特点：

(1)重言式的否定是矛盾式，反之，矛盾式的否定是重言式。所以研究其一就可以了。

(2)两个重言式的合取、析取、蕴含、等值式都是重言式。(3)在重言式中有许多重要的逻辑恒等式和永真蕴含式，它们是逻辑推理的基础。

136.命题公式类型的判断方法

方法之一就是利用命题公式的真值表：若真值表最后一列全为1，则对应的命题公式为重言式；若最后一列全为0，则对应的命题公式为矛盾式；若最后一列既有0又有1，则对应的命题公式为非重言式的可满足式。

14第一章命题逻辑1.3命题公式的重言式15一.逻辑恒等式

设A(P1,P2,…,Pn)，B(P1,P2,…,Pn)是两个命题公式，这里Pi(i=1,2,…,n)不一定在两公式中同时出现。

如果A↔B是重言式，则A与B对任何解释都有相同的真值。记为A⇔B，叫做逻辑恒等式，读做“A恒等于B”。请注意符号↔与符号意义不同：

↔是逻辑联结词,而⇔是表示命题A和B有逻辑等价关系的符号,它的作用相当于代数中的“=”。161.判断两命题公式逻辑等价的方法—真值表法

设A，B为两命题公式，由定义判断A与B是否逻辑等价应判断A↔B是否为重言式，若A↔B的真值表最后一列全为1，则A↔B重言式，因而A⇔B。

而最后一列全为1当且仅当在各赋值之下，A与B的真值相同，因而判断A与B是否逻辑等价可简化为判断公式A，B的真值表是否相同。

17例判断下列命题公式是否逻辑等价？

(1)p∨q与┒p∨┒q(2)┒p∨┒q

与┒(p∨q)

0101001011101001101110110100qp18课堂练习判断下列命题公式是否逻辑等价。

(1)p→(q→r)与(p∧q)→r(2)(p→q)→r与(p∧q)→r192.基本逻辑恒等式1.双重否定律

2.等幂律3.交换律4.结合律5.分配律20基本逻辑恒等式6.德.摩根律7.吸收律8.零律9.同一律10.排中律11.矛盾律21基本逻辑恒等式12.蕴涵等值式13.等价等值式14.假言易位15.等价否定等值式16.归缪论223.代入规则和替换规则

(1).代入规则(RuleofSubstitution)

将逻辑恒等式的某个命题变元的所有出现可用一命题公式代入，其等式不变。就如同在代数式中，

若x

2-y2=(x+y)(x-y)则(a+b)2-(mn)2=(a+b+mn)(a+b-mn)一样。23例如：

对交换律：A∨B⇔B∨A若用p∧q代A，┒p∧r代B，就可得出逻辑恒等公式：(p∧q)∨(┒p∧r)

⇔(┒p∧r)∨(p∧q)若用┒p代A，┒p∧q∨r代B，可得就出逻辑恒等公式：┒p∨(┒p∧q∨r)⇔(┒p∧q∨r)∨┒p……24

(2).替换规则(RuleofReplacement)

设有恒等式A⇔B，若在公式C中出现A的地方,替换以B(不必每一处)而得到公式D，则C⇔D。

例如：对公式：

(P→Q)→R可利用公式P→Q⇔┒P∨Q，对其中的P→Q作替换。得公式

(P→Q)→R⇔(┒P∨Q)→R25应用1

判别下列公式的类型

解：由此可知，该式为重言式。

分配律矛盾律德.摩根律结合律排中律零律26应用2

证明公式恒等和对复合语句化简证明P∧┒Q∨Q⇔

P∨Q

证：P∧┒Q∨Q⇔

Q∨P∧┒Q⇔(Q∨P)∧(Q∨┒Q)⇔(Q∨P)∧1⇔

Q∨P⇔

P∨Q 27

(b)试将语句“情况并非如此:如果他不来,那么我也不去。”化简。

28┒(┒P→┒Q)⇔┒(┒┒P∨┒Q) ⇔┒┒┒P∧┒┒Q ⇔┒P∧Q ⇔

Q∧┒P 化简后的语句含义是：“我去了，而他不来”。

解设P：他要来，

Q：我要去。

则该复合语句可符号化为：┒(┒P→┒Q)。

再简化此公式：29(c)求P→(P↔Q)∨R的仅含∧和┒两种联结词的等价表达式。

30解：

P→(P↔Q)∨R⇔

P→(P→Q)∧(Q→P)∨R⇔┒P∨(┒P∨Q)∧(┒Q∨P)∨R⇔(┒P∨┒P∨Q)∧(┒P∨┒Q∨P)∨R⇔(┒P∨Q)∧(T∨┒Q)∨R⇔(┒P∨Q)∧T∨R

⇔┒P∨Q∨R

⇔┒(P∧┒Q∧┒R) 31应用3

在实际中的应用(1).试用较少的开关设计一个与下图有相同功能的电路。32解：可将上图所示之开关电路用下述命题公式表示：(P∧Q∧S)∨(P∧R∧S)利用基本等价公式，将上述公式转化为：

(P∧Q∧S)∨(P∧R∧S)

((P∧S)∧Q)∨((P∧S)∧R)

(P∧S)∧(Q∨R)所以其开关设计图可简化为：33(2)

设计一种简单的表决器，表决者每人身旁有一个按钮，当表决者同意时则按下按钮；否者不按按钮。当表决结果超过半数时主席台上的绿灯亮，否者红灯亮。为简单起见，设表决者仅有三人，试设计一个满足上述条件的表决器。34解：设三个表决者的按钮分别为P、Q、R。根据题意可知，主席台上绿灯亮的条件可表示成命题公式：(┒P∧Q∧R)∨(P∧┒Q∧R)∨(P∧Q∧┒R)∨(P∧Q∧R)对上述命题公式化简，得：⇔(P∧(Q∨R))∨(Q∧R)于是可用开关电路来设计该表决器。35(3)

在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断： 甲说王教授不是苏州人，是上海人。 乙说王教授不是上海人，是苏州人。 丙说王教授既不是上海人，也不是杭州人。听完以上3人的判断后，王教授笑着说，你们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？36解：分别设命题，P：王教授是苏州人。Q：王教授是上海人。R：王教授是杭州人。

则P、Q、R中必有一个真命题，两个假命题。要通过逻辑演算将真命题找出来，已知前提有：甲的判断为A1=┐P∧Q

乙的判断为A2=P∧┐Q

丙的判断为A3=┐Q∧┐R

37甲的判断全对

B1=A1=┐P∧Q甲的判断对一半 B2=(┐P∧┐Q)∨(P∧Q)甲的判断全错

B3=P∧┐Q乙的判断全对

C1=A2=P∧┐Q乙的判断对一半 C2=(P∧Q)∨(┐P∧┐Q)乙的判断全错

C3=┐P∧Q丙的判断全对

D1=A3=┐Q∧┐R丙的判断对一半 D2=(Q∧┐R)∨(┐Q∧R)丙的判断全错D3=Q∧R38根据王教授所说，则有 E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3) ∨(B2∧C3∧D1)∨(B2∨C1∧D2)∨(B3∧C2∧D1)为真命题。上述命题公式经过等价演算后,可得 E(┐P∧Q∧┐R)∨(P∧┐Q∧R)由题设，王教授不能既是上海人，又是杭州人，因而P、R中必有一个假命题，即P∧┐Q∧R0，于是 E┐P∧Q∧┐R为真命题，因而必有P、R为假命题，Q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。39(4)

在程序设计语言中，将程序简化：FFFTTTABBXYIFATHENIFBTHENXELSEYELSEIFBTHENXELSEY则在此程序中，执行X的条件是：(A∧B)∨(┒A∧B)执行Y的条件是：(A∧┒B)∨(┒A∧┒B)40可分别将两个命题公式化简：执行X的条件为：(Ａ∧Ｂ)∨(┐Ａ∧Ｂ)

Ｂ∧(Ａ∨┐Ａ)Ｂ

执行Y的条件为：(Ａ∧┐Ｂ)∨(┐Ａ∧┐Ｂ)

┐Ｂ∧(Ａ∨┐Ａ)┐Ｂ经转换后，这段程序可简化：IfBthenXelseY，其流程图如下图。STARTENDBXY41二.永真（重言）蕴含式

如果A→B是一永真式,那么称为永真（重言）蕴含式，记为A⇒B，读做“A永真蕴含B”。重言蕴含式可用真值表判定，也可用以下办法证明：(1)假定前件是真，若能推出后件是真，则此蕴含式是真。(2)假定后件是假，若能推出前件是假，则此蕴含式是真。42例1

证明：┒Q∧(P→Q)⇒┒P

方法2:

设┒P是假,则P是真。以下分情况讨论：

(i)若Q为真,则┒Q是假,所以┒Q∧(P→Q)是假。

(ii)若Q是假,则P→Q是假,所以┒Q∧(P→Q)是假。故┒Q∧(P→Q)⇒┒P。方法1:

设┒Q∧(P→Q)是真,则┒Q,P→Q是真。所以,Q是假,P是假。因而┒P是真。故┒Q∧(P→Q)⇒┒P

43常用的基本重言蕴含式44三.恒等式和重言蕴含式的两个性质

(1).若A⇔B,B⇔C

则A⇔C；若A⇒B,B⇒C则A⇒C。

即：逻辑恒等和重言蕴含都是传递的。

(2).若A⇒B，A⇒C，则A⇒B∧C。证(2)：因为A是真时，B和C都真。