命题逻辑等值演算

第二章命题逻辑等值演算例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∨Q)∧P)∨R(P∧Q)∨R又由于：P∧Q(PQ)P∨QPQ所以，(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∧M6PQ∧RP∨(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)FP∧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)PT:(P∧Q)∨(P∧Q)U:(R∧S)∨(R∧S)W:(M∧N)∨(M∧N)根据题意得GT∧U∧WT，于是GT∧U∧W((P∧Q)∨(P∧Q))∧((R∧S)∨(R∧S))∧W((P∧Q∧R∧S)∨(P∧Q∧R∧S)∨(P∧Q∧R∧S)∨(P∧Q∧R∧S))∧W由于P和R不能同时为真，Q和S不能同时为真，P和S不能同时为真（因为这样不符合题意），故上式变为：G(P∧Q∧R∧S)∧((M∧N)∨(M∧N))(P∧Q∧R∧S∧M∧N)∨(P∧Q∧R∧S∧M∧N)由于P,R,M不能同时为真，P,S,N不能同时为真（因为这样不符合题意），则上式仅剩一项P∧Q∧R∧S∧M∧N，可见王小红不是班长，李强是生活委员，丁金生是班长，王小红不是生活委员，李强不是班长，王小红是学习委员，于是得到：王小红是学习委员，李强是生活委员，丁金生是班长。例8.（讨论题）试用多种方法证明蕴含式P∧Q(PQ)解:方法一：只要证明P∧Q(PQ)是永真式。P∧Q(PQ)(P∧Q)∨(P∨Q)P∨Q∨P∨QQ∨P∨QT即为永真式，故P∧Q(PQ)成立。方法二：设P∧Q为T，则P和Q都为T，则PQ为T，故P∧Q(PQ)。方法三：设PQ为F，则P为T，Q为F，则P∧Q为F，故P∧Q(PQ)。例9.（讨论题）联结词“”和“”服从结合律么？解：联结词“”和“”均不服从结合律。证明方法有以下两种：方法一：(PQ)R((P∧Q)∧R)(P∧Q)∨R而P(QR)(P∧(Q∧R))P∨(Q∧R)一般而言(P∧Q)∨R与P∨(P∧Q)是不等价的,故联结词“”不服从结合律。(PQ)R((P∨Q)∨R)(P∨Q)∧R而P(QR)(P∨(Q∨R))P∧(Q∨R)一般而言(P∨Q)∧R与P∧(Q∨R)是不等价的，故联结词“”不服从结合律。方法二：可以举例如下：对于，给出一组真值指派：P为F，Q为T，R为T，则(PQ)R为F，但是P(QR)为T，故联结词“”不服从结合律。对于，给出一组真值指派：P为T，Q为F，R为F，则(PQ)R为T，但是P(QR)为F，故联结词“”不服从结合律。例10.（思考题）设计一个保密锁的控制电路，锁上共有三个按钮A,Q,C。当三键同时按下，或只有A,Q两键按下，或只有A,Q其中之一按下时，锁被打开。请写出此控制电路的公式并画出线路图。分析：本题是逻辑在电路设计中的应用。解题时先用真值表求出开锁条件，再写出逻辑表达式，化成最简的形式，最后根据最简表达式画出电路图。解：根据题目要求，列出开锁条件的真值表：设P：A按下，Q：B按下，R：C按下得真值表如下所示：PQRG00000010010101101001101011011111由真值表写出逻辑表达式为：GP∧Q∧R∨P∧Q∧R∨P∧Q∧R∨P∧Q∧RP∧Q∨(P∧Q∨P∧Q)∧RP∧Q∨((P∨Q)∧(P∨Q))∧R(P∧Q∨P∨Q)∧(P∧Q∨(P∨Q))∧(P∧Q∨R)(P∨Q)∧(P∧Q∨R)P∧Q∨(P∨Q)∧RP∧Q∨P∧R∨Q∧R故保密锁的控制电路如图所示：&A&11B