Associativity of the "and" operator
5 Jan 1996

Here is a more complete version of the "moving parentheses" demonstration from today's class. I've used a simpler formula to help make the process more clear.

Suppose we wish to show the two formulae below are logically equivalent

and we have the associative rule for ^ which tells us that the two formulae are equivalent, we get the substitutions pictured below.
We begin with the formula
p ^ [ q ^ [ r ^ [ s ^ [ t ^ u ]]]]
using the associative rule for ^ with x = p, y = q, and z = [ r ^ [ s ^ [ t ^ u ]]], we obtain
[p ^ q ] ^ [ r ^ [ s ^ [ t ^ u ]]]
using the associative rule for ^ with x = [p ^ q], y = r, and z = [ s ^ [ t ^ u ]], we obtain
[[p ^ q ] ^ r ] ^ [ s ^ [ t ^ u ]]
using the associative rule for ^ with x = [[p ^ q] ^ r], y = s, and z = [ t ^ u ], we obtain
[[[p ^ q ] ^ r ] ^ s ] ^ [ t ^ u ]
using the associative rule for ^ with x = [[[p ^ q] ^ r] ^ s ], y = t, and z = u , we obtain
[[[[p ^ q ] ^ r ] ^ s ] ^ t ] ^ u
Computer Science & Engineering Department,
University of Washington,
PO Box 352350
Seattle, WA 98195-2350 USA
walkup@cs.washington.edu
Last modified: Fri Jan 5 1996