Propositional Logic

Needs to follow instructions in PDF and starter code, uses automated grading so it is very strict (only gives full credit or zero points if minor error)

Get Help With a similar task to - Propositional Logic

Login to view and/or buy answers.. or post an answer
Additional Instructions:

PropLog.pdf CMPSC 442: Homework 4 [100 points] Release Date Wednesday, October 10, 2020, 12:00 am Due Date Monday, October 26, 2020, 11:59 pm TO PREPARE AND SUBMIT HOMEWORK Follow these steps exactly, so the Gradescope autgrader can grade your homework. Failure to do so will result in a zero grade: 1. You *must* download the homework template file homework4_cmpsc442.py from Canvas. Each template file is a python file that gives you a headstart in creating your homework python script with the correct function names for autograding. 2. You *must* rename the file by replacing cmpsc442 with your PSU id from your official PSU. For example, if your PSU email id is abcd1234, you would rename your file as homework4_abcd1234.py to submit to Canvas, and to Gradescope. 3. Upload your *py file to Canvas by the due date, and to Gradescope by its due date. The Gradescope due date is five minutes later, but it is your responsibility to upload on time. If the submission on Canvas or Gradescope closes before you upload, your homework will be counted late, and you might get a zero grade. 4. Make sure your file can import before you submit; the autograder imports your file. If it won't import, you will get a zero. Instructions In this assignment, you will implement a collection of basic algorithms for working with logical expressions, then will apply them to solve textual puzzles expressible using propositional logic. You will find that in addition to a problem specification, most programming questions also include a pair of examples from the Python interpreter. These are meant to illustrate typical use cases, and should not be taken as comprehensive test suites. You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was written in part by the creator of Python. However, your code will not be graded for style. 1. Propositional Logic [65 points] In this section, you will implement a collection of classes corresponding to logical expressions, a simple knowledge base, and algorithms for propositional logic inference via truth table enumeration and resolution. All expressions will be subclasses of the provided base Expr class. The fragment of logic we will be working with can be defined recursively as follows: Atom: Atom(name) is an expression. Negation: If $e$ is an expression, then Not($e$) is an expression. Conjunction: If $e_1,e_2,\ldots,e_n$ are expressions, then And($e_1,e_2,\ldots,e_n$) is an expression. http://legacy.python.org/dev/peps/pep-0008/ Disjunction: If $e_1,e_2,\ldots,e_n$ are expressions, then Or($e_1,e_2,\ldots,e_n$) is an expression. Implication: If $e_1$ and $e_2$ are expressions, then Implies($e_1$, $e_2$) is an expression. Biconditional: If $e_1$ and $e_2$ are expressions, then Iff($e_1$, $e_2$) is an expression. You will find that a generic hash function has been defined for the Expr class, and that the initialization methods for each of its subclasses have been provided. These should not be altered. Combined with the methods for equality checking to be implemented below, this will ensure that expressions behave as expected when used as elements of sets. 1. [3 points] First read through and understand the provided __init__ methods for the Atom, Not, And, Or, Implies, and Iff expression subclasses, keeping in mind that expressions will be considered immutable for our purposes. In particular, review the *args syntax (link) and frozenset class (link) if needed. The former allows for convenient n-ary conjunctions and disjunctions, and the latter is used to ensure immutability. We use sets rather than lists for conjunctions and disjunctions to guarantee that, e.g., all 24 permutations of the conjuncts in the expression $A \land B \land C \land D$ will be equivalent. Moreover, you may find that certain set functions such as union and set difference will prove useful later on. As a first exercise, implement the __eq__(self, other) methods in each subclass, which will be called when expressions are compared using the == operator. You should check for syntactic equality only, in the sense that two expressions should be considered equal only if they are of the same class and have the same internal structure. No simplification should be performed. As a special case, Iff(a, b) should be equal to Iff(b, a). Hint: Each of these can be implemented in a single line. >>> Atom("a") == Atom("a") True >>> Atom("a") == Atom("b") False >>> And(Atom("a"), Not(Atom("b"))) == \ ... And(Not(Atom("b")), Atom("a")) True 2. [2 points] Implement the __repr__(self) method in each expression subclass, which should return a string representation of the given expression. Any reasonable choice will suffice for this exercise, as this is primarily intended for debugging purposes. >>> a, b, c = map(Atom, "abc") >>> Implies(a, Iff(b, c)) Implies(Atom(a), Iff(Atom(b), Atom(c))) >>> a, b, c = map(Atom, "abc") >>> And(a, Or(Not(b), c)) And(Atom(a), Or(Not(Atom(b)), Atom(c))) 3. [5 points] Implement the atom_names(self) method in each expression subclass, which should return the set of names that occur in atoms contained within the given expression. >>> Atom("a").atom_names() set(['a']) >>> a, b, c = map(Atom, "abc") >>> expr = And(a, Implies(b, Iff(a, c))) https://docs.python.org/2/tutorial/controlflow.html#arbitrary-argument-lists https://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset >>> Not(Atom("a")).atom_names() set(['a']) >>> expr.atom_names() set(['a', 'c', 'b']) 4. [5 points] Implement the evaluate(self, assignment) method in each expression subclass, which should return the truth value of the given formula under the provided assignment from atom names to Boolean values. You may assume that the assignment dictionary contains the necessary entries to fully evaluate the expression. >>> e = Implies(Atom("a"), Atom("b")) >>> e.evaluate({"a": False, "b": True}) True >>> e.evaluate({"a": True, "b": False}) False >>> a, b, c = map(Atom, "abc") >>> e = And(Not(a), Or(b, c)) >>> e.evaluate({"a": False, "b": False, ... "c": True} True 5. [10 points] Write a satisfying_assignments(expr) function that generates all assignments from atom names to truth values under which the input expression is true. The assignments may be generated in any order, as long as all satisfying assignments are produced. >>> e = Implies(Atom("a"), Atom("b")) >>> a = satisfying_assignments(e) >>> next(a) {'a': False, 'b': False} >>> next(a) {'a': False, 'b': True} >>> next(a) {'a': True, 'b': True} >>> e = Iff(Iff(Atom("a"), Atom("b")), ... Atom("c")) >>> list(satisfying_assignments(e)) [{'a': False, 'c': False, 'b': True}, {'a': False, 'c': True, 'b': False}, {'a': True, 'c': False, 'b': False}, {'a': True, 'c': True, 'b': True}] 6. [20 points] Implement the to_cnf(self) method in each expression subclass, which should return an expression in conjunctive normal form that is logically equivalent to the input. Specifically, the output of this method should be a literal (i.e. an atom or a negated atom), a disjunction of literals, or a conjunction consisting of literals and/or disjunctions of literals. >>> Atom("a").to_cnf() Atom(a) >>> a, b, c = map(Atom, "abc") >>> Iff(a, Or(b, c)).to_cnf() And(Or(Atom(b), Atom(c), Not(Atom(a))), Or(Not(Atom(b)), Atom(a)), Or(Not(Atom(c)), Atom(a))) >>> Or(Atom("a"), Atom("b")).to_cnf() Or(Atom(b), Atom(a)) >>> a, b, c, d = map(Atom, "abcd") >>> Or(And(a, b), And(c, d)).to_cnf() And(Or(Atom(d), Atom(a)), Or(Atom(a), Atom(c)), Or(Atom(b), Atom(c)), Or(Atom(b), Atom(d))) 7. [20 points] In this question, we will consider a knowledge base to be an object which stores a collection of facts and supports entailment queries based on those facts. First write the __init__(self) and get_facts(self) methods in the KnowledgeBase class, which initialize and return an internal fact set, respectively. Next write the tell(self, expr) method, which converts the input expression to conjunctive normal form and adds the resulting conjuncts to the internal fact set. Lastly write the ask(self, expr) method, which returns a Boolean value indicating whether the facts in the knowledge base entail the input expression. You should determine entailment using the resolution algorithm discussed in class. >>> a, b, c = map(Atom, "abc") >>> kb = KnowledgeBase() >>> kb.tell(a) >>> kb.tell(Implies(a, b)) >>> kb.get_facts() set([Or(Atom(b), Not(Atom(a))), Atom(a)]) >>> [kb.ask(x) for x in (a, b, c)] [True, True, False] >>> a, b, c = map(Atom, "abc") >>> kb = KnowledgeBase() >>> kb.tell(Iff(a, Or(b, c))) >>> kb.tell(Not(a)) >>> [kb.ask(x) for x in (a, Not(a))] [False, True] >>> [kb.ask(x) for x in (b, Not(b))] [False, True] >>> [kb.ask(x) for x in (c, Not(c))] [False, True] 2. Logic Puzzles [30 points] In this section, you will encode some simple logic puzzles in propositional logic and use the functions written in the previous section to solve them. You will be graded both on the correctness of your results and on the correctness of your formulations. 1. [5 points] Consider the following set of facts. If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned. From these, can it be inferred that the unicorn is mythical? That it is magical? That it is horned? Using the atomic expressions Atom("mythical"), Atom("mortal"), Atom("mammal"), Atom("horned"), and Atom("magical"), populate the indicated knowledge base with the appropriate facts, and assign the appropriate queries to the indicated variables. Then, use these to answer the above questions, and record your answers in the corresponding variables. 2. [5 points] You would like to throw a party subject to the following conditions: John will come if Mary or Ann come, Ann will come if Mary does not come, and if Ann comes, then John will not come. Letting the atomic expressions Atom("a"), Atom("j"), and Atom("m") denote that Ann, John, and Mary come, respectively, encode the given conditions as a single conjunction, and use the previously-defined satisfying_assignments(expr) function to compute all valid scenarios. In what way(s) can the guests attend without violating the constraints? 3. [10 points] A game show contestant is to choose between two rooms, each of which may either contain a prize or be empty. The sign on the first door states: "This room contains a prize, and the other room is empty." The sign on the second door states: "At least one room contains a prize, and at least one room is empty." The contestant is told that exactly one sign is true. Let the atomic expression Atom("p1") denote that the first room contains a prize, and let the atomic expression Atom("e1") denote that the first room is empty. Similarly define Atom("p2") and Atom("e2") for the second room. Also let the atomic expressions Atom("s1") and Atom("s2") denote that the first sign and second sign are true, respectively. Using these, populate the indicated knowledge base with the appropriate facts. Then make the necessary queries to determine what the contestant can deduce about the contents of each room and the truth of the signs. What is the correct state of affairs? 4. [10 points] There are three suspects for a murder: Adams, Brown, and Clark. Adams says “I didn’t do it. The victim was old acquaintance of Brown’s. But Clark never knew him.” Brown states “I didn’t do it. I didn’t know the guy.” Clark says “I didn’t do it. I saw both Adams and Brown downtown with the victim that day; one of them must have done it.” Assume that the two innocent men are telling the truth, but that the guilty man is not. Let the atomic expressions Atom("ia"), Atom("ib"), and Atom("ic") denote that Adams, Brown, and Clark are innocent, respectively, and let Atom("ka"), Atom("kb"), and Atom("kc") denote that Adams, Brown, and Clark knew with the victim. Populate the indicated knowledge base with the given information, and query it as necessary to determine which suspect is guilty. Record your answer and the corresponding query in the provided variables. 3. Feedback [5 points] 1. [1 point] Approximately how long did you spend on this assignment? 2. [2 points] Which aspects of this assignment did you find most challenging? Were there any significant stumbling blocks? 3. [2 points] Which aspects of this assignment did you like? Is there anything you would have changed? starter.py ############################################################ # CMPSC 442: Homework 4 ############################################################ student_name = "Type your full name here." ############################################################ # Imports ############################################################ # Include your imports here, if any are used. ############################################################ # Section 1: Propositional Logic ############################################################ class Expr(object): def __hash__(self): return hash((type(self).__name__, self.hashable)) class Atom(Expr): def __init__(self, name): self.name = name self.hashable = name def __eq__(self, other): pass def __repr__(self): pass def atom_names(self): pass def evaluate(self, assignment): pass def to_cnf(self): pass class Not(Expr): def __init__(self, arg): self.arg = arg self.hashable = arg def __eq__(self, other): pass def __repr__(self): pass def atom_names(self): pass def evaluate(self, assignment): pass def to_cnf(self): pass class And(Expr): def __init__(self, *conjuncts): self.conjuncts = frozenset(conjuncts) self.hashable = self.conjuncts def __eq__(self, other): pass def __repr__(self): pass def atom_names(self): pass def evaluate(self, assignment): pass def to_cnf(self): pass class Or(Expr): def __init__(self, *disjuncts): self.disjuncts = frozenset(disjuncts) self.hashable = self.disjuncts def __eq__(self, other): pass def __repr__(self): pass def atom_names(self): pass def evaluate(self, assignment): pass def to_cnf(self): pass class Implies(Expr): def __init__(self, left, right): self.left = left self.right = right self.hashable = (left, right) def __eq__(self, other): pass def __repr__(self): pass def atom_names(self): pass def evaluate(self, assignment): pass def to_cnf(self): pass class Iff(Expr): def __init__(self, left, right): self.left = left self.right = right self.hashable = (left, right) def __eq__(self, other): pass def __repr__(self): pass def atom_names(self): pass def evaluate(self, assignment): pass def to_cnf(self): pass def satisfying_assignments(expr): pass class KnowledgeBase(object): def __init__(self): pass def get_facts(self): pass def tell(self, expr): pass def ask(self, expr): pass ############################################################ # Section 2: Logic Puzzles ############################################################ # Puzzle 1 # Populate the knowledge base using statements of the form kb1.tell(...) kb1 = KnowledgeBase() # Write an Expr for each query that should be asked of the knowledge base mythical_query = None magical_query = None horned_query = None # Record your answers as True or False; if you wish to use the above queries, # they should not be run when this file is loaded is_mythical = None is_magical = None is_horned = None # Puzzle 2 # Write an Expr of the form And(...) encoding the constraints party_constraints = None # Compute a list of the valid attendance scenarios using a call to # satisfying_assignments(expr) valid_scenarios = None # Write your answer to the question in the assignment puzzle_2_question = """ Type your response here. Your response may span multiple lines. Do not include these instructions in your response. """ # Puzzle 3 # Populate the knowledge base using statements of the form kb3.tell(...) kb3 = KnowledgeBase() # Write your answer to the question in the assignment; the queries you make # should not be run when this file is loaded puzzle_3_question = """ Type your response here. Your response may span multiple lines. Do not include these instructions in your response. """ # Puzzle 4 # Populate the knowledge base using statements of the form kb4.tell(...) kb4 = KnowledgeBase() # Uncomment the line corresponding to the guilty suspect # guilty_suspect = "Adams" # guilty_suspect = "Brown" # guilty_suspect = "Clark" # Describe the queries you made to ascertain your findings puzzle_4_question = """ Type your response here. Your response may span multiple lines. Do not include these instructions in your response. """ ############################################################ # Section 3: Feedback ############################################################ feedback_question_1 = """ Type your response here. Your response may span multiple lines. Do not include these instructions in your response. """ feedback_question_2 = """ Type your response here. Your response may span multiple lines. Do not include these instructions in your response. """ feedback_question_3 = """ Type your response here. Your response may span multiple lines. Do not include these instructions in your response. """

Related Questions

Similar orders to Propositional Logic
6
Views
0
Answers
Creating a DNS server (written in C)
WANT >=50% due to being swamped (only standard option minimal, don't care about cache or non-blocking). I require periodic updates of code with a description as there is a Git commit tracking. Also require a makefile according to the specifications and a g...
20
Views
0
Answers
Create inheritance project for a restaurant
Projects must include: -at least three different levels of inheritance - at least nine classes total -the highest superclass must have at least two methods -every subclass must contain a unique method that was not present in its super...
16
Views
0
Answers
Python Code for Suggesting Pets
Must have ___init___ ; ___str___ ; for loops ; while loops ; and must define a function which returns something, I wrote down what idea I had in that form so its best to follow it, this is an entry-level computer science project so it should be pretty easy...
23
Views
0
Answers
Quick HW Computer Science on LL(1) and object creation
Due at 12:00pm today. The question details are in the files attached. One question is on the impact of a parser being LL(1) or not. Another is on imagining a mistake in object creation. The answers are probably max 2 lines long....