Using Variable-Entered Karnaugh Maps in Determining Dependent and Independent Sets of Boolean Functions

An important class for Boolean reasoning problems involvesinterdependence among the members of a set T of Boolean functions.Two notable problems among this class are (a) to establish whether agiven subset of T is dependent, and (b) to produce economicalrepresentations for the complementary families of all dependentsubsets and independent subsets of T. This paper solves these twoproblems via a powerful manual pictorial tool, namely, the variableentered Karnaugh map (VEKM). The VEKM is utilized in executing aLabel-and-Eliminate procedure for producing certain prime implicantsor consequents used in tackling the two aforementioned problems. TheVEKM procedure is a time-saving short cut indeed, since it efficientlyhandles 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 VEKMprocedure significantly reduces the complexities of these tasks byintroducing useful shortcuts and allowing simultaneous processing.The VEKM procedure is described in detail, and then demonstratedvia two illustrative examples, which previously had only black-boxcomputer solutions as they were thought to be not amenable to manualsolution. The first example deals with switching or bivalent functionswhile the second handles 'big' Boolean functions. Both examplesindicate that the VEKM procedure proposed herein enjoys the meritsof insightfulness, simplicity and efficiency