Disjunctive normal form

DISJUNCTIVE NORMAL FORM

For several reasons it is often useful to express any string in a set or normal form--one that uses just a few signals in a particular way. In disjunctive normal form we rewrite a string so that we are thinking of a disjunction of possible conjunctions--as in PQARSAO. (In conjunctive normal form we are thinking of a conjunction of possible disjunctions--as in PQORSOA.)
For the sake of simplicity, strings such as P or PN, PQA or PQARA will not be rewritten (although we could, for example, always say PPO for P).

In order to convert to disjunctive normal form (DNF), we can make use of various substitution rules. For example, we can take the string PQRCCSA through the following steps:
PNQRCOSA.....................CO subs
PNQNROOSA..................CO subs
PNSA QNSA RSA OO.....AO subs

An easier technique is to use the rules for a consistency tree and combine the results.
..................PQRCCSA
....................PQRCC
........................S
....................../...\
...................PN..QRC
........................../..\
....................QN...R
Note that S has to be combined with each of the strings in the three branches:
PNSA QNSA RSA OO.

Go back to the starting page.