Propositional Logic
Chapter 1 - Part 1 Summary
1. Fundamental Concepts
Propositions
A proposition is a declarative statement that can take either the truth value TRUE
or FALSE.
Examples:
"The Earth is a planet" (TRUE)
"The Sun is a star" (TRUE)
Types:
Atomic/Elementary: Cannot be decomposed into simpler propositions
Compound: Composition of several elementary propositions
Paradoxes
Declarative statements whose truth or falsity cannot be determined.
Example: "This sentence is false"
If true ⇒ the sentence is false ⇒ contradiction
If false ⇒ the sentence is true ⇒ contradiction
2. Propositional Language
1
Alphabet
The propositional language alphabet contains:
1. Propositional variables: P, Q, R, P1 , P2 , . . . (capital Latin letters)
2. Logical connectives: ¬, ∧, ∨, →, ↔
3. Parentheses: ( and )
Writing Rules (Syntax)
r1. Every propositional variable is an (atomic) formula
r2. If α is a formula, then ¬α is a formula
r3. If α and β are formulas, then:
(α ∧ β) is a formula
(α ∨ β) is a formula
(α → β) is a formula
(α ↔ β) is a formula
r4. No other expression is a formula of the language
Important De nitions
Literal: An atomic formula or its negation (e.g., P or ¬P )
Complementary literals: Two literals where one is the negation of the
other
Subformula: A formula contained within another formula
Precedence of Connectives
Order of application (highest to lowest):
¬ > ∧ > ∨ > → > ↔
Examples:
P ∧ Q ∨ R is read as (P ∧ Q) ∨ R
P → Q ∧ R is read as P → (Q ∧ R)
2
3. Semantics
Truth Function (Valuation)
A valuation v is a function: v : {T, F }n → {T, F }
Truth tables for connectives:
P Q ¬P P ∧Q P ∨Q P →Q P ↔Q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T
Satis ability
De nition: A valuation v satis es a formula α if v(α) = T (written v |= α)
A formula α is satis able if there exists at least one valuation v such that v |= α
An set of formulas Γ = {α1 , . . . , αn } is satis able if there exists a valuation v that
satis es ALL formulas in Γ
Tautology
A formula α is a tautology (written |= α) if and only if v |= α for ALL valuations
v
Example: |= (P ∧ Q) → Q (always true)
4. Logical Equivalence and Properties
Logical Equivalence
Two formulas α and β are logically equivalent (α ≡ β ) if and only if:
v(α) = v(β) for all valuations v
Equivalently: |= α ↔ β
Properties of Logical Connectives
Commutativity:
α∧β ≡β∧α α∨β ≡β∨α
Associativity:
(α ∧ β) ∧ γ ≡ α ∧ (β ∧ γ)
(α ∨ β) ∨ γ ≡ α ∨ (β ∨ γ)
Distributivity:
α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ)
3
α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ)
De Morgan's Laws:
¬(α ∧ β) ≡ ¬α ∨ ¬β
¬(α ∨ β) ≡ ¬α ∧ ¬β
Idempotence:
α∧α≡α α∨α≡α
5. Logical Consequence
Logical Consequence
A formula β is a logical consequence of a set of formulas Γ = {α1 , . . . , αn }
(written Γ |= β ) if and only if:
For all v, if v |= α1 and . . . and v |= αn then v |= β
In other words: Every valuation that satis es ALL formulas in Γ also satis es β
Key Theorem
Γ |= β if and only if Γ ∪ {¬β} is unsatis able
This connects logical consequence with unsatis ability!
Important Theorems
Theorem 1.1:
α1 , . . . , αn |= β ⇔ α1 , . . . , αn−1 |= (αn → β)
Corollary 1.1:
α1 , . . . , αn |= β ⇔ |= (α1 → (α2 → · · · → (αn → β)))
Theorem 1.2 (Transitivity): If Γ |= α and Γ |= (α → β) then Γ |= β
Theorem 1.3: If Γ |= α and Γ |= ¬α then Γ is unsatis able
6. Normal Forms
Disjunctive Normal Form (DNF)
A formula is in DNF if it has the form:
M1 ∨ M2 ∨ · · · ∨ Mn
where each Mi is a conjunction of literals: L1 ∧ L2 ∧ · · · ∧ Lk
4
Example: P ∨ (Q ∧ ¬R) ∨ (¬Q ∧ P )
Conjunctive Normal Form (CNF)
A formula is in CNF if it has the form:
C1 ∧ C2 ∧ · · · ∧ Cn
where each Ci is a disjunction of literals: L1 ∨ L2 ∨ · · · ∨ Lk
Example: (P ∨ Q ∨ ¬R) ∧ (¬Q ∨ P ) ∧ (¬Q ∨ P )
Theorem 1.7
For every formula α, there exists an equivalent formula α′ in DNF (respectively
CNF) such that:
|= α ↔ α′
This means every formula can be converted to normal form!
7. Complete Sets of Connectives
De nition
A set S of connectives is complete if for every formula α of language L, there exists
a formula α′ using only connectives from S such that α ≡ α′
Example: The set {¬, ∧} forms a complete system
Sheer Connectives: There exist complete sets with just ONE connective
(NAND or NOR)
End of Summary