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