COMP30026 Models of Computation – Propositional Logic
COMP30026 Models of Computation
Propositional Logic
Bach Le / Anna Kalenkova
Lecture Week 2 Part 1 (Zoom)
Semester 2, 2021
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 1 / 18
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 2 / 18
Our Goal for the Next Few Lectures
Introduce/recapitulate propositional logic
Use it as a vehicle for launching more generally applicable logic
concepts.
Use it for simple, mechanised reasoning.
If you are familiar with propositional logic, some of this will be old
hat.
But pay attention anyway, because the concepts and methods we
introduce now will serve as a blueprint for similar (but more complex
and powerful) concepts and methods for predicate logic.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 3 / 18
Administrivia: Grok
Solutions to module 1 problems are now available—Study them!
The first serious assessment tasks are not far away.
Do not neglect Grok! We need to see that your account is working.
Of all Grok enrolled students, 11 have completed all exercises in all 8
modules, and 46 have completed the 6 mandatory modules.
415 have at least one green diamond. But 105 have not completed
module 1 yet. And more than 60 are still to do their first exercise!
If you don’t have a Grok account, please identify yourself asap.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 4 / 18
Propositional = Boolean Logic
Philosophers have been interested in the “rules of reasoning” for
thousands of years. Aristotle’s syllogisms had particular importance
for European scholars.
George Boole is usually considered the
father of modern logic. Boole took an
algebraic view of logic, pointing out that
there are important abstract analogies
between certain arithmetic operations
and the logical connectives.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 5 / 18
Intro Puzzle
Huey, Dewey and Louie are being questioned by their uncle. Here is
what they say:
Huey: “Dewey and Louie had equal share in it; if one is guilty,
so is the other.”
Dewey: “If Huey is guilty, then so am I.”
Louie: “Dewey and I are not both guilty.”
Their uncle, knowing that they are cub scouts, realises that they
cannot tell a lie.
Has he got sufficient information to decide who (if any) are guilty?
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 6 / 18
(Classical) Propositional Logic: Syntax
We shall build propositional formulas from this set of symbols:
A,B ,C , . . .Z ,
︸ ︷︷ ︸
prop. letters
¬,∧,∨,⇒,⇔,⊕,
︸ ︷︷ ︸
connectives
f, t, (, ).
Well-formed formulas (wffs) are generated by the grammar
wff → A | B | C | . . . | Z | f | t
| (¬wff )
| (wff ∧ wff )
| (wff ∨ wff )
| (wff ⇒ wff )
| (wff ⇔ wff )
| (wff ⊕ wff )
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 7 / 18
Propositional Logic: Notational Conveniences
We shall drop outermost parentheses.
We shall assume that ¬ binds tighter than ∧ and ∨.
These bind tighter than ⊕, which binds tighter than ⇒ and ⇔.
This allows us to write, without ambiguity
(((¬Q) ∧ P)⇒ (P ∨ (P ⇔ Q)))
as
¬Q ∧ P ⇒ P ∨ (P ⇔ Q)
Note: O’Donnell et al. (and Makinson) use → instead of ⇒,
and ↔ instead of ⇔. Makinson also uses 0 for f and 1 for t. On a
whiteboard I tend to use 0 and 1, as they are faster to write.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 8 / 18
Propositional Logic: Semantics
A proposition is false (f) or true (t).
A truth assignment maps each propositional letter to t or f.
We can give the semantics of the connectives via truth tables:
A B ¬A A ∧ B A ∨ B A⇒ B A⇔ B A⊕ B
f f t f f t t f
f t t f t t f t
t f f f t f f t
t t f t t t t f
This gives meaning to all propositional formulas, as we let A and B
stand for the values of arbitrary (compound) propositions.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 9 / 18
Connectives Defined in Haskell
Haskell has a type Bool, and some connectives are pre-defined:
data Bool = False | True
not :: Bool -> Bool
not True = False
not False = True
(&&) :: Bool -> Bool -> Bool
False && _ = False
True && x = x
(||) : Bool -> Bool -> Bool
False || x = x
True || _ = True
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 10 / 18
Conjunction and Disjunction
P ∧ Q is the conjunction of P and Q.
P ∨ Q is their disjunction.
An “or” in English sometimes translates to disjunction:
I’ll eat if there is peanut butter or jam in the fridge.
Other times it translates to exclusive or:
Would you like the ice cream or the crème brûlée?
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 11 / 18
The Conditional
The proposition P ⇒ Q is best read “if P then Q” (or sometimes
“P only if Q” or “Q whenever P”). Usually, “implies” is misleading.
A B A⇒ B
f f t
f t t
t f f
t t t
1. If the volume is increased, the pressure
falls.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 12 / 18
The Conditional
The proposition P ⇒ Q is best read “if P then Q” (or sometimes
“P only if Q” or “Q whenever P”). Usually, “implies” is misleading.
A B A⇒ B
f f t
f t t
t f f
t t t
1. If the volume is increased, the pressure
falls.
2. If Melbourne is in Queensland then
Brisbane is in Victoria.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 12 / 18
The Conditional
The proposition P ⇒ Q is best read “if P then Q” (or sometimes
“P only if Q” or “Q whenever P”). Usually, “implies” is misleading.
A B A⇒ B
f f t
f t t
t f f
t t t
1. If the volume is increased, the pressure
falls.
2. If Melbourne is in Queensland then
Brisbane is in Victoria.
3. Melbourne and Brisbane are in
different states and if Melbourne
is in Queensland then so is Brisbane.
We talk about material implication.
Note that A⇒ B has the same truth table as ¬A ∨ B .
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 12 / 18
More Connectives in Haskell
infix 0 ==>
infix 0 <=>
infix 1 <+>
(==>) :: Bool -> Bool -> Bool
False ==> _ = True
True ==> x = x
(<=>) :: Bool -> Bool -> Bool
x <=> y = x == y
(<+>) :: Bool -> Bool -> Bool
x <+> y = x /= y
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 13 / 18
Poll 1
Which of these claims hold?
1 P ⇒ Q has the same truth table as ¬Q ⇒¬P
2 (P ⇒ Q) ∧ (P ⇒ R) has the same truth table as P ⇒ (Q ∧ R)
3 (P ⇒ R) ∧ (Q ⇒ R) has the same truth table as (P ∧ Q)⇒ R
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 14 / 18
Other Binary Connectives
We can also define ↓, or “nor’, as well as ↑, or “nand”.
A B A ↓ B A ↑ B
f f t t
f t f t
t f f t
t t f f
“Nand” is sometimes called Sheffer’s stroke.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 15 / 18
Some Ternary Connectives
A B C if A then B else C median(A,B ,C )
f f f f f
f f t t f
f t f f f
f t t t t
t f f f f
t f t f t
t t f t t
t t t t t
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 16 / 18
On Boolean Short-Circuit Definitions
Most programming languages offer the Boolean connectives ‘and’
and ‘or’, but usually these are not commutative!
In C, Haskell, and many other languages, 0 == 1 && 1/0 == 42
has a behaviour that is different from 1/0 == 42 && 0 == 1.
One evaluates to False, the other causes a run-time error. The first
version avoids the runtime error, because conjunction is not a strict
function in typical programming languages: If the first argument is
false, the second won’t be evaluated.
To model the behaviour properly, we really need three-valued
propositional logic, the third truth value being “undefined”.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 17 / 18
Knights and Knaves Puzzle
On the island of Knights and Knaves, everyone is a knight or knave.
Knights always tell the truth. Knaves always lie.
Today there is a census on the island!
You are a census taker, going from house to house. Fill in what you
know about each of these three houses.
In house 1: Husband: We are both knaves.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 18 / 18
Knights and Knaves Puzzle
On the island of Knights and Knaves, everyone is a knight or knave.
Knights always tell the truth. Knaves always lie.
Today there is a census on the island!
You are a census taker, going from house to house. Fill in what you
know about each of these three houses.
In house 1: Husband: We are both knaves.
In house 2: Wife: At least one of us is a knave.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 18 / 18
Knights and Knaves Puzzle
On the island of Knights and Knaves, everyone is a knight or knave.
Knights always tell the truth. Knaves always lie.
Today there is a census on the island!
You are a census taker, going from house to house. Fill in what you
know about each of these three houses.
In house 1: Husband: We are both knaves.
In house 2: Wife: At least one of us is a knave.
In house 3: Husband: If I am a knight then so is my wife.
Models of Computation (Sem 2, 2021) Propositional Logic c© University of Melbourne 18 / 18