Propositional Logic (AKA Boolean Logic)
Sentences considered in propositional logic are not arbitrary sentences but are the ones that are either true or false, but not both. These kinds of sentences are referred to as propositions.
The truth value refers to the value returned by the proposition, hence it can be either true or false.
Propositional logic uses true statements to form or prove other true statements. There are two parts to propositional logic:
- Representation (syntax) - How to represent a proposition
- Reasoning (algorithm) - How to create or prove new propositions
Test yourself with this applet by Brian S. Borowski.
Models for propositional logic are just sets of truth values for the proposition symbols...
Pros
- A very simple logic.
- Is declarative, i.e. pieces of syntax correspond to facts.
- Allows partial/disjunctive/negated information (unlike most data structures and databases)
- Is compositional, e.g. meaning of B⋀P is derived from the two composites padding the ⋀.
- Meaning in propositional logic is context-independent, unlike natural language, where meaning depends on context.
Cons
- It has a very limited expressive power (unlike natural language). e.g. cannot say pits cause breezes in adjacent squares except by writing one sentence for each square.
Semantics
Here are the main 6 logical connectives (¬, ⋀, ⋁, ⊕, ⇒, ⇔) described in a Truth Table...
| P | Q | ¬ P | P ⋀ Q | P ⋁ Q | P ⊕ Q | P ⇒ Q | P ⇔ Q |
| F | F | T | F | F | F | T | T |
| F | T | T | F | T | T | T | F |
| T | F | F | F | T | T | F | F |
| T | T | F | T | T | F | T | T |
With respect to the truth table entry of implies which is confusing at first as it does not follow one's intuitive understanding of "P implies Q", or "if P then Q". To make this clear, take note of the following points...
- In propositional logic, there is no requirement that P and Q are related, in any way.
- "The sky is blue" ⇒ "Tokyo is the capital of Japan" holds true, even though in English it is a ridiculous and homeless remark.
- Any implication is true whenever its antecedent is false.
- Think about sarcastic remarks such as "You will graduate the day that pigs begin to fly". Perhaps an interesting example would be the following line from Macbeth (Shakespeare)...
- "This apparition, conjured by the witches, tells Macbeth that no one can defeat him until a forest, Birnham Wood, marches against him". Macbeth is heartened, believing it is impossible for a forest to march. The logic states that the statement no one can defeat him then holds true, as long as the Birnham Wood forest is unable to march.
- To further break this down, it can be read as "I am claiming that Q is true, if and only if P is true, otherwise I make no claim".
- NOTE: Be aware that the if and only if used in this statement is followed by an otherwise no claim statement, hence it is not a mathematical equivalent of iff, which states that otherwise false.
- Think about sarcastic remarks such as "You will graduate the day that pigs begin to fly". Perhaps an interesting example would be the following line from Macbeth (Shakespeare)...
- And perhaps have a read of this.
Reasoning Patterns
- Inference Rules
- Modus Ponens (Most well-known inference rule)
- α ⇒ β, α / β
- Reads if α implies β, and α is given, then β can be inferred.
- α ⇒ β, α / β
- And-Elimination
- α ⋀ β / α
- Reads as from α and β being true, α can be inferred, or mathematically, from a conjunction, any of the conjuncts can be inferred.
- α ⋀ β / α
- Modus Ponens (Most well-known inference rule)
Example Problems
- A ⇔ B ⇔ C
Interesting Links
- The Propositional Logic Applet
- A good explanation and quiz questions here
Related
Ancstors ☣ Logic
Siblings ☣ Logic/FirstOrder ☣ Logic/Fuzzy
References
Russell, S. and Norvig, P. (2003). Artificial Intelligence, A Modern Approach (2nd ed.). New Jersey, Pearson Education International
- Brian S. Borowski
