Document Type

Post-Print

Publication Date

8-2004

Subjects

Decomposition method, Boolean functions, Many-valued logic, Decomposition (Mathematics)

Abstract

Modified Reconstructibility Analysis (MRA), a novel decomposition within the framework of set-theoretic (crisp possibilistic) Reconstructibility Analysis, is presented. It is shown that in some cases while 3-variable NPN-classified Boolean functions are not decomposable using Conventional Reconstructibility Analysis (CRA), they are decomposable using Modified Reconstructibility Analysis (MRA). Also, it is shown that whenever a decomposition of 3-variable NPN-classified Boolean functions exists in both MRA and CRA, MRA yields simpler or equal complexity decompositions. A comparison of the corresponding complexities for Ashenhurst-Curtis decompositions, and Modified Reconstructibility Analysis (MRA) is also presented. While both AC and MRA decompose some but not all NPN-classes, MRA decomposes more classes, and consequently more Boolean functions. MRA for many-valued functions is also presented, and algorithms using two different methods (intersection and union) are given. A many-valued case is presented where CRA fails to decompose but MRA decomposes.

Description

Authors' version of a paper that subsequently appeared in the International Journal of General Systems, 33:4, 361-382, published by Taylor & Francis. The version of record may be found at http://dx.doi.org/10.1080/03081070310001638630.

DOI

10.1080/03081070310001638630

Persistent Identifier

http://archives.pdx.edu/ds/psu/16522

Share

COinS