Accession Number : AD0685533

Title :   THE PRINCIPLE OF INCREASING OF THE DEGREE OF INDETERMINACY OF BOOLEAN FUNCTIONS, AN ALGORITHM FOR DETERMINING THE SHORTEST DISJUNCTIVE NORMAL,

Corporate Author : FOREIGN TECHNOLOGY DIV WRIGHT-PATTERSON AFB OHIO

Personal Author(s) : Kornev,Yu. N.

Report Date : 11 OCT 1968

Pagination or Media Count : 27

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.

Descriptors :   (*MATHEMATICAL LOGIC, SPECIAL FUNCTIONS(MATHEMATICAL)), COMPUTER LOGIC, ALGEBRAS, SET THEORY, ALGORITHMS, THEOREMS, USSR

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE