Introduction to Propositional Logic

1 / 23
Importance of logic

Hardware circuits are based on (Boolean) logic

Software is basically a piece of logic

Reasoning about a computer program requires

I a formal logical framework, and
I a trained mind in logical thought

2 / 23
Declarative sentences
A declarative sentence (or proposition) is a true or false statement

Examples
I 5>3
I 5<3
I grass is green
I grass is green and roses are blue
I grass is green or roses are blue
I if x > 1, then x 2 6= x
3 / 23
A line of argument (in natural language)

We want to understand why arguments such as these hold

Example

If the train arrives late and there are no taxis at the station,
then Jane is late for her meeting

Jane is not late for the meeting

The train does arrive late

Therefore, there are taxis at the station

4 / 23
Argument abstraction
Example (Jane)
If the train arrives late, and there are no taxis at the station,
then Jane is late for her meeting
Jane is not late for her meeting
The train does arrive late
Therefore, there are taxis at the station

Key of translation
p the train arrives late
q there are taxis at the station
r Jane is late for her meeting

Abstraction:
If p and not q, then r Not r p Therefore, q
5 / 23
Argument abstraction (another example)
Example (John)
If it is raining, and John did not take his umbrella with him,
then he will get wet
John is not getting wet
It is raining
Therefore, John took his umbrella with him

Key of translation
p it is raining
q John takes his umbrella with him
r John is getting wet

Abstraction:
If p and not q, then r Not r p Therefore, q
6 / 23
Argument formalization
Example (Jane) Example (John)
p the train is late it is raining
q there are taxis at the station John has his umbrella with him
r Jane is late for her meeting John is getting wet

Both arguments have the same abstraction:

If p and not q, then r Not r p Therefore, q

with as logical formalization:

(((p ∧ ¬q) → r ) ∧ (¬r ∧ p)) → q

That the two arguments hold is due to their logical form

It does not depend on the actual content of propositions p, q and r
7 / 23
 Propositional logic

Chrysippus of Soli (c. 279 – c. 206 BC)

introduced a formal system for propositional logic

8 / 23
Symbols of propositional logic

We want to study logic without being distracted by

the concrete contents of propositions

Variables
Denoted by p. They can have the value true (T) or false (F)

Formulas
Formulas φ, ψ are built from variables and four connectives:

¬ ‘not’ (negation)
∧ ‘and’ (conjunction)
→ ‘if . . . then . . . ’ (implication)
↔ ‘if and only if’ (bi-implication)

9 / 23
Negation

A negation ¬φ (“not φ”) is


true if φ is false
false if φ is true

Truth table for ¬ :

φ ¬φ
T = true
T F
F T F = false

10 / 23
Conjunction

A conjunction φ ∧ ψ (“φ and ψ”) is


true if φ is true and ψ is true
false in all other cases

Truth table for ∧:

φ ψ φ∧ψ
T T T
T F F We first list all possible
F T F combinations of assignments
F F F to φ and ψ

11 / 23
Implication

φ → ψ means: if φ is true, then ψ is true

Question
For which truth values of φ and ψ is φ → ψ false ?

12 / 23
Implication

An implication φ → ψ (“φ implies ψ” / “if φ, then ψ”) is



 false if φ is true, and ψ is false
 true otherwise


Truth table for → :

φ ψ φ→ψ
T T T
T F F
F T T
F F T

13 / 23
Implication

(n > 1) → (n + 1 > 1) clearly holds for all natural number n

I n = 0: F→F

I n = 1: F→T

I n = 2: T→T

14 / 23
Principle of explosion

In natural language,

if I’m a movie star, then I’m rich

makes sense, unlike

if I’m a movie star, then the moon is made of cheese

But they are both true (because I’m not a movie star)

15 / 23
Bi-implication

A bi-implication φ ↔ ψ (“φ if and only if ψ”) is


true if φ and ψ have the same truth value
false otherwise

Truth table for ↔:

φ ψ φ↔ψ
T T T
T F F
F T F
F F T

16 / 23
Island of liars and truth speakers

On the Island of Liars and Truth Speakers every inhabitant has

the peculiar property of either:
I always lying, or
I always speaking the truth

For each islander x, the variable tx expresses:

x is a truth speaker

Question
Give a formula expressing that islander x is a liar

Answer: ¬x

17 / 23
An important bi-implication

If an islander x makes an assertion φ, then:

I φ is true if x is a truth speaker

I φ is false if x is a liar

Hence, irrespective of whether or not x is a truth speaker,

the following bi-implication is true:

tx ↔ φ

18 / 23
What are these two islanders ?

Puzzle
You meet two islanders a and b
a says: “We are both liars ”
What are a and b ?

a says, in propositional logic: ¬ta ∧ ¬tb

So ta ↔ (¬ta ∧ ¬tb ) is true

Given this fact, we determine the truth values of ta and tb

19 / 23
Solution: Truth table

We know: ta ↔ (¬ta ∧ ¬tb ) is true

In order to find out what this fact tells us about ta and tb ,

we make a truth table:

ta tb ¬ta ¬tb ¬ta ∧ ¬tb ta ↔ (¬ta ∧ ¬tb )

T T F F F F
T F F T F F
F T T F F T
F F T T T F

We find that the bi-implication is T only if ta is F and tb is T

So: a is a liar and b a truth speaker

20 / 23
Two islanders pointing at each other - part I

Who is lying ? - part I

Islander a says: “b is a truth speaker ”
Islander b says: “a is a truth speaker ”

What can you conclude ?

Answer: a and b are either both truth speakers or both liars

ta tb ta ↔ tb tb ↔ ta
T T T T
T F F F
F T F F
F F T T

21 / 23
Two islanders pointing at each other - part II

Who is lying ? - part II

Islander a says: “b is a liar ”
Islander b says: “a is a liar ”

What can you conclude ?

Answer: Either a or b is a liar, but not both

ta tb ¬ta ¬tb ta ↔ ¬tb tb ↔ ¬ta

T T F F F F
T F F T T T
F T T F T T
F F T T F F

22 / 23
Two islanders pointing at each other - part III

Who is lying ? - part III

Islander a says: “b is a liar ”
Islander b says: “a is a truth speaker ”

What can you conclude ?

Answer: You’re on
the wrong island...

ta tb ¬tb ta ↔ ¬tb tb ↔ ta
T T F F T
T F T T F
F T F T F
F F T F T
23 / 23