王玉红

（赤峰学院 计算机科学与技术系，内蒙古 赤峰 024000）

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

王玉红

（赤峰学院 计算机科学与技术系，内蒙古 赤峰 024000）

数理逻辑就是精确化、数学化的形式逻辑.它是现代计算机技术的基础.数理逻辑包括两个最基本的组成部分，就是“命题逻辑”和“一阶谓词逻辑”.其中命题逻辑又被称为二值逻辑，它的运算特点同电路设计中的开与关、高电位与低电位等现象完全一样，都只有“0”、“1”两种不同的状态，因此，它在电路设计分析中有着广泛而重要的应用.

命题；命题公式；主合取范式；门电路；门延迟时间

1 命题逻辑

1.1 命题及命题联结词

命题是命题逻辑的基本概念.能唯一辨别真假的陈述句被称作命题.

命题有唯一的真值“0”（假）或“1”（真）.在自然语言系统中，陈述句的标志是句号“.”，但并非所有的以句号结尾的句子都是命题.有两种情况必须考虑到，第一种情况是一些不确定性的句子，如陈述句“x+5>8.”，是不能判断词句的正确与否；第二种情况是悖论，如著名的罗素悖论、理发师悖论和说谎者悖论等.在判断一个语句是否是命题时，一般有两个依据，首先看此句子是否是陈述句，其次是最关键的是否能唯一的给出此句子的真假值，有的陈述句虽然现在不能给出真假值，但将来能给出唯一的真假值的，也是命题.如“明年的今天是晴天.”，其真值到了明年是真是假二者必居其一.

在自然语言中，一个陈述句除了句尾有一个标点符号“句号”外，可能还包含多个分隔符“逗号”，由它们共同来表达一个完整的含义；而有的陈述句中可能含有一个或多个“连词”，按照句子本来要表达的含义，也可以将一个陈述句分割成几个子句.所以命题又可以分成原子命题和复合命题.原子命题又被称为简单命题，是不能再次分割的陈述句，它是命令逻辑最基本的单位，通常用单个的英文字母表示.如“p,q,r,s,…”，称为命题符号化.复合命题由原子命题和命题联结词共同组成，基本的命题联结词有五个，分别是否定词“┒”、合取词“Λ”、析取词“ⅴ”、蕴涵词“→”以及等价词“圮”.另外还有逻辑设计中常用的联结词异或词“与非词“↑”和或非词“↓”.通过这些丰富的命题联结词，可以将任何命题进行符号化.

1.2 命题公式

命题公式也叫合式公式，简称为公式，常用大写的英文字母表示，如“A,B,C,…”.一个公式中一般含有命题常项、命题变项、命题联结词、括号等组成.命题公式是有真值的，但命题公式的真值取决于公式中命题变项的值，若给公式中各个变项指定一组真值，就对应公式的一个指派.对含有n个命题变项的公式进行赋值，共有“2n”组不同的指派，可以形成一张表格，称为此公式的真值表.

若有两个公式A和B的真值表相同，我们称这两个公式是等值的，记作“A圳B”.在实际判断中记住一些常见的等值式，用等值演算的方法判断两个公式是否等值.在进行等值演算时总可以得到一系列的等值式，也即说明了一个公式有无穷的等值式.所以就需要一个形式规范的、结构统一的公式，使得彼此等值的公式中的每一个公式都与之等值，这就是命题公式的的主范式.

1.3 命题公式的主析取范式

命题公式的主范式包括主析取范式和主合取范式.主析取范式是极小项的析取式，含有n个命题变项的极小项是这样的简单合取式：每个命题变项与其否定二者之一必按字典顺序出现且仅出现一次，而且公式中只能出现的命题联结词是合取词.n个命题变项可形成2n个极小项,规定将命题变项看成1，其否定看成是0，每个极小项对应的二进制就是成真赋值，对应的十进制记作极小项m的下标.主合取方式是极大项的合取式，极大项的定义类似于极小项，只不过允许出现的命题联结词是析取词.

命题公式的主析取范式的求解常用真值表法.即列出命题公式的真值表，找出其中的极小项，则此命题公式的主析取范式就是这些极小项的析取.

2 数字电路

2.1 门电路

众所周知，所有数字电路的基础是门电路，基本的门电路包括：非门（反向门）、与门和或门，并由它们组成与非门、或非门和异或门等复合门电路.假设门电路的两个输入信号是p和q，对应的逻辑符号分别是

2.2 电路设计中存在的问题

在电路设计中存在的主要问题是门电路延迟和电路太复杂.

一般来说，由门电路组成的数字电路，从信号建立到通过一级门电路，总会有一段时间的延迟.把经过一个反向门、与门和或门的延迟时间称作一级标准门延迟，一个组合电路的延迟时间是信号从输入端到输出端所经过的各级门电路延迟时间之和.很显然，这个延迟时间越短越好，换句话说就是用等价的、延迟时间短的数字电路代替延迟时间长的组合电路.

考虑到实际情况，在完成相同功能的前提下，设计的电路越简单越好.这就要求在设计电路时使用的门电路个数越少越好.

3 利用命题公式优化数字电路设计

从上面的叙述可知，命题公式联结词的否定词、合取词和析取词，恰好对应三个基本的门电路：反向门、与门和或门.要解决电路设计中的问题，就可以利用命题公式的等值公式，从而找到符合要求的电路设计.首先根据要求列出几个输入信号的真值表，并把它们看做是命题变项；然后从真值表中得到组合数字电路公式的主析取范式；最后对主析取范式进行等值演算，直到得到延迟时间最小的等价电路或是复杂度小的电路.

例 设计一个由三方参与的投票器.要求是如果有两个或两个以上的投票人投出赞成票时，决议通过，用“1”来表示；否则决议不能通过，用“0”来表示.

这里我们假设最后投票结果用F表示，投票的三方分别是 p、q、r，且“0”表示投反对票，“1”表示投赞成票.则可以得到如下的投票结果F关于三方p、q、r的真值表.如表 1所示.

表1 投票器F的真值表

图1 三方投票器的电路图a

从表1得到投票结果F的主析取范式：

很显然，从公式F的等值演算过程可以看出，如果直接用F的主析取范式对应的电路实现，有三级电路延迟（如图1所示）；而用等值演算后的电路，电路延迟减少为二级（如图2所示）.

图2 三方投票器的电路图b

对于任何复杂的组合逻辑电路，都可以利用命题公式和各种逻辑元件所共有的二值特性，将其转换为命题逻辑问题，通过命题公式的等值变换，得到最优化的数字逻辑电路.因此，此理论是在自动控制方面有重要的应用.

〔1〕耿素云，屈婉玲，张立昂.离散数学（第四版）.清华大学出版社，2008.

〔2〕马叔良.离散数学（第三版）.电子工业出版社，2009.

〔3〕邵学才.离散数学.清华大学出版社，2001.

〔4〕李盘林，李丽双，李洋，王春立.离散数学.高等教育出版社，1999.

〔5〕王成华，王友仁，胡志忠.电子线路基础.清华大学出版社，2008.

〔6〕高卫斌.电子线路（第3版）.电子工业出版社，2009.

〔7〕梁明理.电子线路（第五版）.高等教育出版社，2008.

TN79

A

1673-260X（2011）02-0066-02