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

精品论文大全三值逻辑函数的基本表式及其 karnaugh 图分析李裕信 湖南省长沙市邮政局，湖南长沙 (410001) e-mail：摘要：本文穷举了单变量三值逻辑函数的 27 种表示式，设计了它的“正八面形”形式的karnaugh 图；明确了由它可衍生出三种二值逻辑变量；提出了独立的 m 元三值逻辑函数个 数的计算公式；特别指出二变量三值逻辑函数的数目是 19683 个，它的 karnaugh 图十分复杂，其主要框架是多个 6 顶点完全图及正八面形按三层嵌套与交叉的图形。关键词：三值逻辑，m 变量的三值逻辑函数，karnaugh 图，衍生的二值逻辑变量， 中图分类号: o1，110。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 代数一样定义“逻辑加”（“或”）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）可视为一种变换，：当 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 = 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 + . 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函数表示式备注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 = .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 = 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 的线性组合，而 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）除了可用“与”“或”“转”表示之外，还可用向量（、 ）表 示。因此三个基底各有三种写法：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 可以确定的是，三值逻辑的单变量函数应是 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即独立存在的三点函数（三角形面）的个数为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)。从它的点线面数量可知，它是一个正六角八面体。因此，有下面的定理：定理 2：三值逻辑单变量函数的卡诺图（图 2.1）的点、线、面具有如下逻辑与数量关系：2.1 三值逻辑单变量函数的卡诺图有 6 个“点”，12 条“边”，8 个“三角形”。它们代表 26 个不 恒为 0 的函数。它形成一个“正八面体”。每条边就是它两个端点的逻辑函数（最小项）之和（或），每个三角形就是它三个端点的逻辑函数（最小项）之和（或），也等于它三条边或任 意两条边的逻辑函数（最小项）之和（或）。每个顶点的函数项等于汇交于此点的“边”所代 表函数之“积”（与）。2.2、26 个不恒为 0 的函数中有 2 个常量（ p26 =1 和 p25 =）；18 个衍生的二值逻辑函数（“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 推出。实际上，在卡诺图 中，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、”型的二值逻辑函数.。显然 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 = 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 的三个三角形中，任一边的函数等于其两端点函数之 和，而且它与所对的顶点的函数互反；任一顶点的函数等于其两汇交边函数之积，而且它与 所对的边的函数互反。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 都是三值逻辑变量，可独立取 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 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 = 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 = 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 + 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 = 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个点构成的一个八面形.。它们中的每一个八面形的顶点 都是三层嵌套三个六角正八面形沿一轴（箭头）各取相对的两顶点组成，即它们与三层 嵌套的三个正八面形是共顶点的。图 4.2 三值逻辑二元函数 karnaugh map（卡诺图）框架图 25. 结论与说明：5.1 本文对单变量三值逻辑函数作了较完备的描述。表 1.1 及图 2.1 所示的卡诺图囊括了单变 量三值逻辑函数所有逻辑关系和公式。可作为基本公式记忆或存储，以备随时调用。应该指出：有多种三值逻辑系统1 ，它们的逻辑代数结构取决于“与”“或”“转”的不同定义（真值表）， 特别是“转”运算的定义。本文研究的只是其中的一种。但所得的结论只需稍加改变即可在其 它系统成立。5.2 三值逻辑多变量函数的表示与性质随变量数目的增加而急剧复杂化。可以运用图论的方 法和定理更深人地探讨多变量函数的逻辑特性。由定理 1 和定理 4 可知，所有的 m 变量逻辑函数由 1- 3m 个最小项决定，即完全由其逻辑图的 1- 3m 个顶点所决定。由图论可知 45 ， 顶点相同而边数不同的图形有很多，即使边数一定，图形也可有多个，故有很多图形都代表 同一个逻辑函数，只要这些图形连通了相同的顶点。这是运用图论时最要注意的一点。5.3 本文只讨论了三值逻辑的代数性质，未涉及对三个逻辑值的诠释问题。不过，可以设想： 生物学中的基因理论应该与三值逻辑理论有联系。每个基因可取三个“值”：“0（无）”、“（隐性）”、“1（显性）”确是逻辑三值的一种解释。这种解释的合理性研究是未来的新的课 题。参考文献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 expression and the karnaugh map of threevalues logical functionli yuxinchangsha post office, chang