# Propositional Logic

## 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:

**syntax**– the rules defining what sentences are accepted,**semantics**– which defines the “truth” of a sentence, and the relationship between sentences,**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`

- i.e.
- complex sentes are generated via operators
- binary ops:
`AND`

($\wedge$),`OR`

($\lor$),`XOR`

($\oplus$), implication ($\longrightarrow$), biconditional ($\longleftrightarrow$) - unary op:
`NOT`

($\neg$) - parentheses

- binary ops:

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

- $\neg$
- $\wedge$
- $\lor, \oplus$
- $\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$.