TruthTables/Workbook_TruthTables.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Truth Tables Tutorial Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Truth Tables tutorial](./TruthTables.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Python that might be non-obvious for a first-time user.\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "1. Truth tables.\n",
    "2. Basic Python knowledge is helpful but not necessary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1. Projective functions (elementary variables)\n",
    "\n",
    "**Goal:** \n",
    "Describe the three projective functions $x_1$, $x_2$, $x_3$ represented by integers. Each of them is a 3-input function, i.e.,  $f(x) : \\{0,1\\}^{3} \\rightarrow \\{0,1\\}$\n",
    "\n",
    "We use the following convention:\n",
    "- $x_1$ is the least significant input.\n",
    "- $x_3$ is the most significant input.\n",
    "\n",
    "> The function $x_1$ (least significant input) is given as an example. \n",
    "The function is true for assignments $001$, $011$, $101$, and $111$, since for all these assignments their least significant bit $x_1 = 1$.\n",
    "\n",
    "If $x_1 = 0b10101010$, what are the values of $x_2$ and $x_3$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's take another look at the truth table for the functions $x_1$, $x_2$, and $x_3$ \n",
    "\n",
    "<table style=\"border:1px solid\">\n",
    "  <col width=50>\n",
    "  <col width=50>\n",
    "  <col width=50>\n",
    "  <col width=100>\n",
    "  <col width=100>\n",
    "  <col width=100>\n",
    "  <col width=150>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center; border:1px solid\">$x_3$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">$x_2$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">$x_1$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Is $x_1 = 1?$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Is $x_2 = 1?$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Is $x_3 = 1?$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Bit of the integer which represents the truth table</th>\n",
    "  </tr>    \n",
    "  <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Least significant</td>\n",
    "  </tr>    \n",
    "  <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "  </tr>    \n",
    "  <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "  </tr>    \n",
    "  <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "  </tr>\n",
    "   <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\"></td>\n",
    "  </tr>\n",
    "   <tr>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Yes</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Most Significant</td>\n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "To convert this form of a truth table into a single integer format, we need to write out all the bits of its values, from the most significant to the least significant. \n",
    "\n",
    "The truth table for $x_2$ is `0b11001100` (the bits in the $x_2$ column, from the bottom row to the top row) and the truth table for $x_3$ is `0b11110000`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_ProjectiveTruthTables \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function ProjectiveTruthTables () : (TruthTable, TruthTable, TruthTable) {\n",
    "    let x1 = TruthTable(0b10101010, 3);\n",
    "    let x2 = TruthTable(0b11001100, 3);\n",
    "    let x3 = TruthTable(0b11110000, 3);\n",
    "\n",
    "    return (x1, x2, x3);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1 of the Truth Tables kata.](./TruthTables.ipynb#Task-1.-Projective-functions-(elementary-variables))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2. \"Exactly 1 bit is true\" function\n",
    "\n",
    "**Goal:** \n",
    "Describe a 3-input function $f(x_3,x_2,x_1)$ represented by an integer which is true if and only if exactly 1 bit out of $x_1$, $x_2$ or $x_3$ is true."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "The function is true for assignments $100$, $010$, and $001$, since for these assignments exactly one bit is true. The function is false for assignments $000$, $011$, $101$, $110$, and $111$, since for all these assignments either all bits are false or more than one bit is true.\n",
    "\n",
    "To spell out the binary notation of the resulting integer, we list the bits (1 if the function is true and 0 if it is false), starting with the input $111$ and ending with $000$: `0b00010110`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_ExactlyOneBitTrue\n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function ExactlyOneBitTrue () : (TruthTable) {\n",
    "    let f = TruthTable(0b00010110, 3);\n",
    "    return f;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2 of the Truth Tables kata.](./TruthTables.ipynb#Task-2.-\"Exactly-1-bit-is-true\"-function)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3. \"Exactly 2 bits are true\" function\n",
    "\n",
    "**Goal:** \n",
    "Describe a 3-input function $f(x_3,x_2,x_1)$ represented by an integer which is true if and only if exactly 2 bits out of $x_1$, $x_2$ or $x_3$ are true.\n",
    "\n",
    "If $f = 0$, what are the values of $x_1$, $x_2$, and $x_3$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "The function is true for assignments $011$, $101$, and $110$, since for these assignments exactly 2 bits are true. The function is false for assignments $000$, $001$, $010$, $100$, $111$, since all these assignments do not have exactly 2 bits as true.\n",
    "\n",
    "The binary notation of the resuling integer is `0b01101000`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_ExactlyTwoBitsTrue\n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function ExactlyTwoBitsTrue () : (TruthTable) {\n",
    "    let f = TruthTable(0b01101000, 3);            // Update the value of f ...\n",
    "    return f;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3 of the Truth Tables kata.](./TruthTables.ipynb#Task-3.-\"Exactly-2-bits-are-true\"-function)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. Compute AND of two truth tables\n",
    "**Goal:** \n",
    "Compute a truth table that computes the conjunction (AND)\n",
    "of two truth tables.  Find a way to perform the computation\n",
    "directly on the integer representations of the truth tables,\n",
    "i.e., without accessing the bits individually."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "For each input, the value of the goal function is an AND of the values of the two given functions for the same input. \n",
    "We can use &&& operator to compute the bitwise conjunction (AND) of two integers representing truth tables to get the integer representing the goal function directly.\n",
    "\n",
    "Remember that `TruthTable` is a user-defined type with fields `bits` and `numVars`. You can access these fields as `tt1::bits` and `tt1::numVars`, respectively, and construct the return value from the fields using a constructor `TruthTable(newBits, newNumVars)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_TTAnd \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function TTAnd (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {\n",
    "    return TruthTable(tt1::bits &&& tt2::bits, tt1::numVars);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 4 of the Truth Tables kata.](./TruthTables.ipynb#Task-4.-Compute-AND-of-two-truth-tables)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5. Compute OR of two truth tables\n",
    "**Goal:** \n",
    "Compute a truth table that computes the disjunction (OR)\n",
    "of two truth tables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Similarly to the previous task, we can use the bitwise OR ||| operator to compute the disjunction (OR) of two truth tables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_TTOr \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function TTOr (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {\n",
    "    return TruthTable(tt1::bits ||| tt2::bits, tt1::numVars);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 5 of the Truth Tables kata.](./TruthTables.ipynb#Task-5.-Compute-OR-of-two-truth-tables)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 6. Compute XOR of two truth tables\n",
    "**Goal:** \n",
    "Compute a truth table that computes the exclusive-OR (XOR)\n",
    "of two truth tables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We can use the bitwise XOR ^^^ operator to compute the exclusive-OR (XOR) of two truth tables such as: tt1 ^^^ tt2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_TTXor \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function TTXor (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {\n",
    "    return TruthTable(tt1::bits ^^^ tt2::bits, tt1::numVars);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 6 of the Truth Tables kata.](./TruthTables.ipynb#Task-6.-Compute-XOR-of-two-truth-tables)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 7. Compute NOT of a truth table\n",
    "**Goal:** \n",
    "Compute a truth table that computes negation of a truth\n",
    "table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We can use the bitwise negation `~~~` operator to compute the negation (NOT) a truth table. \n",
    "Note, though, that this operator will flip all bits of the integer, and we need to flip only $2^{numVars}$ least significant bits, since the rest of the bits should remain set to 0.\n",
    "To do this, we can do the following steps:\n",
    "\n",
    "1. Construct a bitmask `0b0..01..1`, in which the $2^{numVars}$ least significant bits are set to 1, representing all possible inputs to the function. This mask can be constructed as $2^{2^{numVars}} - 1$.\n",
    "2. Subtract the integer representation of the truth table from this mask. This will have the effect of negating each of the least significant $2^{numVars}$ bits, while leaving the most significant bits set to 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_TTNot \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function TTNot (tt : TruthTable) : TruthTable {\n",
    "    return TruthTable((1 <<< (1 <<< tt::numVars)) - 1 - tt::bits, tt::numVars);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 7 of the Truth Tables kata.](./TruthTables.ipynb#Task-7.-Compute-NOT-of-a-truth-table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 8. Build if-then-else truth table\n",
    "**Goal:** \n",
    "Compute the truth table of the if-then-else function `ttCond ? ttThen | ttElse`\n",
    "(`if ttCond then ttThen else ttElse`) by making use of the truth table operations\n",
    "defined in the previous four tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We can use the following formula to satisfy If/Else conditional function: `((NOT ttCond) AND ttThen) OR (ttCond AND ttElse)`. We've implemented all the building blocks of this formula in the previous tasks, so we can use them here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T08_IfThenElseTruthTable \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function TTIfThenElse (ttCond : TruthTable, ttThen : TruthTable, ttElse : TruthTable) : TruthTable {\n",
    "    return TTXor(TTAnd(ttCond, ttThen), TTAnd(TTNot(ttCond), ttElse));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 8 of the Truth Tables kata.](./TruthTables.ipynb#Task-8.-Build-if-then-else-truth-table)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}