English

应用科学学报 ›› 2000, Vol. 18 ›› Issue (1): 6-11.

• 论文 • 上一篇    下一篇

B2上布尔函数的拟单调分解

程立, 刘永才   

  1. 上海大学计算机科学系, 上海 201800
  • 收稿日期:1998-09-07 修回日期:1999-01-25 出版日期:2000-03-31 发布日期:2000-03-31
  • 作者简介:程立(1974-),男,江苏盐城人,硕士研究生.

Quasi-monotone Decomposition of Boolean Functions on B2

CHENG Li, LIU Yong-cai   

  1. Department of Computer Science, Shanghai University, Shanghai 201800, China
  • Received:1998-09-07 Revised:1999-01-25 Online:2000-03-31 Published:2000-03-31

PDF

101

摘要： 系统地讨论了B2上布尔函数的拟单调分解.先使用拟单调分解树来定义布尔函数拟单调分解的一般形式,使其在应用中具有很大的灵活性.然后对⊚、⊕、∪和°运算给出几种实用的拟单调分解法.最后将上述结果推广到布尔函数拟单调分解的一般形式,给出一个布尔函数可以分解成k个单调函数的逻辑组合的充分必要条件.

关键词: B2上布尔函数, 拟单调分解, 单调分解

Abstract: In this paper, quasi-monotone decomposition of Boolean functions on B 2 is discussed systematically. The quasi-monotone decomposition tree is used to define the general form of quasi-monotone decomposition. It gives great flexibility in its application. Several practical quasimonotone decomposition approaches for boolean operators ⊚,⊕, ∪ and ° are given. Then the above results are extended to the general form of quasi-monotone decomposition. In conclusion, we give the necessary and sufficient condition under which a boolean function can be decomposed into k monotonous boolean functions.

Key words: monotone decomposition, boolean funcition on B2, quasi-monotone decomposition

中图分类号: