数理逻辑与数字电路设计优化.docx

上传人:太** 文档编号:72801114 上传时间:2023-02-13 格式:DOCX 页数:4 大小:61.30KB
返回 下载 相关 举报
数理逻辑与数字电路设计优化.docx_第1页
第1页 / 共4页
数理逻辑与数字电路设计优化.docx_第2页
第2页 / 共4页
点击查看更多>>
资源描述

《数理逻辑与数字电路设计优化.docx》由会员分享,可在线阅读,更多相关《数理逻辑与数字电路设计优化.docx(4页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数理逻辑与数字电路设计优化作者:王玉红来源:赤峰学院学报自然科学版2011年第2期王玉红(赤峰学院 计算机科学与技术系,内蒙古 赤峰024000)摘 要:数理逻辑就是精确化、数学化的形式逻辑.它是现代计算机技术的基础.数理逻辑 包括两个最基本的组成部分,就是“命题逻辑”和“一阶谓词逻辑”.其中命题逻辑又被称为二 值逻辑,它的运算特点同电路设计中的开与关、高电位与低电位等现象完全一样,都只有“0”、 “1”两种不同的状态,因此,它在电路设计分析中有着广泛而重要的应用.关键词:命题;命题公式;主合取范式;门电路;门延迟时间中图分类号:TN79文献标识码:A 文章编号:1673-260X (2011

2、) 02-0066-021命题逻辑1.1 命题及命题联结词命题是命题逻辑的基本概念.能唯一辨别真假的陈述句被称作命题.命题有唯一的真值“0”(假)或“1”(真).在自然语言系统中,陈述句的标志是句号 但并非所有的以句号结尾的句子都是命题.有两种情况必须考虑到,第一种情况是一些 不确定性的句子,如陈述句“x+58.”,是不能判断词句的正确与否;第二种情况是悖论,如 著名的罗素悖论、理发师悖论和说谎者悖论等.在判断一个语句是否是命题时,一般有两个依据, 首先看此句子是否是陈述句,其次是最关键的是否能唯一的给出此句子的真假值,有的陈述句 虽然现在不能给出真假值,但将来能给出唯一的真假值的,也是命题.

3、如“明年的今天是晴 天,其真值到了明年是真是假二者必居其一.在自然语言中,一个陈述句除了句尾有一个标点符号“句号”外,可能还包含多个分隔 符“逗号”,由它们共同来表达一个完整的含义;而有的陈述句中可能含有一个或多个“连 词”,按照句子本来要表达的含义,也可以将一个陈述句分割成几个子句.所以命题又可以分成 原子命题和复合命题.原子命题又被称为简单命题,是不能再次分割的陈述句,它是命令逻辑最 基本的单位,通常用单个的英文字母表示.如“p,q,r,s,”,称为命题符号化,复合命题由原 子命题和命题联结词共同组成,基本的命题联结词有五个,分别是否定词“1 ”、合取词 “A”、析取词“v”、蕴涵词“一”

4、以及等价词“?圮” .另外还有逻辑设计中常用的联结词 异或词“ v ”、与非词“ t ”和或非词“ I ” .通过这些丰富的命题联结词,可以将任何命题进 行符号化.1.2 命题公式命题公式也叫合式公式,简称为公式,常用大写的英文字母表示,如“A,B,C,” .一个 公式中一般含有命题常项、命题变项、命题联结词、括号等组成.命题公式是有真值的,但命题 公式的真值取决于公式中命题变项的值,若给公式中各个变项指定一组真值,就对应公式的一 个指派.对含有n个命题变项的公式进行赋值,共有“2n”组不同的指派,可以形成一张表格, 称为此公式的真值表.若有两个公式A和B的真值表相同,我们称这两个公式是等值的

5、,记作“A?圳B” .在实 际判断中记住一些常见的等值式,用等值演算的方法判断两个公式是否等值.在进行等值演算时 总可以得到一系列的等值式,也即说明了一个公式有无穷的等值式.所以就需要一个形式规范的、 结构统一的公式,使得彼此等值的公式中的每一个公式都与之等值,这就是命题公式的的主范 式.1.3 命题公式的主析取范式命题公式的主范式包括主析取范式和主合取范式.主析取范式是极小项的析取式,含有n 个命题变项的极小项是这样的简单合取式:每个命题变项与其否定二者之一必按字典顺序出现 且仅出现一次,而且公式中只能出现的命题联结词是合取词.n个命题变项可形成2n个极小项, 规定将命题变项看成1,其否定看

6、成是0,每个极小项对应的二进制就是成真赋值,对应的十进 制记作极小项m的下标.主合取方式是极大项的合取式,极大项的定义类似于极小项,只不过允 许出现的命题联结词是析取词.命题公式的主析取范式的求解常用真值表法.即列出命题公式的真值表,找出其中的极小 项,则此命题公式的主析取范式就是这些极小项的析取.2数字电路2.1 门电路众所周知,所有数字电路的基础是门电路,基本的门电路包括:非门(反向门)、与门 和或门,并由它们组成与非门、或非门和异或门等复合门电路.假设门电路的两个输入信号是p 和q,对应的逻辑符号分别是 和、“Pq”、“p+q”、“P q”、“p+q”、pvq.2.2 电路设计中存在的问

7、题在电路设计中存在的主要问题是门电路延迟和电路太复杂.一般来说,由门电路组成的数字电路,从信号建立到通过一级门电路,总会有一段时间 的延迟.把经过一个反向门、与门和或门的延迟时间称作一级标准门延迟,一个组合电路的延迟 时间是信号从输入端到输出端所经过的各级门电路延迟时间之和.很显然,这个延迟时间越短越 好,换句话说就是用等价的、延迟时间短的数字电路代替延迟时间长的组合电路.考虑到实际情况,在完成相同功能的前提下,设计的电路越简单越好.这就要求在设计电 路时使用的门电路个数越少越好.3利用命题公式优化数字电路设计从上面的叙述可知,命题公式联结词的否定词、合取词和析取词,恰好对应三个基本的 门电路

8、:反向门、与门和或门.要解决电路设计中的问题,就可以利用命题公式的等值公式,从 而找到符合要求的电路设计.首先根据要求列出几个输入信号的真值表,并把它们看做是命题变 项;然后从真值表中得到组合数字电路公式的主析取范式;最后对上析取范式进行等值演算, 直到得到延迟时间最小的等价电路或是复杂度小的电路.例 设计一个由三方参与的投票器.要求是如果有两个或两个以上的投票人投出赞成票时, 决议通过,用“1”来表示;否则决议不能通过,用“0”来表示.这里我们假设最后投票结果用F表示,投票的三方分别是p、q、r,且“0”表示投反对 票,“1”表示投赞成票.则可以得到如下的投票结果F关于三方p、q、r的真值表

9、.如表1所示.图I三方投工的电路图a表1 投票器F的真值表PqrF00000101001!10010111011100010111从表1得到投票结果F的主析取范式:很显然,从公式F的等值演算过程可以看出,如果直接用F的主析取范式对应的电路实 现,有三级电路延迟(如图1所示);而用等值演算后的电路,电路延迟减少为二级(如图2 所示).对于任何复杂的组合逻辑电路,都可以利用命题公式和各种逻辑元件所共有的二值特性, 将其转换为命题逻辑问题,通过命题公式的等值变换,得到最优化的数字逻辑电路.因此,此理 论是在自动控制方面有重要的应用.参考文献:1)耿素云,屈婉玲,张立昂,离散数学(第四版),清华大学出版社,2008.(2)马叔良.离散数学(第三版),电子工业出版社,2009.3)邵学才.离散数学.14)李盘林,李丽双,(5)王成华,王友仁,6)高卫斌.电子线路7)梁明理.电子线路清华大学出版社,2001.李洋,王春立,离散数学.高等教育出版社,1999.胡志忠,电子线路基础.清华大学出版社,2008.(第3版).电子工业出版社,2009.(第五版).高等教育出版社,2008.

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 应用文书 > 解决方案

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁