Home | | Maths 12th Std | Some Laws of Logical Equivalence

Mathematical Logic | Discrete Mathematics | Mathematics - Some Laws of Logical Equivalence | 12th Maths : UNIT 12 : Discrete Mathematics

Chapter: 12th Maths : UNIT 12 : Discrete Mathematics

Some Laws of Logical Equivalence

Any two compound statements A and B are said to be logically equivalent or simply equivalent if the columns corresponding to A and B in the truth table have identical truth values.

Mathematical Logic

Logical Equivalence

Definition 12.20

Any two compound statements A and B are said to be logically equivalent or simply equivalent if the columns corresponding to A and B in the truth table have identical truth values. The logical equivalence of the statements A and B is denoted by A B or A B .

From the definition, it is clear that, if A and B are logically equivalent, then A B must be tautology.

 

Some Laws of Equivalence

 

1. Idempotent Laws

(i) p p p

(ii) p p p .

Proof


In the above truth table for both p , p p and p p have the same truth values. Hence p p p and p p p .

 

2. Commutative Laws

(i) p q q p

(ii) p q q p .

Proof (i)


The columns corresponding to p q and q p are identical. Hence p q q p .

Similarly (ii) p q q p can be proved.

 

3. Associative Laws

(i) p ( q r ) ( p q ) r (ii) p ( q r ) ( p q ) r .

Proof

The truth table required for proving the associative law is given below.


The columns corresponding to ( p q ) r and p ( q r ) are identical.

Hence p ( q r ) ( p q ) r .

Similarly, (ii) p ( q r ) ( p q ) r can be proved.

 

4. Distributive Laws

(i) p ( q r ) ( p q ) ( p r)

(ii) p ( q r ) ( p q ) ( p r)

Proof (i)


The columns corresponding to p ( q r) and ( p q ) ( p r) are identical. Hence p ( q r ) ( p q ) ( p r) .

Similarly (ii) p ( q r ) ( p q ) ( p r) can be proved.

 

5. Identity Laws

(i) p T T and p F p

(ii) p T p and p FF


(i) The entries in the columns corresponding to p T and T are identical and hence they are equivalent. The entries in the columns corresponding to p F and p are identical and hence they are equivalent.

Dually

(ii) p Tp and p FF can be proved.

 

6. Complement Laws

(i) p ¬ p T and p ¬ p F (ii) ¬T F and ¬F T

Proof


(i) The entries in the columns corresponding to p ¬ p and T are identical and hence they are equivalent. The entries in the columns corresponding to p ¬ p and F are identical and hence they are equivalent.

(ii) The entries in the columns corresponding to ¬T and F are identical and hence they are equivalent. The entries in the columns corresponding to ¬F and T are identical and hence they are equivalent.

 

7. Involution Law or Double Negation Law

 ¬(¬ p)p

Proof


The entries in the columns corresponding to ¬ ( ¬p) and p are identical and hence they are equivalent.

 

8. de Morgan’s Laws

(i) ¬ ( p q) ¬ p ¬q

(ii) ¬ ( p q) ≡ ¬p ¬q

Proof of (i)


The entries in the columns corresponding to ¬ ( p q ) and ¬ p ¬q are identical and hence they are equivalent. Therefore ¬ ( p q) ¬ p ¬q . Dually (ii) ¬ ( p q) ≡ ¬p ¬q can be proved.

 

9. Absorption Laws

(i) p ( p q ) p

(ii) p ( p q ) p


(i) The entries in the columns corresponding to p ( p q) and p are identical and hence they are equivalent.

(ii) The entries in the columns corresponding to p ( p q) and p are identical and hence they are equivalent.

 

Example 12.17

Establish the equivalence property: p q ≡ ¬ p q

Solution


The entries in the columns corresponding to p q and ¬ p q are identical and hence they are equivalent.

 

Example 12.18

Establish the equivalence property connecting the bi-conditional with conditional:

 pq( pq ) (qp)

Solution


The entries in the columns corresponding to p q and ( p → q ) ( q → p) are identical and hence they are equivalent.

 

Example 12.19

Using the equivalence property, show that p q ( p q ) ( ¬ p ¬q) .

Solution

It can be obtained by using examples 12.15 and 12.16 that

 p q ( ¬ p q) ( ¬q p)

... (1)

(¬ p q) ( p ¬q) (by Commutative Law)

... (2)

 ( ¬ p ( p ¬q )) ( q ( p ¬q)) (by Distributive Law)

 ( ¬ p p) ( ¬p ¬q) ( q p) ( q ¬q) (by Distributive Law)

F ( ¬p ¬q) ( q p) F; (by Complement Law)

 ( ¬ p ¬ q ) ( q p) ; (by Identity Law)

 ( p q ) (¬ p ¬q) ; (by Commutative Law)

Finally (1) becomes p q ( p q ) (¬ p ¬q) .

Tags : Mathematical Logic | Discrete Mathematics | Mathematics , 12th Maths : UNIT 12 : Discrete Mathematics
Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
12th Maths : UNIT 12 : Discrete Mathematics : Some Laws of Logical Equivalence | Mathematical Logic | Discrete Mathematics | Mathematics


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.