There are some typos in exercise 1 of the printed version. The distributive laws are written incorrectly in a couple of places!
Homework 4, due Friday, Feb. 4. Some examples and exercises on formal algebraic reasoning: 1. complete formal proofs of simple algebra manipulations I give an example. I justify the theorem P & (Q & R) == R & (Q & P) using the commutative and associative properties of conjunction and the formal rules of algebraic logic, which I give again: We have the following rules: 1. A == A is a theorem for any formula A. (equivalence is reflexive). 2. if A == B is a theorem then B == A is a theorem. (equivalence is symmetric). 3. if A == B and B == C are theorems, then A == C is a theorem. (equivalence is transitive). 4. if B == C is a theorem, then A[B/X] == A[C/X] is a theorem. (equals can be substituted for equals). 5. if A == B is a theorem, then A[C/X] == B[C/X] is a theorem. (any more specific value can replace a variable everywhere in an equation). Now for the example: 1. S & T == T & S (commutative property of conjunction; assumed) 2. (S&T)&U == S&(T&U) (associative property of conjunction; assumed) 3. Q&R == R&Q (line 1 and two applications of rule 5--replace S with Q and T with R) 4. P&(Q&R)==P&(R&Q) (line 3 and rule 4 -- (P&X)[(Q&R)/X]==(P&X)[(R&Q)/X]) 5. P&(R&Q)==(R&Q)&P (line 1 and two applications of rule 5--replace S with P and T with R&Q) 6. P&(Q&R) == (R&Q)&P (lines 4 and 5 and rule 3) 7. (R&Q)&P == R&(Q&P) (line 2 and three applications of rule 5 -- replace S,T,U with R,Q,P respectively) 8. P&(Q&R) == R&(Q&P) Now for the exercise: There were typographical errors in this as written originally! With a level of formality similar to the example above, prove the distributive law (P|Q)&R == (P&R)|(Q&R) from the assumptions P&(Q|R) == (P&Q)|(P&R), P&Q==Q&P and P|Q == Q|P. I supply the first three lines of the proof: 1. S&(T|U) == (S&T)|(S&U) (assumption) 2. S | T == T | S (assumption) 3. S & T == T & S (assumption) The conclusion of your proof should be the equation (P|Q)&R == (P&R)|(Q&R) and each line should be justified in the style shown in the example. 2. matching examples In each case, a theorem is to be applied to a formula. Attempt to match the left side of the theorem to the formula: list the matches of variables to subformulas or indicate why the matching process fails. If the matching process succeeds, show what the result of the application of the formula is. example: apply S&T == T&S to P&(Q&R) solution: matches are S --> P and T --> Q&R the final result is (Q&R)&P. your problems: apply P&P == P to (U&V)&(U&V) apply U&(V|W) == (U&V)|(U&W) to (A|B)&(C|D) apply (U|V)&W == (U&W)|(V&W) to (A|B)&(C|D) apply U&(V|W) == (U&V)|(U&W) to (A|B)&C 3. the associative and commutative matching problem If we adopt Dr. Grantham's approach to handling associative operators, the definition of matching becomes problematic. For example, if we apply the distributive law U&(V|W) == (U&V)|(U&W) to U&(V|W|X) we might get either (U&(V|W))|(U&X) or (U&V)|(U&(W|X)) The reason is that since Grantham does not distinguish between (U|V)|W and U|(V|W), it is possible to match the left side of the equation to the term in two different ways. first thing for you to do: Write down the two possible matches. This is a real problem: ``associative matching'' is something that some computer algebra and theorem proving systems try to implement. One can also implement ``associative and commutative matching'', in which one is allowed to confuse A&B and B&A (for example). Suppose we allow associative matching. Write down as many matches for the left side of the ``FOIL equation'' (a+b)(c+d) = ac + ad + bc + bd to the expression (x+y+z)(u+v+w) as you can come up with, along with the expression which results when you apply each match. I'll start you off with one of them: a-->x b-->y+z c-->u+v d-->w result: x(u+v) + xw + (y+z)(u+v) + (y+z)w Write down at least one additional match which would become possible if we also allowed commutative matching (if we confused (x+y)+z with z+(x+y) as well as with x+(y+z)).