211L11Solutions

Lecture 11

1. Suppose that the set of all propositions PROP is the set of all symbols of the Latin alphabet. Design an algorithm that given a string over the alphabet PROP [ {&,^,_,¬, ), (} detects if the string is a formula.

For the last '(' in the string, take the substring between that ( and the first ')'. If that is of the form p ^ q or p V q or p -> q, or any combination, where p or q are ¬p or ¬q. Then replace everything between and including the brackets with a new proposition p'. Repeat this process until such stage where it is reduced to one proposition, in which case it is a formula, else it is not a formula.

2. Let Φ be formula. Prove that with every occurrence of ( in Φ there is a sub-formula of Φ uniquely associated with (. For example, in the formula Φ = ((p ^ q) V (q -> ¬(p ^ q))) the sub-formula associated with the first occurrence of ( is the Φ itself, the sub-formula associated with the second occurrence of ( is (p ^ q), and the formula associated with the third occurence of ( is (q -> ¬(p ^ q)). For every formula there is a set of parentheses for every sub formula within that formula. This can be demonstrated by how a formula can be built. Any formula can be created by inductivly building on a the base cases of (p ^ q) or (p V q) or (p -> q) for each possible combination of p or ¬p and q or ¬q. In each of these base cases there is a unique '(' associated with the formula. Any formula can be built up by substituting a formula for a proposition. The cardinality of the ( always matches the number of sub-formulas.

3. Prove that the following formulas are equivalent:

• (a) (Φ -> Ψ) and (¬Φ V Ψ).

• (b) (Φ ^ (a V B)) and ((Φ ^ a) V (Φ ^ B)).
• (c) Φ and ¬¬Φ.
• (d) ¬(Φ _ ) and (¬Φ ^ ¬ ).
• (e) ¬(Φ ^ ) and (¬Φ _ ¬ ).
• (f) (Φ ^ (Φ ^ )) and ((Φ ^ Φ) ^ ).

		(Φ -> Ψ) and (¬Φ V Ψ).		

Φ	Ψ	(Φ -> Ψ)	 (¬Φ V Ψ)	
0	0	1	1	
0	1	1	1	
1	0	0	0	
1	1	1	1	



		(Φ ^ (a V B)) and ((Φ ^ a) V (Φ ^ B))		

Φ	a	B	(Φ ^ (a V B))	 ((Φ ^ a) V (Φ ^ B))
0	0	0	FALSE	FALSE
0	0	1	FALSE	FALSE
0	1	0	FALSE	FALSE
0	1	1	FALSE	FALSE
1	0	0	FALSE	FALSE
1	0	1	TRUE	TRUE
1	1	0	TRUE	TRUE
1	1	1	TRUE	TRUE


Φ	¬¬Φ			
1	1			
0	0			


		¬(� ΦV ψ) and (¬Φ ^ ¬ψ)		
Φ	ψ	¬(� ΦV ψ)	(¬Φ ^ ¬ψ)	
1	1	0	0	
1	0	0	0	
0	1	0	0	
0	0	1	1	
 

		¬(� Φ^ ψ) and (¬Φ V ¬ψ)		 

Φ	ψ	¬(� Φ^ ψ)	(¬Φ V ¬ψ)	
1	1	0	0	
1	0	1	1	
0	1	1	1	
0	0	1	1	

		(a^(B^g)) and ((a^B)^g)		
				
a	B	g	(a^(B^g))	((a^B)^g)
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	0	0
1	0	0	0	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

4. Prove that a formula Φ is a contradiction if and only if ¬Φ is valid.

• If Φ is a contradiction, then ¬Φ is valid.

If Φ is a contradiction, then it must be true that the proposition is false. For example a contradiction is the statement "one is an even number". This is the same as saying it is false that "one is an even number", i.e. ¬Φ.

• If ¬Φ is valid, then Φ is a contradiction.

Similarly, if it is false that "one is an even number". Then it is true that "one is an even number" is a contradiction.

5. Convert each of the following formulas into disjunctive normal form: (p -> ¬q), ¬(p -> (s -> ¬(q V p))), ((¬p ^ (s -> p)) ^ (q V ¬s)), ¬(((p V ¬s) ^ (q V ¬p)) -> (p -> q)).

• (p -> ¬q)
• ¬(p -> (s -> ¬(q V p)))
• ((¬p ^ (s -> p)) ^ (q V ¬s))
• ¬(((p V ¬s) ^ (q V ¬p)) -> (p -> q))

(p -> ¬q)							
		A:(¬p^¬q)V(¬p^q)V(p^¬q)					
p	q	¬q	(p -> ¬q)				
FALSE	FALSE	TRUE	TRUE				
FALSE	TRUE	FALSE	TRUE				
TRUE	FALSE	TRUE	TRUE				
TRUE	TRUE	FALSE	FALSE				   


¬(p -> (s -> ¬(q V p)))							
					A: (p^q^s)V(p^¬q^s)		
p	q	s	q V p	¬(q V p))	s -> ¬(q V p))	(p -> (s -> ¬(q V p)))	¬(p -> (s -> ¬(q V p)))
TRUE	TRUE	TRUE	TRUE	FALSE	FALSE	FALSE	TRUE
TRUE	TRUE	FALSE	TRUE	FALSE	TRUE	TRUE	FALSE
TRUE	FALSE	TRUE	TRUE	FALSE	FALSE	FALSE	TRUE
TRUE	FALSE	FALSE	TRUE	FALSE	TRUE	TRUE	FALSE
FALSE	TRUE	TRUE	TRUE	FALSE	FALSE	TRUE	FALSE
FALSE	TRUE	FALSE	TRUE	FALSE	TRUE	TRUE	FALSE
FALSE	FALSE	TRUE	FALSE	TRUE	TRUE	TRUE	FALSE
FALSE	FALSE	FALSE	FALSE	TRUE	TRUE	TRUE	FALSE 


((¬p ^ (s -> p)) ^ (q V ¬s))							
					A: (¬p^q^¬s)V(¬p^¬q^¬s)		
p	q	s	(q V ¬s)	(s -> p)	(¬p ^ (s -> p))	((¬p ^ (s -> p)) ^ (q V ¬s))	
TRUE	TRUE	TRUE	TRUE	TRUE	FALSE	FALSE	
TRUE	TRUE	FALSE	TRUE	TRUE	FALSE	FALSE	
TRUE	FALSE	TRUE	FALSE	TRUE	FALSE	FALSE	
TRUE	FALSE	FALSE	TRUE	TRUE	FALSE	FALSE	
FALSE	TRUE	TRUE	TRUE	FALSE	FALSE	FALSE	
FALSE	TRUE	FALSE	TRUE	TRUE	TRUE	TRUE	
FALSE	FALSE	TRUE	FALSE	FALSE	FALSE	FALSE	
FALSE	FALSE	FALSE	TRUE	TRUE	TRUE	TRUE		 


¬(((p V ¬s) ^ (q V ¬p)) -> (p -> q))								
					A: Always False			
p	q	s	(p -> q)	(p V ¬s)	 (q V ¬p)	((p V ¬s) ^ (q V ¬p))	(((p V ¬s) ^ (q V ¬p)) -> (p -> q))	¬(((p V ¬s) ^ (q V ¬p)) -> (p -> q))
TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	FALSE
TRUE	TRUE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE	FALSE
TRUE	FALSE	TRUE	FALSE	TRUE	FALSE	FALSE	TRUE	FALSE
TRUE	FALSE	FALSE	FALSE	TRUE	FALSE	FALSE	TRUE	FALSE
FALSE	TRUE	TRUE	TRUE	FALSE	TRUE	FALSE	TRUE	FALSE
FALSE	TRUE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE	FALSE
FALSE	FALSE	TRUE	TRUE	FALSE	TRUE	FALSE	TRUE	FALSE
FALSE	FALSE	FALSE	TRUE	TRUE	TRUE	TRUE	TRUE	FALSE

6. We say that is in a conjunctive normal form if it is written as (�1^�2^. . .^�k), where each � is a disjunction of literals. Prove that for every formula � there exists an equivalent formula in a conjunctive normal form.

7. Consider the Evaluate(�,A) algorithm. Find a loop invariant of the algorithm and prove that the algorithm is correct.

8. Finish the inductive step in the proof of Theorem 5