UMBC CMSC 471.02 Spring 2023
Introduction to Artificial Intelligence

Homework Four

out Tuesday April 11, due Friday, April 21

Assignment repository invitation

Here are some simple exercises to help you get comfortable with logic representations. The repository has a Microsoft Word file hw4.docx with the questions and places for your answers. Edit this file to include your answers either in Word or Google Docs.  Save both a hw4.docx and hw4.pdf version of the file with the answers in your repository and commit and push them back to GitHub. All of the required aima python code is included in the starter repository. For many of the questions, we expect you to use the AIMA code to represent the problem and produce an answer. You should copy and paste your input to Python and the answer it gives into hw4.docx. Save your final version as a pdf file, hw4.pdf, and then commit all your changes and push to GitHub.

Notes: The aima logic package requires that propositional variables (i.e., those whose values must be True or False) begin with an uppercase letter and logic variables (i.e., those that can take on any value) begin with a lowercase letter. The Python examples below assume you are using Python 3.X and have done "from logic import *". The aima's logic.py package is well commented, so take a look if you have questions. The answer might be in the comments!

The logic.py module is included in your repository as well as several other modules it imports. However, if you are running this on your own computer you may need to use pip to install some python packages the modules require. Some help in running this on gl or your own computer using PYTHONPATH and a virtual environment is here.

0. Getting Started (0)

We recommend you start by using the jupyter notebook reasoning.ipynb that is in your repository. Doing this on your own computer will require that you have Python installed and also use pip to install jupyter. You can then cd to your hw4 directory, run jupyter notebook, and in your web browser, use Jupyter's file->open command to the notebook. You can also run it on google's colab if you uncomment the commands in the first cell and execute them. We've uploaded the notebook here.

1. Checking Validity (10)

Use the functions in aima's logic.py to see which of the following are valid, i.e., true in every model. You will have to (i) convert these sentences to the appropriate string form that the python code uses (see the comments in the code) and (ii) use the expr() function in logic.py to turn each into an Expr object, and (iii) use the tt_true() function to check for validity. Provide text from a session that shows the result of checking the validity of each. We've done the first one as an example.

1. P ∨ ¬P
   >>> tt_true(expr('P | ~P'))
   True
   
2. (P → Q) ↔ (¬P ∨ Q)
3. P ∧ Q → (Q ∨ P)
4. P ∧ Q → Q
5. ((A ∧ B) → C) ↔ (A → (B → C))
6. ((A → B) → A) → A

2. Satisfiability (14)

Use the functions in logic.py to see which of the following are are satisfiable. An propositional logic expression is satisfiable iff there is a way to assign a value to each of its variables that make the expression True. One way to explore the use of dpll_satisfiable is with the notebook file statisfiability.ipynb in the hw4 code repository.

1. P ∧ Q
   >>> dpll_satisfiable(expr('P & Q'))
   {P: True, Q: True}
   
2. ALIVE ↔ ¬DEAD
3. P → ¬ P ∨ P
4. ¬ (P ∨ ¬ P)
5. P ∧ (P → Q)
6. P ∧ (Q →P)
7. P ∧ (Q ∨ ¬P)
8. P ∧ ¬Q ∧ (P → Q)

3. Propositional Consequence (14)

1. P ∧ Q ⊨ P
   true
   
   
2. P ⊨ P ∨ Q
   
   
3. ¬P ⊨ ¬ ¬ P
   
   
4. P → Q ⊨ ¬ P → ¬ Q
   
   
5. ¬ P ⊨ P → Q
   
   
6. ¬ Q ⊨ P → Q
   
   
7. P ∧ (P → Q) ⊨ Q
   
   
8. ( ¬ P) ∧ (Q → P) ⊨ ¬ Q

4. English to FOL (25)

Translate the following English sentences into first order logic, describing the intended meaning of any non-obvious predicates. Feel free to optionally provide a more direct paraphrase of the meaning of your logic expression in English. If you think a sentence is ambiguous, describe the ambiguity and give logical expressions for all interpretations. We've done the first one for you using a notation with simple ASCII characters for logical operators (e.g., A:∀, E:∃, =>:→, <=>:↔, ^:∧, v:v, ~:¬, >:>)

1. There is no largest prime number.
   
   ~(Ex number(x)^prime(x)^(Ay number(y)^ prime(y) -> y >= x))
   
   paraphrase: It is not true that there is a prime number and it is greater than or equal to all prime numbers.
   predicates: number(x) is true if x is a number and prime(x)is true if x is a prime number.
   
   
2. Good food is not cheap and cheap food is not good.
3. John has exactly two brothers.
4. Every dog is either male or female and no dog can be both male and female.
5. The friend of your enemy is your enemy.
6. An ancestor of your ancestor is your ancestor.

5. Expressing knowledge in CNF (15)

Express each of the following as a set of clauses in conjunctive normal form

a. A ∨ (B  ∧   C)

A ∨ B
A ∨ C

b. A ∨ B ∨ C

c. A ∧ B ∧ C

d. (A ∧ B) ⇔ C

e. A => (B  ⇔  C)

f. A => (( B => C) ∨  ~C)

6. Logic Puzzle (22)

The three ducks Huey, Dewey, and Louie visited their uncle Donald and one of them ate a piece of cake that Donald had been saving for himself. Donald didn't know which one did it, so he decided to ask each one. Donald knows that:

• Only one of his nephews took the cake
• One of the three always tells the truth and the other two always lie

He didn't know which one is the truthful one. So, he asked each one who ate the cake, and they give the following answers.

• Huey: "I ate the cake"
• Dewey: "Huey did not eat the cake"
• Louie: "I did not eat the cake"

Maybe the nephews thought that they could support one another by confusing their uncle Donald, but he able to use logic to determine who took the cake. Explain your reasoning by (a) mapping the problem into propositional logic and (b) showing how the AIMA code can be used to solve this problem.

Hint: These puzzles are hard for people because they are self-referential. Here's a suggestion.

1. Start by trying to figure out the puzzle though a process of elimination
2. Create variables to represent who ate the cake (e.g., P1 might be true if Huey ate it)
3. Create sentences for each of the three statements (e.g., S1 is what Huey says: Huey ate the cake)
4. Create sentences that capture the constraint that only one ate the cake and only one is telling the truth
5. Use the aima dpll_statisfiable function on a conjunction of these local sentences to find a model satisfies them

If you've done things correctly, the sentences will be satisfiable and the model will reveal who ate Donald's cake.

In your answer,

• Show the variables (2) and say what each represents
• Show the sentences (3 and 4) that represent the scenario
• Show what your called dpll_statisfiable with and what it returned
• Name the cake-eater your solution found

What and how to submit

You should edit hw4.docx in your repository either using Microsoft Word or uploading to Google docs and editing, and saving the final versions of both the .docx and .pdf versions. Make sure you include your name and UMBC username. Commit and push these back to your hw4 repository. We will grade the pdf file, so be sure that it has your final answers.