第二章命题逻辑等值演算

1、第二章 命题逻辑等值演算本章内容n等值式基本等值式等值演算置换规则n析取范式和合取范式析取范式与合取范式主析取范式与主合取范式2.1 等值式n两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。n设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。2.1等值式2.1等值式(pq) (pq)的真值表 2.1等值式n例、例、 判断下列各组公式是否等值：（1）p(qr)与(pq)r （2）(pq)r与(pq)r 2.1 等值式n基本等值式2.1 等值式n基本等值式

2、（续）2.1 等值式n基本等值式（续）2.1 等值式n等值演算与置换规则2.1 等值式n应用举例证明两个公式等值2.1 等值式n例、证明两个公式不等值2.1 等值式n应用举例-判断公式类型2.1 等值式n应用举例-判断公式类型2.1 等值式n应用举例-判断公式类型2.2 析取范式与合取范式2.2 析取范式与合取范式2.2 析取范式与合取范式2.2 析取范式与合取范式2.2 析取范式与合取范式n命题公式的方式2.2 析取范式与合取范式n求公式的范式举例2.2 析取范式与合取范式n求公式的范式举例2.2 析取范式与合取范式n极大项与极小项2.2 析取范式与合取范式n极大项与极小项2.2 析取范式与

3、合取范式2.2 析取范式与合取范式n主析取范式与主合取范式2.2 析取范式与合取范式n主析取范式与主合取范式2.2 析取范式与合取范式n主析取范式与主合取范式求公式的主范式2.2 析取范式与合取范式n主析取范式与主合取范式求公式的主范式2.2 析取范式与合取范式n主析取范式与主合取范式求公式的主范式2.2 析取范式与合取范式n主析取范式与主合取范式求公式的主范式2.2 析取范式与合取范式n主范式的用途与真值表相同2.2 析取范式与合取范式n主范式的用途2.2 析取范式与合取范式n主范式的用途2.3 联接词的完备集nN元真值函数定义：就是有n个自变量的函数，其自变量和函数值都是真值为0或者1。一

4、元真值函数有4个2.3 联接词的完备集nN元真值函数二元真值函数有16个 2.3 联接词的完备集nN元真值函数一般地，n元真值函数共有多少个呢？每个自变量有2个取值方式，n个自变量共有2n 个不同取值方式。对n个自变量的每个取值方式，函数值有2个取值方式，即为0或1，故n元真值函数共有 个。例如，3元真值函数共有 =256个。 一般地，函数F:0,1n0,1称为n元真值函数，其中：0,1n为0，1的卡氏积。2.3 联接词的完备集n真值函数与命题公式的关系 对于每个真值函数，都可以找到许多与之等值的命题公式。以2元真值函数为例，所有矛盾式都与F0等值，所有的重言式都与F15等值。又如F13(pq

5、) (pq) (pq) (pq)(pq)(pq)。更重要的是，每个真值函数与唯一的一个主析取范式（主合取范式）等值。还以2元真值函数为例， 0（矛盾式）， （pq） m1， （pq） m2，（pq）（pq） m2m3, 反过来，每个主析取范式对应无穷多个与之等值的公式，所以每个真值函数对应无穷多个与之等值的命题公式。由定理2.5可知，每个命题公式对应唯一的与之等值的真值函数。2.3 联接词的完备集n联结词完备集 定义：定义：设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。联结词完备集。定理：定理：S=,是联结词完备集。n因为任何n

6、(n1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词,，所以S=,是联结词完备集。2.3 联接词的完备集n联结词完备集 以下联结词集都是完备集：n(1) S1=, n(2) S2=, n(3) S3=,n(4) S4=,n(5) S5=, 解答：n(1)，(2)的成立是显然的。n(3) 由于S=,是联结词完备集，因而任何真值函数都可以由仅含S中的联结词的公式表示。同时对于任意公式A,B,AB (AB) (AB),因而任意真值函数都可以由仅含S3 = ,中的联结词的公式表示，所以S3是联结词完备集。n(4) AB (AB)。 n(5） AB AB。2.3 联接词的完备集n单元素联结词构成的联结词完备集 设p、q为两个命题，复合命题“p与q的否定式”（“p或q的否定式”）称作p,q的与非式（或非与非式（或非式）式），记作pq(pq)。符号()称作与非联结与非联结词（或非联结词）词（或非联结词）。pq为真当且仅当p与q不同时为真（pq为真当且仅当p与q同时为假）。 pq(pq） pq(pq） 2.3 联接词的完备集n单元素联结词构成的联结词完备集 ，都是联结词完备集。 证证 已知,为联结词完备集，因而只需证明其中的每个联结词都可以由定义即可。而 n p (pp）