Browse Prior Art Database

Comparing Boolean Expressions of Constant Relations

IP.com Disclosure Number: IPCOM000034354D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 4 page(s) / 79K

Publishing Venue

IBM

Related People

Kruskal, V: AUTHOR

Abstract

A technique is described whereby two Boolean expressions of constant relations are compared for their logical relationship to one another. The concept is a generalization over previous methods of comparing propositional Boolean expressions. Described is a method which systematically computes and encodes the comparisons as a four-bit quantity. The Boolean expressions of constant relations involved herein are the type that are connected normally with ANDs, ORs, NOTs and parentheses. The constant relations are of the form NRC, where N is the symbolic name, R is any of the normal arithmetic relations, such as <, &, =, /, /, and >, and C is a constant number.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 34% of the total text.

Page 1 of 4

Comparing Boolean Expressions of Constant Relations

A technique is described whereby two Boolean expressions of constant relations are compared for their logical relationship to one another. The concept is a generalization over previous methods of comparing propositional Boolean expressions. Described is a method which systematically computes and encodes the comparisons as a four-bit quantity. The Boolean expressions of constant relations involved herein are the type that are connected normally with ANDs, ORs, NOTs and parentheses. The constant relations are of the form NRC, where N is the symbolic name, R is any of the normal arithmetic relations, such as <, &, =, /, /, and >, and C is a constant number. To compare two such Boolean expressions is to determine any relationships they have with one another: consistent, inconsistent, equivalent and implication (one way or the other). A standard method of comparing two propositional Boolean expressions is by compilation.

Such expressions have literals, not constant relations, connected with ANDs, ORs, NOTs, and parentheses. A literal is a symbolic name that may have the value TRUE or FALSE. If the complexity of two Boolean expressions is not too great, they can be compared by compilation. Here all possible values of the literals (TRUE or FALSE) are cycled through, so as to evaluate the Boolean expressions in every case (2n cases, where n is the number of distinct literals).

If, in each case, the two Boolean expressions evaluate to the same truth value, they are equivalent; if always different, they are inconsistent; if in one case they both evaluate to TRUE, they are consistent; and if whenever one evaluates to TRUE and the other does also, the first implies the second. Because each Boolean expression must be evaluated 2n times, execution time is important. Compiling each Boolean expression into machine language subroutine to be called 2n times can speed up the process. For example, a full word (32 bits) can be assigned to each distinct literal. Each word contains all zeros, for FALSE, or all ones, for TRUE. The code generated is typically one having a stack to support the parentheses and AND instructions for the Boolean AND (N or NR, such as used in IBM 370 architecture), its OR instruction for OR (O or OR) and the complement for NOT (XR R,ALLONES, where "ALLONES" is a register initialized to all ones). The operation through all possible truth values is straight- forward. The words that correspond to the Boolean literals are initialized to all zeros. After the generated subroutines are executed for the two Boolean expressions (and the results compared) the word at the highest location is changed to all ones, the subroutines are executed again and so forth. So as to ensure that all 2n cases are cycled through, it is desirable to consider the n words as an n-bit binary number, such that all zeros stand for 0 and all ones stand for 1. At the end of each execution/comparison, a 1 (all on...