{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "14dbed7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# parse tree for propositional logic statements\n",
    "#\n",
    "class Propositional:\n",
    "    \n",
    "    # create a detached single node of a parse tree\n",
    "    #\n",
    "    def __init__(self, root_item):\n",
    "        self._left = None\n",
    "        self._right = None\n",
    "        \n",
    "        if root_item == \"True\":  # you might pass True but also the string \"True\"\n",
    "            self._item = True\n",
    "        elif root_item == \"False\":  # you might pass False but also the string \"False\"\n",
    "            self._item = False\n",
    "        else:\n",
    "            self._item = root_item\n",
    "\n",
    "\n",
    "    # returns a string representing the statement\n",
    "    #\n",
    "    def to_string(self):\n",
    "        \n",
    "        # note on syntax; there is a \"match\" control flow syntax\n",
    "        # for this, but it only runs from Python 3.10 onward\n",
    "        #\n",
    "        if self._item is None:\n",
    "            return \"undefined\"\n",
    "        elif self._item == \"not\":\n",
    "            return \"not \" + self._right.to_string()\n",
    "        elif self._item == \"or\":\n",
    "            return \"(\" + self._left.to_string() + \" or \" + self._right.to_string() + \")\"\n",
    "        elif self._item == \"and\":\n",
    "            return \"(\" + self._left.to_string() + \" and \" + self._right.to_string() + \")\"\n",
    "        elif self._item == \"->\":\n",
    "            return \"(\" + self._left.to_string() + \" -> \" + self._right.to_string() + \")\"\n",
    "        elif self._item == \"<->\":\n",
    "            return \"(\" + self._left.to_string() + \" <-> \" + self._right.to_string() + \")\"\n",
    "        else:\n",
    "            return self._item  # any other case: self._item is False, True, or an atomic statement\n",
    "    \n",
    "\n",
    "    # returns the number of nodes in the tree\n",
    "    #\n",
    "    def get_size(self):\n",
    "        if self._item is None:  # not a valid node\n",
    "            return 0\n",
    "        size = 1\n",
    "        if self._left is not None:\n",
    "            size += self._left.get_size()\n",
    "        if self._right is not None:\n",
    "            size += self._right.get_size()\n",
    "        return size\n",
    "\n",
    "    \n",
    "    # returns a set of atomic statement names occurring in the tree\n",
    "    #\n",
    "    def get_atomic_statements(self):\n",
    "        if self._item is None:\n",
    "            return set()  # empty set\n",
    "        elif self._item in Propositional.non_leaf_items:\n",
    "            atomic = self._right.get_atomic_statements()\n",
    "            if self._left is not None:\n",
    "                for el in self._left.get_atomic_statements():\n",
    "                    atomic.add(el)\n",
    "            return atomic\n",
    "        elif self._item in {False, True}:\n",
    "            return set()  # empty set\n",
    "        else:\n",
    "            return {self._item}  # in this case self is an atomic statement\n",
    "    \n",
    "    \n",
    "    # removes all content from the tree\n",
    "    #\n",
    "    def clear(self):\n",
    "        if self._left is not None:\n",
    "            self._left.clear()\n",
    "        if self._right is not None:\n",
    "            self._right.clear()\n",
    "        self._left = None\n",
    "        self._item = None\n",
    "        self._right = None\n",
    "\n",
    "    \n",
    "    # returns a new tree representing the statement \"not self\"\n",
    "    #\n",
    "    def negation(self):\n",
    "        new_formula = Propositional(\"not\")\n",
    "        new_formula._right = self\n",
    "        return new_formula\n",
    "    \n",
    "    # returns a new tree representing the statement \"self or other\"\n",
    "    #\n",
    "    def disjunction_with(self, other):\n",
    "        new_formula = Propositional(\"or\")\n",
    "        new_formula._left = self\n",
    "        new_formula._right = other\n",
    "        return new_formula\n",
    "    \n",
    "    # returns a new tree representing the statement \"self and other\"\n",
    "    #\n",
    "    def conjunction_with(self, other):\n",
    "        new_formula = Propositional(\"and\")\n",
    "        new_formula._left = self\n",
    "        new_formula._right = other\n",
    "        return new_formula\n",
    "    \n",
    "    # returns a new tree representing the statement \"self -> other\"\n",
    "    #\n",
    "    def conditional_with(self, other):\n",
    "        new_formula = Propositional(\"->\")\n",
    "        new_formula._left = self\n",
    "        new_formula._right = other\n",
    "        return new_formula\n",
    "    \n",
    "    # returns a new tree representing the statement \"self <-> other\"\n",
    "    #\n",
    "    def biconditional_with(self, other):\n",
    "        new_formula = Propositional(\"<->\")\n",
    "        new_formula._left = self\n",
    "        new_formula._right = other\n",
    "        print(\"\\tWarning: <-> not implemented.\", end=\"\\t\")\n",
    "        return new_formula\n",
    "    \n",
    "    \n",
    "    # returns the truth value for any given valuation\n",
    "    #\n",
    "    # the valuation is a dictionary, where keys are the atomic statements and values are False/True\n",
    "    #\n",
    "    def evaluate(self, valuation):\n",
    "\n",
    "        left_evaluation = \"undefined\"\n",
    "        if self._left is not None:\n",
    "            left_evaluation = self._left.evaluate(valuation)\n",
    "        right_evaluation = \"undefined\"\n",
    "        if self._right is not None:\n",
    "            right_evaluation = self._right.evaluate(valuation)\n",
    "        \n",
    "        # note on syntax; there is a \"match\" control flow syntax\n",
    "        # for this, but it only runs from Python 3.10 onward\n",
    "        #\n",
    "        if self._item is None:\n",
    "            return \"undefined\"\n",
    "        elif self._item in {False, True}:\n",
    "            return self._item\n",
    "        elif self._item == \"not\":\n",
    "            if right_evaluation == \"undefined\":\n",
    "                return \"undefined\"\n",
    "            return (not right_evaluation)\n",
    "        elif self._item == \"or\":\n",
    "            if left_evaluation == \"undefined\" or right_evaluation == \"undefined\":\n",
    "                return \"undefined\"\n",
    "            return (left_evaluation or right_evaluation)\n",
    "        elif self._item == \"and\":\n",
    "            if left_evaluation == \"undefined\" or right_evaluation == \"undefined\":\n",
    "                return \"undefined\"\n",
    "            return (left_evaluation and right_evaluation)\n",
    "        elif self._item == \"->\":\n",
    "            if left_evaluation == \"undefined\" or right_evaluation == \"undefined\":\n",
    "                return \"undefined\"\n",
    "            if not left_evaluation:\n",
    "                return True\n",
    "            else:\n",
    "                return right_evaluation\n",
    "        \n",
    "        ######################\n",
    "        # CODE MISSING BELOW #\n",
    "        ######################\n",
    "        #\n",
    "        # implement this part as an exercise to get into this data structure\n",
    "        #\n",
    "        # we return \"undefined\" now, which should be True or False if\n",
    "        # the left-hand side and the right-hand side can be evaluated\n",
    "        #\n",
    "        elif self._item == \"<->\":\n",
    "            print(\"\\tWarning: <-> not implemented.\", end=\"\\t\")\n",
    "            return \"undefined\"\n",
    "        \n",
    "        # any other case: self._item is an atomic statement;\n",
    "        # in this case we can look up the truth value from the valuation\n",
    "        #\n",
    "        else:\n",
    "            if self._item in valuation:\n",
    "                return valuation[self._item]\n",
    "            else:\n",
    "                return \"undefined\"\n",
    "    \n",
    "    \n",
    "    # generate and optionally print the truth table,\n",
    "    # for a given set of atomic statements\n",
    "    # (this may include atomics that don't occur in the formula)\n",
    "    #\n",
    "    # a potentially incomplete valuation is passed as the second argument;\n",
    "    # these values are fixed and will not be varied\n",
    "    #\n",
    "    # output_flag controls whether a print(...) output is generated\n",
    "    #\n",
    "    # the complete truth table should be shown\n",
    "    # for self.specific_truth_table(self.get_atomic_statements(), {}, True)\n",
    "    #\n",
    "    # the return value is a triple containing the number of True, False, and \"undefined\"\n",
    "    # entries of the truth table, respectively\n",
    "    #\n",
    "    def specific_truth_table(self, atomic, valuation, output_flag):\n",
    "        \n",
    "        # loop over atomic until we find a variable without a given fixed truth value assignment\n",
    "        #\n",
    "        # then recursively distinguish the two possible cases, False and True\n",
    "        #\n",
    "        for variable in sorted(atomic):  # sorted is only used here to make the table look ordered\n",
    "            if variable not in valuation:\n",
    "                extended_valuation = valuation.copy()\n",
    "                \n",
    "                extended_valuation[variable] = False\n",
    "                (true0, false0, und0) = \\\n",
    "                self.specific_truth_table(atomic, extended_valuation, output_flag)\n",
    "                \n",
    "                extended_valuation[variable] = True\n",
    "                (true1, false1, und1) = \\\n",
    "                self.specific_truth_table(atomic, extended_valuation, output_flag)\n",
    "                \n",
    "                return (true0 + true1, false0 + false1, und0 + und1)  # add up True, False, undefined entries\n",
    "\n",
    "        # if all the atomic statements were included in the valuation,\n",
    "        # print out a single line of the truth table\n",
    "        #\n",
    "        boolean_value = self.evaluate(valuation)\n",
    "        if output_flag:\n",
    "            for variable in sorted(atomic):  # sorted is only used here to make the table look ordered\n",
    "                if valuation[variable]:         # this blank space before \"True\" is just so that\n",
    "                    print(\" \", sep=\"\", end=\"\")  #  alignment in the table does not get messed up\n",
    "                print(valuation[variable], \"(\", variable, \")\", sep=\"\", end=\"\\t\")\n",
    "            print(\"<>\\t\", boolean_value)\n",
    "        if boolean_value == \"undefined\":\n",
    "            return (0, 0, 1)  # undefined\n",
    "        elif boolean_value:\n",
    "            return (1, 0, 0)  # True\n",
    "        else:\n",
    "            return (0, 1, 0)  # False\n",
    "        \n",
    "    def print_whole_truth_table(self):\n",
    "        return self.specific_truth_table(self.get_atomic_statements(), {}, True)\n",
    "    \n",
    "    # returns the number of False entries in the truth table\n",
    "    #\n",
    "    def num_false_in_truth_table(self):\n",
    "        (t, f, u) = self.specific_truth_table(self.get_atomic_statements(), {}, False)\n",
    "        return f\n",
    "\n",
    "\n",
    "    # items that signify that a node is not a leaf (similar but not identical to above)\n",
    "    #\n",
    "    non_leaf_items = {\"and\", \"not\", \"or\", \"->\", \"<->\"}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "2df518c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S: (((p -> not q) and (q -> not r)) and (r -> not s))\n"
     ]
    }
   ],
   "source": [
    "# let's look at a statement S, given by \"(p -> not-q) and (q -> not-r) and (r -> not-s)\" \n",
    "\n",
    "p_implies_not_q = Propositional(\"p\").conditional_with(Propositional(\"q\").negation())\n",
    "q_implies_not_r = Propositional(\"q\").conditional_with(Propositional(\"r\").negation())\n",
    "r_implies_not_s = Propositional(\"r\").conditional_with(Propositional(\"s\").negation())\n",
    "\n",
    "statement_S = p_implies_not_q.conjunction_with(q_implies_not_r).conjunction_with(r_implies_not_s)\n",
    "\n",
    "print(\"S:\", statement_S.to_string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4cdc3fbf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Truth table of (p -> not q) \n",
      "\n",
      "False(p)\tFalse(q)\t<>\t True\n",
      "False(p)\t True(q)\t<>\t True\n",
      " True(p)\tFalse(q)\t<>\t True\n",
      " True(p)\t True(q)\t<>\t False\n",
      "\n",
      "Number of False entries: 1\n",
      "\n",
      "Truth table of S: (((p -> not q) and (q -> not r)) and (r -> not s)) \n",
      "\n",
      "False(p)\tFalse(q)\tFalse(r)\tFalse(s)\t<>\t True\n",
      "False(p)\tFalse(q)\tFalse(r)\t True(s)\t<>\t True\n",
      "False(p)\tFalse(q)\t True(r)\tFalse(s)\t<>\t True\n",
      "False(p)\tFalse(q)\t True(r)\t True(s)\t<>\t False\n",
      "False(p)\t True(q)\tFalse(r)\tFalse(s)\t<>\t True\n",
      "False(p)\t True(q)\tFalse(r)\t True(s)\t<>\t True\n",
      "False(p)\t True(q)\t True(r)\tFalse(s)\t<>\t False\n",
      "False(p)\t True(q)\t True(r)\t True(s)\t<>\t False\n",
      " True(p)\tFalse(q)\tFalse(r)\tFalse(s)\t<>\t True\n",
      " True(p)\tFalse(q)\tFalse(r)\t True(s)\t<>\t True\n",
      " True(p)\tFalse(q)\t True(r)\tFalse(s)\t<>\t True\n",
      " True(p)\tFalse(q)\t True(r)\t True(s)\t<>\t False\n",
      " True(p)\t True(q)\tFalse(r)\tFalse(s)\t<>\t False\n",
      " True(p)\t True(q)\tFalse(r)\t True(s)\t<>\t False\n",
      " True(p)\t True(q)\t True(r)\tFalse(s)\t<>\t False\n",
      " True(p)\t True(q)\t True(r)\t True(s)\t<>\t False\n",
      "\n",
      "Number of False entries:  8\n"
     ]
    }
   ],
   "source": [
    "print(\"Truth table of\", p_implies_not_q.to_string(), \"\\n\")\n",
    "(t, f, u) = p_implies_not_q.print_whole_truth_table()\n",
    "print(\"\\nNumber of False entries:\", p_implies_not_q.num_false_in_truth_table())\n",
    "\n",
    "print(\"\\nTruth table of S:\", statement_S.to_string(), \"\\n\")\n",
    "\n",
    "(t, f, u) = statement_S.print_whole_truth_table()\n",
    "print(\"\\nNumber of False entries: \", f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9c7969ce",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Truth table of (p and q) \n",
      "\n",
      "False(p)\tFalse(q)\t<>\t False\n",
      "False(p)\t True(q)\t<>\t False\n",
      " True(p)\tFalse(q)\t<>\t False\n",
      " True(p)\t True(q)\t<>\t True\n",
      "\n",
      "Number of False entries:  3\n",
      "\tWarning: <-> not implemented.\t\n",
      "\n",
      "Truth table of R: ((p and q) <-> (q and r)) \n",
      "\n",
      "\tWarning: <-> not implemented.\tFalse(p)\tFalse(q)\tFalse(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\tFalse(p)\tFalse(q)\t True(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\tFalse(p)\t True(q)\tFalse(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\tFalse(p)\t True(q)\t True(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\t True(p)\tFalse(q)\tFalse(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\t True(p)\tFalse(q)\t True(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\t True(p)\t True(q)\tFalse(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\t True(p)\t True(q)\t True(r)\t<>\t undefined\n",
      "\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\tWarning: <-> not implemented.\t\n",
      "Number of False entries: 0\n"
     ]
    }
   ],
   "source": [
    "# now the same for the statement R, given by (p and q) <-> (q and r)\n",
    "#\n",
    "p_and_q = Propositional(\"p\").conjunction_with(Propositional(\"q\"))\n",
    "q_and_r = Propositional(\"q\").conjunction_with(Propositional(\"r\"))\n",
    "print(\"Truth table of\", p_and_q.to_string(), \"\\n\")\n",
    "(t, f, u) = p_and_q.print_whole_truth_table()\n",
    "print(\"\\nNumber of False entries: \", f)\n",
    "\n",
    "statement_R = p_and_q.biconditional_with(q_and_r)\n",
    "\n",
    "print(\"\\n\\nTruth table of R:\", statement_R.to_string(), \"\\n\")\n",
    "\n",
    "(t, f, u) = statement_R.print_whole_truth_table()\n",
    "print(\"\\nNumber of False entries:\", statement_R.num_false_in_truth_table())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4da85d00",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Truth table of False with some additional variables\n",
      "\n",
      "False(p)\tFalse(q)\tFalse(r)\t<>\t False\n",
      "False(p)\tFalse(q)\t True(r)\t<>\t False\n",
      "False(p)\t True(q)\tFalse(r)\t<>\t False\n",
      "False(p)\t True(q)\t True(r)\t<>\t False\n",
      " True(p)\tFalse(q)\tFalse(r)\t<>\t False\n",
      " True(p)\tFalse(q)\t True(r)\t<>\t False\n",
      " True(p)\t True(q)\tFalse(r)\t<>\t False\n",
      " True(p)\t True(q)\t True(r)\t<>\t False\n",
      "\n",
      "Number of False entries:  8\n"
     ]
    }
   ],
   "source": [
    "# as another example, let us create a \"False\" statement\n",
    "# (which should not contain any atomic statements like p, q, ...)\n",
    "#\n",
    "# and still output a table with p, q, and r\n",
    "#\n",
    "false_statement = Propositional(False)\n",
    "print(\"\\nTruth table of\", false_statement.to_string(), \"with some additional variables\\n\")\n",
    "(t, f, u) = false_statement.specific_truth_table({\"p\", \"q\", \"r\"}, {}, True)\n",
    "print(\"\\nNumber of False entries: \", f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "2289d888",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(p and not p)\n",
      "\n",
      "False(p)\t<>\t False\n",
      " True(p)\t<>\t False\n",
      "\n",
      "Number of False entries: 2\n"
     ]
    }
   ],
   "source": [
    "not_p = Propositional(\"p\").negation()\n",
    "p_and_not_p = Propositional(\"p\").conjunction_with(not_p)\n",
    "\n",
    "print(p_and_not_p.to_string(), end=\"\\n\\n\")\n",
    "(t, f, u) = p_and_not_p.print_whole_truth_table()\n",
    "print(\"\\nNumber of False entries:\", p_and_not_p.num_false_in_truth_table())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9149aeac",
   "metadata": {},
   "outputs": [],
   "source": [
    "# below, a helper function that might be useful for implementing\n",
    "# an algorithm that creates a Propositional object with n entries\n",
    "# in the truth table that are False\n",
    "\n",
    "# you are not required to use this - ignore it if you don't think it would help\n",
    "\n",
    "# argument: a natural number n\n",
    "# return value: a list representing that same number by a sequence of binary digits\n",
    "#\n",
    "def natural_number_to_binary_list(n):\n",
    "    if n == 0:\n",
    "        return []\n",
    "    digits, final_digit = natural_number_to_binary_list(n//2), n%2\n",
    "    digits.append(final_digit)\n",
    "    return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "912a97e0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "print(natural_number_to_binary_list(47))  # the binary number version of 47 is 101111"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b05a7565",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}