\documentstyle[fleqn,epsf,aima-slides]{article}
\begin{document}
\begin{huge}
\titleslide{First-order logic}{Chapter 7}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Syntax and semantics of FOL
\blob Fun with sentences
\blob Wumpus world in FOL
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Syntax of FOL: Basic elements}
\begin{tabular}{ll}
Constants & $KingJohn,\ 2,\ UCB,\ldots$ \\
Predicates & $Brother,\ >,\ldots$ \\
Functions & $Sqrt,\ LeftLegOf,\ldots$ \\
Variables & $x,\ y,\ a,\ b,\ldots$ \\
Connectives & $\land\ \lor\ \lnot\ \implies\ \lequiv$ \\
Equality & $=$ \\
Quantifiers & $\forall\ \exists$ \\
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Atomic sentences}
\begin{tabular}{rcl}
Atomic sentence & = & $predicate(term_1,\ldots,term_n)$ \\
& & or $term_1 = term_2$ \\
& & \\
Term & = & $function(term_1,\ldots,term_n)$ \\
& & or $constant$ or $variable$ \\
\end{tabular}
\begin{tabular}{ll}
E.g., & $Brother(KingJohn,RichardTheLionheart)$\\
& $>(Length(LeftLegOf(Richard)),Length(LeftLegOf(KingJohn)))$\\
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Complex sentences}
Complex sentences are made from atomic sentences using connectives
\[
\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. & $Sibling(KingJohn,Richard) \implies Sibling(Richard,KingJohn)$ \\
& ${>}(1,2) \lor {\leq}(1,2)$ \\
& ${>}(1,2) \land \lnot {>}(1,2)$ \\
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Truth in first-order logic}
Sentences are true with respect to a \u{model} and an \u{interpretation}
Model contains objects and relations among them
Interpretation specifies referents for\al
{\em constant symbols} $\rightarrow$ \u{objects}\al
{\em predicate symbols} $\rightarrow$ \u{relations}\al
{\em function symbols} $\rightarrow$ \u{functional relations}
An atomic sentence $predicate(term_1,\ldots,term_n)$ is true\\
iff the \u{objects} referred to by $term_1,\ldots,term_n$\\
are in the \u{relation} referred to by $predicate$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Models for FOL: Example}
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\file{figures}{fol-models.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Universal quantification}
$\All{\} \$
Everyone at Berkeley is smart:\\
$\All{x} At(x,Berkeley) \implies Smart(x)$
$\All{x} P$\quad is equivalent to the \u{conjunction} of \u{instantiations} of $P$
\[
\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}\]
Typically, $\implies$ is the main connective with $\forall$.\\
Common mistake: using $\land$ as the main connective with $\forall$:
\[\All{x} At(x,Berkeley) \land Smart(x)\]
means ``Everyone is at Berkeley and everyone is smart''
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Existential quantification}
$\Exi{\} \$
Someone at Stanford is smart:\\
$\Exi{x} At(x,Stanford) \land Smart(x)$
$\Exi{x} P$\quad is equivalent to the \u{disjunction} of \u{instantiations} of $P$
\[
\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}\]
Typically, $\land$ is the main connective with $\exists$.\\
Common mistake: using $\implies$ as the main connective with $\exists$:
\[\Exi{x} At(x,Stanford) \implies Smart(x)\]
is true if there is anyone who is not at Stanford!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of quantifiers}
$\All{x}\All{y}$ is the same as $\All{y}\All{x}$ (\q{why})
$\Exi{x}\Exi{y}$ is the same as $\Exi{y}\Exi{x}$ (\q{why})
$\Exi{x}\All{y}$ is \u{not} the same as $\All{y}\Exi{x}$
$\Exi{x}\All{y} Loves(x,y)$\\
``There is a person who loves everyone in the world''
$\All{y}\Exi{x} Loves(x,y)$\\
``Everyone in the world is loved by at least one person''
\u{Quantifier duality}: each can be expressed using the other
$\All{x} Likes(x,IceCream)$ \qquad $\lnot \Exi{x} \lnot Likes(x,IceCream)$
$\Exi{x} Likes(x,Broccoli)$ \qquad $\lnot \All{x} \lnot Likes(x,Broccoli)$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Fun with sentences}
Brothers are siblings
.
``Sibling'' is reflexive
.
One's mother is one's female parent
.
A first cousin is a child of a parent's sibling
.
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Fun with sentences}
.
$\All{x,y} Brother(x,y) \lequiv Sibling(x,y)$.
.
$\All{x,y} Sibling(x,y) \lequiv Sibling(y,x)$
.
$\All{x,y} Mother(x,y) \lequiv (Female(x) and Parent(x,y))$
.
$\All{x,y} FirstCousin(x,y) \lequiv
\Exi{p,ps} Parent(p,x) \land Sibling(ps,p) \land Parent(ps,y)$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Equality}
$term_1 = term_2$ is true under a given interpretation\\
if and only if $term_1$ and $term_2$ refer to the same object
\begin{tabular}{ll}
E.g., & $1=2$ and $\All{x} {\times}(Sqrt(x),Sqrt(x)) = x$ are satisfiable\\
& $2=2$ is valid
\end{tabular}
E.g., definition of (full) $Sibling$ in terms of $Parent$:\al
$\All{x,y} Sibling(x,y) \lequiv [\lnot(x\eq y) \land \Exi{m,f} \lnot(m\eq f) \land {}$\nl
$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 $t=5$:
${\sc Tell}(KB,Percept([Smell,Breeze,None],5))$\\
${\sc Ask}(KB,\Exi{a} Action(a,5))$
I.e., does the KB entail any particular actions at $t=5$?
Answer: $Yes,\ \{a/Shoot\}$\qquad $\leftarrow$ \u{substitution} (binding list)
Given a sentence $S$ and a substitution $\sigma$,\\
$S\sigma$ denotes the result of plugging $\sigma$ into $S$; e.g.,\\
$S = Smarter(x,y)$\\
$\sigma = \{x/Hillary,y/Bill\}$\\
$S\sigma = Smarter(Hillary,Bill)$
${\sc Ask(KB,S)}$ returns some/all $\sigma$ such that $KB \models S\sigma$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Knowledge base for the wumpus world}
\u{``Perception''}\\
$\All{b,g,t} Percept([Smell,b,g],t) \implies Smelt(t)$\\
$\All{s,b,t} Percept([s,b,Glitter],t) \implies AtGold(t)$
\u{Reflex}: $\All{t} AtGold(t) \implies Action(Grab,t)$
\u{Reflex with internal state}: do we have the gold already?\\
$\All{t} AtGold(t) \land \lnot Holding(Gold,t) \implies Action(Grab,t)$
$Holding(Gold,t)$ cannot be observed\nl
$\Rightarrow$ keeping track of change is essential
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Deducing hidden properties}
Properties of locations:\\
$\All{l,t} At(Agent,l,t) \land Smelt(t) \implies Smelly(l)$\\
$\All{l,t} At(Agent,l,t) \land Breeze(t) \implies Breezy(l)$
Squares are breezy near a pit:
\u{Diagnostic} rule---infer cause from effect\nl
$\All{y} Breezy(y) \implies \Exi{x} Pit(x) \land Adjacent(x,y)$
\u{Causal} rule---infer effect from cause\nl
$\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
\u{Definition} for the $Breezy$ predicate:\nl
$\All{y} Breezy(y) \lequiv [\Exi{x} Pit(x) \land Adjacent(x,y)]$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Keeping track of change}
Facts hold in \u{situations}, rather than eternally\\
E.g., $Holding(Gold,Now)$ rather than just $Holding(Gold)$
\u{Situation calculus} is one way to represent change in FOL:\nl
Adds a situation argument to each non-eternal predicate\nl
E.g., $Now$ in $Holding(Gold,Now)$ denotes a situation
Situations are connected by the $Result$ function\\
$Result(a,s)$ is the situation that results from doing $a$ is $s$
\epsfxsize=0.3\textwidth
\fig{\file{figures}{situations2.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Describing actions I}
``Effect'' axiom---describe changes due to action\\
$\All{s} AtGold(s) \implies Holding(Gold,Result(Grab,s))$
``Frame'' axiom---describe \u{non-changes} due to action\\
$\All{s} HaveArrow(s) \implies HaveArrow(Result(Grab,s))$
\u{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
\u{Qualification problem}: true descriptions of real actions require endless caveats---what if gold is slippery or nailed down or $\ldots$
\u{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}
\u{Successor-state axioms} solve the representational frame problem
Each axiom is ``about'' a \u{predicate} (not an action per se):
\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
$\All{a,s} Holding(Gold,Result(a,s)) \lequiv {}$\nl
$[(a\eq Grab \land AtGold(s))$\nl
${}\lor (Holding(Gold,s) \land a\neq Release)]$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Making plans}
Initial condition in KB:\nl
$At(Agent,[1,1],S_0)$\nl
$At(Gold,[1,2],S_0)$
Query: ${\sc Ask}(KB,\Exi{s} Holding(Gold,s))$\nl
i.e., in what situation will I be holding the gold?
Answer: $\{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 $S_0$
and that $S_0$ is the only situation described in the KB
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Making plans: A better way}
Represent \u{plans} as action sequences $[a_1,a_2,\ldots,a_n]$
$PlanResult(p,s)$ is the result of executing $p$ in $s$
Then the query ${\sc Ask}(KB,\Exi{p} Holding(Gold,PlanResult(p,S_0)))$\\
has the solution $\{p/[Forward,Grab]\}$
Definition of $PlanResult$ in terms of $Result$:\al
$\All{s} PlanResult([],s) = s$\al
$\All{a,p,s} PlanResult([a|p],s) = PlanResult(p,Result(a,s))$
\u{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}