Boolean functions and boolean algebra.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Boolean functions\n",
    "\n",
    "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.\n",
    "\n",
    "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$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FirstExample ← {(⍺<⍵) ∧ (⍵<3)}\n",
    "1 FirstExample 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "¯5 FirstExample 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0\n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 FirstExample 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0\n",
       "</span>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 FirstExample 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0\n",
       "</span>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 FirstExample 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FirstExamplePermissive ← {(⍺<⍵) ∨ (⍵<3)}\n",
    "1 FirstExamplePermissive 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "¯5 FirstExamplePermissive 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 FirstExamplePermissive 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 FirstExamplePermissive 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 FirstExamplePermissive 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Breaking down the first examples\n",
    "\n",
    "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.\n",
    "\n",
    "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!\n",
    "\n",
    "The three boolean function primitives we just used are the following:\n",
    "\n",
    " - `<` is the \"Less Than\" function that checks if the left argument is strictly smaller than the right argument;\n",
    " - `∧` 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 than `0`/`1`;\n",
    " - `∨` 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 than `0`/`1`.\n",
    " \n",
    " > 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$.\n",
    " \n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Boolean functions - what are they?\n",
    "\n",
    "So, what really _is_ a boolean function?\n",
    "\n",
    "The APL Wiki [defines a boolean function](https://aplwiki.com/wiki/Boolean#Boolean_functions) as\n",
    "\n",
    " > A monadic or dyadic function (sometimes scalar function) which has a boolean result when passed boolean arguments.\n",
    " \n",
    "Let us break down this sentence so we fully understand what it means:\n",
    "\n",
    " - _\"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);\n",
    " \n",
    "Below you can see the function `×` being used monadically and dyadically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">¯1\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "× ¯5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">4\n",
       "</span>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 × 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - _\"(sometimes scalar function)\"_ : a [scalar function](https://aplwiki.com/wiki/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;\n",
    " \n",
    "Below you can see the function `×` acting as a scalar function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">¯1 1 0 1\n",
       "</span>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "× ¯3 5 0 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 4 6\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 × 1 2 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3 4 3\n",
       "</span>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 2 1 × 1 2 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - _\"which has a boolean result\"_ : which returns a value that is either `0` or `1`;\n",
    " \n",
    " \n",
    " \n",
    " - _\"when passed boolean arguments\"_ : when its inputs are either `0` or `1`;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Primitives that are boolean functions\n",
    "\n",
    "Following the definition we just went over, which of APL's primitives are boolean functions? Here they are:\n",
    "\n",
    "## Monadic boolean functions\n",
    "\n",
    "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:\n",
    "\n",
    "```\n",
    "+×! |⌈⌊⊣⊢ ≠≡≢ ↑↓⊂⊃⊆⌷ ∊∪~ ,⍪⌽⊖⍉\n",
    "```\n",
    "\n",
    "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`.\n",
    "\n",
    "### These are the four unique boolean functions:\n",
    "\n",
    " - the identity function, like `⊢` or `⊣`:\n",
    "\n",
    "| Y | f Y |\n",
    "|---|-----|\n",
    "| 0 |   0 |\n",
    "| 1 |   1 |\n",
    "\n",
    " - the negation function, like `~`:\n",
    " \n",
    "| Y | f Y |\n",
    "|---|-----|\n",
    "| 0 |   1 |\n",
    "| 1 |   0 |\n",
    "\n",
    " - the `0` function, like `≡`, `⊢∘0` or `0⍨`:\n",
    " \n",
    "| Y | f Y |\n",
    "|---|-----|\n",
    "| 0 |   0 |\n",
    "| 1 |   0 |\n",
    "\n",
    " - and the `1` function, like `!`, `⊢∘1` or `1⍨`:\n",
    " \n",
    "| Y | f Y |\n",
    "|---|-----|\n",
    "| 0 |   1 |\n",
    "| 1 |   1 |\n",
    "\n",
    "If you want to explore how a given function behaves, you can use the following utility function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬───┐\n",
       "│Y│f Y│\n",
       "├─┼───┤\n",
       "│0│0  │\n",
       "├─┼───┤\n",
       "│1│1  │\n",
       "└─┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MBT ← {'Y' 'f Y'⍪↑(⊢,(⍎⍵))¨0 1}\n",
    "MBT '⊢' ⍝ identity function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬───┐\n",
       "│Y│f Y│\n",
       "├─┼───┤\n",
       "│0│1  │\n",
       "├─┼───┤\n",
       "│1│0  │\n",
       "└─┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MBT '~' ⍝ negation function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬───┐\n",
       "│Y│f Y│\n",
       "├─┼───┤\n",
       "│0│0  │\n",
       "├─┼───┤\n",
       "│1│0  │\n",
       "└─┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MBT '0⍨' ⍝ zero function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬───┐\n",
       "│Y│f Y│\n",
       "├─┼───┤\n",
       "│0│1  │\n",
       "├─┼───┤\n",
       "│1│1  │\n",
       "└─┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MBT '1⍨' ⍝ one function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dyadic boolean functions\n",
    "\n",
    "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:\n",
    "\n",
    "```\n",
    "×*! |⌈⌊⊥⊤⊣⊢ =≠≤<>≥≡≢ ∨∧⍱⍲ ↑↓ ∊⍷∩~ /\\⌿⍀ ⍴⌽⊖\n",
    "```\n",
    "\n",
    "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.\n",
    "\n",
    "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.\n",
    "\n",
    "For starters, another utility function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT ← {'X' 'Y' ('X f Y') ⍪↑0 0 1 1(⊣,⊢,(⍎⍵))¨0 1 0 1}\n",
    "DBT '∨'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Some dyadic boolean functions\n",
    "\n",
    "### _AND_ , _conjunction_\n",
    "\n",
    "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).\n",
    "\n",
    "There are a couple of ways to explain, in words, the return values of the logical \"and\":\n",
    "\n",
    " - always returns `0` except when both arguments are `1`;\n",
    " - only returns `1` if both arguments are `1`;\n",
    " - returns `0` if any of the arguments is `0`.\n",
    " \n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '∧'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _OR_ , _disjunction_\n",
    "\n",
    "The \"or\" function returns `1` if its left argument _or_ its right argument is \"true\" and its APL primitive is `∨` (again, similar to mathematics).\n",
    "\n",
    "This is how the \"or\" function works:\n",
    "\n",
    " - always returns `1` except when both arguments are `0`;\n",
    " - only returns `0` if both arguments are `0`;\n",
    " - returns `1` if any of the arguments is `1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '∨'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _IMP_ , _implication_\n",
    "\n",
    "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.\n",
    "\n",
    "The way implication works is a bit more involved to explain in words:\n",
    "\n",
    " - always returns `1` except if the left argument is `1` and the right argument is `0`;\n",
    " - returns `1` if the second argument is `1` or if the left argument is `0`.\n",
    "\n",
    "A nice mnemonic for how implication works is as follows:\n",
    "\n",
    " > 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?\n",
    " > - Not studying (`0`) and not passing (`0`) $\\implies$ this can happen (`1`);\n",
    " > - Not studying (`0`) and passing (`1`) $\\implies$ this can happen (`1`) if the person is lucky or smart enough;\n",
    " > - Studying (`1`) and not passing (`0`) $\\implies$ this cannot happen (`0`);\n",
    " > - Studying (`1`) and passing (`1`) $\\implies$ this can happen (`1`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '≤'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also confirm the equivalence I stated above, $\\alpha \\implies \\omega$ being the same as $\\omega ∨ \\neg \\alpha$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '{⍵∨~⍺}'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _NAND_\n",
    "\n",
    "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\n",
    "\n",
    " - always returns `1` except when both arguments are `1`;\n",
    " - only returns `0` if both arguments are `1`;\n",
    " - returns `1` if any of the arguments is `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│0    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '⍲'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│0    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '(~∧)'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _NOR_\n",
    "\n",
    "Similar to the \"nand\" function is the \"nor\" function, the negation of the \"or\" function, `(~∨)` or, in one glyph, `⍱`, which\n",
    "\n",
    " - always returns `0` except when both arguments are `0`;\n",
    " - only returns `1` if both arguments are `0`;\n",
    " - returns `0` if any of the arguments is `1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│0    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '⍱'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _XNOR_ , _EQUIV_ , _equivalence_\n",
    "\n",
    "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.\n",
    "\n",
    " - returns `1` if both arguments are the same;\n",
    " - returns `0` if both arguments are different."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '='"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _XOR_ , _exclusive disjunction_\n",
    "\n",
    "The \"xor\" function, sometimes referred to as \"exclusive or\",\n",
    "\n",
    " - returns `1` if there is exactly one `1` among the arguments;\n",
    " - returns `1` if the two arguments are different;\n",
    " - returns `0` if the two arguments are the same.\n",
    " \n",
    "APL doesn't have a primitive specifically for the \"xor\" function but from the explanations above we see we can just go with `≠`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│0    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DBT '≠'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Boolean algebra\n",
    "\n",
    "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.\n",
    "\n",
    "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](https://aplcart.info/?q=boolean#).\n",
    "\n",
    "For now, lets write one utility function to check if two expressions corresponding to two boolean functions are the same when applied monadically/dyadically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SameAs ← {⍺ ≡⍥⍺⍺ ⍵}\n",
    "'~' MBT SameAs '~'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'~' MBT SameAs '~'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'⊣' MBT SameAs '⊢' ⍝ monadic left- and right-tack are the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0\n",
       "</span>"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'0⍨' MBT SameAs '1⍨'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'≤' DBT SameAs '{⍵∨~⍺}' ⍝ implication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'~∨' DBT SameAs '⍱'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0\n",
       "</span>"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'∧' DBT SameAs '∨'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## De Morgan's laws\n",
    "\n",
    "[De Morgan's laws](https://en.wikipedia.org/wiki/De_Morgan%27s_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:\n",
    "\n",
    " - $\\neg(\\alpha\\vee\\omega)$ is the same as $\\neg \\alpha \\wedge \\neg \\omega$, which in APL is saying that `⍺⍱⍵` is the same as `⍺ ∧⍥~ ⍵`;\n",
    " - $\\neg(\\alpha\\wedge\\omega)$ is the same as $\\neg \\alpha \\vee \\neg \\omega$, which in APL is saying that `⍺⍲⍵` is the same as `⍺ ∨⍥~ ⍵`.\n",
    " \n",
    "We can check these are indeed the same with our utility function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'⍱' DBT SameAs '∧⍥~'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'⍲' DBT SameAs '∨⍥~'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rewriting _XOR_ and _XNOR_ with _AND_ , _OR_ and _NOT_\n",
    "\n",
    "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.\n",
    "\n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'≠' DBT SameAs '{(⍺∨⍵)∧~(⍺∧⍵)}'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or tacitly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'≠' DBT SameAs '∨∧∘~∧'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'=' DBT SameAs '{(⍺∧⍵)∨~(⍺∨⍵)}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'=' DBT SameAs '∧∨∘~∨'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The power of _NAND_\n",
    "\n",
    "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]](https://en.wikipedia.org/wiki/NAND_logic)\n",
    "\n",
    "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.\n",
    "\n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬───┐\n",
       "│Y│f Y│\n",
       "├─┼───┤\n",
       "│0│1  │\n",
       "├─┼───┤\n",
       "│1│0  │\n",
       "└─┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NAND ← ⍲\n",
    "NOT ← (NAND⍨)\n",
    "MBT 'NOT'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With \"not\" and \"nand\" we can easily make \"and\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AND ← (NOT NAND)\n",
    "DBT 'AND'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now it feels right to go for the \"or\" function, as we already have \"and\" and \"not\".\n",
    "\n",
    "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 `~(~⍺)∧(~⍵)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OR ← (NOT AND⍥NOT)\n",
    "DBT 'OR'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that this works but we built the \"or\" from the \"and\" and the \"not\" functions; can we simplify it?\n",
    "\n",
    "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!\n",
    "\n",
    "In the end, we can make the \"or\" function more simple with"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OR ← (NAND⍥NOT)\n",
    "DBT 'OR'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│0    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NOR ← (NOT OR)\n",
    "DBT 'NOR'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the \"xor\" function we can just recover the conversion we did earlier on, that showed the \"xor\" function could be written as `∨∧∘~∧`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│0    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR ← (OR AND∘NOT AND)\n",
    "DBT 'XOR'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, \"xnor\" just negates the \"xor\" function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─┬─┬─────┐\n",
       "│X│Y│X f Y│\n",
       "├─┼─┼─────┤\n",
       "│0│0│1    │\n",
       "├─┼─┼─────┤\n",
       "│0│1│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│0│0    │\n",
       "├─┼─┼─────┤\n",
       "│1│1│1    │\n",
       "└─┴─┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XNOR ← NOT XOR\n",
    "DBT 'XNOR'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To conclude, we can check all these correspond to the correct primitives.\n",
    "\n",
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "∧/ '∨' '∧' '⍱' '⍲' '≠' '=' (DBT SameAs)¨ 'OR' 'AND' 'NOR' 'NAND' 'XOR' 'XNOR'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1\n",
       "</span>"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'~' MBT SameAs 'NOT'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge\n",
    "\n",
    "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...\n",
    "\n",
    "I challenge you to do it! Good luck!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}