《2.3 联结词的完备集》由会员分享，可在线阅读，更多相关《2.3 联结词的完备集（17页珍藏版）》请在金锄头文库上搜索。
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)(p
2、r) （4）pp0 （5）p0p （6）p1p 3设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 qpq （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，试将判断结果用命题公 式表示，并设计一个尽可
6、能简单的电路图。解：设p，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课后练习有一会议室，四周都有出入口，门旁装有开关 。为了控制全室的照明，要求设计一个线路，使得 改变任一只开关的状态，就能改变会议室的明暗。 假设，室中无人时灯全灭，有人时等亮。写出控制 电路的逻辑表达式并设计电路图。17
