Archive for the ‘Calculating with booleans’ Category

The infimum

October 18, 2007

The infimum is defined for boolean X and Y by the Golden Rule:

X\sqcap Y\ \equiv\ X\ \equiv\ Y\ \equiv\ X\sqcup Y

By studying this rule we can observe several facts about the infimum. First, since it is defined in terms of \equiv and \sqcup we have

X\sqcap Y

\equiv {Golden Rule}

X\ \equiv\ Y\ \equiv\ X\sqcup Y

\equiv {Symmetry of \equiv and \sqcup}

Y\ \equiv\ X\ \equiv\ Y\sqcup X

\equiv {Golden Rule}

Y\sqcap X

i.e. \sqcap is symmetric.

Exercise: Show that \sqcap is associative.

Furthermore, \sqcap is idempotent:

X\sqcap X

\equiv {Golden Rule}

X\ \equiv X\ \equiv\ X\sqcup X

\equiv {identity of \equiv; idempotence of \sqcup}

X

With regard to last three properties, \sqcap is just like \sqcup. We might very well ask, is \top a fixed point of \sqcap as it is of \sqcup? Let’s calculate:

X\sqcap\top

\equiv{Golden Rule}

X\ \equiv\ \top\ \equiv\ X\sqcup\top

\equiv{fixed point of \sqcup}

X\ \equiv\ \top\ \equiv\ \top

\equiv{identity of \equiv}

X

So \top is the identity of \sqcap.

Next we have two very useful laws of absorption/introduction:

 

X\sqcap(X\sqcup Y)

X\sqcup(X\sqcap Y)

 

We shall prove the first, the second follows by interchanging \sqcap and \sqcup.

 

X\sqcap(X\sqcup Y)

\equiv {Golden rule}

X\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup X\sqcup Y

\equiv {idempotence}

X\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup Y

\equiv {identity of \equiv}

X

 

What about distributivity properties?

 

X\sqcup(Y\sqcap Z)\ \equiv\ (X\sqcup Y)\sqcap(X\sqcup Z)

 

X\sqcup(Y\sqcap Z)

\equiv {Golden rule}

X\sqcup(Y\ \equiv\ Z\ \equiv\ Y\sqcup Z)

\equiv {distributivity}

X\sqcup Y\ \equiv\ X\sqcup Z\ \equiv\ X\sqcup Y\sqcup Z

\equiv {idempotence, preparing for the Golden Rule}

X\sqcup Y\ \equiv\ X\sqcup Z\ \equiv\ X\sqcup Y\sqcup X\sqcup Z

\equiv {Golden Rule}

(X\sqcup Y)\sqcap(\sqcup Z)

 

(X\sqcap Y)\sqcup(X\sqcap Z)

\equiv{\sqcup distributes over \sqcap}

((X\sqcap Y)\sqcup X)\sqcap((X\sqcap Y)\sqcup Z)

\equiv{absorption}

X\sqcap((X\sqcap Y)\sqcup Z)

\equiv{\sqcup distributes over \sqcap}

X\sqcap((X\sqcup Z)\sqcap(Y\sqcup Z))

\equiv{associativity; symmetry}

X\sqcap(((X\sqcup Z)\sqcap Z)\sqcup Y)

\equiv{absorption}

X\sqcap(Y\sqcup Z)

 

So \sqcap distributes over \sqcup. What about \equiv? The best we can do is

 

X\sqcap(Y\equiv Z)

\equiv{Golden rule}

X\ \equiv\ Y\ \equiv\ Z\ \equiv\ X\sqcup(Y\equiv Z)

\equiv{distributivity}

X\ \equiv\ Y\ \equiv\ Z\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup Z

\equiv{symmetry, preparing for Golden rule}

X\ \equiv\ Y\ X\sqcup Y\ \equiv\ Z\ \equiv\ X\sqcup Z

\equiv {Golden rule, twice}

X\sqcap Y\ \equiv\ X\sqcap Z\ \equiv X

 

As a consolation we do have

W\sqcap(X\equiv Y\equiv Z)\ \equiv\ W\sqcap X\ \equiv\ W\sqcap Y\ \equiv\ W\sqcap Z.

 

Finally we have

X\sqcap(X\equiv Y)

\equiv{pseudo-distributivity}

X\sqcap X\ \equiv\ X\sqcap Y\ \equiv X

\equiv{idempotence; identity of \equiv}

X\sqcap Y

Advertisements

The supremum

October 16, 2007

We have seen how to use the \equiv operator to calculate with booleans. It is time to investigate another operator, the supremum, written as `\sqcup‘ and pronounced `cup’.
\sqcup has a higher binding power than \equiv which means that the expression

X\sqcup Y\ \equiv\ Z

is read as

(X\sqcup Y)\equiv Z

(Notice the greater space around \equiv in the first expression).


The first two properties of the supremum are familiar:Associativity:(X\sqcup Y)\sqcup Z\ \equiv\ X\sqcup(Y\sqcup Z)

Symmetry:

X\sqcup Y\ \equiv\ Y\sqcup X

The next two are new:

Idempotence:

X\sqcup X\ \equiv\ X

Distributivity/Factoring:

X\sqcup (Y\equiv Z)\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup Z


Armed with these rules, we can now prove our first property concerning the supremum:Distributivity/Factoring:

X\sqcup (Y\sqcup Z)\ \equiv\ (X\sqcup Y)\sqcup (X\sqcup Z)

Proof

\quad(X\sqcup Y)\sqcup (X\sqcup Z)

\equiv\quad\{associativity\}

\quad X\sqcup (Y\sqcup X)\sqcup Z

\equiv\quad\{symmetry\}

\quad X\sqcup (X\sqcup Y)\sqcup Z

\equiv\quad\{associativity\}

\quad(X\sqcup X)\sqcup (Y\sqcup Z)

\equiv\quad\{idempotence\}

\quad X\sqcup (Y\sqcup Z)


Our next rule isFixed point:

X\sqcup\top\ \equiv\ \top

Proof

\quad X\sqcup\top

\equiv\quad\{(2)\}

\quad X\sqcup(Y\equiv Y)

\equiv\quad\{distributivity\}

\quad X\sqcup Y\ \equiv\ X\sqcup Y

\equiv\quad\{reflexivity\}

\quad\top

Equivalence

October 11, 2007

At the heart of our approach to mathematics is the technique of calculation. When we calculate, we rearrange expressions to form new expressions in accordance with certain rules. These expressions may have many different values. One way we cope with this complexity is to identify values which have properties in common and collect them into groups. Such groups are called types. If a value v belongs to a type T, we say that v is of type T.

***

The first type we will explore is a very simple one – so simple it consists of only two values. The type is called boolean and its values are \top, pronounced “top” and \bot, pronounced “bottom”.

Now we can talk about the value of X = Y :

“The value of X = Y is of type boolean.”

or, equivalently,

“The value of X = Y is either \top or \bot.”

***

Equality between booleans is special, and so when we express equality between X and Y, where X and Y are boolean we write

X\equiv Y

pronounced “X equivales Y “.

What is so special about boolean equality – called equivalence – that we have special symbol for it? The answer gives us our first rule for calculating:

Associativity:
(X \equiv (Y \equiv Z)) \equiv ((X \equiv Y ) \equiv Z)

We give the rule a name to help us remember what it is. Here is how we would use the rule in calculations:

  X \equiv (Y \equiv Z)
\equiv\quad \{\textrm{associativity}\}
  (X \equiv Y ) \equiv Z

An important consequence of $\eqv$’s associativity is that when we have a series of expressions punctuated by $\eqv$ signs it does not matter where we put the brackets. Indeed, we need not write the brackets at all, as for instance in our next rule:\\

Symmetry: X\equiv Y\equiv Y\equiv X

We may parse this rule in several ways:

$ latex (X\equiv Y)\equiv (Y\equiv X)$

X\equiv (Y\equiv Y\equiv X)

(X\equiv Y\equiv Y)\equiv X

The last two expressions tell us that `equivaling’ Y\equiv Y with any boolean X is X. We say that Y\equiv Y is the identity of \equiv. Our next rule gives a name to the identity:

(2) X\equiv\top\equiv X

Up to this point we have simply postulated rules i.e. we have taken it as given that they hold. Our next rule, however, we will prove. How do we prove? When we postulate a rule we are saying that it is an expression which is equivalent to \top. So to show that an expression is a rule, we present a calculation showing that the said expression is also equivalent to \top.

Reflexivity: X\equiv X

Proof

X\equiv X

\equiv {{(2), parsed as X\equiv(\top\equiv X)

X\equiv\top\equiv X

\equiv {(2)}

\top

Such is the equivalence.

Challenge: Does anyone know how to get the latex \quad and \begin{tabular} commands to work in WordPress?