Boolean operators in algebra

The boolean operators of Ampersand behave as one would expect in any boolean algebra. Union (\cup) and intersection (\cap) are both idempotent, commutative, and associative operators. In Ampersand we use a binary difference operator over with the usual semantics: (rs)(rs)=r(r-s)\cup(r\cap s) = r. The (more customary) complement operator is a partial function, because Ampersand supports heterogeneous relation algebra.

Union

The operator \cup (union) satisfies the following axioms:

  1. (commutativity of \cup) rs = srr\cup s\ =\ s\cup r

  2. (associativity of \cup) r(st) = (rs)tr\cup (s\cup t)\ =\ (r\cup s)\cup t

  3. (idempotence of \cup) rr = rr\cup r\ =\ r

Difference

The difference rsr-s is the smallest relation tt that satisfies r  str\ \subseteq\ s\cup t. Smallest means: If there is a tt' for which st=rs\cup t'=r, this implies that tt=tt\cup t'=t'.

Intersection

The intersection \cap is defined as: rs=r(rs)r \cap s = r-(r-s)

Complement

The complement operator is defined as t=V[A×B]t\overline{t} = V_{[A\times B]} - t. The type [A×B][A\times B] comes from the term(s) in which tt is embedded. If that type does not exist or if it is ambiguous, Ampersand will refuse to compile with an appropriate error message.

How to type boolean operators in your script

This page shows how you can write these things in your Ampersand script.

Other explanation

Last updated