Andreas van Cranenburgh 0440949
homework 1

exercise 4

(i) Four possible valuations of p and q:
			
a. I(p) = 0	I(q) = 0	I(~p) = 1
b. I(p) = 0	I(q) = 1	I(~p) = 1	
c. I(p) = 1	I(q) = 1	I(~p) = 0	
d. I(p) = 1	I(q) = 0	I(~p) = 0	

By the semantic definitions of v and ->, we have:

a. I(p -> q) = 1	I(~p v q) = 1
b. I(p -> q) = 1	I(~p v q) = 1
c. I(p -> q) = 1	I(~p v q) = 1
d. I(p -> q) = 0	I(~p v q) = 0

(ii) ~p -> q
(iii)(p -> q) -> q

(iv) 
case d from (i):
d. I(p) = 1		I(q) = 0	I(~p) = 0	
d. I(p -> q) = 0	I(~p v q) = 0

As shown by (i), implication can be seen as a disjunction between
the negation of an antecedent and a consequent. It is not possible to form
a negation using only p, q, v, ( and ).

Consider the Language L with p and q as the only atoms, and v as the only
logical constant. We will prove that it is not possible to form a sentence
equivalent to p -> q in normal propositional logic. 

base case: phi=p, psi=q
	neither I(p) nor I(q) is equivalent to p -> q
	by the semantic definition of implication.
induction step:
	assume that the property holds for phi and psi, 
	then it also holds for I(phi v psi): 
	because if I(phi) = 1 and I(psi) = 0 
	then I(phi v psi) = 1 by the semantic definition of disjunction,
	whereas I(phi -> psi) = 0 by the semantic definition of implication

exercise 5
a) ~(p -> ~q) is equivalent to p ^ q, 
because V( ~(p -> ~q) ) == V(p ^ q) for any valuation of p and q,
by repeated applications of the semantic definitions of negation, implication
and conjunction.

b)
Consider the language L' with ^ and v as the only logical constants.

base case: if phi is an atomic sentence then it is not a tautology, 
	because there is an I such that I(phi)=0
induction step: assume the property holds for phi and psi, then the following
	formulas can be formed:
	a. I(phi ^ psi): 0 if either I(phi)=0 or I(psi)=0, so not a tautology.
	b. I(phi ^ phi): 0 if I(phi)=0, so not a tautology.
	c. I(phi v psi): 0 if both I(phi)=0 and I(psi)=0, so not a tautology.
	d. I(phi v phi): 0 if I(phi)=0, so not a tautology.

c)
Suppose I -< J and VI(phi) = 1,
then VJ(phi) = 1.

base case: if phi is an atomic sentence (proposition symbol), then
	it follows from the definition of -< and the supposition
	that VJ(phi) = 1.
induction step:
	assume the property holds for psi and chi, then it also holds for:
	 a) phi = psi ^ chi
		if VI(psi ^ chi) = 1, then VJ(psi ^ chi) = 1
	 b) phi = psi v chi
		if VI(psi v chi) = 1, then VJ(psi v chi) = 1
	because 
no other positive sentences can be formed or they are equivalent to these.


d)
~((p -> q) -> ~q)

by the result from 4(i) we can rewrite ->
~(~(~p v q) v ~q)

now let's see if the negations cancel each other out or not:

~((p ^ ~q) v ~q)
 (~(p ^ ~q) ^ q)
   (~p v q) ^ q

Alas, there is still one negation left, so this is not a positive formula.