第8讲 命题公式的真值表与等值 主要内容: 1.命题公式的真值表. 2.命题公式的等值的定义,记住常见的命题公式的等值式.

3.3 命题公式及其真值表 有了前面的两节内容, 就可以得到命题逻辑的符号体系. 由于所讲内容侧重于在后继课程中的应用, 我们不给出逻辑演算系统的形式语言的定义. 1.命题公式的定义 这里的命题公式就是逻辑函数或逻辑表达式, 其中的常量是逻辑常量1和0, 其中的变元是命题变元或逻辑变量.

命题公式是由命题常量、命题变元、逻辑联结词、左圆括号(及由圆括号)构成的有意义(well-formed)的符号串, 其严格定义需借助于递归定义方式给出. Def (1)1, 0, p, q, r, … (2)A  (A) (3)A, B  (4)有限次应用(1)(2)(3)所得到的符号串是仅有的命题公式.

命题公式可称为合式公式(well-formed formula, WFF)或简称为公式,其全称为命题合式公式 命题公式可称为合式公式(well-formed formula, WFF)或简称为公式,其全称为命题合式公式. 这儿的公式实际上是书写正确、含义清楚的表达式或者说符号串,与以前所学过的公式含义不尽一致. 上面已经谈到,命题公式是逻辑函数(它与形式系统中的WFF的定义不尽一致),可以借助于函数给命题公式下定义.

严格按照命题公式的定义,就会出现很多的括号 严格按照命题公式的定义,就会出现很多的括号. 一方面,这些括号使命题公式的结构清晰、含义清楚；而另一方面,括号太多给命题公式的阅读和书写带来不便. 因此,特作如下一些可以省略括号的约定: (1)最外层的括号可以省略. 在形成最终的命题公式时, 所有的中间过程得到的命题公式,包含其本身,都称为该命题公式的子公式.

(2) 9个联结词运算的优先顺序依次为: 符合本约定的有些括号可以不写. 如命题公式 Remark 这种规定不是唯一的.

(3)同级运算从左至右依次进行. 如 实际上, 在对命题进行符号化时, 只要书写正确的逻辑函数都是命题公式.

2.命题的符号化 命题的符号化就是使用符号—命题变元、逻辑联结词和括号将所给出的命题表示出来. 一方面说明, 符号体系来源于实际问题,另一方面也是给出进一步学习逻辑演算系统的语义解释时的一种标准模型. 命题的符号化的步骤: Step 1 找出所给命题的所有原子命题, 并用小写英文字母或带下标表示； Step 2 确定应使用的联结词,进而将原命题用符号表示出来.

例3-7(P81) 将下列命题符号化. (1)天气很好或很热. (2)如果张三和李四都不去,那么我就去. (3)仅当你走, 我留下. (4)我今天进城, 除非天下雨. (5)你只有刻苦学习, 才能取得好成绩. Hint (1) 或? (2) “张三不去”是复合命题. (3)p: 你走, q: 我留下, 仅当?

(4)p: 我今天进城, q: 天下雨. 除非 = 如果不. (5)p:你刻苦学习, q: 你取得好成绩. 只有p, 才q?

3.命题公式的真值表 对于命题公式,若对中出现的每个命题变元都指定一个真值1或者0,就对命题公式A进行了一种真值指派(assignment)或一个解释(interpretation),而在该指派下会求出公式A的一个真值. 将A的所有可能的真值指派以及在每一个真值指派下的取值列成一个表,就得到命题公式A的真值表(truth table). 例3-8 写出命题公式 的真值表.

p q r p pq (pq) r 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

要求大家能准确写出一个命题公式的真值表,这是本节的重点内容,当然必须牢记联结词的运算表才行. 由表知,含3个命题变元的命题公式有8 = 23 种不同的真值指派. 很显然,含2个命题变元的命题公式有4 = 22 种不同的真值指派. 一般来说,含n个命题变元的命题公式的不同的真值指派有2n种.

4.命题公式的类型 (1)在任何指派下均取真的命题公式称为永真式或重言式(tautology)； (2)在任何指派下均取假的命题公式称为永假式或矛盾式(contradiction)； (3)至少有一种指派使其为真的命题公式称为可满足式(contingency, satisfactable formula)； (4)至少有一种指派使其为真同时至少有一种指派使其为假的命题公式称为中性式(neutral formula).

命题公式的分类 例3-9 真值表法? p q pq pq 1 1 1 1 0 0 1 0 0

例3-10 Proof 由A =1可推出B = 1, 则A  B永真. 由B =0可推出A = 0, 则A  B永真. 取值法? (本质上是真值表法)

最后介绍永真式的代入定理RS(Rule of Substitution). Theorem 3-1(永真式的代入定理) Proof 显然. 如何使用?

3.4 逻辑等值的命题公式 我们经常将一个命题, 如“四边形的对边平行”转换成与之逻辑等价的命题 “四边形的对边相等”, 所谓逻辑等价是指由“四边形的对边平行”可得出“四边形的对边相等”, 且由“四边形的对边相等”可得出“四边形的对边平行”. 显然, 这两个命题的真值是相同的，这时称这两个命题是逻辑等值的. 下面讨论两个命题公式逻辑等值.

1.逻辑等值的定义 Def 给定两个命题公式A和B, 若在任何真值指派下A和B的真值都相同,则称命题公式A和B逻辑等价或逻辑等值(logically equal)或简称为等值或相等,记为 A = B. Remark A  B与 A = B(A  B)是不同的. Proof ? Theorem 3-2 A = B的充要条件是A  B永真. 下面的例子说明如何利用真值表证明两个命题公式等值.

例3-11 证明 Proof p q pq pq pq (pq)(pq) 1 1 1 1 0 0 1 0 0

Theorem 3-3(P86) 例如, Theorem 3-4 逻辑等值是命题公式间的等价关系:(1)自反.(2)对称.(3)传递.

2.基本等值式 (I)与, , 有关的等值式 Theorem 3-5(P86) Remarks (1)与集合的有关性质类似. (2)每条性质均可证明.

(II)其他重要的等值式 Theorem (1) (2) (3) (4) (5) (6) Proof(?)

3.等值演算法 基本等值式有很多用途,如化简命题公式、判断命题公式的类型、证明等值式、计算命题公式的范式、命题逻辑中的推理等,要求大家要熟记,特别是定理3-5中的等值式. 在使用等值式时,下列的等值置换定理RR (Rule of Replacement)是至关重要的,它的证明是显然的. 等值置换定理 设C是命题公式A的子公式,若C = D, 则将A中的C部分或全部替换为D所得到的命题公式与A等值.

利用基本等值式以及等值置换定理求解问题的方法称为“等值演算法”. 例3-13(P87) 化简(?)下列命题公式并将最后结果用只含和表示. (1) (2) Solution (1) 数字逻辑,计算机组成中经常化简单!

利用等值演算法, 判断一个命题公式的类型是比较方便的. 例3-14(P88) 设A, B, C是任意的命题公式,判断下列命题公式的类型: (1) (2) Solution (2)

两个命题公式等值,可以根据定义,利用真值表进行证明. 下面是证明两个命题公式等值的等值演算法. 例3-15(P88) 设A, B, C是任意的命题公式,证明下列等值式. (1) (2) Proof (2)

4.对偶原理 在与, , 有关的基本等值式中,除性质(1)外,其它性质都是成对出现的,两者间有一定的联系. 先给出命题公式的对偶式的定义. Def 3-4 设命题公式A中只含有3个逻辑联结词, ,  , 将A中的换成 ；A中的换成 ；A中的1换成0；A中的0换成1, 所得到的命题公式称为是A的对偶式(dual formula), 记为A*. 例 Remark 一般来说

根据De Morgan律可以证明下面的对偶定理. 对偶原理 设A和B是命题公式, 若A = B, 则A* = B*. 有了对偶原理后, 定理3-5中除性质(1)外的等值式,只需要记住其中一个就可以了. 同时,有了对偶原理,我们可以求出任意命题公式的对偶式.