资源描述：
《命题逻辑等值演算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章命题逻辑等值演算例1.设三元真值函数f为：f（0,0,0）＝0，f（0,0,1）＝1，f（0,1,0）＝0，f（1,0,0）＝1f（0,1,1）＝1，f（1,0,1）＝1，f（1,1,0）＝0，f（1,1,1）＝1试用一个仅含联结词，的命题形式来表示f。解：根据三元真值函数f的定义，可知其具有以下真值表：PQRf(P,Q,R)TTTTTTFFTFTTTFFTFTTTFTFFFFTTFFFF则根据真值表法可以求出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
2、∨Q)∧P)∨R(P∧Q)∨R又由于：P∧Q(PQ)P∨QPQ所以，(P∧Q)∨R(P∧Q)R((PQ))R所以，f可以用仅含，的命题((PQ))R来表示。例2.不用真值表判断下列公式是永真式、永假式还是其它。(1)(P∨Q)(P∧Q);(2)((QP)∨P)∧(P∨R);(1)((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、为永假式。（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∧M6PQ∧RP∨(Q∧R)(P∨Q)∧(P∨R)(P∨Q∨R)∧(P∨
4、Q∨R)∧(P∨Q∨R)M4∧M5∧M6所以，(PQ)∧(PR)PQ∧R成立。(2).P∧Q∧(P∨Q)(P∧Q∧P)∨(P∧Q∧Q)FP∧Q∧(P∨Q)(P∧Q∧P)∨(P∧Q∧Q)F所以，P∧Q∧(P∨Q)P∧Q∧(P∨Q)例4.试求下列各公式的主析取范式和主合取范式。(1)(P(Q∧R))∧(P(QR))(2)((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(主合取范式)则其主析取范式
5、为m1∨m2∨m3∨m7(2)((P∨Q)R)P((P∨Q)∨R)∨P((P∨Q)∧R)∨P(P∧R)∨(Q∧R)∨P(Q∧R)∨P(Q∨P)∧(R∨P)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1∧M3(主合取范式)则其主析取范式为m2∨m4∨m5∨m6∨m7例5.用等值演算法证明下面等值式。(1)P(P∧Q)∨(P∧Q)(2)(PQ)∧(PR)P(Q∧R)(3)(PQ)(P∨Q)∧(P∧Q)(4)(P∧Q)∨(P∧Q)(P∨Q)∧(P∧Q)解:(1)右边P∧(P∨Q)∧(P∨Q)∧(Q∨Q)P∧(P∨Q∧Q)∧TP∧PP左边所以P(P∧Q)∨(
6、P∧Q)(2)左边(P∨Q)∧(P∨R)P∨Q∧RP(Q∧R)右边所以(PQ)∧(PR)P(Q∧R)(3)左边((PQ)∧(QP))(P∨Q)∨(Q∨P)P∧Q∨Q∧P(P∨Q)∧(P∨P)∧(Q∨Q)∧(Q∨P)(P∨Q)∧(Q∨P)(P∨Q)∧(P∧Q)右边所以(PQ)(P∨Q)∧(P∧Q)(4)左边(P∧Q)∨(P∧Q)(P∨P)∧(P∨Q)∧(Q∨P)∧(Q∨Q)(P∨Q)∧(Q∨P)(P∨Q)∧(P∧Q)右边所以(P∧Q)∨(P∧Q)(P∨Q)∧(P∧Q)例6.将下列公式化成与之等值且只含{,∨,∧}中联结词的公式。(1)(P(Q(Q∧R)))(2)
7、P(QR)解：(1)(P(Q(Q∧R)))(P∨(Q(Q∧R))∧((Q∧R)Q))(P∨(Q∨(Q∧R))∧((Q∧R)∨Q))(P∨(Q∨R))P∧Q∧R(2)P(QR)(P(QR))∧((QR)P)(P((QR)∧(RQ)))∧(((QR)∧(RQ))P)(P∨(Q∨R)∧(R∨Q))∧(((QR)∧(RQ))∨P)(P∨(Q∨R)∧(R∨Q))∧((Q∨R)∨(R∨Q)∨P)(P∨Q∧R∨R∧Q)∧(Q∧R∨R∧Q∨P)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)例7.在某班班委成员的选举中，已知王小红、李强、丁金生三位同学被选进了班
8、委会，该班的甲、乙、丙三名学生预言：甲
