资源描述:
《命题逻辑等值演算》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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、委会,该班的甲、乙、丙三名学生预言:甲