《逻辑与布尔代数》课件

逻辑与布尔代数探索从古典逻辑到现代数字系统设计的理论基础课程概述课程目标掌握逻辑基础和布尔代数教材资料指定教材与补充阅读材料评分标准考试、作业及课堂表现时间安排周课程，每周学时163第一部分逻辑基础数理逻辑应用实际应用场景推理规则有效推理方法谓词逻辑带有量词的逻辑命题逻辑基本命题运算什么是逻辑学？起源1研究有效推理的学科三段论2亚里士多德的推理体系发展历程3从传统到现代数理逻辑应用领域4计算机科学、数学、哲学命题及其分类命题定义能判断真假的陈述句命题类型简单命题•复合命题•命题状态真命题•假命题•表示符号用、、等字母表示p qr命题的真值真值表确定方法逻辑类型列出所有可能赋值情况分析命题内容二值逻辑真或假系统分析命题真假根据定义判断真假多值逻辑多种真值逻辑联结词否定¬真变假，假变真合取∧类似且，同真才真析取∨类似或，同假才假蕴含→前假后真，结果为真等价↔真值相同则为真否定运算否定定义命题的否定为非，记作p p¬p真值表为真时为假，为假时为真p¬p p¬p双重否定律¬¬p≡p应用案例开关电路，反向控制合取运算合取定义真值表命题与的合取，记为∧仅当、都为真时结果为真p q p q p q对比特性等同于日常语言中的且交换律、结合律、分配律析取运算析取运算∨表示或，当、至少有一个为真时结果为真，仅当都为假时结果为假p q p q p q蕴含运算蕴含定义如果，那么，记作p q p→q真值规则仅当为真为假时结果为假p q特殊性前件为假时，蕴含式恒为真条件关系是的充分条件，是的必要条件p qqp等价运算p qp↔q真真真真假假假真假假假真等价运算表示当且仅当，当、真值相同时结果为真，不同时为p↔qp qp q假复合命题练习联结词构建真值计算常见错误利用各种联结词组合命题按运算优先级计算真值运算顺序混淆，真值判断失误命题公式合式公式符合语法规则的命题表达式基本元素命题变元和命题常量p,q,r T,F构成规则变元是公式，联结词连接的公式也是公式分解方法按主联结词递归分解复杂公式真值表与公式2^n5可能情况基本步骤个变元有种可能赋值列出所有变元组合及中间计算结果n2^n3简化技巧利用对称性减少计算量重言式与矛盾式重言式矛盾式判定与应用永真式，在任何赋值下均为真永假式，在任何赋值下均为假通过真值表判定∨∧用于定理证明•p¬p•p¬p∨∨p→q↔¬p q•¬p¬p构建有效论证逻辑等价关系等价定义为重言式时，称与等价，记为p↔qp qp≡q德摩根律·∧∨，∨∧¬p q≡¬p¬q¬p q≡¬p¬q分配律∧∨∧∨∧p qr≡pqp r结合律∧∧∧∧pqr≡pqr替换规则与等价变换确定目标识别规则替换变形验证结果明确原始公式和期望形式选择适用的等价规则按步骤执行等价变换检查变换是否正确范式范式概念基本范式1具有特定形式的逻辑表达式合取范式和析取范式CNF DNF主范式转换方法4主合取范式和主析取范式PCNF利用逻辑等价变换和真值表PDNF谓词逻辑基础命题局限无法表达内部结构和量化关系谓词定义刻画对象性质或关系的函数基本元素个体词和谓词a,b,c P,Q,R量词引入全称量词∀和存在量词∃全称量词与存在量词全称量词∀存在量词∃量词转换对所有个体，为真存在个体，使为真∀∃x Pxx Px¬xPx≡x¬Px例∀例∃∃∀xx0→x^20xx^2=2¬xPx≡x¬Px谓词公式的构造与解释一阶语法谓词、变量、量词和联结词的组合规则解释模型给定论域及解释函数确定公式意义真值判定基于解释评估公式真假公式分析∀∃x yx第二部分布尔代数数字电路设计实际工程应用布尔代数应用电路分析与综合布尔函数表达式与真值表基本概念运算与定律布尔代数的历史与发展1854年1乔治·布尔发表《思维规律研究》21938年克劳德·香农证明布尔代数与开关电路的关系1940年代3冯·诺依曼计算机架构采用二进制逻辑现代应用4数字系统设计、计算机体系结构的基础布尔代数的公理系统1封闭性2单位元3互补性任意两元素的运算结果仍在集合内存在和，满足特定运算律每个元素有唯一互补元014对偶原理5集合论联系互换运算和单位元得到对偶定理布尔代数与集合运算直接对应布尔代数的基本运算与运算或运算非运算·+对应逻辑且对应逻辑或对应逻辑非电路中的串联电路中的并联电路中的反相优先级非与或可用括号改变布尔代数的基本定律布尔函数2^n2^2^n函数定义函数数量从到的映射变量布尔函数的个数{0,1}^n{0,1}n4表示方法真值表、表达式、卡诺图、逻辑电路布尔表达式表达式构成表达式求值等价表达式变量、常量、运算符组合代入变量值形式不同但函数相同遵循布尔代数语法规则按运算优先级计算可通过定律相互转换最小项与最大项变量最小项最大项x=0,y=0xy x+yx=0,y=1xy x+yx=1,y=0xy x+yx=1,y=1xy x+y最小项在特定变量赋值下值为的与项1最大项在特定变量赋值下值为的或项0标准形式析取标准形式合取标准形式特性SOP POS最小项之和最大项之积唯一表示可相互转换F=Σm_i F=ΠM_i便于逻辑设计卡诺图基础构造原理格雷码排列的二维真值表维度分类根据变量数确定一维或二维表格相邻概念仅一个变量取值不同的单元主要优势直观显示最简表达式

二、三变量卡诺图二变量图三变量图合并规则方格表示四种输入组合方格表示八种输入组合相邻的个可合并消除个变量2×22×42^n1n四变量卡诺图四变量卡诺图使用个方格，展示所有可能的输入组合，注意边缘单元的环绕相邻性4×4=16卡诺图化简法填写卡诺图将函数真值写入对应位置最大圈组找出所有的最大相邻组合1质蕴涵项识别必须使用的圈组最小覆盖选择最少圈组覆盖所有1无关项在卡诺图中的应用无关项定义表示方法优化应用输入组合不会出现用或标记可视为或X d01函数值可任意指定区别于和选择有利于简化的取值01减少项数或门电路布尔代数的逻辑门实现基本逻辑门复合逻辑门门电路构建与门、或门、非门与非门、或非门、连接多个门实现复异或门杂函数表达式转换布尔表达式直接映射为门电路组合逻辑电路电路特点输出仅依赖当前输入，无记忆状态常见类型加法器、编码器、译码器、多路复用器设计方法功能规格布尔函数化简电路实现→→→时序问题门延迟可能导致竞争冒险半加器与全加器编码器与译码器编码器译码器应用示例多输入少输出少输入多输出键盘扫描将个输入编码为位二进制将位二进制译码为个输出地址解码2^n nn2^n如优先编码器如译码器显示驱动8-33-8多路复用器与多路分配器多路复用器多路分配器1数据选择器，多输入单输出数据分配器，单输入多输出2设计案例函数实现数据总线选择，控制信号分发任意布尔函数可用多路复用器实现与通用门NAND NOR门完备性门完备性成本效率NAND NOR仅用门构建任意逻辑函数仅用门构建任意逻辑函数减少芯片类型，提高集成度NAND NOR可编程逻辑设备类型编程语言PLD简单可编程逻辑•PLD•VHDL复杂可编程逻辑•CPLD•Verilog现场可编程门阵列•FPGA•SystemVerilog设计方法结构化描述•行为级描述•混合级设计•第三部分实际应用与扩展量子计算布尔逻辑的量子扩展多值逻辑超越二值的逻辑系统算法设计逻辑在算法中的应用工程问题实际工程案例分析逻辑设计案例分析交通灯控制状态转换与时序控制售货机控制器输入识别与状态管理简易计算器运算单元与显示控制电梯控制优先级处理与安全保障时序逻辑简介基本特点触发器类型状态机输出取决于当前输入和历史状态、、、触发器离散状态系统SR DJK T含有存储元件不同时钟触发方式状态转换图和表和模型Moore Mealy逻辑推理在人工智能中的应用定理证明自动推导数学公式证明专家系统基于规则的知识推理知识表示逻辑形式化描述事实和规则机器学习逻辑规则与神经网络结合多值逻辑与模糊逻辑三值逻辑模糊逻辑应用场景真、假、未知三种状态真值在区间连续变化自动控制系统[0,1]数据库中应用广泛处理不精确信息模式识别SQL决策支持系统量子计算中的逻辑量子比特量子门量子优势叠加态，同时表示和幺正变换，可逆操作并行处理指数级状态空间01课程总结与展望进阶路径学习方法数理逻辑、计算理论、数字系理论结合实践，多做习题统设计知识回顾发展趋势命题逻辑、谓词逻辑、布尔代量子计算、非经典逻辑、可验数核心概念证硬件设计。