Question

Propositional Logic

Using operator properties and other logical equivalences (not truth tables), prove these statements.

1. ((p→r)∧(q→r)∧(p∨q))→r (tautology)

2. ¬(q→p)∧(p∧q∧s→r)∧p (contradiction)

3. (p→q)∧(p→r)≡p→(q∧r)

Answer 1

1. ((p→r)∧(q→r)∧(p∨q))→r (tautology)
((p→r)∧(q→r)∧(p∨q))→r = ((p' v r)∧(q→r)∧(p∨q))→r [As x→y =x' v y ]
   = ((p' v r)∧(q' v r)∧(p∨q))→r [As x→y =x' v y ]
   =( (p'∧q' v p'∧r v r∧q' v r∧r)∧(p∨q))→r [By distributive law ]
     =( (p'∧q' v p'∧r v r∧q' v r)∧(p∨q))→r [r∧r = r, By Idempotence law ]
   =( (p'∧q' v p'∧r v r)∧(p∨q))→r   [ r∧q' v r = r , By Absorption law ]
   =( (p'∧q' v r)∧(p∨q))→r [ p'∧r v r = r , By Absorption law ]
=( ( (p v q)' v r)∧(p∨q))→r [p'∧q' =(p v q)' By Demorgans law ]
= ( (p v q)'∧(p∨q) v r∧(p∨q))→r [By distributive law ]
   = ( F v r∧(p∨q))→r [ As X' ∧ X =F, By Negation Law]
   = (r∧(p∨q))→r [ By Identity law ]
   =( r∧(p∨q))' v r   [As x→y =x' v y ]
   = ( r' v (p∨q)') v r [ By Demorgans law ]
   =r' v r v (p∨q)' [By Associative Law ]
= T v (p∨q)' [r' v r =T By Negatitaion Law ]
   = T [ T v X= T By Domination Law ]

Therefore, ((p→r)∧(q→r)∧(p∨q))→r is Tautology .
Hence, proved


2. ¬(q→p)∧(p∧q∧s→r)∧p is contradiction
¬(q→p)∧(p∧q∧s→r)∧p = ¬(q' v p)∧(p∧q∧s→r)∧p   [As x→y =x' v y ]
=(q∧p')∧(p∧q∧s→r)∧p [ By Demorgan's law ]
=(q∧p')∧p∧(p∧q∧s→r) [ By associative law ]
   = q∧(p'∧p)∧(p∧q∧s→r) [ By associative law ]
=q ∧F∧(p∧q∧s→r) [ X' ∧ X =F By Negatiation law ]  
   =F ∧(p∧q∧s→r) [ F ∧ X =F ]
   = F
Therefore , ¬(q→p)∧(p∧q∧s→r)∧p is contradiction.
Hence,proved.

3.(p→q)∧(p→r)≡p→(q∧r)
Let us take a left hand side.
(p→q)∧(p→r) = (p' v q ) ∧ (p' v r)    [As x→y =x' v y ]
   = ((p' v q ) ∧ p') v ( (p' v q ) ∧ r) [ By Distributive Law ]
   = p' v ( (p' v q ) ∧ r) [ By Absorption law ]
   = p' v p' ∧ r v q ∧ r [ By Distributive Law ]
= p' v q ∧ r [ p' v p' ∧ r = p' By absorption law ]
=p→(q∧r) [ As p→(q∧r) = p' v q ∧ r ]   

Hence, proved.