Summary Modelling Computing Systems Hoofdstuk 3 Faron Moller & Georg Struth

Hoofdstuk 3

A monoid consist of:

- A set of A
- An element e ∈ A
- A binary operator ⊕

That satisfy the following three laws, for all x, y and z:

1. e ⊕ x = x
2. x ⊕ e = x
3. x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z

We sometimes say that e is the unit of ⊕. The third law states that the operator ⊕ is
associative(how we put the () ).



A Boolean algabra consist of:

- a set B
- Two elements, 0 ∈ B and 1 ∈ B, called the
zero and unit respectively.
- Two operators + and ·, called the sum and
product respectively.
- A unary operator ‘ called the inverse.

Figure on the right shows the different laws for
Boolean algabra.




Truth tables for Boolean algabra

, Any equation derived from the laws is known as a theorem. We can also show that for all x, we have
x + x = x.

Proof x + x = (x + x) · 1 = (x + x) · (x + x’) = x + (x · x’) = x + 0 = x

Many of these derived theorems follow use the following property. If x + y = x + z and x · y = x · z,
then y = z. In other words, if y and z ‘behave the same’ on every element x, we can conclude that y
and z are equal. We can use this to show that (x’)’ = x.