第一命题逻辑等值演算

1第1页，共19页，2023年，2月20日，星期一等值式

定义若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式说明：定义中，A,B,均为元语言符号,A或B中可能有哑元出现.例如，在(pq)((pq)(rr))中，r为左边公式的哑元.

用真值表可验证两个公式是否等值请验证：p(qr)(pq)rp(qr)(pq)r

第2页，共19页，2023年，2月20日，星期一基本等值式

双重否定律

:AA等幂律：

AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)第3页，共19页，2023年，2月20日，星期一基本等值式(续)德·摩根律:(AB)AB

(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,

A1A排中律:AA1矛盾律:AA0第4页，共19页，2023年，2月20日，星期一基本等值式(续)蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础第5页，共19页，2023年，2月20日，星期一等值演算与置换规则

等值演算:

由已知的等值式推演出新的等值式的过程置换规则：若AB,则(B)(A)

等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式

(3)置换规则第6页，共19页，2023年，2月20日，星期一应用举例——证明两个公式等值

例1证明

p(qr)(pq)r证

p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r

（结合律，置换规则）(pq)r

（德摩根律，置换规则）(pq)r

（蕴涵等值式，置换规则）

说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出

第7页，共19页，2023年，2月20日，星期一应用举例——证明两个公式不等值例2证明:p(qr)(pq)r

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

方法一真值表法（自己证）方法二观察赋值法.容易看出000,010等是左边的的成真赋值，是右边的成假赋值.

方法三用等值演算先化简两个公式，再观察.第8页，共19页，2023年，2月20日，星期一应用举例——判断公式类型

例3

用等值演算法判断下列公式的类型(1)q(pq)

解q(pq)

q(pq)（蕴涵等值式）

q(pq)（德摩根律）

p(qq)（交换律，结合律）

p0（矛盾律）

0（零律）由最后一步可知，该式为矛盾式.

第9页，共19页，2023年，2月20日，星期一例3(续)(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)（蕴涵等值式）

(pq)(pq)（交换律）

1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？

第10页，共19页，2023年，2月20日，星期一例3(续)(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些第11页，共19页，2023年，2月20日，星期一1.4联结词全功能集

复合联结词排斥或与非式或非式真值函数联结词全功能集第12页，共19页，2023年，2月20日，星期一复合联结词

排斥或:pq(pq)(pq)与非式:pq(pq)或非式:pq(pq)

第13页，共19页，2023年，2月20日，星期一真值函數

问题：含n个命题变项的所有公式共产生多少个互不相同的真值表？答案为个，为什么？定义

称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:{0,1}n{0,1}表示F是n元真值函数.

共有个n元真值函数.例如F:{0,1}2{0,1}，且F(00)=F(01)=F(11)=0，F(01)=1，则F为一个确定的2元真值函数.第14页，共19页，2023年，2月20日，星期一命题公式与真值函数

对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.

例如：pq,pq,(pq)((pq)q)等都对应表中的第15页，共19页，2023年，2月20日，星期一2元真值函数对应的真值表pq00010111

00000000000011110011001101010101

pq00010111

11111111000011110011001101010101

第16页，共19页，2023年，2月20日，星期一联结词的全功能集

定义

在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集{,,,,}中，由于

pqpq,所以，为冗余的联结词;类似地，也是冗余的联结词.又在{,,}中，由于

pq(pq)，所以，是冗余的联结词.类似地，也是冗余的联结词.

第17页，共19页，2023年，2月20日，星期一联结词的全功能集(续)定义

设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.

若S1,S2是两个联结词集合，且S1

S2.若S1是全功能集，则S2也是全功能集.

第18页，共19页，2023