Book contents
- Frontmatter
- Contents
- List of Algorithms
- Preface
- PART I PRELIMINARIES
- PART II COMBINATIONAL CIRCUITS
- 9 Representations of Boolean Functions by Formulas
- 10* The Digital Abstraction
- 11 Foundations of Combinational Circuits
- 12 Trees
- 13 Decoders and Encoders
- 14 Selectors and Shifters
- 15 Addition
- 16 Signed Addition
- PART III SYNCHRONOUS CIRCUITS
- PART IV A SIMPLIFIED DLX
- Bibliography
- Index
9 - Representations of Boolean Functions by Formulas
from PART II - COMBINATIONAL CIRCUITS
Published online by Cambridge University Press: 05 November 2012
- Frontmatter
- Contents
- List of Algorithms
- Preface
- PART I PRELIMINARIES
- PART II COMBINATIONAL CIRCUITS
- 9 Representations of Boolean Functions by Formulas
- 10* The Digital Abstraction
- 11 Foundations of Combinational Circuits
- 12 Trees
- 13 Decoders and Encoders
- 14 Selectors and Shifters
- 15 Addition
- 16 Signed Addition
- PART III SYNCHRONOUS CIRCUITS
- PART IV A SIMPLIFIED DLX
- Bibliography
- Index
Summary
In Chapter 6, we used Boolean formulas to represent Boolean functions. The idea was to write a Boolean formula over a set of n variables and then assign 0−1 values to each variable. This assignment induces a truth value to the formula, and thus we have a Boolean function over n bits. In fact, any Boolean function can be represented by a Boolean formula if the set of connectives is complete. In Section 6.6, we proved that the set {¬, and, or} is a complete set of connectives.
In this chapter, we consider special representations of functions that are often called normal forms. Boolean formulas in a normal form are restricted forms of formulas.
Given a Boolean function, one may want to find a shortest representation of the function by a Boolean formula. This question is not well defined because one needs to specify how a Boolean function is represented. Suppose the function is described by its truth table. In this case, the truth table has 2n entries, where n denotes the number of bits in the domain of the function. Obviously, we can only read or write truth tables for rather small values of n. If n ≥ 100, then all the atoms in the universe would not suffice!
Nevertheless, we present a method by Quine and McCluskey to find a shortest representation of a function by a Boolean formula in a normal form called a sum of products.
- Type
- Chapter
- Information
- Digital Logic DesignA Rigorous Approach, pp. 109 - 132Publisher: Cambridge University PressPrint publication year: 2012