23 联结词的完备集

1、第二章 命题逻辑等值演算2.3 联结词的完备集 1 五个基本的联结词：、。 在实际应用中（如数字逻辑电路），可由五个基本的联结词，产生更多的联结词： （1）异或 （2）条件否定 （3）与非 （4）或非2 设p，q为二命题，复合命题“p，q之中恰有一个成立”称为p与q的异或式或排斥或式，记作pq，称作异或联结词。 易见：1、pq (pq)(pq) (pq) 2、pq为真当且仅当p，q中恰有一个为真异或联结词的性质：（1）pq（2）(pq)r（3）p(qr)（4）pp（5）p0（6）p1定义 异或联结词异或联结词的性质：（1）pqqp（2）(pq)rp(qr)（3）p(qr)(pq)(pr)（4）

2、pp0（5）p0p（6）p1p3 设p、q、r为三命题，若pqr，则prq，qrp且pqr0。思考题4定义 蕴涵否定联结词 设p，q为二命题，复合命题“pq的否定”称为命题p和q的蕴涵（条件）否定式，记作 ， 称为蕴涵（条件）否定联结词。 由定义知：1、 2、 为真当且仅当p为真q为假5 设p、q为二命题，复合命题“p与q的否定”称为p与q的与非式，记作pq，称作与非联结词。 易见：1、 pq （pq） 2、 pq为真当且仅当p与q不同时为真。与非联结词的性质：（1）pp (pp) p（2）(pq)(pq) (pq) pq（3）(pp)(qq) pq (pq) pq 定义 与非联结词与非联结词

3、的性质：（1）pp （2）(pq)(pq) （3）(pp)(qq) 6 设p、q为二命题，复合命题“p或q的否定”称为p与q的或非式，记作pq，称作或非联结词。 易见：1、 pq （pq） 2、 pq为真当且仅当p与q同时为假。或非联结词的性质：（1）pp （2）(pq)(pq) （3）(pp)(qq) 定义 或非联结词或非联结词的性质：（1）pp (pp) p（2）(pq)(pq) (pq) pq（3）(pp)(qq) pq (pq) pq7联结词完备集 定义：一个联结词集合，若对于任何一个公式均可以用该集合中的联结词来表示或等值表示，就称为联结词完备集。 如果该集合任意去掉一个联结词，就不

4、再具备这种特性，就称为最小完备集。定理：,是联结词完备集。推论：,，,， ,，, 等都是联结词完备集。 8 因为pq （pq） pq （pq） pq p q pq （p q） 定理：、是联结词完备集，并且是最小联结词完备集。（P39） 推论：、是联结词完备集，并且是最小联结词完备集。 推论： 是联结词完备集，并且是最小联结词完备集。9思考题定义如表所示的二元逻辑联结词“ ”，（1）证明是联结词完备集。（2）请利用该联结词表示下述公式：（pq）r10数字逻辑电路命题逻辑的应用11门电路 为了方便电路逻辑设计的需要，现将命题逻辑联结词相对应的门电路汇总于下图：12 例1 设计一个控制楼梯照明的电路

5、，使得分别装在楼梯上下两层的两只开关都能控制照明。写出控制电路的逻辑表达式并设计电路图。 解：两只开关的状态分别表示为s1，s2，“0”表示开关断开，“1”表示开关接通。用S表示楼梯的照明状态，“1”表示灯亮，“0”表示灯灭。 S（s1s2）（s1s2）s1s2 电路图如下：13 例2 一家航空公司为了保障安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也可能发生故障，因此采用了三台计算机同时复核，再根据“少数服从多数”的原则作出判断。假设三台计算机中同时有一台以上的计算机出现故障的概率为0，试将判断结果用命题公式表示，并设计一个尽可能简单的电路图。 解：设p，

6、q，r分别表示三台计算机的答案， S表示判断结果， “0”表示飞行计划有误，“1”表示飞行计划正确。 S(pqr)(pqr)(pqr)(pqr) (qr)(pr)(pq) 电路图如下：14 例3 有一种电子锁，锁上共有三个键A、B和C。当三键同时按下，或A、B两键同时按下，或只有A、B其中之一按下时，锁被打开。设计该电子锁的控制电路的公式并画出电路图。 解：用“0”表示键未按下，“1”表示键按下。G表示锁的状态，“1”表示打开，“0”表示未打开。 则G（ABC）（ABC） （ABC）（ABC） （AB）（ABC）（ABC） （A（B（BC）（ABC） （A（BC）（ABC） （AB）（AC）（ABC） （AB）（AB）C） （AB）（AC）（BC）15G （AB）（AC）（BC）电子锁控制电路图如下：16课后练习 有一会议室