Thumbnail
Access Restriction
Subscribed

Author Natapoff, Alan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1967
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract An extension of the work initiated by Quine in reducing an arbitrary Boolean truth function to its minimal form is presented. Apart from the unique parts of the form, the entire class of nonunique forms is discussed. The portion of the truth table that is left uncovered by the unique parts of the solution is partitioned into topologically invariant components of which it is the direct sum. Each component may be covered independently of the others. The generation of the set of coverings of a component is developed around a central theorem: A union of cells, all basic to a particular vertex, contains no further cells basic to that vertex. A proof of the theorem is given. The components are components in the topological sense and are preserved under changes of representation. The discussion focuses on the general, unrefinable structure of a Boolean function, as opposed to practical means for calculating its minimal coverings.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1967-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 14
Issue Number 2
Page Count 6
Starting Page 376
Ending Page 381


Open content in new tab

   Open content in new tab
Source: ACM Digital Library