{
 "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",
    "        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",
    "        # NEW CODE #\n",
    "        ############\n",
    "        #\n",
    "        elif self._item == \"<->\":\n",
    "            if left_evaluation == \"undefined\" or right_evaluation == \"undefined\":\n",
    "                return \"undefined\"\n",
    "            else:\n",
    "                return (left_evaluation == right_evaluation)\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": "0024d23d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Truth table of ((p or q) and (not p or not q)) \n",
      "\n",
      "False(p)\tFalse(q)\t<>\t False\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",
      "True 2 times, false 2 times, undefined 0 times\n"
     ]
    }
   ],
   "source": [
    "# Task 4.1b:\n",
    "# Create a Propositional object for the statement\n",
    "# ((p ∨ q) ∧ (¬p ∨ ¬q)) and print its truth table.\n",
    "#\n",
    "p_or_q = Propositional(\"p\").disjunction_with(Propositional(\"q\"))\n",
    "not_p_or_not_q = Propositional(\"p\").negation().disjunction_with(Propositional(\"q\").negation())\n",
    "statement_S = p_or_q.conjunction_with(not_p_or_not_q)\n",
    "\n",
    "print(\"Truth table of\", statement_S.to_string(), \"\\n\")\n",
    "(t, f, u) = statement_S.print_whole_truth_table()\n",
    "print(\"\\nTrue\", t, \"times, false\", f, \"times, undefined\", u, \"times\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9f3eb24a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Truth table of ((p and q) <-> (q and r)) \n",
      "\n",
      "False(p)\tFalse(q)\tFalse(r)\t<>\t True\n",
      "False(p)\tFalse(q)\t True(r)\t<>\t True\n",
      "False(p)\t True(q)\tFalse(r)\t<>\t True\n",
      "False(p)\t True(q)\t True(r)\t<>\t False\n",
      " True(p)\tFalse(q)\tFalse(r)\t<>\t True\n",
      " True(p)\tFalse(q)\t True(r)\t<>\t True\n",
      " True(p)\t True(q)\tFalse(r)\t<>\t False\n",
      " True(p)\t True(q)\t True(r)\t<>\t True\n",
      "\n",
      "True 6 times, false 2 times, undefined 0 times\n"
     ]
    }
   ],
   "source": [
    "# Task 4.1c/d: What is the truth table for the statement (p ∧ q) ↔ (q ∧ r)?\n",
    "#\n",
    "p_and_q = Propositional(\"p\").conjunction_with(Propositional(\"q\"))\n",
    "q_and_r = Propositional(\"q\").conjunction_with(Propositional(\"r\"))\n",
    "statement_R = p_and_q.biconditional_with(q_and_r)\n",
    "\n",
    "print(\"Truth table of\", statement_R.to_string(), \"\\n\")\n",
    "(t, f, u) = statement_R.print_whole_truth_table()\n",
    "print(\"\\nTrue\", t, \"times, false\", f, \"times, undefined\", u, \"times\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2df518c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Truth table of (p or (q and r)) \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 True\n",
      " True(p)\tFalse(q)\tFalse(r)\t<>\t True\n",
      " True(p)\tFalse(q)\t True(r)\t<>\t True\n",
      " True(p)\t True(q)\tFalse(r)\t<>\t True\n",
      " True(p)\t True(q)\t True(r)\t<>\t True\n",
      "\n",
      "True 5 times, false 3 times, undefined 0 times\n"
     ]
    }
   ],
   "source": [
    "# Task 4.1e: Create truth table with top three entries False, bottom five True\n",
    "#\n",
    "statement_T = Propositional(\"p\").disjunction_with(\n",
    "    Propositional(\"q\").conjunction_with(Propositional(\"r\"))\n",
    ")\n",
    "\n",
    "print(\"Truth table of\", statement_T.to_string(), \"\\n\")\n",
    "(t, f, u) = statement_T.print_whole_truth_table()\n",
    "print(\"\\nTrue\", t, \"times, false\", f, \"times, undefined\", u, \"times\")"
   ]
  },
  {
   "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
}