命题逻辑等值演算.doc

第二章命题逻辑等值演算
例1 . 设三元真值函数f为:
f(0,0,0)=0,f(0,0,1)=1,f(0,1,0)=0,f(1,0,0)=1
f(0,1,1)=1,f(1,0,1)=1,f(1,1,0)=0,f(1,1,1)=1
试用一个仅含联结词,的命题形式来表示f 。
解:根据三元真值函数f的定义,可知其具有以下真值表:
P
Q
R
f(P,Q,R)
T
T
T
T
T
T
F
F
T
F
T
T
T
F
F
T
F
T
T
T
F
T
F
F
F
F
T
T
F
F
F
F
则根据真值表法可以求出f的主合取范式为:
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
而:
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
(P∨Q∨R)∧(P∨R)
((P∨Q)∧P)∨R
(P∧Q)∨R
又由于:
P∧Q(PQ) P∨QP Q
所以,
(P∧Q) ∨R
( P∧Q)R
((PQ))R
所以,f可以用仅含,的命题((PQ))R来表示。
例2 . 不用真值表判断下列公式是永真式、永假式还是其它。
(P∨Q)(P∧Q) ;
((QP)∨P)∧(P∨R) ;
((P∨Q)R)((P∨Q)∨R) .
解:(1) (P∨Q)(P∧Q) (P∨Q)∨(P∧Q) (P∧Q)∨(P∧Q)
所以,(P∨Q)(P∧Q)既非永真式也非永假式。
(2) ((QP)∨P)∧(P∨R) ((Q∨P)∨P)∧(P∨R)
T∧(P∨R) F∧(P∨R) F
所以,((QP)∨P)∧(P∨R)为永假式。
(3) ((P∨Q)R)((P∨Q)∨R) ((P∨Q)∨R)((P∨Q)∨R)
((P∨Q)∨R)((P∨Q)∨R) T
所以,((P∨Q)R)((P∨Q)∨R)为永真式。
例3 . 证明下列等价式。
(1)(PQ)∧(PR) PQ∧R ;
(2)P∧Q∧(P∨Q) P∧Q∧(P∨Q) .
解:说明: 这两道题看似麻烦,但是如果不采用直接推导的方法,而是利用范式或是左右夹击推导的方法,会起到事半功倍的效果。
(1). (PQ)∧(PR) (P∨Q)∧(P∨R)
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
M4∧M5∧M6
PQ∧R P∨(Q∧R) (P∨Q)∧(P∨R)
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
M4∧M5∧M6
所以,(PQ)∧(PR) PQ∧R成立。
(2). P∧Q∧(P∨Q)
(P∧Q∧P)∨(P∧Q∧Q)
F
P∧Q∧(P∨Q)
(P∧Q∧P)∨(P∧Q∧Q)
F
所以,P∧Q∧(P∨Q) P∧Q∧(P∨Q)
例4 . 试求下列各公式的主析取范式和主合取范式。
(P(Q∧R))∧(P(QR))
((P∨Q)R)P
解: (1) (P(Q∧R))∧(P(QR)) (P∨(Q∧R))∧(P∨(Q∨R))
(P∨Q)∧(P∨R)∧(P∨Q∨R)
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
M4∧M5∧M6∧M0 (主合取范式)
则其主析取范式为m1∨m2∨m3∨m7
(2) ((P∨Q)R)P ((P∨Q)