《命题逻辑等值演算》由会员分享，可在线阅读，更多相关《命题逻辑等值演算（9页珍藏版）》请在金锄头文库上搜索。
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的主合取范式为：（PQR）（PQR）（PQR）而： （PQR）（PQR）（PQR）(PQR)（PR）(PQ)P)R(PQ)R 又由于： PQ(PQ) PQ
2、P Q所以， (PQ) R( PQ)R(PQ)R所以，f可以用仅含，的命题(PQ)R来表示。例2 . 不用真值表判断下列公式是永真式、永假式还是其它。(1) (PQ)(PQ) ;(2) (QP)P)(PR) ;(3) (PQ)R)(PQ)R) .解：（1） (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) 所以，(PQ)(PQ)既非永真式也非永假式。 （2） (QP)P)(PR) (QP)P)(PR) T(PR) F(PR) F 所以，(QP)P)(PR)为永假式。 （3） (PQ)R)(PQ)R) (PQ)R)(PQ)R) (PQ)R)(PQ)R) T 所以，(PQ)R)(PQ)R)为永
3、真式。例3 . 证明下列等价式。 （1）(PQ)(PR) PQR ; （2）PQ(PQ) PQ(PQ) .解：说明: 这两道题看似麻烦，但是如果不采用直接推导的方法，而是利用范式或是左右夹击推导的方法，会起到事半功倍的效果。(1). (PQ)(PR) (PQ)(PR)(PQR)(PQR)(PQR)M4M5M6PQR P(QR) (PQ)(PR)(PQR)(PQR)(PQR) M4M5M6所以，(PQ)(PR) PQR成立。(2). PQ(PQ) (PQP)(PQQ) FPQ(PQ) (PQP)(PQQ) F 所以，PQ(PQ) PQ(PQ)例4 . 试求下列各公式的主析取范式和主合取范式。(1
4、) (P(QR)(P(QR)(2) (PQ)R)P解: (1) (P(QR)(P(QR) (P(QR)(P(QR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)M4M5M6M0 (主合取范式)则其主析取范式为m1m2m3m7(2) (PQ)R)P (PQ)R)P (PQ) R)P (PR)(QR)P(QR)P (QP)(RP)(PQR)(PQR)(PQR)M0M1M3 (主合取范式)则其主析取范式为m2m4m5m6m7例5 . 用等值演算法证明下面等值式。(1) P (PQ)(PQ)(2) (PQ)(PR) P(QR)(3) (PQ) (PQ)(PQ)(4) (PQ)(PQ
5、) (PQ)(PQ)解: (1) 右边 P(PQ)(PQ)(QQ) P(PQQ)T PPP 左边 所以P (PQ)(PQ)(2) 左边 (PQ)(PR) PQR P(QR) 右边 所以(PQ)(PR) P(QR)(3) 左边 (PQ)(QP) (PQ)(QP) PQQP (PQ)(PP)(QQ)(QP) (PQ)(QP) (PQ)(PQ) 右边 所以(PQ) (PQ)(PQ) (4) 左边 (PQ)(PQ) (PP)(PQ)(QP)(QQ) (PQ)(QP) (PQ)(PQ)右边 所以 (PQ)(PQ) (PQ)(PQ)例6 . 将下列公式化成与之等值且只含, 中联结词的公式。(1) ( P(
6、Q(QR)(2) P(QR)解：(1) ( P(Q(QR) (P(Q(QR)(QR)Q) (P(Q(QR)(QR)Q) (P(QR) PQR(2) P(QR) (P(QR)(QR)P) (P(QR)(RQ)(QR)(RQ)P) (P(QR)(RQ)(QR)(RQ)P) (P(QR)(RQ)(QR)(RQ)P) (PQRRQ)(QRRQP) (PQR)(PQR)(PQR)(PQR)例7. 在某班班委成员的选举中，已知王小红、李强、丁金生三位同学被选进了班委会，该班的甲、乙、丙三名学生预言：甲说：王小红为班长，李强为生活委员。乙说：丁金生为班长，王小红为生活委员。丙说：李强为班长，王小红为学习委员
7、。 班委会分工名单公布后发现，甲、乙、丙三人恰好都猜对了一半。问王小红、李强、丁金生各任何职（用等值演算求解）？解：设P：王小红为班长； Q：李强为生活委员； R：丁金生为班长；S：王小红为生活委员； M：李强为班长； N：王小红为学习委员。由已知条件可得公式：T: (PQ)(PQ)U: (RS)(RS)W: (MN)(MN) 根据题意得G TUW T，于是G TUW (PQ)(PQ)(RS)(RS)W (PQRS)(PQRS)(PQRS)(PQRS)W由于P和R不能同时为真，Q和S不能同时为真，P和S不能同时为真（因为这样不符合题意），故上式变为：G (PQRS) (MN)(MN) (PQR
8、SMN)(PQRSMN)由于P,R,M不能同时为真，P,S,N不能同时为真（因为这样不符合题意），则上式仅剩一项PQRSMN，可见王小红不是班长，李强是生活委员，丁金生是班长，王小红不是生活委员，李强不是班长，王小红是学习委员，于是得到： 王小红是学习委员，李强是生活委员，丁金生是班长。例8 .（讨论题）试用多种方法证明蕴含式PQ(PQ)解: 方法一：只要证明PQ(PQ)是永真式。 PQ(PQ) (PQ)(PQ) PQPQ QPQ T即为永真式，故PQ(PQ)成立。方法二：设PQ为T，则P和Q都为T，则PQ为T，故PQ(PQ)。方法三：设PQ为F，则P为T，Q为F，则PQ为F，故PQ(PQ)。
9、例 9 . （讨论题）联结词“”和“”服从结合律么？解：联结词“”和“”均不服从结合律。证明方法有以下两种：方法一：(PQ)R (PQ)R) (PQ)R 而 P(QR) (P(QR) P(QR) 一般而言(PQ)R与P(PQ)是不等价的,故联结词“” 不服从结合律。 (PQ)R (PQ)R) (PQ)R 而 P(QR) (P( QR) P(QR) 一般而言(PQ)R与P(QR)是不等价的，故联结词“”不服从结合律。方法二：可以举例如下： 对于，给出一组真值指派：P为F，Q为T，R为T，则(PQ)R为F，但是P(QR)为T，故联结词“”不服从结合律。 对于，给出一组真值指派：P为T，Q为F，R为
10、F，则(PQ)R为T，但是P(QR)为F，故联结词“”不服从结合律。例 10 . （思考题）设计一个保密锁的控制电路，锁上共有三个按钮A,Q,C。当三键同时按下，或只有A,Q两键按下，或只有A,Q其中之一按下时，锁被打开。请写出此控制电路的公式并画出线路图。分析：本题是逻辑在电路设计中的应用。解题时先用真值表求出开锁条件，再写出逻辑表达式，化成最简的形式，最后根据最简表达式画出电路图。解：根据题目要求，列出开锁条件的真值表： 设P：A按下 ， Q：B按下 ， R：C按下 得真值表如下所示：PQRG00000010010101101001101011011111 由真值表写出逻辑表达式为： G PQRPQRPQRPQR PQ(PQPQ)R PQ(PQ)(PQ)R (PQPQ)(PQ(PQ)(PQR) (PQ)(PQR) PQ(PQ)R PQPRQR故保密锁的控制电路如图所示：&A 11B & G&1 C 例 10 图
