{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Boolean logic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sources\n",
    "\n",
    "* Hyde, Write Great Code, Volume 1: Understanding the Machine (2004), Chapter 3: Binary Arithmetic and Bit Operations\n",
    "* Nisan and Schocken, *The Elements of Computing Systems: Building a Modern Computer from First Principles* (2008), Chapter 1: Boolean Logic\n",
    "* Mims, *Workbook I: Basic Electronics, Transistors and Integrated Circuits*, second printing (2013)\n",
    "* Mims, *Workbook II: Digital Logic Projects*, second printing (2013)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolean algebra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Boolean expressions\n",
    "\n",
    "$ f(x, y, z) = (x + y) \\cdot \\overline{z} $\n",
    "\n",
    "`(x OR y) AND NOT z`\n",
    "\n",
    "### Canonical representation\n",
    "\n",
    "$ f(x, y, z) = \\overline{x}y\\overline{z} + x\\overline{y}\\overline{z} + xy\\overline{z} $\n",
    "\n",
    "`((NOT x) AND y AND (NOT z)) OR (x AND (NOT y) AND (NOT z)) OR (x AND y AND (NOT z))`\n",
    "\n",
    "### Truth table representation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_truth_table(f, arr):\n",
    "    for row in arr:\n",
    "        print(row, f(*row))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Evaluate using bitwise operators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0] 0\n",
      "[0, 0, 1] 0\n",
      "[0, 1, 0] 1\n",
      "[0, 1, 1] 0\n",
      "[1, 0, 0] 1\n",
      "[1, 0, 1] 0\n",
      "[1, 1, 0] 1\n",
      "[1, 1, 1] 0\n"
     ]
    }
   ],
   "source": [
    "def foo(x, y, z):\n",
    "    return (~x & y & ~z) | (x & ~y & ~z) | (x & y & ~z);\n",
    "\n",
    "vals = [ [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],\n",
    "         [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1] ]\n",
    "\n",
    "print_truth_table(foo, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logical operations on bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Four main logical operations are performed on bits:\n",
    "\n",
    "1. AND\n",
    "2. OR\n",
    "3. XOR (exclusive or)\n",
    "4. NOT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### AND truth table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| AND | 0 | 1 |\n",
    "|-----|---|---|\n",
    "| 0   | 0 | 0 |\n",
    "| 1   | 0 | 1 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### OR truth table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| OR | 0 | 1 |\n",
    "|----|---|---|\n",
    "| 0  | 0 | 1 |\n",
    "| 1  | 1 | 1 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### XOR truth table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the first or second value, but *not* both, is 1, the result is 1, otherwise the result is zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| XOR | 0 | 1 |\n",
    "|-----|---|---|\n",
    "| 0   | 0 | 1 |\n",
    "| 1   | 1 | 0 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NOT truth table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| NOT | 0 | 1 |\n",
    "|-----|---|---|\n",
    "|     | 1 | 0 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bitwise (bit-by-bit) operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two values, operate bitwise on bit zero of both operands, then bit one of both operands, and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bitwise logical AND of two 8-bit numbers:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "10110101 // Operand 1\n",
    "11101110 // Operand 2\n",
    "10100100 // Result\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b10100100'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(0b10110101 & 0b11101110)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Uses for bitwise logical operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check an integer value to see if it is even or odd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If bit position zero of a binary integer value contains one, that integer is odd; if it contains zero, then that integer is even. Testing bit position zero:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def bitwise_is_odd(i):\n",
    "    return (i & 1) != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bitwise_is_odd(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bitwise_is_odd(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## The `nand` gate\n",
    "\n",
    "$\\overline{x \\cdot y}$\n",
    "\n",
    "`NOT (x AND y)`\n",
    "\n",
    "### Truth table representation: direct\n",
    "\n",
    "`if a = b = 1 then out = 0 else out = 1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0] 1\n",
      "[0, 1] 1\n",
      "[1, 0] 1\n",
      "[1, 1] 0\n"
     ]
    }
   ],
   "source": [
    "def _nand(a, b):\n",
    "    if a == b == 1:\n",
    "        return 0\n",
    "    else:\n",
    "        return 1\n",
    "\n",
    "vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]\n",
    "print_truth_table(_nand, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic logic gates\n",
    "\n",
    "(See also https://en.wikipedia.org/wiki/NAND_logic)\n",
    "\n",
    "### Summary\n",
    "\n",
    "`Not` built with `Nand` (`_n_` prefix refers to `Nand`):\n",
    "```py\n",
    "def _n_not(a):\n",
    "    return _nand(a, a)\n",
    "```\n",
    "\n",
    "`And` built with `Nand` and `Not`:\n",
    "```py\n",
    "def _n_and(a, b):\n",
    "    return _n_not(_nand(a, b))\n",
    "```\n",
    "\n",
    "`Or` built with `Nand`, `Not`, and `And`:\n",
    "```py\n",
    "def _n_or(a, b):\n",
    "    return _n_not(_n_and(_nand(a, a), _nand(b, b)))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic logic gates: `not`\n",
    "\n",
    "$\\overline{x}$\n",
    "\n",
    "`NOT (x)`\n",
    "\n",
    "Converts its input from 0 to 1 and from 1 to 0.\n",
    "\n",
    "#### Truth table representation: direct\n",
    "\n",
    "`if in = 0 then out = 1 else out = 0`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0] 1\n",
      "[1] 0\n"
     ]
    }
   ],
   "source": [
    "def _not(a):\n",
    "    if a == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "vals = [ [0], [1] ]\n",
    "print_truth_table(_not, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Truth table representation: Nand logic\n",
    "\n",
    "Joining the inputs of a Nand gate leaves only the NOT gate:\n",
    "\n",
    "`Not(a) = Nand(a, a)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0] 1\n",
      "[1] 0\n"
     ]
    }
   ],
   "source": [
    "def _n_not(a):\n",
    "    return _nand(a, a)\n",
    "\n",
    "vals = [ [0], [1] ]\n",
    "print_truth_table(_n_not, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### In HDL (using built-in primitive `Nand` chip)\n",
    "\n",
    "```verilog\n",
    "/**\n",
    " * Not gate:\n",
    " * out = not in\n",
    " */\n",
    "\n",
    "CHIP Not {\n",
    "    IN in;\n",
    "    OUT out;\n",
    "\n",
    "    PARTS:\n",
    "    \n",
    "    // Using built-in primitive Nand chip:\n",
    "    // Not(a) = Nand(a, a)\n",
    "    Nand(a = in, b = in, out = out);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Basic logic gates: `and`\n",
    "\n",
    "$ x \\cdot y $\n",
    "\n",
    "`x AND y`\n",
    "\n",
    "Returns 1 when both its inputs are 1, else 0.\n",
    "\n",
    "#### Truth table representation: direct\n",
    "\n",
    "`if a = b = 1 then out = 1 else out = 0`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0] 0\n",
      "[0, 1] 0\n",
      "[1, 0] 0\n",
      "[1, 1] 1\n"
     ]
    }
   ],
   "source": [
    "def _and(a, b):\n",
    "    if a == b == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]\n",
    "print_truth_table(_and, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Circuit representation\n",
    "\n",
    "Two switches connected in series. The LED will only be illuminated if both switches are closed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe frameborder='0' height='448' marginheight='0' marginwidth='0' scrolling='no' src='https://123d.circuits.io/circuits/1836053-and-gate-using-two-switches-and-led/embed#breadboard' width='650'></iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%HTML\n",
    "<iframe frameborder='0' height='448' marginheight='0' marginwidth='0' scrolling='no' src='https://123d.circuits.io/circuits/1836053-and-gate-using-two-switches-and-led/embed#breadboard' width='650'></iframe>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Truth table representation: Nand logic\n",
    "\n",
    "`AND = NOT NAND`\n",
    "\n",
    "`And(a, b) = Not(Nand(a, b))`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0] 0\n",
      "[0, 1] 0\n",
      "[1, 0] 0\n",
      "[1, 1] 1\n"
     ]
    }
   ],
   "source": [
    "def _n_and(a, b):\n",
    "    return _n_not(_nand(a, b))\n",
    "\n",
    "vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]\n",
    "print_truth_table(_n_and, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### In HDL\n",
    "\n",
    "```verilog\n",
    "/**\n",
    " * And gate:\n",
    " * out = 1 if (a == 1 and b == 1)\n",
    " *       0 otherwise\n",
    " */\n",
    "\n",
    "CHIP And {\n",
    "    IN a, b;\n",
    "    OUT out;\n",
    "\n",
    "    PARTS:\n",
    "\n",
    "    // Using built-in primitive Nand chip\n",
    "    // and previously built Not chip:\n",
    "    // And(a, b) = Not(Nand(a, b))\n",
    "    Nand(a = a, b = b, out = c);\n",
    "    Not(in = c, out = out);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic logic gates: `or`\n",
    "\n",
    "$ x + y $\n",
    "\n",
    "`x OR y`\n",
    "\n",
    "Returns 1 when at least one of its inputs is 1, and 0 otherwise.\n",
    "\n",
    "#### Truth table representation: direct\n",
    "\n",
    "`if a = b = 0 then out = 0 else out = 1`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0] 0\n",
      "[0, 1] 1\n",
      "[1, 0] 1\n",
      "[1, 1] 1\n"
     ]
    }
   ],
   "source": [
    "def _or(a, b):\n",
    "    if a == b == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return 1\n",
    "\n",
    "vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]\n",
    "print_truth_table(_or, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Circuit representation\n",
    "\n",
    "Two switches connected in parallel. The LED will be illuminated if either switch is open."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe frameborder='0' height='448' marginheight='0' marginwidth='0' scrolling='no' src='https://123d.circuits.io/circuits/1869391-or-gate-using-two-switches-and-led/embed#breadboard' width='650'></iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%HTML\n",
    "<iframe frameborder='0' height='448' marginheight='0' marginwidth='0' scrolling='no' src='https://123d.circuits.io/circuits/1869391-or-gate-using-two-switches-and-led/embed#breadboard' width='650'></iframe>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Truth table representation: Nand logic\n",
    "\n",
    "`OR = NOT (NAND AND NAND)`\n",
    "\n",
    "`Or(a, b) = Not(And(Nand(a, a), Nand(b, b)))`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0] 0\n",
      "[0, 1] 1\n",
      "[1, 0] 1\n",
      "[1, 1] 1\n"
     ]
    }
   ],
   "source": [
    "def _n_or(a, b):\n",
    "    return _n_not(_n_and(_nand(a, a), _nand(b, b)))\n",
    "\n",
    "vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]\n",
    "print_truth_table(_n_or, vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### In HDL\n",
    "\n",
    "```verilog\n",
    " /**\n",
    " * Or gate:\n",
    " * out = 1 if (a == 1 or b == 1)\n",
    " *       0 otherwise\n",
    " */\n",
    "\n",
    "CHIP Or {\n",
    "    IN a, b;\n",
    "    OUT out;\n",
    "\n",
    "    PARTS:\n",
    "\n",
    "    // Using built-in primitive Nand chip\n",
    "    // and previously built Not and And chips:\n",
    "    // Or(a, b) = Not(And(Nand(a, a), Nand(b, b)))\n",
    "    Nand(a = a, b = a, out = c);\n",
    "    Nand(a = b, b = b, out = d);\n",
    "    And(a = c, b = d, out = e);\n",
    "    Not(in = e, out = out);\n",
    "}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic logic gates: `xor`\n",
    "\n",
    "WORKINGHERE"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  },
  "widgets": {
   "state": {},
   "version": "1.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}