第二章-命题逻辑等值演算课件

第二章命题逻辑等值演算第二章命题逻辑等值演算1本章内容等值式基本等值式等值演算置换规则析取范式和合取范式析取范式与合取范式主析取范式与主合取范式本章内容等值式22.1等值式两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式A↔B应为重言式。2.1等值式两公式什么时候代表了同一个命题呢？32.1等值式2.1等值式42.1等值式(p∨q)↔(┐p∧┐q)的真值表2.1等值式(p∨q)↔(┐p∧┐q)的真值表52.1等值式例、判断下列各组公式是否等值：（1）p→(q→r)与(p∧q)→r（2）(p→q)→r与(p∧q)→r2.1等值式例、判断下列各组公式是否等值：62.1等值式基本等值式2.1等值式基本等值式72.1等值式基本等值式（续）2.1等值式基本等值式（续）82.1等值式基本等值式（续）2.1等值式基本等值式（续）92.1等值式等值演算与置换规则2.1等值式等值演算与置换规则102.1等值式应用举例——证明两个公式等值2.1等值式应用举例——证明两个公式等值112.1等值式例、证明两个公式不等值2.1等值式例、证明两个公式不等值122.1等值式应用举例---判断公式类型2.1等值式应用举例---判断公式类型132.1等值式应用举例---判断公式类型2.1等值式应用举例---判断公式类型142.1等值式应用举例---判断公式类型2.1等值式应用举例---判断公式类型152.2析取范式与合取范式2.2析取范式与合取范式162.2析取范式与合取范式2.2析取范式与合取范式172.2析取范式与合取范式2.2析取范式与合取范式182.2析取范式与合取范式2.2析取范式与合取范式192.2析取范式与合取范式命题公式的方式2.2析取范式与合取范式命题公式的方式202.2析取范式与合取范式求公式的范式举例2.2析取范式与合取范式求公式的范式举例212.2析取范式与合取范式求公式的范式举例2.2析取范式与合取范式求公式的范式举例222.2析取范式与合取范式极大项与极小项2.2析取范式与合取范式极大项与极小项232.2析取范式与合取范式极大项与极小项2.2析取范式与合取范式极大项与极小项242.2析取范式与合取范式2.2析取范式与合取范式252.2析取范式与合取范式主析取范式与主合取范式2.2析取范式与合取范式主析取范式与主合取范式262.2析取范式与合取范式主析取范式与主合取范式2.2析取范式与合取范式主析取范式与主合取范式272.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式282.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式292.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式302.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式312.2析取范式与合取范式主范式的用途——与真值表相同2.2析取范式与合取范式主范式的用途——与真值表相同322.2析取范式与合取范式主范式的用途2.2析取范式与合取范式主范式的用途332.2析取范式与合取范式主范式的用途2.2析取范式与合取范式主范式的用途342.3联接词的完备集N元真值函数定义：就是有n个自变量的函数，其自变量和函数值都是真值为0或者1。一元真值函数有4个2.3联接词的完备集N元真值函数352.3联接词的完备集N元真值函数二元真值函数有16个2.3联接词的完备集N元真值函数362.3联接词的完备集N元真值函数一般地，n元真值函数共有多少个呢？每个自变量有2个取值方式，n个自变量共有2n个不同取值方式。对n个自变量的每个取值方式，函数值有2个取值方式，即为0或1，故n元真值函数共有个。例如，3元真值函数共有=256个。

一般地，函数F:{0,1}n→{0,1}称为n元真值函数，其中：{0,1}n为{0，1}的卡氏积。

2.3联接词的完备集N元真值函数372.3联接词的完备集真值函数与命题公式的关系对于每个真值函数，都可以找到许多与之等值的命题公式。以2元真值函数为例，所有矛盾式都与F0等值，所有的重言式都与F15等值。又如F13↔(p→q)↔(┐p∨q)↔┐(p∧┐q)↔(┐p∧┐q)∨(┐p∧q)∨(p∧q)。更重要的是，每个真值函数与唯一的一个主析取范式（主合取范式）等值。还以2元真值函数为例，0（矛盾式），（p∧q）m1，（p∧┐q）m2，（p∧┐q）∨（p∧q）m2∨m3,…反过来，每个主析取范式对应无穷多个与之等值的公式，所以每个真值函数对应无穷多个与之等值的命题公式。由定理2.5可知，每个命题公式对应唯一的与之等值的真值函数。2.3联接词的完备集真值函数与命题公式的关系382.3联接词的完备集联结词完备集定义：设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理：S={┐,∧,∨}是联结词完备集。因为任何n(n≥1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词┐,∧,∨，所以S={┐,∧,∨}是联结词完备集。2.3联接词的完备集联结词完备集392.3联接词的完备集联结词完备集以下联结词集都是完备集：(1)S1={┐,∧,∨,→}(2)S2={┐,∧,∨,→,}(3)S3={┐,∧}(4)S4={┐,∨}(5)S5={┐,→}解答：(1)，(2)的成立是显然的。(3)由于S={┐,∧,∨}是联结词完备集，因而任何真值函数都可以由仅含S中的联结词的公式表示。同时对于任意公式A,B,A∨B┐┐(A∨B)┐(┐A∧┐B),因而任意真值函数都可以由仅含S3={┐,∧}中的联结词的公式表示，所以S3是联结词完备集。(4)A∧B┐(┐A∨┐B)。(5）A∨B┐A→B。2.3联接词的完备集联结词完备集402.3联接词的完备集单元素联结词构成的联结词完备集设p、q为两个命题，复合命题“p与q的否定式”（“p或q的否定式”）称作p,q的与非式（或非式），记作p↑q(p↓q)。符号↑(↓)称作与非联结词（或非联结词）。p↑q为真当且仅当p与q不同时为真（p↓q为真当且仅当p与q同时为假）。

p↑q↔┐(p∧q）p↓q↔┐(p∨q）2.3联接词的完备集单元素联结词构成的联结词完备集412.3联接词的完备集单元素联结词构成的联结词完备集{↑}，{↓}都是联结词完备集。证已知{┐,∧,∨}为联结词完备集，因而只需证明其中的每个联结词都可以由↑定义即可。而

┐p↔┐(p∧p）↔p↑p；p∧q↔┐┐(p∧q)↔┐(p↑q)↔(p↑q