Propositional Logic

1 Mar 2022

Notes Artificial Intelligence 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
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

$\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$ .