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