TruthTables/TruthTables.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Truth Tables Kata\n",
    "\n",
    "This kata provides an introduction into representing Boolean functions in terms of integers, in which each bit represents a truth value for some input assignment.\n",
    "\n",
    "* Boolean function manipulation based on integers is discussed in the book Hacker's Delight by Henry S. Warren.\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tutorial teaches you how to represent Boolean functions as\n",
    "integers.  We use the bits in the binary integer representation\n",
    "as truth values in the truth table of the Boolean function.\n",
    "\n",
    "Formally, a Boolean function is a function $f(x) : \\{0,1\\}^n \\rightarrow \\{0,1\\}$\n",
    "that takes an $n$-bit input, called input assignment, and produces\n",
    "a 1-bit output, called function value or truth value.\n",
    "\n",
    "We can think of an $n$-variable Boolean function as an integer with at\n",
    "least $2^n$ binary digits.  Each digit represents the truth value for\n",
    "each of the $2^n$ input assignments. The least significant bit represents \n",
    "the assignment 00...00, the next one - 00...01, and so on, and \n",
    "the most significant bit represents 11...11.\n",
    "\n",
    "In Q# we can use the `0b` prefix to specify integers in binary notation,\n",
    "which is useful when describing the truth table of a Boolean function.\n",
    "For example, the truth table of the 2-input function ($x_1 \\wedge x_2$) can be\n",
    "represented by the integer `0b1000 = 8`.\n",
    "\n",
    "Here is how you would get this representation: \n",
    "\n",
    "<table style=\"border:1px solid\">\n",
    "  <col width=50>\n",
    "  <col width=50>\n",
    "  <col width=100>\n",
    "  <col width=150>\n",
    "  <tr>\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\">$f(x_1, x_2)$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Bit of 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\">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\">1</td>\n",
    "    <td style=\"text-align:center; border:1px solid\">0</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",
    "  </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\">Most significant</td>\n",
    "  </tr>    \n",
    "</table>\n",
    "\n",
    "Since the number of bits in a Q# integer is always the same, we need to\n",
    "specify the number of variables explicitly.  Therefore, it makes sense\n",
    "to introduce a user defined type for truth tables. \n",
    "Here is its definition:\n",
    "\n",
    "    newtype TruthTable = (bits : Int, numVars : Int);"
   ]
  },
  {
   "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",
    "<details>\n",
    "    <summary><b>Hint #1</b></summary>\n",
    "    Here is a sample truth table for function $x_1$:\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=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\">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\">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",
    "  </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\"></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\"></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",
    "  </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",
    "  </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\"></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\">Most Significant</td>\n",
    "  </tr>\n",
    "</table>\n",
    "</details>\n",
    "<br/>\n",
    "\n",
    "<details>\n",
    "    <summary><b>Hint #2</b></summary>\n",
    "    Using the above truth table as an example, find out the assignments where $x_2 = 1$ and $x_3 = 1$.\n",
    "</details>\n",
    "<br/>\n",
    "\n",
    "<details>\n",
    "    <summary><b>Hint #3</b></summary>\n",
    "    Here is a complete truth table for these projective functions:\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",
    "</details>"
   ]
  },
  {
   "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(0, 0);           // Update the value of x2 ...\n",
    "    let x3 = TruthTable(0, 0);           // Update the value of x3 ...\n",
    "\n",
    "    return (x1, x2, x3);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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.\n",
    "\n",
    "<br/>\n",
    "\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click Here</b></summary>\n",
    "    Here is the truth table for the function $f(x_3,x_2,x_1)$:\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=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\">$f(x_1,x_2,x_3)$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Bit of 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\">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",
    "  </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\">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\">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\"></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\">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\"></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\"></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\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Most Significant</td>\n",
    "  </tr>\n",
    "</table>\n",
    "</details>"
   ]
  },
  {
   "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(0, 3);            // Update the value of f ...\n",
    "    return f;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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",
    "<br/>\n",
    "\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click Here</b></summary>\n",
    "    Here is the truth table for the function $f(x_3,x_2,x_1)$:\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=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\">$f(x_1,x_2,x_3)$</th>\n",
    "    <th style=\"text-align:center; border:1px solid\">Bit of 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\">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\"></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\"></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\"></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",
    "  </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",
    "  </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\">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\"></td>\n",
    "    <td style=\"text-align:center; border:1px solid\">Most Significant</td>\n",
    "  </tr>\n",
    "</table>\n",
    "</details>"
   ]
  },
  {
   "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(0, 3);            // Update the value of f ...\n",
    "    return f;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "You can use bit-wise operations in Q# for this task.  See\n",
    "<a href=\"https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/bitwiseexpressions\">Q# Bitwise Expressions</a>.\n",
    "</details>"
   ]
  },
  {
   "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "Be careful not to set bits in the integer that are out-of-range\n",
    "in the truth table.\n",
    "</details>\n"
   ]
  },
  {
   "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Truth Tables Workbook](./Workbook_TruthTables.ipynb#Task-8.-Build-if-then-else-truth-table).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 9. Find all true input assignments in a truth table\n",
    "**Goal:** \n",
    "Return an array that contains all input assignments in a truth table\n",
    "that have a true truth value.  These input assignments are called minterms.\n",
    "The order of assignments in the return does not matter.\n",
    "\n",
    "> You could make use of Q# library functions to implement this operation in a\n",
    "single return statement without implementing any helper operations. Useful\n",
    "Q# library functions to complete this task are `Mapped`, `Filtered`, `Compose`,\n",
    "`Enumerated`, `IntAsBoolArray`, `EqualB`, `Fst`, and `Snd`.\n",
    "\n",
    "> **Example:**\n",
    "The truth table of 2-input OR is `0b1110`, i.e., its minterms are `[1, 2, 3]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T09_AllMinterms \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "function AllMinterms (tt : TruthTable) : Int[] {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 10. Apply truth table as a quantum operation\n",
    "**Goal:** \n",
    "Apply the X operation on the target qubit, if and only if\n",
    "the classical state of the controls is a minterm of the truth table."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T10_ApplyFunction \n",
    "\n",
    "open Quantum.Kata.TruthTables;\n",
    "\n",
    "operation ApplyXControlledOnFunction (tt : TruthTable, controls : Qubit[], target : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  }
 ],
 "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
}