\documentstyle[fleqn,epsf,aima-slides]{article}
\begin{document}
\begin{huge}
\titleslide{Logical agents}{Chapter 6}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Knowledge bases
\blob Wumpus world
\blob Logic in general
\blob Propositional (Boolean) logic
\blob Normal forms
\blob Inference rules
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Knowledge bases}
\epsfxsize=0.8\maxfigwidth
\fig{\file{figures}{kbs.ps}}
Knowledge base = set of \u{sentences} in a \u{formal} language
\u{Declarative} approach to building an agent (or other system):\nl
{\sc Tell} it what it needs to know
Then it can {\sc Ask} itself what to do---answers should follow from the KB
Agents can be viewed at the \u{knowledge level}\nl
i.e., what they know, regardless of how implemented
Or at the \u{implementation level}\nl
i.e., data structures in KB and algorithms that manipulate them
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{A simple knowledge-based agent}
\input{\file{algorithms}{logical-agent-algorithm}}
The agent must be able to:\al
Represent states, actions, etc.\al
Incorporate new percepts\al
Update internal representations of the world\al
Deduce hidden properties of the world\al
Deduce appropriate actions
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Wumpus World PAGE description}
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.6\textwidth}
\u{Percepts} Breeze, Glitter, Smell\\
\u{Actions} Left turn, Right turn,\nl
Forward, Grab, Release, Shoot\\
\u{Goals} Get gold back to start\\
without entering pit or wumpus square
\end{minipage}}
&
\epsfxsize=0.3\textwidth
\epsffile{\file{figures}{wumpus-world.ps}}
\end{tabular}
\u{Environment}\al
Squares adjacent to wumpus are smelly\al
Squares adjacent to pit are breezy\al
Glitter if and only if gold is in the same square\al
Shooting kills the wumpus if you are facing it\al
Shooting uses up the only arrow\al
Grabbing picks up the gold if in the same square\al
Releasing drops the gold in the same square
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Wumpus world characterization}
\q{Is the world deterministic}
\q{Is the world fully accessible}
\q{Is the world static}
\q{Is the world discrete}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Wumpus world characterization}
\q{Is the world deterministic} Yes---outcomes exactly specified
\q{Is the world fully accessible} No---only \u{local} perception
\q{Is the world static} Yes---Wumpus and Pits do not move
\q{Is the world discrete} Yes
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Exploring a wumpus world}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq0.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq4.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq5.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq6.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
\vspace*{0.4in}
\epsfxsize=0.6\textwidth
\fig{\sfile{figures}{wumpus-seq7.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Other tight spots}
\begin{tabular}{lr}
\epsfxsize=2.7in
\raisebox{-0.5in}[2.5in]{\epsffile{\file{figures}{wumpus-bb.ps}}}
&
\hbox{\begin{minipage}[b]{0.5\textwidth}
Breeze in (1,2) and (2,1)\al
$\Rightarrow$ no safe actions\\
Assuming pits uniformly distributed,\\
(2,2) is most likely to have a pit
\end{minipage}}
\\
& \\
\epsfxsize=1.8in
\epsffile{\file{figures}{wumpus-s.ps}}
&
\hbox{\begin{minipage}[b]{0.65\textwidth}
Smell in (1,1) \al
$\Rightarrow$ cannot move
Can use a strategy of \u{coercion}:\al
shoot straight ahead\al
wumpus was there $\Rightarrow$ dead $\Rightarrow$ safe\al
wumpus wasn't there $\Rightarrow$ safe\al
\end{minipage}}
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Logic in general}
\u{Logics} are formal languages for representing information\al
such that conclusions can be drawn
\u{Syntax} defines the sentences in the language
\u{Semantics} define the ``meaning'' of sentences;\al
i.e., define \u{truth} of a sentence in a world
E.g., the language of arithmetic
$x+2 \geq y$ is a sentence; $x2+y>{}$ is not a sentence
$x+2 \geq y$ is true iff the number $x+2$ is no less
than the number $y$
$x+2 \geq y$ is true in a world where $x\eq 7,\ y\eq 1$\\
$x+2 \geq y$ is false in a world where $x\eq 0,\ y\eq 6$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Types of logic}
Logics are characterized by what they commit to as ``primitives''
Ontological commitment: what exists---facts? objects? time? beliefs?
Epistemological commitment: what states of knowledge?
\begin{LARGE}
\input{\file{tables}{ontological-epistemological-table}}
\end{LARGE}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Entailment}
\[KB \models \alpha\]
Knowledge base $KB$ \u{entails} sentence $\alpha$\nl
if and only if\\
$\alpha$ is true in all worlds where $KB$ is true
E.g., the KB containing ``the Giants won'' and ``the Reds won''\\
entails ``Either the Giants won or the Reds won''
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Models}
Logicians typically think in terms of \u{models}, which are formally\\
structured worlds with respect to which truth can be evaluated
We say $m$ is a \u{model} of a sentence $\alpha$
if $\alpha$ is true in $m$
$M(\alpha)$ is the set of all models of $\alpha$
Then $KB \models \alpha$ if and only if $M(KB) \subseteq M(\alpha)$
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.6\textwidth}
E.g. $KB$ = Giants won and Reds won\nl
$\alpha$ = Giants won
\end{minipage}}
&
\epsfxsize=3.2in
\raisebox{-2in}[0in]{\epsffile{\file{figures}{model-inclusion.ps}}}
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Inference}
$KB\vdash_i\alpha$ = sentence $\alpha$ can be derived from $KB$ by procedure $i$
\u{Soundness}: $i$ is sound if\nl
whenever $KB\vdash_i\alpha$, it is also true that $KB\models\alpha$
\u{Completeness}: $i$ is complete if\nl
whenever $KB\models\alpha$, it is also true that $KB\vdash_i\alpha$
Preview: we will define a logic (first-order logic) which is
expressive enough to say almost anything of interest, and for which
there exists a sound and complete inference procedure.
That is, the procedure will answer any question whose answer follows
from what is known by the $KB$.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Propositional logic: Syntax}
Propositional logic is the simplest logic---illustrates basic ideas
The proposition symbols $P_1$, $P_2$ etc are sentences
If $S$ is a sentence, $\lnot S$ is a sentence
If $S_1$ and $S_2$ is a sentence, $S_1 \land S_2$ is a sentence
If $S_1$ and $S_2$ is a sentence, $S_1 \lor S_2$ is a sentence
If $S_1$ and $S_2$ is a sentence, $S_1 \implies S_2$ is a sentence
If $S_1$ and $S_2$ is a sentence, $S_1 \lequiv S_2$ is a sentence
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Propositional logic: Semantics}
Each model specifies true/false for each proposition symbol
\begin{tabular}{lccc}
E.g. & $A$ & $B$ & $C$\\
& $True$ & $True$ & $False$
\end{tabular}
Rules for evaluating truth with respect to a model $m$:
\begin{tabular}{rcclcl}
$\lnot S$ & is true iff & $S$ & is false & & \\
$S_1 \land S_2$ & is true iff & $S_1$ & is true \u{and} & $S_2$ & is true\\
$S_1 \lor S_2$ & is true iff & $S_1$ & is true \u{or} & $S_2$ & is true\\
$S_1 \implies S_2$ & is true iff& $S_1$ & is false \u{or} & $S_2$ & is true\\
\qquad i.e., & is false iff& $S_1$ & is true \u{and} & $S_2$ & is false\\
$S_1 \lequiv S_2$ & is true iff& $S_1\implies S_2$ & is true \u{and} & $S_2\implies S_1$ & is true
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Propositional inference: Enumeration method}
Let $\alpha = A \lor B$ and $KB = (A\lor C) \land (B \lor \lnot C)$
Is it the case that $KB\models\alpha$? \\
Check all possible models---$\alpha$ must be true wherever $KB$ is true
\input{\file{tables}{abc-truth-table}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Propositional inference: Solution}
\input{\file{tables}{abc-solution-table}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Normal forms}
Other approaches to inference use syntactic operations
on sentences, often expressed in standardized forms
\u{Conjunctive Normal Form} (CNF---universal)\nl
{\em conjunction} of $\underbrace{\mbox{{\em disjunctions} of {\em literals}}}$\nl
\phantom{{\em conjunction} of {\em disjuncti}}{\em clauses}\nl
E.g., $(A \lor \lnot B) \land (B \lor \lnot C \lor \lnot D)$
\u{Disjunctive Normal Form} (DNF---universal)\nl
{\em disjunction} of $\underbrace{\mbox{{\em conjunctions} of {\em literals}}}$\nl
\phantom{{\em disjunction} of {\em conjuncti}}{\em terms}\nl
E.g., $(A\land B) \lor (A \land \lnot C) \lor (A \land \lnot D)
\lor (\lnot B \land \lnot C) \lor (\lnot B \land \lnot D)$
\u{Horn Form} (restricted)\nl
{\em conjunction} of {\em Horn clauses} (clauses with $\leq 1$ positive literal)\nl
E.g., $(A \lor \lnot B) \land (B \lor \lnot C \lor \lnot D)$\nl
Often written as set of implications:\nl
$B \implies A$ and $(C \land D) \implies B$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Validity and Satisfiability}
A sentence is \u{valid} if it is true in \u{all} models\nl
e.g., $A \lor \lnot A$, \qquad $A \implies A$, \qquad
$(A \land (A \implies B)) \implies B$
Validity is connected to inference via the \u{Deduction Theorem}:\nl
$KB \models \alpha$ if and only if $(KB \implies \alpha)$ is valid
A sentence is \u{satisfiable} if it is true in \u{some} model\nl
e.g., $A\lor B$,\qquad $C$
A sentence is \u{unsatisfiable} if it is true in \u{no} models\nl
e.g., $A\land \lnot A$
Satisfiability is connected to inference via the following:\nl
$KB \models \alpha$ if and only if $(KB \land \lnot \alpha)$ is unsatisfiable\\
i.e., prove $\alpha$ by {\em reductio ad absurdum}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Proof methods}
Proof methods divide into (roughly) two kinds:\al
\u{Model checking}\al
truth table enumeration (sound and complete for propositional)\al
heuristic search in model space (sound but incomplete)\nl
e.g., the GSAT algorithm (Ex. 6.15)
\u{Application of inference rules}\al
Legitimate (sound) generation of new sentences from old\al
\u{Proof} = a sequence of inference rule applications\nl
Can use inference rules as operators in a standard search alg.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Inference rules for propositional logic}
\u{Resolution} (for CNF): complete for propositional logic
\[
\frac{\alpha \lor \beta,\qquad \lnot \beta \lor \gamma}{\alpha \lor \gamma}
\]
\u{Modus Ponens} (for Horn Form): complete for Horn KBs
\[\frac{\alpha_1,\ldots,\alpha_n,\qquad \alpha_1\land \cdots \land \alpha_n\implies \beta}{\beta}
\]
Can be used with \u{forward chaining} or \u{backward chaining}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Summary}
Logical agents apply \u{inference} to a \u{knowledge base}\al
to derive new information and make decisions
Basic concepts of logic:\al
-- \u{syntax}: formal structure of \u{sentences}\al
-- \u{semantics}: \u{truth} of sentences wrt \u{models}\al
-- \u{entailment}: necessary truth of one sentence given another\al
-- \u{inference}: deriving sentences from other sentences\al
-- \u{soundess}: derivations produce only entailed sentences\al
-- \u{completeness}: derivations can produce all entailed sentences
Wumpus world requires the ability to represent partial
and negated information, reason by cases, etc.
Propositional logic suffices for some of these tasks
Truth table method is sound and complete for propositional logic
\end{huge}
\end{document}