next up previous
Next: Homework 5 Up: Homework Assignments Previous: Homework 3

Homework 4

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

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

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)


	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


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:


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)).

Randall Holmes