\documentclass{article}
\usepackage{fleqn}
\usepackage{epsf}
\usepackage[dvips]{color}
\usepackage{aima2e-slides}
\begin{document}
\begin{huge}
\titleslide{First-order logic}{Chapter 8}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Why FOL?
\blob Syntax and semantics of FOL
\blob Fun with sentences
\blob Wumpus world in FOL
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Pros and cons of propositional logic}
\smiley\ Propositional logic is \emph{declarative}: pieces of syntax correspond to facts
\smiley\ Propositional logic allows partial/disjunctive/negated information\al
(unlike most data structures and databases)
\smiley\ Propositional logic is \emph{compositional}: \al
meaning of \mat{$B_{1,1}\land P_{1,2}$} is derived from meaning of \mat{$B_{1,1}$} and of \mat{$P_{1,2}$}
\smiley\ Meaning in propositional logic is \emph{context-independent}\al
(unlike natural language, where meaning depends on context)
\frowny\ Propositional logic has very limited expressive power\al
(unlike natural language)\al
E.g., cannot say ``pits cause breezes in adjacent squares''\nl
except by writing one sentence for each square
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{First-order logic}
Whereas propositional logic assumes world contains \emph{facts},\\
first-order logic (like natural language) assumes the world contains
\begin{itemize}
\item \defn{Objects}: people, houses, numbers, theories,
Ronald McDonald, colors, baseball games, wars, centuries $\ldots$
\item \defn{Relations}: red, round, bogus, prime, multistoried $\ldots$, \\
brother of, bigger than, inside, part of, has color, occurred after, owns, comes between, $\ldots$
\item \defn{Functions}: father of, best friend, third inning of, one more
than, end of $\ldots$
\end{itemize}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Logics in general}
\input{tables/ontological-epistemological-table}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Syntax of FOL: Basic elements}
\begin{tabular}{ll}
Constants & \mat{$KingJohn,\ 2,\ UCB,\ldots$} \\
Predicates & \mat{$Brother,\ >,\ldots$} \\
Functions & \mat{$Sqrt,\ LeftLegOf,\ldots$} \\
Variables & \mat{$x,\ y,\ a,\ b,\ldots$} \\
Connectives & \mat{$\land\ \lor\ \lnot\ \implies\ \lequiv$} \\
Equality & \mat{$=$} \\
Quantifiers & \mat{$\forall\ \exists$} \\
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Atomic sentences}
\begin{tabular}{rcl}
Atomic sentence & = & \mat{$predicate(term_1,\ldots,term_n)$} \\
& & or \mat{$term_1 = term_2$} \\
& & \\
Term & = & \mat{$function(term_1,\ldots,term_n)$} \\
& & or \mat{$constant$} or \mat{$variable$} \\
\end{tabular}
\begin{tabular}{ll}
E.g., & \mat{$Brother(KingJohn,RichardTheLionheart)$}\\
& \mat{$>(Length(LeftLegOf(Richard)),Length(LeftLegOf(KingJohn)))$}\\
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Complex sentences}
Complex sentences are made from atomic sentences using connectives
\mat{\[
\lnot S,\quad S_1\land S_2,\quad S_1 \lor S_2,\quad
S_1 \implies S_2,\quad S_1 \lequiv S_2
\]}
\begin{tabular}{ll}
E.g. & \mat{$Sibling(KingJohn,Richard) \implies Sibling(Richard,KingJohn)$} \\
& \mat{${>}(1,2) \lor {\leq}(1,2)$} \\
& \mat{${>}(1,2) \land \lnot {>}(1,2)$} \\
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Truth in first-order logic}
Sentences are true with respect to a \defn{model} and an \defn{interpretation}
Model contains $\geq 1$ objects (\defn{domain elements}) and relations among them
Interpretation specifies referents for\al
\mat{constant symbols} $\rightarrow$ \note{objects}\al
\mat{predicate symbols} $\rightarrow$ \note{relations}\al
\mat{function symbols} $\rightarrow$ \note{functional relations}
An atomic sentence \mat{$predicate(term_1,\ldots,term_n)$} is true\\
iff the \note{objects} referred to by \mat{$term_1,\ldots,term_n$}\\
are in the \note{relation} referred to by \mat{$predicate$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Models for FOL: Example}
\vspace*{0.3in}
\epsfxsize=0.85\textwidth
\fig{\file{figures}{fol-model.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Truth example}
Consider the interpretation in which\\
\mat{$Richard$} $\rightarrow$ \note{Richard the Lionheart}\\
\mat{$John$} $\rightarrow$ \note{the evil King John}\\
\mat{$Brother$} $\rightarrow$ \note{the brotherhood relation}
Under this interpretation, \mat{$Brother(Richard,John)$} is true\\
just in case \note{Richard the Lionheart} and \note{the evil King John}\\
are in \note{the brotherhood relation} in the model
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Models for FOL: Lots!}
Entailment in propositional logic can be computed by enumerating models
We \emph{can} enumerate the FOL models for a given KB vocabulary:
For each number of domain elements \mat{$n$} from \mat{$1$} to \mat{$\infty$}\\
\tab For each \mat{$k$}-ary predicate \mat{$P_k$} in the vocabulary\\
\tab\tab For each possible \mat{$k$}-ary relation on \mat{$n$} objects\\
\tab\tab\tab For each constant symbol \mat{$C$} in the vocabulary\\
\tab\tab\tab\tab For each choice of referent for \mat{$C$} from \mat{$n$} objects $\ldots$
Computing entailment by enumerating FOL models is not easy!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Universal quantification}
\mat{$\All{\} \$}
Everyone at Berkeley is smart:\\
\mat{$\All{x} At(x,Berkeley) \implies Smart(x)$}
\mat{$\All{x} P$}\quad is true in a model \mat{$m$} iff \mat{$P$} is true with \mat{$x$} being\\
\emph{each} possible object in the model
\emph{Roughly} speaking, equivalent to the \note{conjunction} of \note{instantiations} of \mat{$P$}
\mat{\[
\begin{array}{rl}
& (At(KingJohn,Berkeley) \implies Smart(KingJohn)) \\
\land& (At(Richard,Berkeley) \implies Smart(Richard)) \\
\land& (At(Berkeley,Berkeley) \implies Smart(Berkeley)) \\
\land& \ldots
\end{array}\]}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{A common mistake to avoid}
Typically, \mat{$\implies$} is the main connective with \mat{$\forall$}
Common mistake: using \mat{$\land$} as the main connective with \mat{$\forall$}:
\mat{\[\All{x} At(x,Berkeley) \land Smart(x)\]}
means ``Everyone is at Berkeley and everyone is smart''
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Existential quantification}
\mat{$\Exi{\} \$}
Someone at Stanford is smart:\\
\mat{$\Exi{x} At(x,Stanford) \land Smart(x)$}
\mat{$\Exi{x} P$}\quad is true in a model \mat{$m$} iff \mat{$P$} is true with \mat{$x$} being\\
\emph{some} possible object in the model
\emph{Roughly} speaking, equivalent to the \note{disjunction} of \note{instantiations} of \mat{$P$}
\mat{\[
\begin{array}{rl}
& (At(KingJohn,Stanford) \land Smart(KingJohn)) \\
\lor& (At(Richard,Stanford) \land Smart(Richard)) \\
\lor& (At(Stanford,Stanford) \land Smart(Stanford)) \\
\lor& \ldots
\end{array}\]}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Another common mistake to avoid}
Typically, \mat{$\land$} is the main connective with \mat{$\exists$}
Common mistake: using \mat{$\implies$} as the main connective with \mat{$\exists$}:
\mat{\[\Exi{x} At(x,Stanford) \implies Smart(x)\]}
is true if there is anyone who is not at Stanford!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of quantifiers}
\mat{$\All{x}\All{y}$} is the same as \mat{$\All{y}\All{x}$} (\q{why})
\mat{$\Exi{x}\Exi{y}$} is the same as \mat{$\Exi{y}\Exi{x}$} (\q{why})
\mat{$\Exi{x}\All{y}$} is \emph{not} the same as \mat{$\All{y}\Exi{x}$}
\mat{$\Exi{x}\All{y} Loves(x,y)$}\\
``There is a person who loves everyone in the world''
\mat{$\All{y}\Exi{x} Loves(x,y)$}\\
``Everyone in the world is loved by at least one person''
\note{Quantifier duality}: each can be expressed using the other
\mat{$\All{x} Likes(x,IceCream)$} \qquad \mat{$\lnot \Exi{x} \lnot Likes(x,IceCream)$}
\mat{$\Exi{x} Likes(x,Broccoli)$} \qquad \mat{$\lnot \All{x} \lnot Likes(x,Broccoli)$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Fun with sentences}
Brothers are siblings
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Fun with sentences}
Brothers are siblings
\mat{$\All{x,y} Brother(x,y) \implies Sibling(x,y)$}.
``Sibling'' is symmetric
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Fun with sentences}
Brothers are siblings
\mat{$\All{x,y} Brother(x,y) \implies Sibling(x,y)$}.
``Sibling'' is symmetric
\mat{$\All{x,y} Sibling(x,y) \lequiv Sibling(y,x)$}.
One's mother is one's female parent
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Fun with sentences}
Brothers are siblings
\mat{$\All{x,y} Brother(x,y) \implies Sibling(x,y)$}.
``Sibling'' is symmetric
\mat{$\All{x,y} Sibling(x,y) \lequiv Sibling(y,x)$}.
One's mother is one's female parent
\mat{$\All{x,y} Mother(x,y) \lequiv (Female(x) \land Parent(x,y))$}.
A first cousin is a child of a parent's sibling
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Fun with sentences}
Brothers are siblings
\mat{$\All{x,y} Brother(x,y) \implies Sibling(x,y)$}.
``Sibling'' is symmetric
\mat{$\All{x,y} Sibling(x,y) \lequiv Sibling(y,x)$}.
One's mother is one's female parent
\mat{$\All{x,y} Mother(x,y) \lequiv (Female(x) \land Parent(x,y))$}.
A first cousin is a child of a parent's sibling
\mat{$\All{x,y} FirstCousin(x,y) \lequiv
\Exi{p,ps} Parent(p,x) \land Sibling(ps,p) \land Parent(ps,y)$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Equality}
\mat{$term_1 = term_2$} is true under a given interpretation\\
if and only if \mat{$term_1$} and \mat{$term_2$} refer to the same object
\begin{tabular}{ll}
E.g., & \mat{$1=2$} and \mat{$\All{x} {\times}(Sqrt(x),Sqrt(x)) = x$} are satisfiable\\
& \mat{$2=2$} is valid
\end{tabular}
E.g., definition of (full) \mat{$Sibling$} in terms of \mat{$Parent$}:\al
\mat{$\All{x,y} Sibling(x,y) \lequiv [\lnot(x\eq y) \land \Exi{m,f} \lnot(m\eq f) \land {}$}\nl
\mat{$Parent(m,x) \land Parent(f,x) \land Parent(m,y) \land Parent(f,y)]$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Interacting with FOL KBs}
Suppose a wumpus-world agent is using an FOL KB\\
and perceives a smell and a breeze (but no glitter) at \mat{$t=5$}:
\mat{${\sc Tell}(KB,Percept([Smell,Breeze,None],5))$}\\
\mat{${\sc Ask}(KB,\Exi{a} Action(a,5))$}
I.e., does \mat{$KB$} entail any particular actions at \mat{$t=5$}?
Answer: \mat{$Yes,\ \{a/Shoot\}$}\qquad $\leftarrow$ \defn{substitution} (binding list)
Given a sentence \mat{$S$} and a substitution \mat{$\sigma$},\\
\mat{$S\sigma$} denotes the result of plugging \mat{$\sigma$} into \mat{$S$}; e.g.,\\
\mat{$S = Smarter(x,y)$}\\
\mat{$\sigma = \{x/Hillary,y/Bill\}$}\\
\mat{$S\sigma = Smarter(Hillary,Bill)$}
\mat{${\sc Ask(KB,S)}$} returns some/all \mat{$\sigma$} such that \mat{$KB \models S\sigma$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Knowledge base for the wumpus world}
\note{``Perception''}\\
\mat{$\All{b,g,t} Percept([Smell,b,g],t) \implies Smelt(t)$}\\
\mat{$\All{s,b,t} Percept([s,b,Glitter],t) \implies AtGold(t)$}
\note{Reflex}: \mat{$\All{t} AtGold(t) \implies Action(Grab,t)$}
\note{Reflex with internal state}: do we have the gold already?\\
\mat{$\All{t} AtGold(t) \land \lnot Holding(Gold,t) \implies Action(Grab,t)$}
\mat{$Holding(Gold,t)$} cannot be observed\nl
$\Rightarrow$ keeping track of change is essential
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Deducing hidden properties}
Properties of locations:\\
\mat{$\All{x,t} At(Agent,x,t) \land Smelt(t) \implies Smelly(x)$}\\
\mat{$\All{x,t} At(Agent,x,t) \land Breeze(t) \implies Breezy(x)$}
Squares are breezy near a pit:
\defn{Diagnostic} rule---infer cause from effect\nl
\mat{$\All{y} Breezy(y) \implies \Exi{x} Pit(x) \land Adjacent(x,y)$}
\defn{Causal} rule---infer effect from cause\nl
\mat{$\All{x,y} Pit(x) \land Adjacent(x,y) \implies Breezy(y)$}
Neither of these is complete---e.g., the causal rule doesn't say
whether squares far away from pits can be breezy
\defn{Definition} for the \mat{$Breezy$} predicate:\nl
\mat{$\All{y} Breezy(y) \lequiv [\Exi{x} Pit(x) \land Adjacent(x,y)]$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Keeping track of change}
Facts hold in \defn{situations}, rather than eternally\\
E.g., \mat{$Holding(Gold,Now)$} rather than just \mat{$Holding(Gold)$}
\defn{Situation calculus} is one way to represent change in FOL:\nl
Adds a situation argument to each non-eternal predicate\nl
E.g., \mat{$Now$} in \mat{$Holding(Gold,Now)$} denotes a situation
Situations are connected by the \mat{$Result$} function\\
\mat{$Result(a,s)$} is the situation that results from doing \mat{$a$} in \mat{$s$}
\epsfxsize=0.3\textwidth
\fig{\file{figures}{situations2.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Describing actions I}
``Effect'' axiom---describe changes due to action\\
\mat{$\All{s} AtGold(s) \implies Holding(Gold,Result(Grab,s))$}
``Frame'' axiom---describe \emph{non-changes} due to action\\
\mat{$\All{s} HaveArrow(s) \implies HaveArrow(Result(Grab,s))$}
\defn{Frame problem}: find an elegant way to handle non-change\nl
(a) representation---avoid frame axioms\nl
(b) inference---avoid repeated ``copy-overs'' to keep track of state
\defn{Qualification problem}: true descriptions of real actions require endless caveats---what if gold is slippery or nailed down or $\ldots$
\defn{Ramification problem}: real actions have many secondary consequences---what about the dust on the gold, wear and tear on gloves, $\ldots$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Describing actions II}
\defn{Successor-state axioms} solve the representational frame problem
Each axiom is ``about'' a \emph{predicate} (not an action per se):
\mat{\begin{eqnarray*}
\mbox{P true afterwards}&\lequiv& [\mbox{an action made P true}\\
&\lor & \mbox{P true already and no action
made P false}]
\end{eqnarray*}}
For holding the gold:\al
\mat{$\All{a,s} Holding(Gold,Result(a,s)) \lequiv {}$}\nl
\mat{$[(a\eq Grab \land AtGold(s))$}\nl
\mat{${}\lor (Holding(Gold,s) \land a\neq Release)]$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Making plans}
Initial condition in KB:\nl
\mat{$At(Agent,[1,1],S_0)$}\nl
\mat{$At(Gold,[1,2],S_0)$}
Query: \mat{${\sc Ask}(KB,\Exi{s} Holding(Gold,s))$}\nl
i.e., in what situation will I be holding the gold?
Answer: \mat{$\{s/Result(Grab,Result(Forward,S_0))\}$}\nl
i.e., go forward and then grab the gold
This assumes that the agent is interested in plans starting at \mat{$S_0$}
and that \mat{$S_0$} is the only situation described in the KB
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Making plans: A better way}
Represent \note{plans} as action sequences \mat{$[a_1,a_2,\ldots,a_n]$}
\mat{$PlanResult(p,s)$} is the result of executing \mat{$p$} in \mat{$s$}
Then the query \mat{${\sc Ask}(KB,\Exi{p} Holding(Gold,PlanResult(p,S_0)))$}\\
has the solution \mat{$\{p/[Forward,Grab]\}$}
Definition of \mat{$PlanResult$} in terms of \mat{$Result$}:\al
\mat{$\All{s} PlanResult([\,],s) = s$}\al
\mat{$\All{a,p,s} PlanResult([a|p],s) = PlanResult(p,Result(a,s))$}
\defn{Planning systems} are special-purpose reasoners designed to do this
type of inference more efficiently than a general-purpose reasoner
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Summary}
First-order logic: \al
-- objects and relations are semantic primitives\al
-- syntax: constants, functions, predicates, equality, quantifiers
Increased expressive power: sufficient to define wumpus world
Situation calculus:\al
-- conventions for describing actions and change in FOL\al
-- can formulate planning as inference on a situation calculus KB
\end{huge}
\end{document}