UNIT 1 : mathematical logic and predicates ..

If u want to see the material on mathematical logic : click here

Some important formulas ...

Normal form or canonical form ...

It is of two types 

=> conjunctive normal form [c n f]

=> disjunctive normal form  [d n f]

Disjunctive = addition

conjuctive normal form =product

elementary product : a product of variables and their negation in a formula is called elementary product .

ex : ~p^q 

elementary sum : a sum of variable of variable and their negation in a formula is called elementary sum .

ex : ~pvq

factor : any part of elementary sum r product which is itself an elementary sum r product .

Normal Forms

Let A(P₁, P₂, P₃, …, P_n) be a statement formula where P₁, P₂, P₃, …, P_n are the atomic variables. If A has truth value T for all possible assignments of the truth values to the variables P₁, P₂, P₃, …, P_n , then A is said to be a tautology. If A has truth value F, then A is said to be identically false or a contradiction.

1.2.1 Disjunctive Normal Forms

A product of the variables and their negations in a formula is called an elementary product. A sum of the variables and their negations is called an elementary sum. That is, a sum of elementary products is called a disjunctive normal form of the given formula.

Example:

The disjunctive normal form of

1. PÙ (P® Q) Û PÙ (ù PÚ Q) Û (PÙ ù P)Ú (PÙ Q).

1.2.2 Conjunctive Normal Forms

A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of a given formula.

Example 1:

The conjunctive normal form of
(a) P Ù (P® Q) Û P Ù (ù P Ú Q).

(b) ù (P Ú Q) Û ù P Ù ù Q. 

Example 2:

(a) Show that the formula ù B Ú (ù A Ù B) Ú (A Ù B) is a tautology.

ù B Ú (ù A Ù B) Ú (A Ù B) Û ù B Ú ((ù A Ú A) Ù B)
Û (ù B Ú ù A Ú A) Ù (ù B Ú B)
Û T Ù T
Û T.
Therefore, it is a tautology.

(b) Show that the formula (ù B Ù A) Ù B is a contradiction.

(ù B Ù A) Ù B Û A Ù (B Ù ù B)
Û A Ù F Û F.
Therefore, it is a contradiction.

(c) Show that (Q® P) Ù ( ù P Ù Q) is a contradiction.

(Q® P) Ù ( ù P Ù Q) Û (ù Q Ú P) Ù (ù P Ù Q)
Û (ù P Ù Q Ù ù Q) Ú (P Ù ù P Ù Q)
Û F Ú F
Û F.
Therefore, it is a contradiction.

1.2.3 Principal Disjunctive Normal Form (PDNF)

Let us assume A and B be two statement variables. All possible formulas by using conjunction are given as follows. The total number of formulas for two variables A and B are 2² formulas. They are A Ù B, A Ù ùB,
ùA Ù B and ù A Ù ù B.

These are called minterms or Boolean conjunctions of A and B. The minterms (2ⁿ terms) are denoted by M₀, M₁, … ,M₂ⁿ_-1.

A formula equivalent to a given formula consisting of the disjunction of minterms only is called PDNF of the given formula.

1.2.4 Principal Conjunctive Normal Forms (PCNF)

The duals of minterms are called maxterms. For a given number of variables the maxterm consists of 

disjunctions in which each variable or its negation, but not both, appears only once.

For a given formula, an equivalent formula consisting of conjunctions of maxterms only is known as its principal conjunctive normal form. This is also called the product of sums canonical form.

DISJUNCTION NORMAL FORM EXAMPLE :


1) p^(p->q)


sol ; p^(~pvq)
       
      ( p^~p)v(p^q)           ..{ asso .pro}


===> sum of two product terms 


CONJUNCTIVE NORMAL FORM :


1) pv(p->q)


    pv( p^~q)
    
   (PVP)^(PV~Q)


===> product of two elementary sums