清华离散数学(第2版)：2.2-3

2.2 命题逻辑等值演算 2.2.1 等值式与等值演算– 等值式与基本等值式 – 真值表法与等值演算法

2.2.2 联结词完备集– 真值函数 – 联结词完备集 – 与非联结词和或非联结词1

等值式定义2.11 若等价式A B是重言式, 则称A与B等值, 记作 A B, 并称A B是等值式 说明: (1) 是元语言符号, 不要混同于 和= (2) A与B等值当且仅当A与B在所有可能赋值下的真值都相 同, 即A与B有相同的真值表 2n (3) n个命题变项的真值表共有 2 个, 故每个命题公式都有 无穷多个等值的命题公式 (4) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变 项称作A的哑元. 同样,在A中出现, 但不在B中出现的命题变 项称作B的哑元. 哑元的值不影响命题公式的真值. 2

真值表法例1 判断 (p q) 与 p q 是否等值 解 p q 0 0 0 1 1 0 1 1 p q 1 1 0 0 1 0 1 0 p q (p q) p q (p q) ( p q) 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1

结论: (p q) ( p q)3

真值表法(续)例2 判断下述3个公式之间的等值关系: p (q r), (p q) r, (p q) r 解 p q r p (q r) (p q) r 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 (p q) r 1 1 1 1 1 1 0 14

p (q r)与(p q) r等值, 但与(p q) r不等值

基本等值式双重否定律 幂等律 交换律 结合律 分配律 A A A A A, A A A A B B A, A B B A (A B) C A (B C) (A B) C A (B C) A (B C) (A B) (A C) A (B C) (A B) (A C) (A B) A B (A B) A B A (A B) A, A (A B) A5

德摩根律吸收律

基本等值式(续)零律 同一律 排中律 矛盾律 蕴涵等值式 等价等值式 A 1 1, A A 1 A A 0 A B A B A B (A B) (B A) A 0 0 A 0 A, A 1 A

假言易位归谬论

A B B A(A B) (A B) A6

等价否定等值式 A B A B

等值演算等值演算: 由已知的等值式推演出新的等值式的过程 置换规则: 若A B, 则 (B) (A) 例3 证明 p (q r) (p q) r 证 p (q r) p ( q r) (蕴涵等值式)

( p q) r (p q) r (p q) r

(结合律)(德摩根律) (蕴涵等值式)7

实例等值演算不能直接证明两个公式不等值. 证明两个公式不等值的基本思想是找到一个赋值使一个成真, 另一个成假.

例4 证明: p (q r)

(p q) r

方法一 真值表法(见例2) 方法二 观察法. 容易看出000使左边成真, 使右边成假. 方法三 先用等值演算化简公式, 再观察.

实例例5 用等值演算法判断下列公式的类型

(1) q (p q)解 q (p q) (德摩根律) (交换律，结合律) (矛盾律) (零律) q ( p q) (蕴

涵等值式) q (p q) p (q q) p 0 0 该式为矛盾式.9

实例(续)(2) (p q) ( q p)解 (p q) ( q p) ( p q) (q p) (蕴涵等值式)

( p q) ( p q) (交换律) 1 该式为重言式.

实例(续)(3) ((p q) (p q)) r) 解 ((p q) (p q)) r) (分配律) (排中律) (同一律) (p (q q)) r p 1 r p r

非重言式的可满足式.如101是它的成真赋值,000是它的

成假赋值.总结:A为矛盾式当且仅当A 0; A为重言式当且仅当A 1 说明:演算步骤不惟一,应尽量使演算短些11

真值函数定义2.12 称F:{0,1}n {0,1}为n元真值函数n元真值函数共有 2 个 每一个命题公式对应于一个真值函数 每一个真值函数对应无穷多个命题公式 1元真值函数2n

p0 1

F0(1) 00

F1(1) 01

F2(1) 10

F3(1) 1112

2元真值函数 p q 0 0 1 1 0 1 0 1F0( 2 ) F1( 2 ) F2( 2 ) F3( 2 ) F4( 2 ) F5( 2 ) F6( 2 ) F7( 2 )

0 0 0 0F8( 2 )

0 0 0 1F9( 2 )

0 0 1 0( F102 )

0 0 1 1( F112 )

0 1 0 0( F122 )

0 1 0 1( F132 )

0 1 1 0( F142 )

0 1 1 1( F152 )

p q 0 0 1 1 0 1 0 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 113

联结词完备集定义2.13 设S是一个联结词集合, 如果任何n(n 1) 元真值 函数都可以由仅含S中的联结词构成的公式表示,则称S是 联结词完备集

定理2.1 下述联结词集合都是完备集: (1) S1={ , , , , } (2) S2={ , , , } A B (A B) (B A) (3) S3={ , , } A B A B (4) S4={ , } A B (A B) ( A B) (5) S5={ , } A B ( A B) A B ( A) B A B (6) S6={ , }14

复合联结词与非式: p q (p q), 称作与非联结词 或非式: p q (p q), 称作或非联结词p q为真当且仅当p,q不同时为真 p q为真当且仅当p,q不同时为假 定理2.2 { },{ }是联结词完备集 证 p (p p) p p p q (p q) (p q) (p q) (p q) 得证{ }是联结词完备集. 对于{ }可类似证明.15

2.3 范式 2.3.1 析取范式与合取范式– 简单析取式与简单合取式 – 析取范式与合取范式

2.3.2 主析取范式与主合取范式– 极小项与极大项 – 主析取范式与主合取范式 – 主范式的用途16

简单析取式与简单合取式文字:命题变项及其否定的统称 简单析取式:有限个文字构成的析取式 如 p, q, p q, p q r, … 简单合取式:有限个文字构成的合取式 如 p, q, p q, p q r, … 定理2.3 (1) 一个简单析取式是重言式当且仅当它同时含 某个命题变项和它的否定 (2) 一个简单合取式是矛盾式当且仅当它同时含某个命题 变项和它的否定17

析取范式与合取范式析取范式:由有

限个简单合取式组成的析取式 A1 A2 Ar, 其中A1,A2, ,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1 A2 Ar , 其中A1,A2, ,Ar是简单析取式 范式:析取范式与合取范式的统称 定理2.4 (1) 一个析取范式是矛盾式当且仅当它的每一个 简单合取式都是矛盾式 (2) 一个合取范式是重言式当且仅当它的每一个简单析取 式都是重言式18

范式存在定理定理2.5 任何命题公式都存在着与之等值的析取范式与 …… 此处隐藏：1634字，全部文档内容请下载后查看。喜欢就下载吧 ……