{ "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", " 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": "b05a7565", "metadata": {}, "outputs": [], "source": [ "# helper function\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": 3, "id": "75b45ee6", "metadata": {}, "outputs": [], "source": [ "# work out the propositional logic statement part\n", "# corresponding to the sublist digits[i:m]\n", "#\n", "def binary_list_to_statement(digits, i):\n", " m = len(digits)\n", " \n", " # look for the next \"1\" digit and proceed from there\n", " #\n", " for j in range(i, m):\n", " if digits[j] == 1:\n", " \n", " # construct disjunctive clause p_i or ... or p_j\n", " #\n", " stat = Propositional(\"p\" + str(i))\n", " for k in range(i+1, j+1):\n", " stat = stat.disjunction_with(Propositional(\"p\" + str(k)))\n", " \n", " # does the statement continue further, or have we reached the end?\n", " #\n", " if j+1 < m:\n", " \n", " # remainder of the statement, constructed recursively\n", " #\n", " tail = binary_list_to_statement(digits, j+1)\n", " \n", " # two-way branching off in the decision tree\n", " #\n", " if i == j:\n", " \n", " # (p_i or ... or p_j) and tail\n", " #\n", " stat = stat.conjunction_with(tail)\n", " \n", " # three-way branching off in the decision tree\n", " #\n", " else:\n", " # construct conjunctive clause p_i and ... and p_j\n", " #\n", " clause = Propositional(\"p\" + str(i))\n", " for k in range(i+1, j+1):\n", " clause = clause.conjunction_with(Propositional(\"p\" + str(k)))\n", " \n", " # (p_i and ... and p_j) -> tail\n", " #\n", " clause = clause.conditional_with(tail)\n", " \n", " # (p_i or ... or p_j) and ((p_i and ... and p_j) -> tail)\n", " #\n", " stat = stat.conjunction_with(clause)\n", " \n", " return stat\n", " \n", " # case that there were only \"0\" digits terminally\n", " #\n", " # add tautological clauses, just to use the remaining atomic statements\n", " # somehow, in order to bring the truth table to the appropriate size\n", " #\n", " stat = Propositional(\"p\" + str(i)).conditional_with(Propositional(\"p\" + str(i)))\n", " for j in range(i+1, m):\n", " tauto_clause = Propositional(\"p\" + str(j)).conditional_with(Propositional(\"p\" + str(j)))\n", " stat = stat.conjunction_with(tauto_clause)\n", " return stat\n", "\n", "\n", "# function that constructs and returns a propositional logic statement\n", "# with n False entries in its truth table\n", "#\n", "def n_false_statement(n):\n", " digits = natural_number_to_binary_list(n)\n", " return binary_list_to_statement(digits, 0)" ] }, { "cell_type": "code", "execution_count": 4, "id": "2cf7e690", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\t0\t(p0 -> p0)\n", "1\t1\tp0\n", "2\t2\t(p0 and (p1 -> p1))\n", "3\t3\t(p0 and p1)\n", "4\t4\t(p0 and ((p1 -> p1) and (p2 -> p2)))\n", "5\t5\t(p0 and (p1 or p2))\n", "6\t6\t(p0 and (p1 and (p2 -> p2)))\n", "7\t7\t(p0 and (p1 and p2))\n", "8\t8\t(p0 and (((p1 -> p1) and (p2 -> p2)) and (p3 -> p3)))\n", "9\t9\t(p0 and ((p1 or p2) or p3))\n", "10\t10\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 -> p3))))\n", "11\t11\t(p0 and ((p1 or p2) and ((p1 and p2) -> p3)))\n", "12\t12\t(p0 and (p1 and ((p2 -> p2) and (p3 -> p3))))\n", "13\t13\t(p0 and (p1 and (p2 or p3)))\n", "14\t14\t(p0 and (p1 and (p2 and (p3 -> p3))))\n", "15\t15\t(p0 and (p1 and (p2 and p3)))\n", "16\t16\t(p0 and ((((p1 -> p1) and (p2 -> p2)) and (p3 -> p3)) and (p4 -> p4)))\n", "17\t17\t(p0 and (((p1 or p2) or p3) or p4))\n", "18\t18\t(p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> (p4 -> p4))))\n", "19\t19\t(p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> p4)))\n", "20\t20\t(p0 and ((p1 or p2) and ((p1 and p2) -> ((p3 -> p3) and (p4 -> p4)))))\n", "21\t21\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 or p4))))\n", "22\t22\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 and (p4 -> p4)))))\n", "23\t23\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 and p4))))\n", "24\t24\t(p0 and (p1 and (((p2 -> p2) and (p3 -> p3)) and (p4 -> p4))))\n", "25\t25\t(p0 and (p1 and ((p2 or p3) or p4)))\n", "26\t26\t(p0 and (p1 and ((p2 or p3) and ((p2 and p3) -> (p4 -> p4)))))\n", "27\t27\t(p0 and (p1 and ((p2 or p3) and ((p2 and p3) -> p4))))\n", "28\t28\t(p0 and (p1 and (p2 and ((p3 -> p3) and (p4 -> p4)))))\n", "29\t29\t(p0 and (p1 and (p2 and (p3 or p4))))\n", "30\t30\t(p0 and (p1 and (p2 and (p3 and (p4 -> p4)))))\n", "31\t31\t(p0 and (p1 and (p2 and (p3 and p4))))\n", "32\t32\t(p0 and (((((p1 -> p1) and (p2 -> p2)) and (p3 -> p3)) and (p4 -> p4)) and (p5 -> p5)))\n", "33\t33\t(p0 and ((((p1 or p2) or p3) or p4) or p5))\n", "34\t34\t(p0 and ((((p1 or p2) or p3) or p4) and ((((p1 and p2) and p3) and p4) -> (p5 -> p5))))\n", "35\t35\t(p0 and ((((p1 or p2) or p3) or p4) and ((((p1 and p2) and p3) and p4) -> p5)))\n", "36\t36\t(p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> ((p4 -> p4) and (p5 -> p5)))))\n", "37\t37\t(p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> (p4 or p5))))\n", "38\t38\t(p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> (p4 and (p5 -> p5)))))\n", "39\t39\t(p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> (p4 and p5))))\n", "40\t40\t(p0 and ((p1 or p2) and ((p1 and p2) -> (((p3 -> p3) and (p4 -> p4)) and (p5 -> p5)))))\n", "41\t41\t(p0 and ((p1 or p2) and ((p1 and p2) -> ((p3 or p4) or p5))))\n", "42\t42\t(p0 and ((p1 or p2) and ((p1 and p2) -> ((p3 or p4) and ((p3 and p4) -> (p5 -> p5))))))\n", "43\t43\t(p0 and ((p1 or p2) and ((p1 and p2) -> ((p3 or p4) and ((p3 and p4) -> p5)))))\n", "44\t44\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 and ((p4 -> p4) and (p5 -> p5))))))\n", "45\t45\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 and (p4 or p5)))))\n", "46\t46\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 and (p4 and (p5 -> p5))))))\n", "47\t47\t(p0 and ((p1 or p2) and ((p1 and p2) -> (p3 and (p4 and p5)))))\n", "48\t48\t(p0 and (p1 and ((((p2 -> p2) and (p3 -> p3)) and (p4 -> p4)) and (p5 -> p5))))\n", "49\t49\t(p0 and (p1 and (((p2 or p3) or p4) or p5)))\n" ] } ], "source": [ "# print out the first 50 statements generated by the function\n", "#\n", "for n in range(50):\n", " statement = n_false_statement(n)\n", " print(n, statement.num_false_in_truth_table(), statement.to_string(), sep=\"\\t\")" ] }, { "cell_type": "code", "execution_count": 5, "id": "b776d135", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 13 = [1, 1, 0, 1]\n", "\n", "===\n", "Truth table of (p0 and (p1 and (p2 or p3))) \n", "\n", "False(p0)\tFalse(p1)\tFalse(p2)\tFalse(p3)\t<>\t False\n", "False(p0)\tFalse(p1)\tFalse(p2)\t True(p3)\t<>\t False\n", "False(p0)\tFalse(p1)\t True(p2)\tFalse(p3)\t<>\t False\n", "False(p0)\tFalse(p1)\t True(p2)\t True(p3)\t<>\t False\n", "False(p0)\t True(p1)\tFalse(p2)\tFalse(p3)\t<>\t False\n", "False(p0)\t True(p1)\tFalse(p2)\t True(p3)\t<>\t False\n", "False(p0)\t True(p1)\t True(p2)\tFalse(p3)\t<>\t False\n", "False(p0)\t True(p1)\t True(p2)\t True(p3)\t<>\t False\n", " True(p0)\tFalse(p1)\tFalse(p2)\tFalse(p3)\t<>\t False\n", " True(p0)\tFalse(p1)\tFalse(p2)\t True(p3)\t<>\t False\n", " True(p0)\tFalse(p1)\t True(p2)\tFalse(p3)\t<>\t False\n", " True(p0)\tFalse(p1)\t True(p2)\t True(p3)\t<>\t False\n", " True(p0)\t True(p1)\tFalse(p2)\tFalse(p3)\t<>\t False\n", " True(p0)\t True(p1)\tFalse(p2)\t True(p3)\t<>\t True\n", " True(p0)\t True(p1)\t True(p2)\tFalse(p3)\t<>\t True\n", " True(p0)\t True(p1)\t True(p2)\t True(p3)\t<>\t True\n", "\n", "True 3 times, false 13 times, undefined 0 times\n" ] } ], "source": [ "import random\n", "\n", "# random n < 50\n", "#\n", "n = random.randrange(50)\n", "print(\"n =\", n, \"=\", natural_number_to_binary_list(n))\n", "\n", "statement = n_false_statement(n)\n", "\n", "print(\"\\n===\\nTruth table of\", statement.to_string(), \"\\n\")\n", "(t, f, u) = statement.print_whole_truth_table()\n", "print(\"\\nTrue\", t, \"times, false\", f, \"times, undefined\", u, \"times\")" ] }, { "cell_type": "code", "execution_count": 6, "id": "f97cc12b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 81313 = [1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1]\n", "\n", "===\n", "Statement: (p0 and (((p1 or p2) or p3) and (((p1 and p2) and p3) -> (p4 and (p5 and (p6 and ((p7 or p8) and ((p7 and p8) -> (p9 and ((p10 or p11) and ((p10 and p11) -> ((((p12 or p13) or p14) or p15) or p16))))))))))))\n", "\n", "False 81313 times\n" ] } ], "source": [ "import random\n", "\n", "# random n < 100000\n", "#\n", "n = random.randrange(100000)\n", "print(\"n =\", n, \"=\", natural_number_to_binary_list(n))\n", "\n", "statement = n_false_statement(n)\n", "\n", "print(\"\\n===\\nStatement:\", statement.to_string())\n", "f = statement.num_false_in_truth_table()\n", "print(\"\\nFalse\", f, \"times\")" ] }, { "cell_type": "code", "execution_count": null, "id": "1ed87818", "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 }