Browse Prior Art Database

Matrix Method of Modifying Logical Expressions

IP.com Disclosure Number: IPCOM000085619D
Original Publication Date: 1976-May-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 15K

Publishing Venue

IBM

Related People

Demers, RA: AUTHOR

Abstract

It is occasionally necessary to simplify logical expressions such that all factored clauses are distributed. Herein described is an algorithm which uses a matrix to organize pointers to the clauses of a logical expression. Further simplifications involving the application of DeMorgan's Laws are also described.

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

Page 1 of 3

Matrix Method of Modifying Logical Expressions

It is occasionally necessary to simplify logical expressions such that all factored clauses are distributed. Herein described is an algorithm which uses a matrix to organize pointers to the clauses of a logical expression. Further simplifications involving the application of DeMorgan's Laws are also described.

Given an expression such as,

(A AND (B OR C)), (1) the problem is to distribute the "and" clause over the "or" clause and generate the expression: (A AND B) OR (A AND C).

This obviously is a very simple example. The algorithm described herein is capable of simplifying more complex expressions.

Assume that expression (1) has been parsed and converted to reverse Polish form and that a tree structure of pointers has been built. The resulting tree structure is:

(Image Omitted)

such that M = 0 and M (1, 1) = tree pointer, and the row and column pointers =


1.

Loop through M in row major order, applying the following rules:

1. If the index at column 1 of a row is 0, quit.

2. If the index is 0, increment the row pointer

and reset the column pointer to 1.

3. If the index points to an operand, increment

the column pointer. The left tree pointer is

0 for an operand.

4. If the index points to an AND operator, replace

the index in the matrix with its left tree

pointer and put its right tree pointer in the

next available column of the same row.

5. If the index points to an OR operator, copy the

row into the next available row, replace the

index in the original row with its left tree

and replace the index in the new row with its

right tree pointer.

The following figure illustrates the application of these rules for expression
(1).

(Image Omitted)

Note that for this simple case, the algorithm reaches the desired matrix in four steps but continues to process until the quit rule is reached, thereby verifying complete simplification of the

1

Page 2 of 3

expression. If an expression is already fully simplified, the algorithm serves to prove this fact. The resulting matrix may be interpreted in the following way: 1. "and" the clauses in a row.

2. "or" the rows.

Thus, the result: (1 AND 2) OR (1 AND 3)

or (A AND B) OR (A AND C).

The NOT operator is easily added to this algorithm to provide a complete set of Boolean operators. Note that NOT is a unary operator and its right tree pointer is always zero. The following four rules are added to the basic set: 6. If the index points to a NOT operator, replace it

with a pointer to the negative of its left tree

operand. This results in the following

transformation:

NOT (A AND B) --> (A NAND B)

NOT (A OR B) --> (A NOR B)

NOT (NOT A) --> (IS A)

7. If the index points to a NAND operator,

copy the row into the next available row,

replace the index in the original row with

a pointer to the negative of its left tree

operand, and replace the index in the new

row with a pointer to the negative of its

right tree operand.

This results in the following transformation:

(...