Using variable-entered Karnaugh maps in determining dependent and independent sets of Boolean functions

Abstract EN

An important class for Boolean reasoning problems involves interdependence among the members of a set T of Boolean functions.

Two notable problems among this class are (a) to establish whether a given subset of T is dependent, and (b) to produce economical representations for the complementary families of all dependent subsets and independent subsets of T.

This paper solves these two problems via a powerful manual pictorial tool, namely, the variableentered Karnaugh map (VEKM).

The VEKM is utilized in executing a Label-and-Eliminate procedure for producing certain prime implicants or consequents used in tackling the two aforementioned problems.

The VEKM procedure is a time-saving short cut indeed, since it efficiently handles the three basic tasks demanded by the solution procedure, which are: (a) To combine several Boolean relations into a single one, (b) to compute conjunctive eliminants of a Boolean function, and (c) to derive the complete sum (CS) of a Boolean function.

The VEKM procedure significantly reduces the complexities of these tasks by introducing useful shortcuts and allowing simultaneous processing.

The VEKM procedure is described in detail, and then demonstrated via two illustrative examples, which previously had only black-box computer solutions as they were thought to be not amenable to manual solution.

The first example deals with switching or bivalent functions while the second handles 'big' Boolean functions.

Both examples indicate that the VEKM procedure proposed herein enjoys the merits of insightfulness, simplicity and efficiency