THE PRINCIPLE OF INCREASING OF THE DEGREE OF INDETERMINACY OF BOOLEAN FUNCTIONS, AN ALGORITHM FOR DETERMINING THE SHORTEST DISJUNCTIVE NORMAL,
Abstract:
The article deals with investigating the properties of disjunctive normal forms d.n.f. realizing a partially definite Boolean function. The first part of the article examines a set of nonsimplifiable reduced d.n.f. r.d.n.f. derived by increasing the degree of indeterminacy of a given partially definite Boolean function. It is shown that a set of nonsimplifiable r.d.n.f. does not contain any redundant information on irredundant d.n.f.i.d.n.f.. The second part of the article illustrates the usefulness of the determination of the set of r.d.n.f. as exemplified by the construction of the shortest d.n.f. of a partially definite Boolean function phixl, ..., xn. It is demonstrated that one of the r.d.n.f., here termed the main nonsimplifiable r.d.n.f., engenders the set of i.d.n.f. of the function phixl, ..., xn, containing the shortest d.n.f. An algorithm for the construction of the i.d.n.f. that is the shortest in the interior of a set of i.d.n.f. of the function phixl, ..., xn is presented and ways of improving this algorithm are considered.