UMBC CMSC 471 02 Spring 2021
Introduction to Artificial Intelligence

Homework Four

out Tuesday March 30, due Friday, April 9

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 hy4.docx.

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 funning this on gl or your own computer using PYTHONPATH and a virtual environement is here.

0. Getting Started (0)

We recommend you start by using the jupyter notebooks satisfiability.ipynb and logic.ipynb that are 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 open one of the notebooks. You can also run these on google's colab if you uncomment the commands in the first cell and execute them.

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 (6)

Use the functions in logic.py to see which of the following are are satisfiable. We've done the first one as an example. 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)

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 person is either male or female and no person 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 (20)

Your friend says that a cat is considered to be aggressive (A) if hisses (H) when you pet it (P) and if it does not hiss, it is not aggressive.

a. (10) Which of the following are correct representations of this assertion?

5.a.1 (H ^ A) ⇔ P

5.a.2 H => (A ⇔ P)

5.a.3 H => (( P => A) ∨ ~A)

b. (10) Express each of the above as a set of clauses in conjunctive normal form

5.b.1 (H ^ A) ⇔ P

5.b.2 H => (A ⇔ P)

5.b.3 H => (( P => A) ∨ ~A)

6. Logic Puzzle (25)

There are three robots: WALL-E, R2D2 and 3CPO. You want some help writing software and think that one of them can do it. You know that

• One and only one of them knows Python
• One of the three robots always tells the truth and the other two always lie

but you don't know which one knows Python and which one is the truthful one. So, you ask each one which of the three knows Python, and they give the following answers.

• WALL-E: "I know Python"
• R2D2: "I do not know Python"
• C3PO: "WALL-E does not know Python"

What the bots don't know is that you are a smart person rather than a robot and can use logic to reveal who is lying and who is telling the truth and discover which one of them knows Python. 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.

• Start by trying to figure out the puzzle though a process of elimination
• Create variables to represent who knows python (e.g. P1 might be true if WALL-E knows Python)
• Create sentences for each of the three statements (e.g., S1 is what WALL-E says: WALL-E knows Python)
• Create sentences that capture the constrains that only one knows Python and only one is telling the truth
• Use dpll_statisfiable on a conjunction of these local sentences to see what model satisfies them

If you've done things correctly, the sentences will be satisfiable and the model will reveal who know Python.

What and how to submit

You should start with hw4.docx to create this file, 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.