1. Complete Boolean Base

~p = p => F
Once we have define a connective, we can use it for the rest of the connectives   
T = ~F
p \/ q = ~p => q
p /\ q =  ~( ~p V ~ q) 
p <=> q = (p => q) /\ (q => p)
p xor q = ~p <=> q
ite(p,q,r) = p /\ q) \/ (~p /\ r) 

Since we can write each connective in Propositional Logic in terms of just
{=>,F}, every propositional(boolean) expression has an equivalent formula
which uses just {=>,F}. Hence {=>,F} is a complete boolean base.


2.
(p => r) /\ (q => r) /\ (~p => -r)
______________________________________________________
|             (A)      (B)       (C)                 |
| p  q  r  |(p => r)|(q => r)|(~p => ~r)|A /\ B /\ C |
|__________|________|________|__________|____________|     
| T  T  T  |    T   |   T    |    T     |      T     |
| T  T  F  |    F   |   F    |    T     |      F     |
| T  F  T  |    T   |   T    |    T     |      T     |
| T  F  F  |    F   |   T    |    T     |      F     |
| F  T  T  |    T   |   T    |    F     |      F     |
| F  T  F  |    T   |   F    |    T     |      F     |
| F  F  T  |    T   |   T    |    F     |      F     |
| F  F  F  |    T   |   T    |    T     |      T     |
|____________________________________________________|


ite((~p \/ ~q), ~(p \/ q), r)
______________________________________________
|          |   (A)    |    (B)  |            |
| p  q  r  |(~p \/ ~q)|~(p \/ q)|ite(A,B,r)  |
|__________|__________|_________|____________|    
| T  T  T  |    F     |    F    |      T     |    
| T  T  F  |    F     |    F    |      F     |   
| T  F  T  |    T     |    F    |      F     |    
| T  F  F  |    T     |    F    |      F     |    
| F  T  T  |    T     |    F    |      F     |    
| F  T  F  |    T     |    F    |      F     |     
| F  F  T  |    T     |    T    |      T     |    
| F  F  F  |    T     |    T    |      T     |     
|____________________________________________|




(p => q) = (~q => ~p)
_______________________________________________
|         |    (A)   |   (B)    |            |
| p  q    |(p => q)  |(~q => ~p)|    A = B   |
|_________|__________|__________|____________|    
| T  T    |    T     |    T     |      T     |    
| T  F    |    F     |    F     |      T     |    
| F  T    |    T     |    T     |      T     |     
| F  F    |    T     |    T     |      T     |     
|_________|__________|__________|____________|



p /\ (p \/ q) = ~p
______________________________________________
|         |    (A)   |   (B)    |            |
| p  q    | (p \/ q) | (p /\ A) |   B = ~p   |
|_________|__________|__________|____________|    
| T  T    |    T     |    T     |      F     |    
| T  F    |    T     |    T     |      F     |    
| F  T    |    T     |    F     |      F     |     
| F  F    |    F     |    F     |      F     |     
|_________|__________|__________|____________|



p (+) q (+) r
__________________________________
|          |    (A)   |          |           
| p  q  r  |  p (+) q |  A (+) r |
|__________|__________|__________|   
| T  T  T  |    F     |    T     |      
| T  T  F  |    F     |    F     |       
| T  F  T  |    T     |    F     |       
| T  F  F  |    T     |    T     |      
| F  T  T  |    T     |    F     |    
| F  T  F  |    T     |    T     |         
| F  F  T  |    F     |    T     |       
| F  F  F  |    F     |    F     |  
|__________|__________|__________|



3. Characterizing Formula. 

1.  (p/\q)\/r = (p/\r)\/q

To falsify the statement 
Take p = false q = false r = true. 

Take p = q = r would make this statement True. 

So the statement is both Satisfiable and Falsifiable. 

2. ((p => q)/\(r=>s)/\(p\/r))=>(q\/s)
Use method2(used in word problems), since this is an implication.
Towards a contradiction, lets assume this formula is falsifiable.
The only way a => b is false, is when conclusion(b) is false and antecedent(a) is true.
i.e. q \/s is false, which makes q := false and s:= false
The antecedent is true, when p => q, r=>s and p\/r is true.
Since q and s is false, the first p=>q is true only when p is false and
r=>s is true only when r is false. But then this makes p\/r false, which
contradicts our assumption that the antecedent is true. Therefore this formula is valid. 

3. (p\/q) => (p/\q)/\(~p/\q)/\(p/\~q)
Take p = True q = False to see that the statement is Falsifiable.
Take p = False and q = False to see that the statement is Satisfiable. 


4. ~q /\ (p=>q) => q
This can be simplified to p \/ q 
So the Statement is Satisfiable for p = True and q = True 
And Falsifiable p = False and q = False. 

5.  p/\((true/\r)/\(false \/ q))
This is simplified to p /\ q /\ r

This is Satisfiable for p =q = r = T
and Falsifiable for any other assignment to p , q , r. 

Simplification of Formulas.

1.  ~(p \/ (~p/\ q))
    ={ by De morgan's Identity }
    (~p /\ ~(~p /\ q))
    ={ by Demorgans Identity}
    (~p /\ (p \/ ~q)
    = { by distributive property of /\ over \/}
   ~p /\ ~q


2. (p \/ q) /\ (( p/\r) \/ (p /\ ~r) \/ (p /\ q)  \/ q
   ={by reverse distribution of /\ over \/}
   (p \/ q) /\ (( p /\ (r \/ ~r)  \/ (p /\ q) \/ ( q))
   ={by Absorption}
   (p \/ q) /\ (( p /\ (r \/ ~r)) \/ (q)
   ={ By using p \/ ~p = True and True \/ p = True }
   (p \/ q) /\ ( p \/ q)
   ={p /\ p = p}
   (p \/ q)

3. ( p /\ ( ~p \/ q)) \/ ((p \/ ~q) /\ q)
   ={by distribution of /\ over \/}
   (p /\ ~p \/ p /\ q) \/ ((p \/ ~q) /\ q)
   ={by p /\ ~p = False}
   (p /\ q) \/ ((p \/ ~q) /\ q)
   ={by distribution of \/ over /\}
   ( p /\ q ) \/ ((p /\q) \/ (~q /\ q))
   ={by p /\ ~p = False}
   (p /\ q) /\ (p /\ q) 
   = {by p /\ p = p}
   p /\ q

4. (~p /\ ( p \/ q)) \/ ((q \/ ( p /\ p)) /\ ( p \/ ~q))
   ={by distributive of /\ over \/}
   (~p /\ p \/ ~p /\ q) \/ ((q \/ ( p /\ p)) /\ ( p \/ ~q)))
   ={by p /\p = False and False \/ p = p}
   (~p /\ q) \/ ((q \/ ( p /\ p)) /\ ( p \/ ~q)))
   ={by p /\ p = p }
   (~p /\ q) \/ ((q \/ p)  /\ ( p \/ ~q)))
   ={ by p \/ q = q \/ p}
   (~p /\ q) \/ ((p \/ q)  /\ ( p \/ ~q)))
   ={ By distribution }
   (~p /\ q) \/ ((p /\(p \/ ~q)) \/ (q /\ (p \/ ~q)))
   ={By Distribution}
    (~p /\ q) \/ ((p /\ p \/ p /\ ~q) \/ (q /\ p \/ q /\ ~q))
   = { by p /\ p = p and q /\ ~q = False}
    (~p /\ q) \/ (p \/ (p /\ ~q) \/ (p /\ q))
   = { by Absorption }
    (~p /\ q) \/ (p \/ (p /\ q))
   = { by Absorption }
    (~p /\ q) \/ p

5.  (p = q) /\ (~q = r) /\ (r = ~q) /\(p= ~r)
    = { by using p = ~q = ~p = q}
    (p = q) /\ (~q = r) /\ (~q = r) /\ (p = ~r)
    = { by using p /\ p = p}
    (p = q) /\ (~q = r) /\ (p = ~r)
    ={ by using p = q in rest of the expression}
    (p = q) /\ (~q = r) /\ (q = ~r)
    = { by using p = ~q is ~p = q}
    (p = q) /\ (~q = r) /\ (~q = r)
    = { by using p /\ p = p}
    (p = q) /\ (~q = r)

6. (~p /\ r) \/ (q /\ ~r) \/ (p /\ q /\ r) \/ ( p /\ ~q)
={by reverse distribution}
 (~p /\ r) \/ (q /\ ~r) \/ p /\ ((q /\ r) \/ ~q)
={distribute and use q \/ ~q = true}
 (~p /\ r) \/ (q /\ ~r) \/ p /\ ((q \/ ~q) /\ (r \/ ~q))
 (~p /\ r) \/ (q /\ ~r) \/ p /\ (true /\ (r \/ ~q))
={true /\ p = p}
 (~p /\ r) \/ (q /\ ~r) \/ p /\ (r \/ ~q)
={distribute} 
(~p /\ r) \/ (q /\ ~r) \/ (p /\ r) \/ (p /\ ~q)
={commutavity and associativity of \/}
(~p /\ r) \/ (p /\ r) \/ (q /\ ~r) \/ (p /\ ~q)
={reverse distribute}
 ((p \/ ~p)/\r) \/ (q /\ ~r) \/ (p /\ ~q) 
={p \/ ~p = true and true /\ p = p}
 r  \/ (q /\ ~r) \/ (p /\ ~q)
={distribute, r \/ ~r = true and true /\ p = p} 
(r \/ q) \/ (p /\ ~q) 

7. (p => (q => r) ) = ((p /\ q) => r)
   = { by boolean equality of p =>q = ~p \/ q}
   (p => (~q \/ r)) = ((p /\ q) => r)
   = { by boolean equality of p =>q = ~p \/ q}
   (~p \/ ~q \/ r) = ((p /\ q) => r)
   ={ by Demorgans equality}
   (~(p/\q) \/ r) = ((p /\ q) => r)
   = { by boolean equality of p =>q = ~p \/ q}
   ((p /\ q) => r) = ((p /\ q) => r)
   = { p=p = true}
    true

Word problems

1. 
The weather is warm: p
the sky is clear: q
go swimming: r 
go boating: s

weather is warm and sky is clear :  p /\ q 
either we go swimming or we go boating : r \/ s
do not go swimming : ~r
sky is not clear : ~q
not the case that if we do not go swimming then the sky is not clear 
~( ~r => ~q)

Conclusion : 
weather is warm or we go boating : p \/ s

So the formalization is:
(((p /\ q) => (r \/ s) )  /\ (~(~r => ~q))) => (p \/ s)


Lets see if we can find an assignment for p,q,r,s that falsifies this statement

For this expression to be false. 
p \/ s should be false ( i.e p = false and s = false) 

This reduces antecedent to 
(F => (r \/ F)) /\ (~( q=>r))
 = T /\ ~(~q \/ r)
 = q /\ ~r

Pick q := true and r :=false which would falsify the formula.



2. Tom takes the advanced course : p 
  Cs 2800 is interesting.: q
  Tom gets good grade : r
  
Statement 1 : p => q 
Statement 2 : r /\ p 
Conclusion : q

Claim:
((p=>q) /\ (r/\p)) => q

The only way to falsify this formula is 
q = false and 
((p => q) /\ (r /\ p)) = True

But q = false would mean antecedent = false. 
So this is not falsifiable and therefore a valid claim.

3. 
Ed wins first prize : p 
Fred wins second prize : q 
George is disappointed : r 

Statement 1: p -=> (q \/ r) 
Statement 2: ~q
Conclusion r => ~p 

Claim:
(( p => (q \/ r) ) /\ ~q ) => (r=> ~p)

The only way this formula will not be valid is 
(( p => (q V r) ) /\ ~q )  = True
(r => ~p)  = False
i.e r = True and p = True

Choose q := False 
this would result in falsifying this formula. 

Therefore claim is not Valid.

4.  weather forecast is correct : p 
  seeds are planted in March : q
  first harvest happens in July : r

Statement 1: p => (q=>r) 
Statement 2: ~r
Conclusion: r => ~p

Claim:
((p=> (q=>r )) /\ ~r) => (r=> ~p)

Towards a contradiction lets try to falsify the claim 
(r=> ~p) = false and ((p=> (q=>r )) /\ ~r) = true
which makes r = true and p = true 
but r = true makes the antecedent False, contradicting our
assumption that the claim is false. 

So the claim is valid. 

5. Natasha is a spy : p 
    works for USA: q 
    works for USSR : r

Note (+) : XOR

Statement 1: p => (q (+) r) 
Statement 2: p 
Conclusion: r /\ q

Claim:
(p => (q (+) r ) /\ p) => (r /\ q)

to Falsify this 
choose r = false q = true p = true
to show the counterexample(falsifying assignment)
So the claim is not VALID

6. Arthur pulled a sword from stone : p 
  Arthur is King : q 

Statement 1: p => q
Statement 2: q
Conclusion : p 

Claim:
((p => q ) /\ q ) => p

To falsify this 
Choose p := false 
and q := false . 

So this claim is not valid. 


6. Decision Procedures. 

1.(defun Falsifiable (f) 
	(not (UNSAT (not f))))

2. (defun Satisfiable (f)
	(not (UNSAT f)))

3. (defun Validity (g)
	(UNSAT (not g)))