CSCI 379 homework 3: logic

There’s not as much code for this assignment and a much longer writeup.

Follow the usual file conventions; include your responses here in hw3-write-up.txt.

Label the sections and organize your text so it’s easy for us to read and see which problem you are answering. Your written responses must use proper, college-level English style and clearly, effectively, and convincingly communicate your understanding. In particular, you must use complete sentences and correct grammar; you’re not commenting code, where brief sentence fragments are acceptable. This is part of the requirements for this and similar assignments, and your marks will reflect that.

If you’re using plain text, you may want to copy and paste the various logical symbols to use them in your response.

If you want to do proper math typesetting and use LaTeX or Typst, go ahead. I recommend Typst, which is a much newer system whose syntax is far more sane and easy to use, though TeX and friends are still incredibly dominant across the quantitative sciences.

Write a propositional logic sentence evaluator¶

Given a sentence in propositional logic and a model, what’s the truth value of that sentence in the model?

Writeup¶

Validity, satisfiability, and contradiction¶

For the following logical statements, show if it is valid, satisfiable (but not valid), or a contradiction by producing the truth table.

1. \((A \Rightarrow B) \land (\lnot A \Rightarrow \lnot B)\)

2. \(((A \Rightarrow B) \land (B \Rightarrow C)) \Rightarrow (\lnot C \Rightarrow \lnot A)\)

3. \((A \Leftrightarrow B) \lor (A \land B)\)

4. \(\lnot(A \lor \lnot(A \land B))\)

You can do this problem by hand – that is, by actually thinking – or by being lazy and using the code you wrote. Build a Sentence object for one of the above, then iterate over all values for A, B, and C and just print to get the truth table.

(Recall that laziness is one of the three virtues of a programmer.)

If you do write code, say so in your writeup and include it at the bottom of hw3.py.

Entailment¶

For the following entailments, show if the entailment is correct or incorrect. You may use truth tables and inference rules as justification. Please describe why your justifications proves correctness or incorrectness.

You can do this like the above – by hand or with code.

1. \((A \lor B) \models A\)

2. \(A_i \models (A_0 \lor A_1 \lor \dots \lor A_i \lor \dots \lor A_n)\)

3. \((A \land B) \lor (A \land C) \models A\)

4. \(((A_0 \land A_1 \land \dots \land A_n) \Rightarrow (B_0 \land B_1 \land \dots \land B_n)) \models (\lnot (B_0 \land B_1 \land \dots \land B_n) \Rightarrow \lnot (A_0 \land A_1 \land \dots \land A_n))\)

5. \((A \Rightarrow B) \models A\)

Conjunctive normal form¶

In class, you were told that theorem provers leverage conjunctive normal form (CNF). To do this, they convert formulas not in CNF to CNF. Every statement in propositional logic can be written in CNF. To demonstrate this, convert the following non-CNF clauses to CNF using logical equivalences. That is, the formula should only consist of Variables, Negations, and Disjunctions (or operators). State which equivalence rules you used. Please see the cheat sheet on Moodle for examples of logical equivalence.

1. \((A \land B)\)

2. \(((A \land B) \Rightarrow C)\)

3. \((A \Leftrightarrow B)\)

Wumpus World¶

The following questions are about Hunt the Wumpus, using the game world shown below. You may assume your agent has knowledge of any information written in a square. In this problem, you will use theorem proving to the location of the gold.

(In your response, if you want to go all-in on the silly emoji, as I did here, you can use 🟡 for glitter detected or gold present, and if you like 🪤 for the start or visited cells. Or, have fun and use your own system – just be clear and provide a legend.)

(I’ll add, though, that being boring and just using, uh, words is also a very good choice.)

1. Describe a propositional logic rule that states the gold must be in one of the squares in the cave. You may assume the board will always be a 4x4 grid and you may reference squares using the coordinates above. You may assume this is in all knowledge bases for Hunt the Wumpus.

2. Describe a propositional logic that states if a pit is in a room then the gold is not in that room. Craft a rule that states if the Wumpus is in a room then the gold is not in that room. You may assume this is in all knowledge bases for Hunt the Wumpus.

3. Given the board above, show \(G_{3,4}\). Use the board to craft a knowledge base. Use inference rules to add to the knowledge base. Provide the full knowledge base at the end. Show your work as a series of steps.