Tutorialspoint.dev

Mathematics | Propositional Equivalences

Introduction
Two logical expressions are said to be equivalent if they have the same truth value in all cases. Sometimes this fact helps in proving a mathematical result by replacing one expression with another equivalent expression, without changing the truth value of the original compound proposition.

Types of propositions based on Truth values

    There are three types of propositions when classified according to their truth values



  1. Tautology – A proposition which is always true, is called a tautology.
  2. Contradiction – A proposition which is always false, is called a contradiction.
  3. Contingency – A proposition that is neither a tautology nor a contradiction is called a contingency.

Example,

1. p vee 
eg p  is a tautology.
2. p wedge 
eg p  is a contradiction.
3. p vee q  is a contingency.

Definition of Logical Equivalence
Formally,
Two propositions p and q are said to be logically equivalent if p leftrightarrow q is a Tautology. The notation pequiv q is used to denote that p and q are logically equivalent.
One way of proving that two propositions are logically equivalent is to use a truth table. The truth table must be identical for all combinations for the given propositions to be equivalent. But this method is not always feasible since the propositions can be increasingly complex both in the number of propositional variables used and size of the expression.
In this case, there needs to be a better way to prove that the two given propositions are logically equivalent. That better way is to construct a mathematical proof which uses already established logical equivalences to construct additional more useful logical equivalences.
Some basic established logical equivalences are tabulated below-

  egin{tabular}{ ||c||c|| }      hline     Equivalence & Name of Identity\     hline          hline     pwedge T equiv p &  Identity Laws\     pvee F equiv p &  \     hline          pwedge F equiv F &  Domination Laws\     pvee T equiv T &  \     hline          pwedge p equiv p &  Idempotent Laws\     pvee p equiv p &  \     hline          
eg(
eg p) equiv p &  Double Negation Law\     hline          pwedge q equiv qwedge p &  Commutative Laws\     pvee q equiv qvee p &  \     hline          (pwedge q) wedge requiv pwedge (q wedge r) &  Associative Laws\     (pvee q) vee requiv pvee (q vee r) &  \     hline      pwedge (q vee r)equiv (pwedge q)vee (pwedge r) &  Ditributive Laws\     pvee (q wedge r)equiv (pvee q)wedge (pvee r) &  \     hline          hline      
eg(pwedge q) equiv 
eg p vee 
eg q &  De Morgan's Laws\     
eg(pvee q) equiv 
eg p wedge 
eg q &  \     hline      pwedge (p vee q)equiv p &  Absorption Laws\     pvee (p wedge q)equiv p &  \     hline          pwedge 
eg p equiv F &  Negation Laws\     pvee 
eg p equiv T &  \     hline end{tabular}

The above Logical Equivalences used only conjunction, disjunction and negation. Other logical Equivalences using conditionals and bi-conditionals are-



 egin{tabular}{ ||c|| } hline p
ightarrow q equiv 
eg pvee q \  p
ightarrow q equiv 
eg q
ightarrow 
eg p \ pwedge q equiv 
eg(q
ightarrow 
eg p)\ (p
ightarrow q)wedge (p
ightarrow r) equiv p
ightarrow (qwedge r)\ (p
ightarrow r)wedge (q
ightarrow r) equiv (pvee q)
ightarrow r\ (p
ightarrow q)vee (p
ightarrow r) equiv p
ightarrow (qvee r)\ (p
ightarrow r)vee (q
ightarrow r) equiv (pwedge q)
ightarrow r\  hline end{tabular} quad egin{tabular}{ ||c|| } hline pleftrightarrow q equiv (p
ightarrow q) wedge (q
ightarrow p) \ pleftrightarrow q equiv 
eg p leftrightarrow 
eg q \ pleftrightarrow q equiv (pwedge q) vee (
eg p wedge 
eg q) \ 
eg (pleftrightarrow q) equiv pleftrightarrow 
eg q\ hline end{tabular}


Example,
Show that 
eg (p
ightarrow q) equiv pwedge 
eg q.

Considering LHS,

     egin{align*} 
eg (p
ightarrow q) &equiv 
eg(
eg p vee q) && 	ext Using:first:equivalence:of:Conditionals\ &equiv 
eg(
eg p) wedge 
eg q&& 	ext Using:De:Morgan's:law\ &equiv pwedge 
eg q&& 	ext Using:Double:negation:law end{align}

Another example,
Show that 
eg(pvee (
eg p wedge q)) equiv 
eg p wedge 
eg q.

Considering LHS,

     egin{align*} 
eg(pvee (
eg p wedge q)) &equiv 
eg p wedge 
eg(
eg p wedge q) && 	ext Using:De:Morgan's:law\ &equiv
eg p wedge (
eg(
eg p) vee 
eg q)&& 	ext Using:De:Morgan's:law\ &equiv
eg p wedge (p vee 
eg q)&& 	ext Using:Double:negation:law\ &equiv(
eg p wedge p)vee (
eg p wedge 
eg q)&& 	ext Using:Distributive:law\ &equiv F vee (
eg p wedge 
eg q) && 	ext Using:Negation:Law\ &equiv 
eg p wedge 
eg q && 	ext Using:Identity:Law end{align}

The above examples could easily be solved using a truth table. But this can only be done for a proposition having a small number of propositional variables. When the number of variables grows the truth table method becomes impractical.
For a proposition having 20 variables, 2^{20} rows have to be evaluated in the truth table. This may be easy to do with a computer, but even a computer would fail in computing the truth table of a proposition having 1000 variables.

GATE CS Corner Questions

Practicing the following questions will help you test your knowledge. All questions have been asked in GATE in previous years or in GATE Mock Tests. It is highly recommended that you practice them.
1. GATE CS 2008, Question 33
2. GATE CS 2014 Set-2, Question 63
3. GATE CS 2006, Question 27
4. GATE CS 2015 Set-3, Question 65

References,
Logical Equivalence – Wikipedia
Discrete Mathematics and its Applications, by Kenneth H Rosen

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter