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
    • This leads to inferences

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
  • Road conditions
  • 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$.