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**

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**

** **

(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 *.

** **

(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.

** **

(i) *p* ∨ ( *q*
∨ *r*
)
≡
(
*p* ∨ *q*
)
∨ *r*
(ii) *p* ∧ ( *q*
∧ *r*
)
≡
(
*p* ∧ *q*
)
∧ *r*
.

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.

** **

(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.

** **

(i) *p* ∨ **T **≡ **T **and *p* ∨ **F **≡ *p*

(ii) *p* ∧ **T **≡ *p* and *p* ∧ **F** ≡ **F**

(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* ∧ **T** ≡ *p* and *p* ∧ **F** ≡ **F** can
be proved.

** **

(i) *p* ∨ ¬ *p*
≡
**T** and *p* ∧ ¬
*p* ≡ **F** (ii) ¬**T**
≡ **F** and ¬**F** ≡ **T**

(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.

** **

¬(¬ *p***)** ≡ *p*

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

** **

(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.

** **

(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.

** **

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

* p*↔ *q* ≡ ( *p* → *q* ) ∧ (*q* → *p*)

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

Using
the equivalence property, show that *p*
↔
*q* ≡ ( *p* ∧ *q* ) ∨ ( ¬ *p*
∧
¬*q*) .

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

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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