ON THE DELAY REQUIRED TO REALIZE BOOLEAN FUNCTIONS,

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)

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1969
Accession Number
AD0690098

Entities

People

  • David E. Muller
  • Franco P. Preparata

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Circuits
  • Complex Variables
  • Electrical Circuits
  • Electrical Equipment
  • Electronic Circuits
  • Electronic Equipment
  • Functions (Mathematics)
  • Logic
  • Logic Devices
  • Logic Gates
  • Mathematical Analysis

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Programming and Software Development.