The Language of Propositional Logic
Introduction
Consider the following argument:
Whenever it rains, the grass gets wet.
The grass is dry.
Hence, it is not raining.
If we let
• R denote “It is raining,”
• W denote “The grass is wet,”
• ¬ denote “it is not the case that,” and
• → denote “implies that,”
then the above argument can be formalized as
(R → W)
¬W
¬R
The Language of Propositional Logic
In order to discuss simple arguments like the one we have just seen, we need to set up a suitable framework. For this, we use the language of propositional logic.
Just as the English language is made up of words that are formed from letters, the language of propositional logic will be made up of formulas that are formed from symbols.
Definition
The following are the symbols of propositional logic, arranged into three groups.
• Propositional variables: P1, P2, P3, P4, P5, . . .
• Connectives: ¬, →
• Brackets: (, )
Notation: We will often use the letters P, Q, R, S to denote propositional variables.
Propositional Formulas
In English, words are finite strings from the alphabet, but not all finite strings of letters are words. In propositional logic, certain finite strings from the symbol set will be called formulas.
Later, when we assign meaning to our language, the formulas of propositional logic will correspond to statements which can be either true or false.
Definition
Propositional formulas are certain finite strings of symbols, defined inductively as follows:
(1) All propositional variables are formulas.
(2) If ϕ is a formula, so is ¬ϕ.
(3) If ϕ and ψ are formulas, so is (ϕ → ψ).
So the formulas are built up from propositional variables using the connectives.
Question
Which of the following are formulas?
For those that are, show how they are built up from the propositional variables.
1. ¬¬¬P
2. P → Q → R
3. ()P
4. ¬(¬P → R)
5. (¬P)
Induction and Subformulas
Propositional Formulas
Since formulas are built up inductively from propositional variables using the connectives ¬ and →, we can use the method of mathematical induction to prove facts about formulas.
The base case will be to prove the fact about propositional variables.
There will be two inductive steps, one for each of
• formulas of the form. ¬ϕ, assuming we know the fact holds for ϕ, and
• formulas of the form. (ϕ → ψ), assuming the fact holds for ϕ and ψ.
Question
Which of the following are subformulas of (¬(P → Q) → (Q → P))?
1. ¬P
2. ¬Q
3. (Q → P)
4. → P
5. (¬(P → Q) → (Q → P))
Truth Assignments and Truth Tables
Truth Assignments
We are now ready to give meaning to our propositional formulas.
Definition
A truth assignment is a function that assigns a truth value of T (true) or F (false) to every propositional variable. That is, a truth assignment is a function
e : {P1, P2, P3, . . .} → {T, F}
If e is a truth assignment, then we extend e to be a function eˆ on all formulas as follows:
• If ϕ = P, a propositional variable, then eˆ(ϕ) = e(ϕ).
• If ϕ = ¬ψ where we have defined eˆ(ψ), then eˆ(ϕ) = T if eˆ(ψ) = F, otherwise eˆ(ϕ) = F.
• If ϕ = (ψ → χ) where we have defined eˆ(ψ) and eˆ(χ), then eˆ(ϕ) = F if eˆ(ψ) = T and eˆ(χ) = F, and eˆ(ϕ) = T otherwise.
Normally, we simply write e in place of eˆ.
Questions
1. Let e be a truth assignment such that e(P) = T, e(Q) = T, and e(R) = F.
Find e((P → (R → ¬Q))).
2. Let e be the truth assignment given by
Find e(((¬P4 → P3) → (P18 → ¬P1))).