In this assignment, you will get some hands-on experience with logic. You'll see how logic can be used to represent the meaning of natural language sentences, and how it can be used to solve puzzles and prove theorems. Most of this assignment will be translating English into logical formulas, but in Problem 4, we will delve into the mechanics of logical inference. Finally, for the ethics question you will revisit the ethical frameworks and concepts you learned about this quarter through once again writing negative impact statements.
NOTE: There is a final mandatory written question after the extra credit problem 5. Do not forget to answer this question! Also for this assignment only, there are no hidden test cases for the programming questions -- if you pass all the visible test cases, then you will get full credit!
We've created a LaTeX template here for you to use that contains the prompts for each question.
To get started, launch a Python shell and try typing the following commands to add logical expressions into the knowledge base.
from logic import * Rain = Atom('Rain') # Shortcut Wet = Atom('Wet') # Shortcut kb = createResolutionKB() # Create the knowledge base kb.ask(Wet) # Prints "I don't know." kb.ask(Not(Wet)) # Prints "I don't know." kb.tell(Implies(Rain, Wet)) # Prints "I learned something." kb.ask(Wet) # Prints "I don't know." kb.tell(Rain) # Prints "I learned something." kb.tell(Wet) # Prints "I already knew that." kb.ask(Wet) # Prints "Yes." kb.ask(Not(Wet)) # Prints "No." kb.tell(Not(Wet)) # Prints "I don't buy that."To print out the contents of the knowledge base, you can call
kb.dump()
. For the example above, you get:
==== Knowledge base [3 derivations] === * Or(Not(Rain),Wet) * Rain - WetIn the output, '*' means the fact was explicitly added by the user, and '-' means that it was inferred. Here is a table that describes how logical formulas are represented in code. Use it as a reference guide:
Name | Mathematical notation | Code |
Constant symbol | $\text{stanford}$ | Constant('stanford') (must be lowercase) |
Variable symbol | $x$ | Variable('$x') (must be lowercase) |
Atomic formula (atom) | $\text{Rain}$ $\text{LocatedIn}(\text{stanford}, x)$ |
Atom('Rain') (predicate must start with uppercase)Atom('LocatedIn', 'stanford', '$x')
(arguments are symbols)
|
Negation | $\neg \text{Rain}$ | Not(Atom('Rain')) |
Conjunction | $\text{Rain} \wedge \text{Snow}$ | And(Atom('Rain'), Atom('Snow')) |
Disjunction | $\text{Rain} \vee \text{Snow}$ | Or(Atom('Rain'), Atom('Snow')) |
Implication | $\text{Rain} \to \text{Wet}$ | Implies(Atom('Rain'), Atom('Wet')) |
Equivalence | $\text{Rain} \leftrightarrow \text{Wet}$ (syntactic sugar for $\text{Rain} \to \text{Wet} \wedge \text{Wet} \to \text{Rain}$) | Equiv(Atom('Rain'), Atom('Wet')) |
Existential quantification | $\exists x . \text{LocatedIn}(\text{stanford}, x)$ | Exists('$x', Atom('LocatedIn', 'stanford', '$x')) |
Universal quantification | $\forall x . \text{MadeOfAtoms}(x)$ | Forall('$x', Atom('MadeOfAtoms', '$x')) |
The operations And
and Or
only take two arguments.
If we want to take a conjunction or disjunction of more than two, use
AndList
and OrList
. For example:
AndList([Atom('A'), Atom('B'), Atom('C')])
is equivalent to
And(And(Atom('A'), Atom('B')), Atom('C'))
.
Write a propositional logic formula for each of the following English
sentences in the given function in submission.py
. For example,
if the sentence is "If it is raining, it is wet," then you would
write Implies(Atom('Rain'), Atom('Wet'))
, which would be
$\text{Rain} \to \text{Wet}$ in symbols (see examples.py
).
Note: Don't forget to return the constructed formula!
python grader.py 1aIf your formula is wrong, then the grader will provide a counterexample, which is a model that your formula and the correct formula don't agree on. For example, if you accidentally wrote
And(Atom('Rain'), Atom('Wet'))
for
"If it is raining, it is wet,", then the grader would output the
following:
Your formula (And(Rain,Wet)) says the following model is FALSE, but it should be TRUE: * Rain = False * Wet = True * (other atoms if any) = False
In this model, it's not raining and it is wet, which satisfies the correct formula $\text{Rain} \to \text{Wet}$ (TRUE), but does not satisfy the incorrect formula $\text{Rain} \wedge \text{Wet}$ (FALSE). Use these counterexamples to guide you in the rest of the assignment.
Write a first-order logic formula for each of the following English
sentences in the given function in submission.py
. For example,
if the sentence is "There is a light that shines," then you would
write
Exists('$x', And(Atom('Light', '$x'), Atom('Shines', '$x')))
,
which would be $\exists x . \text{Light}(x) \wedge \text{Shines}(x)$ in
symbols (see examples.py
).
Tips:
'$x'
instead of Variable('$x')
to represent a variable symbol.
Note: You do NOT have to enforce that the mother is a "person".
Note: You do NOT have to enforce that the child is a "person".
Father(x,y)
in terms of
Male(x)
and Parent(x,y)
.
Granddaughter(x,y)
in terms of
Female(x)
and Child(x,y)
.
Note: It is ok for a person to be their own child.
liar()
to return a list of 6 formulas, one for each
of the above facts.
3a-0
to 3a-5
to debug each formula only if you
implement them in the order specified.
python grader.py 3a-0 python grader.py 3a-1 python grader.py 3a-2 python grader.py 3a-3 python grader.py 3a-4 python grader.py 3a-5 python grader.py 3a-all # Tests the conjunction of all the formulasTo solve the puzzle and find the answer,
tell
the formulas to the
knowledge base and ask
the query
CrashedServer('$x')
, by running:
python grader.py 3a-run
In this problem, we will see how to use logic to automatically prove mathematical theorems. We will focus on encoding the theorem and leave the proving part to the logical inference algorithm. Here is the theorem:
If the following constraints hold:Note: in this problem, "larger than" is just an arbitrary relation, and you should not assume it has any prior meaning. In other words, don't assume things like "a number can't be larger than itself" unless explicitly stated.
ints()
to construct 6 formulas for each of the
constraints. The consequence has been filled out for you (query
in the code).
4a-0
to 4a-5
to debug each formula only if you
implement them in the order specified. You can test your code using
the following commands:
python grader.py 4a-0 python grader.py 4a-1 python grader.py 4a-2 python grader.py 4a-3 python grader.py 4a-4 python grader.py 4a-5 python grader.py 4a-all # Tests the conjunction of all the formulasTo finally prove the theorem,
tell
the formulas to the
knowledge base and ask
the query by running model checking
(on a finite model):
python grader.py 4a-run
Semantic parsing is the task of converting natural lanugage utterances into
first-order logic formulas. We have created a small set of grammar rules in
the code for you in
createBaseEnglishGrammar()
. In this problem, you will add
additional grammar rules to handle a wider variety of sentences.
Specifically, create a GrammarRule
for each of the following
sentence structures.
$Clause ← every $Noun $Verb some $Noun
$Clause ← there is some $Noun that every $Noun $Verb
$Clause ← if a $Noun $Verb a $Noun then the former $Verb the latter
nli.py
! For example:
$ python nli.py > Every person likes some cat. >>>>> I learned something. ------------------------------ > Every cat is a mammal. >>>>> I learned something. ------------------------------ > Every person likes some mammal? >>>>> Yes.
In Homework 1: Foundations, you practiced spotting ethical issues in real-world scenarios. In this question, you will return to a similar task equipped with the ethical frameworks and concepts you have learned and applied during the quarter. Just like on homework 1, you will write a negative impacts statement for the scenarios below that justifies your decision using one of the ethical frameworks / concepts you learned about this quarter. Specifically, you will:
[1] Inspired by https://www.cc.gatech.edu/ai/robot-lab/online-publications/AWS.pdf.
[2] Modified from cervical cancer screening in India.
[3] Modified from optimal forest growth modeling.