Notes Artificial Intelligence Propositional Logic

Propositional Logic

1 Mar 2022

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

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,

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

Propositional Logic

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

atomic::= ⟨prop⟩binop::= ∧ ∣ ∨ ∣ → ∣ ↔ ∣ ⊕complex::=⟨atomic⟩ ∣ ¬ complex ∣ ⟨complex⟩⟨binop⟩⟨complex⟩ ∣ (⟨complex⟩)\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:

  • PP
  • P∨QP \lor Q
  • ¬(¬X∧¬Y)\neg(\neg X \wedge \neg Y)
  • lights on↔¬ dark\textrm{lights on} \leftrightarrow \neg\,\textrm{dark}

Invalid:

  • P∨∨QP \lor\lor Q
  • (→P)(\rightarrow P)

Due to ambiguity of the grammar, there are multiple possible parse trees given an expression; for example A∧B→P∨¬QA \wedge B \rightarrow P \lor \neg{Q} can be interpreted as (A∧B)→(P∨¬Q)(A \wedge B) \rightarrow (P \lor \neg{Q}), A∧(B→P∨¬Q),A \wedge (B \rightarrow P \lor \neg{Q}), or A∧(B→P)∨¬QA \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∨B∨CA \lor B \lor C can be either (A∨B)∨C(A \lor B) \lor C or A∨(B∨C)A \lor (B \lor C).

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