Boolean functions#
The bare minimum you need to know about boolean functions in order to use them is that “true” and “false” in APL are respectively 1 and 0. If this comes as a shock to you, do not worry: you will get used to it in no time.
To help you get used to it, lets jump right into some examples. Lets write a function that returns “true” (1, really) if the left argument is smaller than the right one and if the right argument is smaller than \(3\):
FirstExample ← {(⍺<⍵) ∧ (⍵<3)}
1 FirstExample 2
¯5 FirstExample 2
0 FirstExample 3
2 FirstExample 0
5 FirstExample 4
Ok, maybe you changed your mind and your function is too restrictive. Maybe you just need any of the two previous conditions to be true, so you are happy with either having the left argument smaller than the right one or the right argument smaller than \(3\). Lets write a more permissive function:
FirstExamplePermissive ← {(⍺<⍵) ∨ (⍵<3)}
1 FirstExamplePermissive 2
¯5 FirstExamplePermissive 2
0 FirstExamplePermissive 3
2 FirstExamplePermissive 0
5 FirstExamplePermissive 4
Breaking down the first examples#
Go back to the FirstExample and FirstExamplePermissive example functions above and count the number of different boolean functions we just used. How many did you count? If your answer is \(3\), you are spot on.
If you answered \(2\) because you only considered ∨ and ∧ that is an honest mistake! If you also answered \(2\) but because you did not even notice that ∨ and ∧ are different… well, maybe you need a pair of glasses!
The three boolean function primitives we just used are the following:
<is the “Less Than” function that checks if the left argument is strictly smaller than the right argument;∧is the “Logical AND” function when we use it for our boolean purposes and it checks if both arguments are true; the∧primitive can also be used to find the lowest common multiple (lcm) of two numbers other than0/1;∨is the “Logical OR” function when we use it for our boolean purposes and it checks if any of the arguments is true; the∨primitive can also be used to find the greatest common divisor (gcd) of two numbers other than0/1.
Just a math-y side note: in actuality we can look at the
∧primitive simply as the lcm function, as the behaviour of the lcm matches the behaviour of the “Logical AND” when the left and right arguments are just zeroes and ones. Same thing goes for the∨primitive if we agree on the convention that \(\gcd(0, 0) = 0\) (for example by extending the fact that \(k > 0 \implies \gcd(0, k) = k\)) even though any number is a divisor of \(0\) and hence there cannot be the greatest common divisor of \(0\) and \(0\).
If you check your language bar, you will see that close to the ∨ and ∧ primitives are the ⍱ and ⍲ primitives. Try comparing them to ∨ and ∧ to understand what they do. Further down this notebook you will get your answer so go ahead and explore on your own:
Boolean functions - what are they?#
So, what really is a boolean function?
The APL Wiki defines a boolean function as
A monadic or dyadic function (sometimes scalar function) which has a boolean result when passed boolean arguments.
Let us break down this sentence so we fully understand what it means:
“A monadic or dyadic function” : a function that can be called with one argument is a monadic function and a function that can be called with two arguments is a dyadic function. Some functions can be called with either one or two arguments (almost all primitive functions in APL);
Below you can see the function × being used monadically and dyadically:
× ¯5
1 × 4
“(sometimes scalar function)” : a scalar function is a function that naturally permeates through arrays into simple elements. If you are familiar with other programming languages, it may make sense to you to think of scalar functions as functions that automatically and recursively map over the arguments;
Below you can see the function × acting as a scalar function:
× ¯3 5 0 7
2 × 1 2 3
3 2 1 × 1 2 3
“which has a boolean result” : which returns a value that is either
0or1;“when passed boolean arguments” : when its inputs are either
0or1;
Primitives that are boolean functions#
Following the definition we just went over, which of APL’s primitives are boolean functions? Here they are:
Monadic boolean functions#
Monadic boolean functions are functions that return 0 or 1 when they receive 0 or 1 as input, and all these primitives satisfy this restriction:
+×! |⌈⌊⊣⊢ ≠≡≢ ↑↓⊂⊃⊆⌷ ∊∪~ ,⍪⌽⊖⍉
But in all fairness, there are only four unique monadic boolean functions, corresponding to the tables below, and many of the primitives above only made it to the list because they act as the identity function when applied to 0 and to 1.
These are the four unique boolean functions:#
the identity function, like
⊢or⊣:
Y |
f Y |
|---|---|
0 |
0 |
1 |
1 |
the negation function, like
~:
Y |
f Y |
|---|---|
0 |
1 |
1 |
0 |
the
0function, like≡,⊢∘0or0⍨:
Y |
f Y |
|---|---|
0 |
0 |
1 |
0 |
and the
1function, like!,⊢∘1or1⍨:
Y |
f Y |
|---|---|
0 |
1 |
1 |
1 |
If you want to explore how a given function behaves, you can use the following utility function:
MBT ← {'Y' 'f Y'⍪↑(⊢,(⍎⍵))¨0 1}
MBT '⊢' ⍝ identity function
MBT '~' ⍝ negation function
MBT '0⍨' ⍝ zero function
MBT '1⍨' ⍝ one function
Dyadic boolean functions#
Dyadic boolean functions, on the other hand, are functions that return either 0 or 1 when the left and right arguments are 0 or 1. These are the primitives that qualify:
×*! |⌈⌊⊥⊤⊣⊢ =≠≤<>≥≡≢ ∨∧⍱⍲ ↑↓ ∊⍷∩~ /\⌿⍀ ⍴⌽⊖
There were only four unique monadic boolean functions but there are sixteen (16) unique dyadic boolean functions. Most of them have well-known meanings for us, although the names that we are most used to can vary depending on our background, be it mathematics, electronics, computer science, etc.
In the context of logic or boolean algebra we usually hear people say things like conjunction, disjunction, implication, equivalence (and others) and we will now map these terms to APL functions.
For starters, another utility function:
DBT ← {'X' 'Y' ('X f Y') ⍪↑0 0 1 1(⊣,⊢,(⍎⍵))¨0 1 0 1}
DBT '∨'
Some dyadic boolean functions#
AND , conjunction#
The “and” function returns 1 if its left argument and its right argument are “true” and its APL primitive is ∧ (much like the symbol for the corresponding logical operation in traditional mathematics).
There are a couple of ways to explain, in words, the return values of the logical “and”:
always returns
0except when both arguments are1;only returns
1if both arguments are1;returns
0if any of the arguments is0.
These are all equivalent and it might seem pointless to enumerate them but turns out to be helpful to be able to reason about equivalent formulations of the same function.
DBT '∧'
OR , disjunction#
The “or” function returns 1 if its left argument or its right argument is “true” and its APL primitive is ∨ (again, similar to mathematics).
This is how the “or” function works:
always returns
1except when both arguments are0;only returns
0if both arguments are0;returns
1if any of the arguments is1.
DBT '∨'
IMP , implication#
The implication \(\alpha \implies \omega\) returns 1 if its left argument implies the right argument, wich can be defined as \(\omega ∨ (\neg \alpha)\) where \(\neg \alpha\) means “not \(\alpha\)” (so ~⍺ in APL). APL doesn’t have a dedicated primitive for this but we will see that the ≤ comparison function can do the job.
The way implication works is a bit more involved to explain in words:
always returns
1except if the left argument is1and the right argument is0;returns
1if the second argument is1or if the left argument is0.
A nice mnemonic for how implication works is as follows:
We will reason about taking a final exam depending on whether a smart person studied the subject or not; do these situations make sense or not?
Not studying (
0) and not passing (0) \(\implies\) this can happen (1);Not studying (
0) and passing (1) \(\implies\) this can happen (1) if the person is lucky or smart enough;Studying (
1) and not passing (0) \(\implies\) this cannot happen (0);Studying (
1) and passing (1) \(\implies\) this can happen (1).
DBT '≤'
We can also confirm the equivalence I stated above, \(\alpha \implies \omega\) being the same as \(\omega ∨ \neg \alpha\):
DBT '{⍵∨~⍺}'
NAND#
The “nand” function is the negation of the “and” function and can be written in APL as (~∧) except we do not need that because of the builtin primitive ⍲, which
always returns
1except when both arguments are1;only returns
0if both arguments are1;returns
1if any of the arguments is0.
DBT '⍲'
DBT '(~∧)'
NOR#
Similar to the “nand” function is the “nor” function, the negation of the “or” function, (~∨) or, in one glyph, ⍱, which
always returns
0except when both arguments are0;only returns
1if both arguments are0;returns
0if any of the arguments is1.
DBT '⍱'
XNOR , EQUIV , equivalence#
The “xnor” function returns 1 if the two arguments are the same, which from the boolean algebra point of view is saying that the two arguments are equivalent . In APL, we can just use the = primitive.
returns
1if both arguments are the same;returns
0if both arguments are different.
DBT '='
XOR , exclusive disjunction#
The “xor” function, sometimes referred to as “exclusive or”,
returns
1if there is exactly one1among the arguments;returns
1if the two arguments are different;returns
0if the two arguments are the same.
APL doesn’t have a primitive specifically for the “xor” function but from the explanations above we see we can just go with ≠:
DBT '≠'
Boolean algebra#
Boolean algebra is the branch of mathematics in which we use boolean operations to manipulate boolean values. We already introduced many boolean operations and now we will explore some boolean algebra identities.
To learn more about the uses of boolean functions and boolean arrays specifically in APL, there is a notebook on that subject matter in the making. Until then, consider exploring the query results for “boolean” on aplcart.info.
For now, lets write one utility function to check if two expressions corresponding to two boolean functions are the same when applied monadically/dyadically:
SameAs ← {⍺ ≡⍥⍺⍺ ⍵}
'~' MBT SameAs '~'
'~' MBT SameAs '~'
'⊣' MBT SameAs '⊢' ⍝ monadic left- and right-tack are the same
'0⍨' MBT SameAs '1⍨'
'≤' DBT SameAs '{⍵∨~⍺}' ⍝ implication
'~∨' DBT SameAs '⍱'
'∧' DBT SameAs '∨'
De Morgan’s laws#
De Morgan’s laws teach us to “distribute” the negation ~ over a conjunction/disjunction, that is, they allow one to remove the parenthesis in the two following expressions:
\(\neg(\alpha\vee\omega)\) is the same as \(\neg \alpha \wedge \neg \omega\), which in APL is saying that
⍺⍱⍵is the same as⍺ ∧⍥~ ⍵;\(\neg(\alpha\wedge\omega)\) is the same as \(\neg \alpha \vee \neg \omega\), which in APL is saying that
⍺⍲⍵is the same as⍺ ∨⍥~ ⍵.
We can check these are indeed the same with our utility function.
'⍱' DBT SameAs '∧⍥~'
'⍲' DBT SameAs '∨⍥~'
Rewriting XOR and XNOR with AND , OR and NOT#
The “implies”, “xor” and “xnor” boolean functions can be written in terms of the “and”, “or” and “not” boolean functions. Above, we already did that for the “implies” function so lets take care of the other two.
Recall that the “xor” function returns “true” if the left or the right arguments are true and not both of them are true, so we can really write \(\alpha \texttt{ xor } \omega = (\alpha ∨ \omega)∧\neg(\alpha ∧ \omega)\). In APL we had settled with ≠ for the “xor” function, so lets check if this adds up:
'≠' DBT SameAs '{(⍺∨⍵)∧~(⍺∧⍵)}'
or tacitly:
'≠' DBT SameAs '∨∧∘~∧'
We can do a similar thing for “xnor” which returns “true” if the left and right arguments are true or if the left and right arguments are false, so \(\alpha \texttt{ xnor } \omega = (\alpha ∧ \omega)∨(\neg\alpha ∧ \neg\omega) = (\alpha ∧ \omega)∨\neg(\alpha ∨ \omega)\) (we just used a De Morgan law!). In APL we had used = for the “xnor” function so lets check this identity:
'=' DBT SameAs '{(⍺∧⍵)∨~(⍺∨⍵)}'
'=' DBT SameAs '∧∨∘~∨'
The power of NAND#
The exercise we just did, of rewriting boolean functions in terms of other boolean functions, can be taken to an extreme… Did you know you can write any boolean function just in terms of the “nand” boolean function?[1]
So lets do it, because why not? For this exercise we are allowed to use the “nand” primitive ⍲ and then we can only use parenthesis and chain our “nand” primitives in smart ways. Lets start with the “not” and “and” gates because they seam the easiest.
We cannot really make “and” out of “nand” without the “not” function; on the other hand the “not” function is monadic and “nand” is dyadic, so the only thing we can do is take “not“‘s argument, duplicate it and feed it into the “nand” function:
NAND ← ⍲
NOT ← (NAND⍨)
MBT 'NOT'
With “not” and “nand” we can easily make “and”:
AND ← (NOT NAND)
DBT 'AND'
Now it feels right to go for the “or” function, as we already have “and” and “not”.
Recall that the De Morgan law states that ~(⍺∨⍵) is the same as (~⍺)∧(~⍵) so we can negate both expressions again and we get that ⍺∨⍵ is the same as ~(~⍺)∧(~⍵).
OR ← (NOT AND⍥NOT)
DBT 'OR'
Notice that this works but we built the “or” from the “and” and the “not” functions; can we simplify it?
If you check above, you can see that the “or” function “returns 1 if any of the arguments is 1” while the “nand” function “returns 1 if any of the arguments is 0” so we just need to invert the inputs to transform one into the other!
In the end, we can make the “or” function more simple with
OR ← (NAND⍥NOT)
DBT 'OR'
We are almost there, we are only missing the “nor”, “xor” and “xnor” functions. Getting the “nor” is easy, as we just have to negate the “or”:
NOR ← (NOT OR)
DBT 'NOR'
For the “xor” function we can just recover the conversion we did earlier on, that showed the “xor” function could be written as ∨∧∘~∧:
XOR ← (OR AND∘NOT AND)
DBT 'XOR'
Finally, “xnor” just negates the “xor” function:
XNOR ← NOT XOR
DBT 'XNOR'
To conclude, we can check all these correspond to the correct primitives.
To see if all correspondences are correct we use a little something from the notebook on using boolean functions and boolean arrays in APL, the ∧/ reduction that checks if all the booleans in an array are true:
∧/ '∨' '∧' '⍱' '⍲' '≠' '=' (DBT SameAs)¨ 'OR' 'AND' 'NOR' 'NAND' 'XOR' 'XNOR'
'~' MBT SameAs 'NOT'
Challenge#
This property that the “nand” function has, the possibility of using it to create all other boolean functions, is called “functional completeness” and this is not a property that is unique to the “nand” function. The “nor” function is also functionally complete, meaning you can use the “nor” ⍱ function to write all other boolean functions we have seen…
I challenge you to do it! Good luck!