Semantic and Syntactic Simplification of Truth Functions
Door: Verstralen, H.H..F.M. | 01-01-1990 The purpose of Project 'optimal Item Selection' is to solve a number of issues in automated test design, making extensive use of optimization techniques.some restrictions in Linear Programming (LP) problems are easier formulated as a Boolean expression. Here we describe a way to translate a Boolean expression, or the associated function, via a Disjunctive Normal Form (DNF) representation, to an equivalent aet of linear restrictions. The transformation of a truth function f into the wanted DNF proceeds in two steps. First the set PI(f) of prime implicants of f is calculated, and
second a 'cheapest• subset of PI, equivalent with f is chosen. The best known algorithms for the first step, to find PI (f) , are the semantic algorithm of Quine (1952) and Mccluskey (1956) or, if one has a Boolean
expression for f, the syntactic algorithm of Quine (1955) . The first algorithm is appreciably improved, and the scope of the second is enlarged to include valid formula's. As a consequence it can also be used as a
validity test for Boolean expressions. The second step is discussed as well, where the suggestions of Quine (1955) are supplemented with two properties of redundant elements of PI (f) , that make their identification more easy. However, the set covering approach to the second step appears to be better suited.
Kunnen we je helpen?
Stel je vraag via onze kanalen of kijk in de veelgestelde vragen.
Voor scholen: Vergeet niet om het brinnummer bij de hand te hebben en/of in de mail te vermelden, zodat we jouw vraag sneller kunnen behandelen!