三值逻辑函数的基本表式及其 Karnaugh 图分析.doc

《三值逻辑函数的基本表式及其 Karnaugh 图分析.doc》由会员分享，可在线阅读，更多相关《三值逻辑函数的基本表式及其 Karnaugh 图分析.doc（9页珍藏版）》请在三一办公上搜索。

1、精品论文大全三值逻辑函数的基本表式及其 Karnaugh 图分析李裕信 湖南省长沙市邮政局，湖南长沙 (410001) E-mail：lyx9989摘要：本文穷举了单变量三值逻辑函数的 27 种表示式，设计了它的“正八面形”形式的Karnaugh 图；明确了由它可衍生出三种二值逻辑变量；提出了独立的 m 元三值逻辑函数个 数的计算公式；特别指出二变量三值逻辑函数的数目是 19683 个，它的 Karnaugh 图十分复杂，其主要框架是多个 6 顶点完全图及正八面形按三层嵌套与交叉的图形。关键词：三值逻辑，m 变量的三值逻辑函数，Karnaugh 图，衍生的二值逻辑变量， 中图分类号: O1，1

2、10。14文献标识码: A引论：一个三值逻辑变量 A，除了可取“0”和“1”（也可写为 F假和 T真）两个值之外，还可 取一个乏晰值。按照 J. Lukasiewicz 和 E. L. Post 的规定，可用“0、1、2”三个值 分别表示“假、 乏晰、真”（或顺序反过来）三个逻辑状态;还可以用“0”“”“1” 三个值 分别表示“假、乏晰、真”。本文采用最后一种表示码，以使其最接近二值 Bool 代数的习惯1 2 。对“”这个逻辑 值的理解应是“非 0 非 1”和“亦 0 亦 1”它是“0”与“1”之间的过渡逻辑状态值。对于这样的三值 逻辑变量 A 与 B,可和 Bool 代数一样定义“逻辑加”

3、（“或”）A+B(即 AUB),和“逻辑乘”（“与”）AB即 AB ，按下面真值表定义：表 0-1： A+B 的真值表表 0-2： AB 的真值表A+BAB01ABAB010010000101111101但是，对于一个独立的三值逻辑变量，如果不附加任何条件，则不存在 Bool 代数中的“逻辑非”运算。然而，却可以定义一种“转移”运算，它的定义是：三值逻辑变量 A 的“逻 辑转移 量记为A, 而且：0 = 1，1 = ， = 0.(当然也可反过来定义：0 = ， = 0，. 1 = )。 即有下面真值表：表 0-3“转移”逻辑真值表A01A10三值逻辑变量 A 的函数 P（A）可视为一种变换，：

4、当 A 依次取 0、1 时，P（A）依次取、 ，（、是可取0、.1.的常数 ）故 P（A）可用向量（、 ）表 示。-9-.根据定义可知（，、）=（ 、 、）；.(、 ) = ( 、 、)；.而.(、 ) =（、）。. .(1).即矢量的“转移”运算可等价地分配到各个分量上去。下面的定理将指出 , 只要定义了“或”“与 关系作完备的描述。”“转”，就可对任意的三值逻辑变量的设 A 为任意三值逻辑变量，由于它是一种类似于 Bool 代数的“格”，下列基本恒等式成立1.30.1、并项律.：.A. 1 = A；A. A = A； A. 0 = 0；A +1 = 1；A + A = A；.A+ 0 =

5、A；A + A + A = 1；A + A + A = ；.A + A + A = 1；.A + A + A = ；. (2).A + A = ；.A + A = 1；.A + A = 1；.AA + AA + AA = 1；0.2、转移律：A = A.；.A.A.A = 0；.A A = A + A；.A + A = A.A + AA.(3)上述所有的恒等式都可通过“与”“或”“转”的真值表得到验证。1. 单变量三值逻辑函数表示式“总表”分析：13 .定理 1：三值逻辑代数中，变量 A 的函数 P（A）可写成三个基底 . A 、. A 、. A的线性组合表式：P（A）= . . A+ . A

6、 + . A (4)其中、是可取0、.1.的常数.。可将三个基底依次记为 P1、P2、P3 。将 P1、 P2、 P3 用P4、P5、P. 6 表示。则所有不恒为0的单变量函数，都可以 通过P1、P2、P3、P4、P5、P6 这六个函数中的 1 - -3个函数迭加得到。证明：由于三值逻辑变量 A 可取 0、 、.1.三个值中的任一个值，那么能够写出的A 的函数 P （ A ）的个数应等于从0、 、.1.三个元素中任取三个（允许取相同的）的排列数 3 3 ，即 27 个。在这里，可以穷举这 27 个函数的形式及真值表表 1.1 三值逻辑变量 A 的函数 P(A)的表达式总表AP(A)01函数表示

7、式备注P1100P1 = A .三项之和等于 1P2010P2 . = AP3 .001P = A3P 400P 4 = . A = A . A = P1三项之和等于 P500P5 . = A = A A = P 2P 600P 6 . = A = A A = P 3P 71P7 = .A = A.A = P1 + P2 . + P3 .1P 81P8 . = . A = A. A = P1 + P2 . + P3P 91P9 . = . A = A. A = P1 + P2 . + P3P10011P10 = . A . = A . A . = P2 + P3三项之和等于P 11101P11

8、 = .A = AA = P1 + P3三项之和等于 1P12110P12 = . A = A A = P1 + P 2P130P13 = A = P 2 . + P 3三项之和等于 P 14 .0P14 . = A = P1 . + P 3P15 .0P15 = A = P1 . + P 2P16 .11P = A . = P + P + P .16 1 2 3三项之和等于 1P1711P17 = A . = P1 + P2 + P3P18 .11 P18 = A. = P1 + P2 + P3P19 .01P19 = A = P2 + P3三项之和等于 1P 20 .10P20 = A =

9、 P1 + P3P 21 .10P 21 = A = P1 + P 2P 22 .01 P22 = A.A = P2 + P3三项之和等于 1P 23 .10P23 = A.A = P1 + P2P 24 .01P24 = A.A = P1 + P3P 25 .P25 = = P1 + P2 + P.常量 P 26 .111P26 = 1 = P1 + P2 + P3常量 1P27.000P27 = 0 = 0P1 + 0P2 + 0P常量 0借助于“或”“与”“转”的真值表和恒等式（1）（2）（3），可以列出表 1.1。并由表 1.1 可知，所有 27 种函数都可写成P1、P2、P3 的线性

10、组合，而 P1、P2、P3 就是三个“基底”，即（4）式得证。由于、 中等于 1 的项就是 P1、P2、P3 中的项，而、 中等于 的项就是 P4、P5、P6 中的项。这 27 个函数中的所有不恒为 0 的单变量函数，都可通过P1、 P2、 P3、 P4、 P5、 P6中的1 - -3个函数迭加得到。 .因此，定理的后一断语 理 2全部得证。也成立。故定定理 1 列出了所有 27 个单变量三值逻辑函数表示式的总表，此表囊括了单变量三值逻辑函数所有的单项式和恒等变换关系。从定理 1 还可看出， （、 ）就是函数 P（A）的向量表示。任一函数 P（A）除了可用“与”“或”“转”表示之外，还可用向量

11、（、 ）表 示。因此三个基底各有三种写法：P1 = A = (100);.P2 = A = (010);.P3 = A = (001);.而其它函数也可写为P4 = P1 = A = ( 00 )；.P5 = P2 = A = (0 0)；.P6= P3 = A = (00 ).等等。可将 P1、P2、P3、P4、P5、P6 这六个函数项称为三值逻辑函数的“最小项” 。在本文设计的卡诺图(Karnaughmap)中“,最小项”用“点”表示，而二个最小项之和（或）用连接两点 形表示。的线段表示，三个最小项之和（或）则可用连接三点的三角2. 三值逻辑单变量函数的卡诺图的分析由定理 1 可以确定的是

12、，三值逻辑的单变量函数应是 6 个最小项中 1-3 个之和。同时要考虑，6个最小项是P1、P2、P3、P1、P2、P3，而且Pk + Pk = Pk (k = 1、2、3);Pj + Pk + Pk = Pj + Pk ;.Pj + Pk + Pk = Pj + Pk。即三个最小项（点）中若含有Pk 和Pk 则它们之和实际上是二个最小项（点）之和；二个最小项（点）之和6也可能实际上是一个最小项（点）。在6点中取3个的函数共有C 3 = 20个，但要除去实际上是退化为两个点之和的函数，这种需要除去的函数个数共有C1 C1 + C 2 C1 = 12,3 23 2即独立存在的三点函数（三角形面）的

13、个数为C 3 （C1 C1 + C 2 C1）= 20 - 12 = 8个；在6点63 23 2中取2个的函数共有C 2 = 15个，需要减去“实际上是退化为一点的函数”的个数C1 = 363个，即独立存在的二点函数（线段）的个数为C 2 C1 = 15 3 = 12；独立存在的一点63函数（最小项）的个数是6。所以反映独立的单变量函数个数及它们之间关系的几何图 形具有8个三角形面、12条棱线、6个顶点，点、线、面总数是8 + 12 + 6 = 26正是不为0的单变量函数的总数。显然，它就是本文设计的三值逻辑单变量函数的卡诺图(Karnaugh map)。从它的点线面数量可知，它是一个正六角八

14、面体。因此，有下面的定理：定理 2：三值逻辑单变量函数的卡诺图（图 2.1）的点、线、面具有如下逻辑与数量关系：2.1 三值逻辑单变量函数的卡诺图有 6 个“点”，12 条“边”，8 个“三角形”。它们代表 26 个不 恒为 0 的函数。它形成一个“正八面体”。每条边就是它两个端点的逻辑函数（最小项）之和（或），每个三角形就是它三个端点的逻辑函数（最小项）之和（或），也等于它三条边或任 意两条边的逻辑函数（最小项）之和（或）。每个顶点的函数项等于汇交于此点的“边”所代 表函数之“积”（与）。2.2、26 个不恒为 0 的函数中有 2 个常量（ P26 =1 和 P25 =）；18 个衍生的二值

15、逻辑函数（“1、0”，“、0”，“1、”三种类型各 6 个）和 6 个真三值函数（ P19-24 ）。图 2.1 三值逻辑单变量函数的卡诺图2.3、以 P7、P8、P9为三顶点，以 P16、P17、P18为三边, 可组成满足 2.1的点线关系的三角形。它是“1、”类型的二值逻辑三角形。故共有三个二值逻辑三角形（见图 2.1）图 2.2 三值逻辑变量 A 衍生的（0、1）（0、）（、1）三种类型二值逻辑变量关系图证明:定理的 2.1 实际上是三值逻辑单函数卡诺图的定义规则，其合理性已经在前面证明，它是定理 1 的推论，可从卡诺图验证。2.2 也可从卡诺图和表 1.1 推出。实际上，在卡诺图 中，

16、6 个点与 12 条边所代表的逻辑函数都用（、 ）标记（见图 2.1），而 8 个三角形代表的逻辑函数分别是 P1P2 P3 =（111）=1， P4 P5 P6 =（）=， P4 P2 P3 =（11）=P16 ， P5 P1P3 =（11）=P17 ， P1P2 P6 =（11）=P18 ， P1P5 P6 =（1）=P7 ， P4 P2 P6 . =（1）=P8 . P4 P5 P3 . =（1）=P9 。前二个三角形分别代表 1 和 两个常数，每个三角形的六要素(三“点”三“边”)分别是“1、0”和“、0”类型的二值逻辑函数；后六个三角形所 代表的函数都是“1、”型的二值逻辑函数.。显

17、然 2.2 成立。将 2.2 中所指的 18 个二值逻辑 函数，按类型分别组成三个三角形，即得 2.3 的结论。因此，图 2.1 画出的三值逻辑单变量 函数的卡诺图概括了三值逻辑单变量函数所有的逻辑变换关系。3. 任意三值逻辑变量衍生的三种类型二值逻辑变量分析：定理 3：任意三值逻辑变量可衍生如图 2.2 所示的（0、1）（0、）（、1）三种类型二值 逻辑变量。它们符合下表（表 3.1）所示的规律：表 3.1 三值逻辑变量衍生的（0、）（0、1）（、1）三种类型二值逻辑变量的基本逻辑规则最简二值变量取值反演（非）运算重迭律反演的意义 A ,. A0，.A. = A 0.A ， .A0， 1.A

18、 = A1 0.A,.A 即.A，1.A = A1 证明：当三值逻辑变量 A 依次取值 0、1 时， 由“与”“转”运算的真值表表 0.2 和表 0.3可直接算得 A 与 .A 分别依次取为 1、0、0 与 0、1、1。即它们是只取 0、1 的二值逻 辑变量，而且它们是互反的；一般地，当 x 是(0,1)型的二值变量时，x. 是与 x 互反的(0,1)型的二值变量。用同样的方法可证（0、）（、1）两种类型二值逻辑变量的基本逻辑规则。此外，通过直接运算还可以证明图 2.2 的三个三角形中，任一边的函数等于其两端点函数之 和，而且它与所对的顶点的函数互反；任一顶点的函数等于其两汇交边函数之积，而且

19、它与 所对的边的函数互反。4. 三值逻辑多变量函数的表示及其卡诺图框架图：定理 4：m 个独立的三值逻辑变量形成的“m 元函数”可写成3m 个“基底”的线性组合形式： P（A、B、.) = 1442443 m个变量1 P1+ 2 P2+ . + 3m P3m . . . . . .( 5)其中 1、2、.3m 是可取 0、 、1中任一值得常数。P（A、B、.)的不同单项函数个数1442443 m个变量m共有33个；而不恒为 0的“最小项”个数共为2 3 m 项。证明：以 m=2 为例。对于两个独立的三值逻辑变量 A、B 形成的“二元函数”P（A、B）而言，由于 A、B 都是三值逻辑变量，可独立

20、取 0、1中任一值，它们有 9 种组合状态：00、0、01、0、1、10、1、11（即 3 中取 2、允许重复的排列数）。即 P（A、B） 函数空间的基底应是 9 维单位向量：（100000000）（010000000）（001000000）（000100000）（000010000）（000001000）（000000100）（000000010）（00000001），这 9 个基底也可写为： A B、. A B、. A B .、 A B.、. A B、. A B、. A B、. A B、. A B .它们依次简记为P1、 P2、. P9 .。于是 P （ A 、 B ）= 1 P1 + 2

21、 P2 + . + 9 P9 . . .( 6 )由于 1 2 . 9 是从 0、 、1三个值中每次取出允许重复的 9个数的一个排列，它共有3 3 2= 3 9= 19683 个。将 9 个基底分别乘以 ，可得到另外9个简单函数： P1、 P2、. P9 ,(记为 P10 、 P11、. P18 )它们与基底组成18 个“最小项”，显然，任意的 P （ A 、 B ）可写为这18 个最小项中若干个(不超过 9个）的迭加。至此，已证明当 m = 2时定理成立。可以用数学归纳法证明一般情况下定理成立。对于二变量三值函数，18 个最小项的表式及基本关系如下:P1 = AB；.P2 = .AB；.P3

22、 = A B.；(7)P4 = AB.；.P5 = .AB；.P6 = .A B；.(8)P7 = .AB；.P8 = .AB；.P9 = A B；.(9) P10 = P1 = AB；.P11 = P2 = .AB；.P12 = .P3 = A B；.(10) P13 = P4 = AB；.P14 = P5 = .AB；.P15 = .P6 = A B；.(11) P16 = P7 = AB；.P17 = P8 = .AB；.P18 = .P9 = A B；.(12)P19 = P1 + P2 + P3 = A；.(13a).P20 = P4 + P5 + P6 = A.(13b).P21

23、= P7 + P8 + P9 = A；.(13c). P22 = P10 + P11 + P12 = A；.(14a).P23 = P13 + P14 + P15 = A；.(14b).P24 = P16 + P17 + P18 = A；.(14c). P25 = P1 + P4 + P7 = B；.(15a).P26 = P2 + P5 + P8 = B；.(15b).P27 = P3 + P6 + P9 = B；.(15c). P28 = P10 + P13 + P16 = B；.(16a).P29 = P11 + P14 + P17 = B；.(16b).P30 = P12 + P15

24、+ P18 = B；.(16c).从（13）-（-16）表示三个函数项之和（或）Pi + Pj + Pk 当 i=1(mod. 3)、j=2(mod. 3)、k=3(mod.3).时，可消去一个变量。.这是简化三值逻辑函数的最基本法则。 由于二变量三值逻辑函数的个数多达19683个 ，逻辑关系十分复杂，要画出所有的函数的逻辑图是不可能的，也是不必要的。但可以根据单变量三值逻辑函数的卡诺图的特点构造 二变量三值逻辑函数卡诺图的基本框架，它可以是如图 4.1 这样的多个 6 顶点完全图及正八 面形按三层嵌套与交叉的图形。也可画出如图4.2的卡诺图框架图。图中，A1 = A,.A 2 = A,.A3

25、 = A,.A4 = A1.A5 = A 2 .A6 = A3.B1 = B,.B2 = B,.B3 = B,.B4 = B1.B5 = B2 .B6 = B3.以A1。B1、A 2。B1、A3。B1、A 4。B1、A5。B1、A6。B1和A1。B2、A2。B2、A3。B2、A 4。B2、A5。B2、A6。B2及A1。B3、A2。B3、A3。B3、A4。B3、A5。B3、A6。B3这18个点组成的三个六角正八面形为基准，按三层嵌套画成图4.2所示。其中除了这三个六角正八面形外，还有三个轴（图上箭头）上每轴6个点构成的一个八面形.。它们中的每一个八面形的顶点 都是三层嵌套三个六角正八面形沿一轴（

26、箭头）各取相对的两顶点组成，即它们与三层 嵌套的三个正八面形是共顶点的。图 4.2 三值逻辑二元函数 Karnaugh map（卡诺图）框架图 25. 结论与说明：5.1 本文对单变量三值逻辑函数作了较完备的描述。表 1.1 及图 2.1 所示的卡诺图囊括了单变 量三值逻辑函数所有逻辑关系和公式。可作为基本公式记忆或存储，以备随时调用。应该指出：有多种三值逻辑系统1 ，它们的逻辑代数结构取决于“与”“或”“转”的不同定义（真值表）， 特别是“转”运算的定义。本文研究的只是其中的一种。但所得的结论只需稍加改变即可在其 它系统成立。5.2 三值逻辑多变量函数的表示与性质随变量数目的增加而急剧复杂化

27、。可以运用图论的方 法和定理更深人地探讨多变量函数的逻辑特性。由定理 1 和定理 4 可知，所有的 m 变量逻辑函数由 1- 3m 个最小项决定，即完全由其逻辑图的 1- 3m 个顶点所决定。由图论可知 45 ， 顶点相同而边数不同的图形有很多，即使边数一定，图形也可有多个，故有很多图形都代表 同一个逻辑函数，只要这些图形连通了相同的顶点。这是运用图论时最要注意的一点。5.3 本文只讨论了三值逻辑的代数性质，未涉及对三个逻辑值的诠释问题。不过，可以设想： 生物学中的基因理论应该与三值逻辑理论有联系。每个基因可取三个“值”：“0（无）”、“（隐性）”、“1（显性）”确是逻辑三值的一种解释。这种解

28、释的合理性研究是未来的新的课 题。参考文献1朱玉成 ：三值 逻辑 理论 ，多值 数字 逻辑 理论 M ，杭州 ，浙 江 大 学 出 版社 ，2006 ， 5.2 5.6 2张毅：逻辑代数，数字电路与逻辑设计M，北京，人民邮电出版社，1982，83-1413 耿素云，屈婉玲，张立昂：格与布尔代数，离散数学M,北京，清华大学出版社，1992，210-2164 F.哈拉里著，李蔚萱译：附录 1：图的图解，图论M，上海，上海科学技术出版社，206203、247-25 5王朝瑞： 完全图；图的代数表示，图论M，北京，人民教育出版社 1981，8-12Analysis of basic expressio

29、n and the Karnaugh map of ThreeValues Logical functionLi YuxinChangsha Post Office, Changsha, Hunan Province, China (410001)AbstractThis paper has exhausted 27 kinds of expressions of the one variable three values logical function, designed the Karnaugh map in its “Octahedron” form。 In the paper, it

30、 has been determined that threekinds of two values logical variables can be derived from the three values logical function, anda formula to calculate the number of dissimilar m variables three values logical functions has been putforward。Particularly it has been calculated that the number of the thr

31、ee values logical functions with independent dual variables is 19683。 The Karnaugh map ofthe three values logical function isextremely complex and its main frame lies in a few 6 vertices complete graph and three-layer nestedOctahedron graph。Keywords: three values logic, the m variables three-value logical function, the Karnaugh map, derivative two values logical variable作者简介：李裕信，男，1937 年生，湖南长沙人，教授级高级工程师,退休前长期从事邮电 高等函授教学及计算机中心工作。