Accession Number : AD0690098

Title :   ON THE DELAY REQUIRED TO REALIZE BOOLEAN FUNCTIONS,

Corporate Author : ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Preparata,Franco P. ; Muller,David E.

Report Date : JUL 1969

Pagination or Media Count : 14

Abstract : Using as logic modules two-input one-output arbitrary logic gates, this paper considers the problem of the longest chain (Number of levels) in a tree-type interconnection realizing a Boolean function of n variables. Specifically, one is interested in the minimum number of levels L(n) by which one can constructively realize all Boolean functions of n variables. It was previously shown that L(n) = or < n for n = 3,4 and it was so conjectured for n = 5; in this paper one is able to show that this holds for n = 5, 6, 7 and conjecture that L(8) = or < 8. (Author)

Descriptors :   (*SPECIAL FUNCTIONS(MATHEMATICAL), *COMPUTER LOGIC), GATES(CIRCUITS), LOGIC CIRCUITS, THEOREMS

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE