## Motivation§

The driver of the power of intelligent systems is the knowledge the systems have about their universe of discourse… — Feigenbaum

In order to give intelligent systems the expertise to solve problems, we need to give it a general language for encoding knowledge.

The natural langauges are too ambiguous, so we must find ways to be more expressive with higher-level languages.

## Logic§

The standard way of expressing knowledge in knowledge bases is with logic.

Logic has a few advantages over procedural languages:

• Context-independence
• Easier to determine correctness of a single line; easier to debug and maintain
• Well-defined semantics
• Not subject to order, global variables, side-effects
• Rules can be applied in various ways

In procedural languages, we must say how something is done; declarative languages lets us describe the world, and the system can determine the course of action given a model of the world.

Driving

When driving, we must know or infer:

• Laws
• How to operate a vehicle
• Right of way
• Turn signal
• Safety
• Speed
• Pedestrians
• Changing lanes
• Obstacles
• Other vehicles and drivers
• etc…

It is better to encode all of these in a knowledge base then have a system deduce the course of action, rather than enumerating each possible case in a massive if-else block.

### Inference Algorithms§

Inference Algorithms

Inference Algorithms give us a way to extract conclusions and make decisions given a rule base.

aka: inference, automated deduction, theorem-proving

Inference algorithms are the foundation for expert systems; essentially, load a rule base and describe the current situation, and the expert system allows us to ask it what conclusions it came up with. This is a powerful tool, as we are also able to ask how the system yielded an aswer, i.e. “proof”.

### Types of Logic§

There are many forms of logic,

• propositional/Boolean logic,
• First-order logic (FOL) and other higher-order logics,
• modal logics, epistemic, temporal, fuzzy, probablistic, non-sentential

They differ in expressiveness and computational complexity, but FOL has become the lingua franca for most knowledge systems in AI.

Each logic has its own:

1. syntax – the rules defining what sentences are accepted,
2. semantics – which defines the “truth” of a sentence, and the relationship between sentences,
3. proof theory – a way to derive an answer from a question

## Propositional Logic§

Propositional logic has

• well-defined sentences
• atomic sentences are given by propositional symbols
• i.e. P, Q, low_battery, bum_bright_room_113_lights_on
• complex sentes are generated via operators
• binary ops: AND ($\wedge$), OR ($\lor$), XOR ($\oplus$), implication ($\longrightarrow$), biconditional ($\longleftrightarrow$)
• unary op: NOT ($\neg$)
• parentheses

Propositional Logic

Below, the grammar for propositional logic is given in Backus-Naur Form (BNF):

\begin{align*} \textrm{atomic} &::=\ \langle\text{prop}\rangle\\ \textrm{binop} &::=\ \wedge\ |\ \lor\ |\ \rightarrow\ |\ \leftrightarrow\ |\ \oplus\\ \textrm{complex} &::= \langle\textrm{atomic}\rangle\ |\ \neg\,\textrm{complex}\ |\ \langle\textrm{complex}\rangle\langle\textrm{binop}\rangle\langle\textrm{complex}\rangle\ |\ (\langle\textrm{complex}\rangle) \end{align*}

Propositional Logic

Legal expressions:

• $P$
• $P \lor Q$
• $\neg(\neg X \wedge \neg Y)$
• $\textrm{lights on} \leftrightarrow \neg\,\textrm{dark}$

Invalid:

• $P \lor\lor Q$
• $(\rightarrow P)$

Due to ambiguity of the grammar, there are multiple possible parse trees given an expression; for example $A \wedge B \rightarrow P \lor \neg{Q}$ can be interpreted as $(A \wedge B) \rightarrow (P \lor \neg{Q})$, $A \wedge (B \rightarrow P \lor \neg{Q}),$ or $A \wedge (B \rightarrow P) \lor \neg{Q}$.

An order of precedence between operators can also be used to help disambiguate a logical expression, in order of highest to lowest

1. $\neg$
2. $\wedge$
3. $\lor, \oplus$
4. $\rightarrow, \leftrightarrow$

However, there still exists ambiguity, e.g. $A \lor B \lor C$ can be either $(A \lor B) \lor C$ or $A \lor (B \lor C)$.

We can say that each operator is left-associative to favor $(A \lor B) \lor C$.