There’s no code to write for this assignment, but the usual guidelines apply, and for the sake of consistency, you’ll submit your response using CSgit.
Follow the usual file conventions; include your responses in
hw4-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. In addition, this is a writing assignment and your 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 here to use them in your response. See List of logic symbols - Wikipedia if you’d like more.
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. For LaTeX, one simple way to get started is with the Overleaf online editor.
For the following entailments, state if the entailment is true and explain why. Assume all \(p_i\) is from the set of people (\(P\)).
\(∃ p_1, ∀ p_j : likes(p_1, p_j) ⊨ ∀ p_i, ∃ p_2 : likes (p_i, p_2)\)
\(∃ p_1 : is\_nice(p_1) ∨ is\_mean(p_1) ⊨ (∃ p_1 : is\_nice(p_1)) ∨ (∃ p_2 : is\_mean(p_2))\)
\((∃ p_1 : is\_nice(p_1)) ∧ (∃ p_2 : is\_old(p_2)) ⊨ ∃ p_1 : is\_nice(p_1) ∧ is\_old(p_1)\)
\(∀ p: likes(p, Doug) ∧ likes(Doug, p) ⇒ friends(Doug, p) ⊨ ∃ p : friends(Doug, p)\)
\(∀ p: f(p) ∧ g(p) ⇒ h(p), ¬ h(Doug) ⊨ ¬ f(Doug) ∨ ¬ g(Doug)\)
You may have noticed a similarity between conjunction and universal quantification, and between disjunction and existential quantification – “and” is similar to “for all”, and “or” is like “there exists”.
De Morgan’s laws describe how conjunction and disjunction distribute
over each other, but they apply not just to and’s and
or’s, it is also useful with the existential and universal
quantifiers.
For the following examples, state what the left side of the \(≡\) is saying in English. Then state what the right side is saying in English. Then argue why these are equivalent.
\(∀ p ∈ P : knows(p, Doug) ≡ ¬ (∃ p ∈ P: ¬ knows(p, Doug))\)
\(∃ p ∈ P: likes(Doug, p) ≡ ¬ (∀ p ∈ P: ¬ likes(Doug, p))\)
For the following questions, given the starting knowledge base, show that goal statement is true by adding to the knowledge base using things the agent perceives and the rules of inference.
Explain your reasoning. For each inference you make, say which rule you are using.
These questions use the following relations.
is-a
and has-a terminology in OOP.
The agent is starting in square \((1, 1)\). They perceive no smell and no breeze. Show safe([1, 2]).
| Name | Sentence / axiom |
|---|---|
| R1 | ∀ \(s\) ∈ S : ¬has-a(\(s\), pit) ∧ ¬has-a(s, W) ⇒ safe(s) |
| R2 | ∀ \(s_i\), \(s_j\) ∈ S : ¬breeze(\(s_i\)) ∧ adjacent(\(s_i\), \(s_j\)) ⇒ ¬has-a(\(s_j\), pit) |
| R3 | ∀ \(s_i\), \(s_j\) ∈ S : ¬stench(\(s_i\)) ∧ adjacent(\(s_i\), \(s_j\)) ⇒ ¬has-a(\(s_j\), W) |
The agent is starting in square \([1, 1]\). There is no pit. They move to \([2, 1]\) and feel a breeze. Show has-a([3,1], pit) ∨ has-a([2, 2], pit).
| Name | Sentence / axiom |
|---|---|
| R1 | ∀ s_i ∈ S, ∃ s_j ∈ S : breeze(\(s_i\)) ⇒ adjacent(\(s_i\), \(s_j\)) ∧ has-a(\(s_j\), pit) |
| R2 | \(f(s) ∧ (s = x ∨ s = y) ≡ f(x) ∨ f(y)\) |
| R3 | adjacent([2,1], \(s\)) ⇔ (\(s\) = [1,1] ∨ \(s\) = [2,2] ∨ \(s\) = [3,1]) |