NPN-representatives of a set of optimal boolean formulas

Hideaki Fukuhara, Eiji Takimoto, Kazuyuki Amano

Research output: Contribution to journalArticlepeer-review


For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND,OR,NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND,OR,NOT,XOR,MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPNr epresentatives in C B*.

Original languageEnglish
Pages (from-to)1008-1015
Number of pages8
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number6
Publication statusPublished - Jun 2010

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Applied Mathematics
  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'NPN-representatives of a set of optimal boolean formulas'. Together they form a unique fingerprint.

Cite this