Basic logic homework 1, 0440949, Andreas van Cranenburgh

Exercise 1
(i) 
We consider all valuations of phi and psi:

I(phi) = 0, I(psi) = 0, then the formula is 1 
I(phi) = 0, I(psi) = 1, then the formula is 1
I(phi) = 1, I(psi) = 0, then the formula is 1
I(phi) = 1, I(psi) = 1, then the formula is 1

(ii)
Counterexample: p=false, q=true, truth table:
p	q	p -> q	(p -> q) -> q	((p -> q) -> q) -> p	
0	1	0	1		0

(iii)
phi = p, psi = p
((p -> p) -> p ) -> p is a tautology

Exercise 2
(i)
(ii)
(iii)

Exercise 3
proof by induction

base case: Phi_0 = p is logically equivalent to p or a tautology
inductive step: 
	Phi_n+1 = Phi_n -> p is a logically equivalent to p or a tautology
	Phi_n+1 = p -> Phi_n is a logically equivalent to p or a tautology
closure: no other sentences can be formed