Normal forms | Readstall

Normal forms

05-02-19 Himaja G 0 comment

Normal forms:   The problem of determining, in a finite number of steps, whether given statement formula is a tautology or a contradiction or at least satisfying is known as a decision problem. The construction of truth table involves a finite number of steps, and, as such, a decision problem can be posed for other logical statements, particularly for the predicate calculus. However in the later case, the solution of the decision problem may not be simple. The earlier we solve truth table on some statement formulas. The construction of truth tables may not be practical, even with use of computer. So, we may consider further procedures are known as normal forms.

In this we have two types of normal forms. They are:

  1. Disjunctive normal forms
  2. Conjunctive normal forms 

1.Disjunctive normal forms:

A formula which is equivalent to a given formula and which consists of a sum of elementary products is called disjun place of “disjunction” in our negation is called an elementary sum. It will be convenient to use the word “product” in place of nctive normal form of the given formula. A product of the variables and their negations in a formula is called an elementary product. Similarly, a sum of the variables and their word “product” in place of “conjunction” and “sum” i“conjunction” and “sum” in place of “disjunction” in our current discussion.

Let P and Q be any two atomic variables. Then  P, ~P∨Q, ~Q∨P∨~P, P∨~P, and Q∨~Q are some examples on elementary sum of the variables. Any part of an elementary sum or product which itself an elementary sum or product is called a factor of the original elementary sum or product. Thus ~Q, P∧~P, ~Q∧P are some of the factors of ~Q∧P∧~P. the following statements hold for elementary sum and products.

A necessary and sufficient condition for elementary sum to be identically rue is that if contain at least one pair of factors in which one is the negation of the other.

Ex: 1.Obtain the disjunctive normal form of (a): P∧ (P Q)

Answer:   P∧ (P Q) P∧(~P∨Q)

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

 (b):  ~ (P∨Q) ⇔ (P∧Q)

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

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

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

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

This is the required normal form.

The disjunctive normal of a given is not unique. In fact, different disjunctive normal forms can be obtained for a given formula if the disjunctive laws are applied in different ways.

   Conjunctive normal forms:

A formula which is equivalent to a given formula and which consists of a product of elementary sum is called conjunctive normal form of the given formula. A product of the variables and their negations in a formula is called an elementary sum. Similarly, a sum of the variables and their word “product” in place of “conjunction” and “sum” in place of “disjunction” in our negation is called an elementary sum. It will be convenient to use the word “product” in place of “conjunction” and “sum” in place of “disjunction” in our current discussion.

A necessary and sufficient condition for an elementary product to be identically false is that it contains at least one pair of factors in which one is negation of the other.

Let P and Q be any two atomic variables. Then ~P∧Q , ~Q∧P∧~P, P∧~Q, and Q∧~P are some examples of elementary products.

Ex: 1.Obtain the conjunctive normal form of (a): P∧ (P Q)

Answer:   P∧ (P Q) P∧ (~P∨Q)

                                       P∧ (~P∨Q)

This is the required normal form.

 (b):  ~ (P∨Q) ⇔ (P∧Q)

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

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

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

This is the required normal form.

The conjunctive normal of a given is not unique. In fact, different conjunctive normal forms can be obtained for a given formula if the conjunctive laws are applied in different ways.

 

 



Leave a reply