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

第二章命题逻辑等值演算本章内容等值式基本等值式等值演算置换规则析取范式和合取范式析取范式与合取范式主析取范式与主合取范式2.1等值式两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式A↔B应为重言式。2.1等值式2.1等值式(p∨q)↔(┐p∧┐q)的真值表2.1等值式例、判断下列各组公式是否等值：（1）p→(q→r)与(p∧q)→r（2）(p→q)→r与(p∧q)→r2.1等值式基本等值式2.1等值式基本等值式（续）2.1等值式基本等值式（续）2.1等值式等值演算与置换规则2.1等值式应用举例——证明两个公式等值2.1等值式例、证明两个公式不等值2.1等值式应用举例---判断公式类型2.1等值式应用举例---判断公式类型2.1等值式应用举例---判断公式类型2.2析取范式与合取范式2.2析取范式与合取范式2.2析取范式与合取范式2.2析取范式与合取范式2.2析取范式与合取范式命题公式的方式2.2析取范式与合取范式求公式的范式举例2.2析取范式与合取范式求公式的范式举例2.2析取范式与合取范式极大项与极小项2.2析取范式与合取范式极大项与极小项2.2析取范式与合取范式2.2析取范式与合取范式主析取范式与主合取范式2.2析取范式与合取范式主析取范式与主合取范式2.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主析取范式与主合取范式求公式的主范式2.2析取范式与合取范式主范式的用途——与真值表相同2.2析取范式与合取范式主范式的用途2.2析取范式与合取范式主范式的用途2.3联接词的完备集N元真值函数定义：就是有n个自变量的函数，其自变量和函数值都是真值为0或者1。一元真值函数有4个2.3联接词的完备集N元真值函数二元真值函数有16个2.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联接词的完备集真值函数与命题公式的关系对于每个真值函数，都可以找到许多与之等值的命题公式。以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联接词的完备集联结词完备集定义：设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理：S={┐,∧,∨}是联结词完备集。因为任何n(n≥1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词┐,∧,∨，所以S={┐,∧,∨}是联结词完备集。2.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联接词的完备集单元素联结词构成的联结词完备集设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联接词的完备集单元素联结词构成的联结词完备集{↑}，{↓}都是联结词完备集。证已知{┐,∧,∨}为联结词完备集，因而只需证明其中的每个联结词都可以由↑定义即可。而┐p↔┐(p∧p）↔p↑p；p∧q↔┐┐(p∧q)↔┐(p↑q)↔(p↑q)↑(p↑q)；p∨q↔┐┐(p∨q)↔┐(┐p∧┐q)↔┐p↑┐q↔(p↑p)↑(q↑q)；由上可知{↑}是联结词完备集，类似可证{↓}是联结词完备集。↑，↓都是二元联结词。EndofChapter2