Principle normal forms | Readstall

Principle normal forms

07-02-19 Himaja G 0 comment

Principle normal forms:  In the earlier we have discussed about normal forms ad conjunctive and disjunctive normal forms. These normal forms have principle forms. Now we discussed about the principle normal forms.

Principle disjunctive normal forms: Let P and Q be two statement variables. Let us construct all possible formulas which consist of conjunction of P or its negation and conjunctions of Q or its negation. None of the formulas should contain both a variable and its negation. Furthermore, any formula which is obtained by commuting the formulas in the conjunction is not included in the list because such a formulas will be equivalent to one included in the list. For example, either P∧ Q or Q ∧P is included, but not both. For two variables P and Q, they are:         P∧Q            P∧~Q          ~P∧Q             ~P∧~Q

These formulas are called min terms or Boolean conjunctions of P and Q. from the truth tables of these min terms, it is clear that no two min terms are equivalent. We assert that if the truth table of any formula containing only the variable P and Q is known, then one can easily obtain an equivalent formula which consists of a disjunction of some of the min terms. This statement is demonstrated as follows.

P Q PQ P~Q ~PQ ~P~Q
T T T F F F
T F F T F F
F T F F T F
F F F F F T

 

For every truth table T in the truth table of the given formula, select the min terms which also have the value T for the some combinations of the truth values of P and Q. the disjunctions of these min terms will then be equal to the given formula. This discussion provides the basic for a proof that formula containing any connective symbol is equivalent to a formula containing ∧, ∨ and ~.

For a given formula, an formula consisting of disjunctions of min terms only is known is principle disjunction normal form. Such a normal form is also called the sum-of-products canonical form.

Some examples are:

  1. P∧Q                          (P∧Q)∨(~P∧Q) ∨(~P∧~Q)
  2. P∨Q                          (P∧Q) ∨(P∧~Q) ∨(~P∧Q)
  3. ~(P∧Q)                   (P∧~Q) ∨(~P∧Q) ∨(~P∧~Q)
  4. ~P∨Q                       (~P∧(Q∨~Q)) ∨(Q∧ (P∨~P))

(~P∧Q) ∨(~P∧~Q) ∨(Q∧P) ∨(Q∧~P)

(~P∧Q) ∨(~P∧~Q) ∨(P∧Q)

  1. (P∧Q) ∨(~P∧R) ∨ (Q∧R)

(P∧Q∧ (R∨~R)) ∨(~P∧R∧ (Q∨~Q)) ∨(Q∧R∧ (P∨~P)

(P∧Q∧R) ∨ (P∧Q∧~R) ∨ (~P∧Q∧R) ∨ (~P∧~Q∧R)

Principle conjunctive normal forms:

           In order to define the principal conjunctive normal form, we first define the formulas as max terms. For a given number of variables, the max terms consists of disjunctions in which each variable or its negation, but not both, appears only once. Thus the max terms are the duals of min terms. Either from the duality principle or directly from the truth tables, it can be ascertained that each of the max terms has the truth value of F for exactly one combination of the truth value F for different combinations of the truth values of the variables.

In order to determine whether two given formulas P and Q are equivalent, one can obtain any one of the principle normal forms of the two formulas and compare them. It is not necessary assume that both formulas have the same variables. In fact each formula can be assumed to depend upon all the variables that appear in both two formulas, by introducing the missing variables and then reducing them to their principal normal forms.

Some examples are:

  1. (~PR) ∧ (Q⇔P)

⇔ (P∨R) ∧ (Q→P) ∧ (P→Q)

⇔ (P∨R) ∧ (~Q∨P) ∧ (~P∨Q)

⇔ (P∨R∨ (Q∧~Q)) ∧ (~Q∨P∨R(R∧~R)) ∧ (~P∨Q∨(R∧~R))

⇔ (P∨Q∨R) ∧ (P∨~Q∨R) ∧ (P∨~Q∨~R) ∧ (~P∨Q∨R)∧ (~P∨Q∨~R)

2.(P∧Q) ∨ (~ P∧R)

((P∧Q) ∨~P) ∧((P∧Q) ∨R)

(P∨~P) ∧(Q∨~P) ∧(P∨R) ∧(Q∨R)

(Q∨~P∨ (R∧~R)) ∧(P∨R∨ (Q∧~Q)) ∧(Q∨R∨(P∧~P))

(Q∨~P∨R) ∧ (Q∨~P∨~R) ∧ (P∨R∨Q) ∧ (P∨R∨~Q) ∧ (Q∨R∨P) ∧ (Q∨R∨~P)

(~P∨Q∨R) ∧ ( ~P∨Q∨~R) ∧ ( P∨Q∨R) ∧ ( P∨~Q∨R)



Leave a reply