资源描述：
《2.3 联结词的完备集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章命题逻辑等值演算2.3联结词的完备集1五个基本的联结词：┐、∧、∨、→、。在实际应用中（如数字逻辑电路），可由五个基本的联结词{┐，∧，∨，→，}产生更多的联结词：（1）异或（2）条件否定（3）与非（4）或非2设p，q为二命题，复合命题“p，q之中恰有一个成立”称为p与q的异或式或排斥或式，记作pq，称作异或联结词。易见：1、pq(p∧┐q)∨(┐p∧q)┐(pq)2、pq为真当且仅当p，q中恰有一个为真异或联结词的性质：（1）pq（2）(pq)r（3）p∧(qr)（
2、4）pp（5）p0（6）p1定义异或联结词异或联结词的性质：（1）pqqp（2）(pq)rp(qr)（3）p∧(qr)(p∧q)(p∧r)（4）pp0（5）p0p（6）p1┐p3设p、q、r为三命题，若pqr，则prq，qrp且pqr0。思考题4定义蕴涵否定联结词设p，q为二命题，复合命题“pq的否定”称为命题p和q的蕴涵（条件）否定式，记作，称为蕴涵（条件）否定联结词。由定义知：1、2、为真当且仅当p为真q为假5设p、q为二命题，复合命题
3、“p与q的否定”称为p与q的与非式，记作pq，称作与非联结词。易见：1、pq┐（p∧q）2、pq为真当且仅当p与q不同时为真。与非联结词的性质：（1）pp┐(p∧p)┐p（2）(pq)(pq)┐(pq)p∧q（3）(pp)(qq)┐p┐q┐(┐p∧┐q)p∨q定义与非联结词与非联结词的性质：（1）pp（2）(pq)(pq)（3）(pp)(qq)6设p、q为二命题，复合命题“p或q的否定”称为p与q的或非式，记作pq，称作或非联结词。
4、易见：1、pq┐（p∨q）2、pq为真当且仅当p与q同时为假。或非联结词的性质：（1）pp（2）(pq)(pq)（3）(pp)(qq)定义或非联结词或非联结词的性质：（1）pp┐(p∨p)┐p（2）(pq)(pq)┐(pq)p∨q（3）(pp)(qq)┐p┐q┐(┐p∨┐q)p∧q7联结词完备集定义：一个联结词集合，若对于任何一个公式均可以用该集合中的联结词来表示或等值表示，就称为联结词完备集。如果该集合任意去掉一个联结词，就不再具备这种特
5、性，就称为最小完备集。定理：{┐,∧,∨}是联结词完备集。推论：{┐,∧,∨,→}，{┐,∧,∨,→,}，{┐,∧,∨,→,,}，{┐,∧,∨,→,,,}等都是联结词完备集。8因为p∨q┐（┐p∧┐q）p∧q┐（┐p∨┐q）p∨q┐p→qp∧q┐（p→┐q）定理：{}、{}是联结词完备集，并且是最小联结词完备集。（P39）推论：{┐、∧}、{┐、∨}、{┐、→}是联结词完备集，并且是最小联结词完备集。推论：是联结词完备集，并且是最小联结词完备集。9思考题定义如表所示的二元逻辑联
6、结词“·”，（1）证明{·}是联结词完备集。（2）请利用该联结词·表示下述公式：（pq）∧r10——数字逻辑电路命题逻辑的应用11门电路为了方便电路逻辑设计的需要，现将命题逻辑联结词相对应的门电路汇总于下图：12例1设计一个控制楼梯照明的电路，使得分别装在楼梯上下两层的两只开关都能控制照明。写出控制电路的逻辑表达式并设计电路图。解：两只开关的状态分别表示为s1，s2，“0”表示开关断开，“1”表示开关接通。用S表示楼梯的照明状态，“1”表示灯亮，“0”表示灯灭。S（┐s1∧s2）∨（s1∧┐s2）
7、s1s2电路图如下：13例2一家航空公司为了保障安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也可能发生故障，因此采用了三台计算机同时复核，再根据“少数服从多数”的原则作出判断。假设三台计算机中同时有一台以上的计算机出现故障的概率为0，试将判断结果用命题公式表示，并设计一个尽可能简单的电路图。解：设p，q，r分别表示三台计算机的答案，S表示判断结果，“0”表示飞行计划有误，“1”表示飞行计划正确。S(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧
8、r)(q∧r)∨(p∧r)∨(p∧q)电路图如下：14例3有一种电子锁，锁上共有三个键A、B和C。当三键同时按下，或A、B两键同时按下，或只有A、B其中之一按下时，锁被打开。设计该电子锁的控制电路的公式并画出电路图。解：用“0”表示键未按下，“1”表示键按下。G表示锁的状态，“1”表示打开，“0”表示未打开。则G（A∧B∧C）∨（A∧B∧┐C）∨（A∧┐B∧┐C）∨（┐A∧B∧┐C）（A∧B）∨（A∧┐B∧┐C）∨（┐A∧B∧┐C）（A∧（B∨（
