English

应用科学学报 ›› 1986, Vol. 4 ›› Issue (2): 186-188.

• 论文 • 上一篇    

构造环和范式的两个改进算法

刘永才   

  1. 上海科学技术大学
  • 收稿日期:1983-11-01 修回日期:1984-02-26 出版日期:1986-06-30 发布日期:1986-06-30

TWO IMPROVED ALGORITHMS OF CONSTRUCTING RSNF

LIU YONGCAI   

  1. Shanghai University of Science and Technology
  • Received:1983-11-01 Revised:1984-02-26 Online:1986-06-30 Published:1986-06-30

PDF

72

摘要： 任一n元布尔函数f(x1,…,xn)的环和范式(RNF).

Abstract: J. E. Savage has developed an algorithm of constructing Boolean function's ring-siim normal form (RSNF),which is based on disjunction normal form (DNF). In this paper the complexity of Savage's algorithm ≤ 2·3n-2n-1 is obtained (the upper bound can be achieved) and two direct algorithms of constructing BSNF are given. The complexities of the two direct algorithms are the same, being 3n -2n.