Equivalence of Formulas | Readstall

Equivalence of Formulas

03-02-19 Himaja G 0 comment

EQUIVALENCE OF FORMULAS                                                      

Let A and B be two statement formulas and let p1 ,p2,…..pn. Denote all variables occurring in both A and B. Consider an assignment of truth values to p1, p2, …. pn. And the resulting truth values of A and B.  Assuming that the variables and the assignment and truth values to the variables appearing in the same order in the truth tables of A and B, then the final columns in the truth tables for A and B are identical if A and B are equivalent.

In the below we have some examples of formulas which are equivalent verify their equivalence by truth tables:

  1. ~(~P) is equivalent to P                                                                 

 

P ~P ~(~P)
T F T
F T F

 

In the above truth table the identical values of  P and ~(~P) are same. So they are equivalent to each other.


2.(P∧~P) ∨ Q  is equivalent to Q

P Q ~P P~P (P∧~P) ∨
T T F F T
T F F F F
F T T F T
F F T F F

In the above truth table (P∧~P) ∨ Q   and Q identical values are equivalent.

In the definition of two equivalence of two formulas, it is not necessary to assume that they both contain same variables. This point is illustrated in the above example given (2).  It may , however, be denoted that if two formulas are equivalent and a  Particular variable only on them, in (2) the truth values of (P∧~P) ∨ Q   is independent of the truth value of P.

Equivalence is a symmetric relation; that is, ”A is equivalent to B” is the same as “B is equivalent to A”. Also if A⇔B and B⇔C , then A equivalent to C. This relation may also be expressed by saying that the equivalence of statement formulas is transitive.

Some of the equivalent formulas are:

   1.Idempotent laws:

P∨P⇔P                    P∧P⇔P                                                                                      (1)

 2 .Associative laws:

(P∨Q) ∨RP∨(Q∨R)                     (P∧Q) ∧R⇔P∧ (Q∧R)                                        (2)

 3 .Commutative laws:   

P∨Q⇔Q∨P                 P∧Q⇔Q∧P                                                                             (3)

4.Distributive laws:

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

5 .Absorption laws:

P∨F⇔P                                                            P∧T⇔P                                            (5)

P∨T⇔T                                                             P∧F⇔F                                            (6)

P∨~P⇔T                                                           P∧~P⇔F                                         (7)

P∨ (P∧Q) ⇔P                                                  P∧ (P∨Q) ⇔P                                  (8)

6 .De Morgan’s laws:

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

Example  problem on equivalent formulas:

Ex:1 .Show that (~P∧(~Q∧R)) ∨ (Q∧R) ∨ (P∧R)⇔R

Solution:

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

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

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

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

(~(P∨ Q) ∨ (P∨ Q)) ∧R                                                      using(9),(3)

T∧R                                                                                        using(7)

R                                                                                             using(5)



Leave a reply