Discrete Mathematics for Computer Science

Normal Forms 121

substituting always stops. Consider, for example, the substitution in the formula

(p -•* q) +- (r +-* s)

If the substitution is first performed on the second <+-, the resultant formula is

((p (-- q) - (r ++ s)) A ((r +* s) -- (p +* q))

which has more *->'s to replace than in the original formula! At first sight, one might

expect that if the substitutions are made in the wrong order, the process might continue

generating more +-*'s at each stage, and the process might continue forever. (Hint: One

method is to, instead of just counting the number of - symbols, put a weight on

each *-> symbol, with the weight of the ++ symbol in * X x being dependent on the

number of +*'s in V and X. If the correct method of calculating weights is used, it can

be shown that the total weight of the +-+'s decreases with each substitution.

28. The second stage of the procedure to "push negations inward" started with a formula
    whose only logical connectives are -, v, and A and constructed a tautologically equiv-
    alent formula with negations applied only to proposition letters.
    (a) Write an algorithm describing exactly what is done. The algorithm should work
    on formulas as strings of symbols. To avoid what in this case is irrelevant detail,
    the program should assume that all proposition letters are one character long and
    that any symbol encountered, except for (, ), A, V, and -- , is a proposition letter.
    Assume that the formula contains no blanks. (It is perhaps easiest to consider the
    program as a function that is passed the original formula-a string-as a parame-
    ter, and then returns the equivalent formula with all the negations pushed inward.
    It is easiest to use recursion to handle many subformulas.)
    (b) Prove that your program from part (a) works. (Hint: if your program in part (a)
    uses recursion to handle subformulas, it is natural to do this proof by induction on
    formulas. However, the induction may not be straightforward.)

Normal Forms

Although two formulas may be logically equivalent, one may be "easier" for someone to
understand or to manipulate. For example, in one formula, it may be easy to determine
that the formula is satisfiable. It may be fairly obvious that one formula is a tautology but
quite difficult to conclude that from the other form of the same formula. In this section, we
discuss two special forms or representations for formulas logically equivalent to a given
formula. These forms are called disjunctive normal forms and conjunctive normal forms.
Formulas in conjunctive normal form make it easy to determine when a formula is satisfi-
able. Formulas in disjunctive normal form are easy to use when asking whether a formula
is a tautology. These special forms have assumed prominence in computer science, in both
theoretical and applied areas. The famous P 0 .A/P problem deals with conjunctive nor-
mal forms, and combinatorial networks use both conjunctive and disjunctive normal forms
to find representations of combinatorial circuits.