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 phi(xl, ..., 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 phi(xl, ..., 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 phi(xl, ..., xn) is presented and ways of improving this algorithm are considered.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 11, 1968
- Accession Number
- AD0685533
Entities
People
- Yu. N. Kornev
Organizations
- National Air and Space Intelligence Center