Chapter 1 Propositional Logic
- 1.1 Syntax
- 1.2 Semantics
- 1.3 Satisfiability and Validity
- 1.4 Equivalence and Implication
- 1.5 Substitution
- 1.6 Normal Forms
- 1.7 Decision Procedures for Satisfiability
- 1.8 Summary
- Exercises
1.1 Syntax
- not: \(\neg F\)
- and: \(F_1\land F_2\)
- or: \(F_1\lor F_2\)
- implication: \(F_1\implies F_2\)
- if and only if: \(F_1\iff F_2\)
Precedence from highest to lowest: \(\neg\), \(\land\), \(\lor\), \(\implies\), \(\iff\)
Associativity of binary operators: \(\land\) and \(\lor\) are left-associative, \(\implies\) and \(\iff\) are right-associative.
1.2 Semantics
An interpretation:
\[I: P\mapsto\mathrm{true}, Q\mapsto\mathrm{false},\dots\]
A truth table:
| \(F\) | \(\neg F\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Given that all symbols used are included in the interpretation, we can evaluate an arbitrary expression.
Constants:
\[\forall I, I\vDash\top, I\nvDash\bot\]