Browse Prior Art Database

Optimization of Boolean Expressions-Historical Developments

IP.com Disclosure Number: IPCOM000129346D
Original Publication Date: 1980-Jul-01
Included in the Prior Art Database: 2005-Oct-05
Document File: 14 page(s) / 60K

Publishing Venue

Software Patent Institute

Related People

JACK MINKER: AUTHOR [+3]

Abstract

Boolean expressions play an essential role in all aspects of computer science. Interest in them is rooted in compiler design. Clearly, every compiler must be designed to evaluate Boolean expressions. It is theK6oK essential that the compiled code be as efficient as possible. Historical developments OF this subject and Plated topics am discussed. Given a Boolean expression, techniques am described to optimize its evaluation. The optimum solution to the Boolean expression evaluation is presented for the situation when probabilities are known concerning whether or not the propositional variables evaluate to true (T), and costs am given to determine the evaluation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1980 by the American Federation of Information Processing Societies, Inc. Used with permission.

Optimization of Boolean Expressions-Historical Developments

JACK MINKER

RITA G. MINKER

  (Image Omitted: © 1980 by the American Federation of Information Processing Societies, Inc. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the AFIPS copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the American Federation of Information Processing Societies, Inc. To copy otherwise, or to republish, requires specific permission. Authors' address: Jack Minker, Department of Computer Science and the Institute for Physical Science & Technology, University of Maryland, College Park, MD 20742. Rita C. Minker, Division of Computer Research and Technology, National Institutes of Health, Bethesda, MD 20205. Note: Jack Minker's work on this paper was supported by the F National Science Foundation under grant number NSF MCS 73-03433-02, and by the National Aeronautics and Space Administration under grant number NGR 21-002-

270.9. © 1980 AFIPS0164-1239/80/030227-238

Optimization of Boolean Expressions-Historical Developments

JACK MINKER

RITA G. MINKER .00/0)

Boolean expressions play an essential role in all aspects of computer science. Interest in them is rooted in compiler design. Clearly, every compiler must be designed to evaluate Boolean expressions. It is theK6oK essential that the compiled code be as efficient as possible. Historical developments OF this subject and Plated topics am discussed. Given a Boolean expression, techniques am described to optimize its evaluation. The optimum solution to the Boolean expression evaluation is presented for the situation when probabilities are known concerning whether or not the propositional variables evaluate to true (T), and costs am given to determine the evaluation.

Keywords and phrases: Boolean expressions, branch and bound, code optimization, decision tables, historical developments, take transformation

CR category: 1.2

1 Introduction

The development of Boolean algebra in 1847 by George Boole was very important for mathematics, engineering, and computer science. Each of these fields has benefited by the use of this work.

The primary purpose of this paper is to trace the history of algorithms that optimize the evaluation of Boolean expressions. A Boolean expression is an expression constructed of

IEEE Computer Society, Jul 01, 1980 Page 1 IEEE Annals of the History of Computing Volume 2 Number 3, Pages 227-238

Page 2 of 14

Optimization of Boolean Expressions-Historical Developments

Boolean variables connected by the binary logical operators A (and) and V (or) and by the unary operator [NB: math has not been copy edited] (not). Boolean variables take on tw...