# Math Help - Conditional Propositions & Logical Equivalence

1. Here now is a syntactical proof that p^(qvr) ====> (p^q)v(p^r) i.e p^(qvr) logically implies (p^q)v(p^r) or [p^(qvr) -----> (p^q)v(p^r)] is a tautology.

LETS do it in steps:

1)p^(qvr)......................................... ..................asumption

2) p...........................................from 1 and using addition elimination

3) qvr.........................................from 1 and using addition elimination

4) q................................................. .....................assuption

5) p^q........................................from 2 and 4 and using addition introduction

6) (p^q)v(p^r).............................from 5 and using disjunction introduction

7) q-----> (p^q)v(p^r).................. from 4 to 6 and using the conditional proof rule

8) r................................................. .......................assumption

9) p^r.........................................from 2 and 8 and using addition introduction

10) (p^q)v(p^r)...........................from 9 and using disjunction introduction

11) r------> (p^q)v(p^r)...............from 8 to 10 and using the conditional proof rule

12) (p^q)v(p^r).............................from 3,7,11 and using proof by cases or (another name) disjunction elimination

Hence we have proved : p^(qvr) ====> (p^q)v(p^r)

NOW the laws of logic used here are:
b) addition introduction...........P^Q======> P, or..P^Q====.> Q
c) disjunction introduction...........P=======> PvQ
d) disjunction elimination...............{ (PvQ) ^[ (P---->R) ^(Q---->R)] }=====>R. This law is also called proof by cases and

Many times is completely destroyed in mathematical proofs particularly those in mathematical analysis.

There may be other interesting proofs for the above,and the converse can be done in a similar way

2. Here is a semantical proof of p^(qvr) ===> (p^q)v(p^r)............................1

without using the true table

we know that p^(qvr) ------> (p^q)v(p^r) is a tautology for all the values of p,q,r .

Suppose now that the above is not a tautology ,then there exist values of p,q,r for which the above is false:

Then by the definition of '------>',conditional , p^(qvr) must be true and

(p^q)v(p^r) false .

Now by the definition of '^' p must be true, and (qvr) true....................

Also by the definition of 'v' ,since (p^q)v(p^r) is false ,(p^q) must be false and (q^r) false.

Since p^q is false by the definition again of '^' p must be false and q the same.

So far we have proved that p is true and also p is false.

Thus ...........p^(qvr) ------> (p^q)v(p^r) is a tautology...................

and...........p^(qvr) ===> (p^q)v(p^r) i.e p^(qvr) logically implies

(p^q)v(p^r)

For the converse i.e (p^q)v(p^r)====>p^(qvr) a similar processes is applicable.
That law of logic is used very often in set theory particularly in proving

............... $A\cap$ (BUC) = ( $A \cap B$ )U ( $A\cap C$ )................................

In every day life the law is used very often as the following example shows:

We say : if i go to the movies i will buy a coca cola or beer which means that :i go to the movies and buy a coca cola or i go to the movies and buy a beer

3. Let me now give asyntactical proof of IxI<y<===> --y<x<y in steps
All proofs in mathematics are syntacical

NOTE (L) will mean law of logic ,(T) A theorem,(D) a definition,(A) an axiom

So
1) IxI<y............................................. ......... an assumption
2) $\forall{x}$( x≥0 or x< 0)................................... (A)
3) x≥0 or x<0 ..............................................from line2 and using Universal elimination (L)
4) x≥0 .................................................. ......A hypothesis
5) $\forall{x}$ ( x≥0 $\longrightarrow$IxI=x )..........................(D) in apsolute values
6) x≥0 $\longrightarrow$ IxI=x .....................................from 5 and Univ. elimin. (L)
7) IxI=x .................................................. .....from 4 and 6 and using M.Ponens (L)
8) x<y .................................................. .......By substituting 7 into 1 (L)
9) $\forall{a}\forall{b}\forall{c}$ (a≤b and b<c $\longrightarrow$a<c) .............(T) or a result coming out from iniqalities
10) 0≤x and x<y $\longrightarrow$0<y .............................from 9 and Univ.Elim.where we put a=0,b=x,c=y (L)
11) 0≤x and x<y ............................................from 4 and 8 and using Conjuction Introduction (L)
12) 0<y .................................................. ......from 10 and 11 and using M.Ponens (L)
13) $\forall{a}\forall{b}$ (a<b<----->-a>-b) .............................(T)
14) 0<y<-----> 0>-y ......................................from 13 and Univ. Elim. where a=0,b=y (L)
15) -y<0 .................................................. .....from 12 and 14 and using M.Ponens (L)
16) $\forall{a}\forall{b}\forall{c}$ (a<b and b≤c $\longrightarrow$ a<c) ....................(T)
17) -y<0 and 0≤x - $\longrightarrow$y<x ..........................from 16 and Univ. Elim.where we put a=-y,b=0,c=x (L)
18) -y<0 and 0≤x ...........................................from15 and 4 and using conjuction introduction (L)
19) -y<x .................................................. .....from 17 and 18 and using M.Ponens (L)
20) -y<x and x<y ( -y<x<y) ..............................from 8 and 19 and conjuction introduction (L)
21) x≥0 $\longrightarrow$ -y<x<y .....................................from steps 4 to 21 and using the rule of conditional proof (L)

Now in a similar way and using the definition of apsolute values x<0 $\longrightarrow$ IxI=-x we will come to the result x<0 $\longrightarrow$y<x<y ( 1a)

22) -y<x<y .................................................. ..from 2, (1a),21 and Disjuction Elimination (L)
23) IXI<y $\longrightarrow$y<x<y ....................................from steps 1 to 23 and using the rule of conditinal proof (L)

the converse i,e -y<x<y I $\longrightarrow$xI<y can be done in a similar way

Page 2 of 2 First 12