FIT2014 Theory of Computation Lecture 2 Propositional Logic
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 2
Propositional Logic
slides by Graham Farr
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 21
Lecture overview
I Propositions
I Logical operations
I Tautologies, logical equivalence
I Disjunctive Normal Form
I Conjunctive Normal Form
I Representing logical statements
2 / 21
Propositions
Definition: A proposition is a statement which is either true or false.
Examples
1 + 1 = 2 — a proposition which is true.
The earth is flat. — a proposition which is false.
It will rain tomorrow. — a proposition.
’Twas brillig, and the slithy toves
did gyre and gimble in the wabe.
From: Lewis Carroll, Through the Looking Glass, and What Alice
Found There, Macmillan, London, 1871.
— not a proposition.
Come and work for us! — not a proposition.
This statement is false. — not a proposition.
For brevity, a proposition may be given a name, which has a truth value, True or False.
For example, let X be the proposition 1 + 1 = 2. Then the truth value of X is True.
3 / 21
Logical operations
Not ¬ (∼, , − )
And ∧ (&)
Or ∨
Implies ⇒ (→)
Equivalence ⇔ (↔)
A connective is a binary logical operation. E.g.: ∧, ∨, ⇒, ⇔.
4 / 21
Negation
P: You have prepared for next week’s tutorial.
¬P: You have not prepared for next week’s tutorial.
Other notation: ∼ P, P, −P
Truth table:
P ¬P
F T
T F
5 / 21
Conjunction
P Radhanath was a computer.
Q Radhanath was a person.
P ∧ Q Radhanath was a computer and a person. Radhanath Sikdar (1813–1870)
http://news.bbc.co.uk/2/hi/south_
asia/3193576.stm
Truth table:
P Q P ∧ Q
F F F
F T F
T F F
T T T
6 / 21
http://news.bbc.co.uk/2/hi/south_asia/3193576.stm
http://news.bbc.co.uk/2/hi/south_asia/3193576.stm
Disjunction
P I will study FIT3155 Advanced Data Structures & Algorithms.
Q I will study MTH3170 Network Mathematics.
P ∨ Q I’ll study FIT3155 or I’ll study MTH3170.
I’ll study at least one of FIT3155 and MTH3170.
Disjunction is sometimes called inclusive-OR, and sometimes written as +.
Truth table:
P Q P ∨ Q
F F F
F T T
T F T
T T T
7 / 21
De Morgan’s Laws
¬(P ∨ Q) = ¬P ∧ ¬Q
¬(P ∧ Q) = ¬P ∨ ¬Q
Can be proved using truth tables:
P Q P ∨ Q ¬(P ∨ Q) ¬P ¬Q ¬P ∧ ¬Q
F F F T T T T
F T T F T F F
T F T F F T F
T T T F F F F
Augustus De Morgan
(1806–1871)
https://mathshistory.st-andrews.
ac.uk/Biographies/De_Morgan/
8 / 21
https://mathshistory.st-andrews.ac.uk/Biographies/De_Morgan/
https://mathshistory.st-andrews.ac.uk/Biographies/De_Morgan/
Conditional
P Stars are visible.
Q The sun has set.
P ⇒ Q If stars are visible then the sun has set.
Stars being visible implies the sun has set.
Stars are visible only if the sun has set.
Stars are visible is sufficient for the sun to have set.
Q ⇐ P same as P ⇒ Q
Also called implication.
9 / 21
Conditional
Truth table:
P Q P ⇒ Q
F F T
F T T
T F F
T T T
P Grace is a COBOL expert.
Q Grace can program.
P ⇒ Q If Grace is a COBOL expert then she can program.
Grace Hopper (1906–1992)
https://www.cs.vassar.edu/
history/hopper
10 / 21
https://www.cs.vassar.edu/history/hopper
https://www.cs.vassar.edu/history/hopper
Biconditional
P The triangle is right-angled.
Q The side lengths satisfy
a2 + b2 = c2. a
c
b
a2 + b2 < c2 a c b a2 + b2 = c2 a c b a2 + b2 > c2
P ⇔ Q The triangle is right-angled if and only if
a2 + b2 = c2.
The triangle being right-angled is a
necessary and sufficient condition
for a2 + b2 = c2.
Q ⇔ P a2 + b2 = c2 is a
necessary and sufficient condition
for the triangle being right-angled.
Truth table:
P Q P ⇔ Q
F F T
F T F
T F F
T T T
11 / 21
Tautologies, logical equivalence
Definitions
A tautology is a statement that is always true.
In other words, the right-hand column of its truth table . . . .
Two statements P and Q are logically equivalent if their truth tables are identical.
In other words, P ⇔ Q is a . . . .
Examples
¬¬P is logically equivalent to P
¬(P ∨ Q) is logically equivalent to ¬P ∧ ¬Q
¬(P ∧ Q) is logically equivalent to ¬P ∨ ¬Q
P ⇒ Q is logically equivalent to ¬P ∨ Q
P ⇔ Q is logically equivalent to (P ⇒ Q) ∧ (P ⇐ Q)
and to (¬P ∨ Q) ∧ (P ∨ ¬Q)
These can all be proved using truth tables.
12 / 21
History
George Boole (1815–1864)
https://mathshistory.st-andrews.ac.uk/Biographies/Boole/
13 / 21
https://mathshistory.st-andrews.ac.uk/Biographies/Boole/
Distributive Laws
P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)
P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
Compare with ordinary algebra:
p × (q + r) = (p × q) + (p × r)
but
p + (q × r) 6= (p + q)× (p + r)
14 / 21
Laws of Boolean algebra
¬¬P = P
¬True = False ¬False = True
P ∧ Q = Q ∧ P P ∨ Q = Q ∨ P
(P ∧ Q) ∧ R = P ∧ (Q ∧ R) (P ∨ Q) ∨ R = P ∨ (Q ∨ R)
P ∧ P = P P ∨ P = P
P ∧ ¬P = False P ∨ ¬P = True
P ∧ True = P P ∨ False = P
P ∧ False = False P ∨ True = True
Distributive Laws
P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
De Morgan’s Laws
¬(P ∨ Q) = ¬P ∧ ¬Q ¬(P ∧ Q) = ¬P ∨ ¬Q
15 / 21
Disjunctive Normal Form (DNF)
X Y P
F F T
¬X ∧ ¬Y
F T T
¬X ∧ Y
T F F
T T T
X ∧ Y
P = (¬X ∧ ¬Y ) ∨ (¬X ∧ Y ) ∨ (X ∧ Y )
Exercise: simplify this as much as possible, using Boolean algebra.
16 / 21
Disjunctive Normal Form (DNF)
X Y P
F F T ¬X ∧ ¬Y
F T T ¬X ∧ Y
T F F
T T T X ∧ Y
P = (¬X ∧ ¬Y ) ∨ (¬X ∧ Y ) ∨ (X ∧ Y )
Exercise: simplify this as much as possible, using Boolean algebra.
16 / 21
Disjunctive Normal Form (DNF)
X Y P
F F T ¬X ∧ ¬Y
F T T ¬X ∧ Y
T F F
T T T X ∧ Y
P = (¬X ∧ ¬Y ) ∨ (¬X ∧ Y ) ∨ (X ∧ Y )
Exercise: simplify this as much as possible, using Boolean algebra.
16 / 21
Disjunctive Normal Form (DNF)
X Y P
F F T ¬X ∧ ¬Y
F T T ¬X ∧ Y
T F F
T T T X ∧ Y
P =
conjunction︷ ︸︸ ︷
(¬X ∧ ¬Y )∨
conjunction︷ ︸︸ ︷
(¬X ∧ Y )∨
conjunction︷ ︸︸ ︷
(X ∧ Y )
Exercise: simplify this as much as possible, using Boolean algebra.
16 / 21
Disjunctive Normal Form (DNF)
X Y P
F F T ¬X ∧ ¬Y
F T T ¬X ∧ Y
T F F
T T T X ∧ Y
P =
conjunction︷ ︸︸ ︷
(¬X ∧ ¬Y )∨
conjunction︷ ︸︸ ︷
(¬X ∧ Y )∨
conjunction︷ ︸︸ ︷
(X ∧ Y )︸ ︷︷ ︸
disjunction
Exercise: simplify this as much as possible, using Boolean algebra.
16 / 21
Disjunctive Normal Form (DNF)
X Y P
F F T ¬X ∧ ¬Y
F T T ¬X ∧ Y
T F F
T T T X ∧ Y
P =
conjunction︷ ︸︸ ︷
(¬X ∧ ¬Y )∨
conjunction︷ ︸︸ ︷
(¬X ∧ Y )∨
conjunction︷ ︸︸ ︷
(X ∧ Y )︸ ︷︷ ︸
disjunction
Exercise: simplify this as much as possible, using Boolean algebra.
16 / 21
Disjunctive Normal Form (DNF)
X Y Z P
F F F T ¬X ∧ ¬Y ∧ ¬Z
F F T F
F T F T ¬X ∧ Y ∧ ¬Z
F T T F
T F F F
T F T T X ∧ ¬Y ∧ Z
T T F T X ∧ Y ∧ ¬Z
T T T F
P = (¬X ∧ ¬Y ∧ ¬Z ) ∨ (¬X ∧ Y ∧ ¬Z ) ∨ ( X ∧ ¬Y ∧ Z ) ∨ ( X ∧ Y ∧ ¬Z )
17 / 21
Disjunctive Normal Form (DNF)
P = (¬X ∧ ¬Y ∧ ¬Z ) ∨ (¬X ∧ Y ∧ ¬Z ) ∨ ( X ∧ ¬Y ∧ Z ) ∨ ( X ∧ Y ∧ ¬Z )
I A literal is an appearance of a variable in which it is either unnegated or negated
just once.
I Example: there are 12 literals in the above expression.
I A logical expression is in DNF if it is a disjunction of conjunctions of literals.
I Every logical expression is equivalent to one in DNF.
I To see this: “just” use the truth table.
I BUT this can be exponentially large (in # of variables).
I In effect, DNF enumerates all situations in which P is True.
I There is another Normal Form that is much more useful for us . . .
18 / 21
Conjunctive Normal Form (CNF)
I A logical expression is in CNF if it is a conjunction of disjunctions of literals.
I E.g.:
disjunction︷ ︸︸ ︷
(¬P ∨ Q)∧
disjunction︷ ︸︸ ︷
(P ∨ ¬Q)︸ ︷︷ ︸
conjunction
I Each disjunction of literals is called a clause.
I Every logical expression is equivalent to one in CNF.
I One way to see this:
Given P,
find the DNF of its negation, ¬P,
then negate it
and use De Morgan’s Laws.
I BUT it is usually much faster, and much less error-prone, to work directly from
the stated conditions that P must satisfy.
I In this unit, CNF will be much more important than DNF.
19 / 21
Conjunctive Normal Form (CNF)
Example:
You are planning a dinner party. Your guest list must have:
I at least one of: Harry, Ron, Hermione, Ginny
Harry ∨ Ron ∨ Hermione ∨ Ginny
I Hagrid only if it also has Norberta
Hagrid⇒ Norberta ¬Hagrid ∨ Norberta
I none, or both, of Fred and George
Fred⇔ George (¬Fred ∨ George) ∧ (Fred ∨ ¬George)
I no more than one of: Voldemort, Bellatrix, Dolores.
¬Voldemort ∨ ¬Bellatrix ∨ ¬Dolores . . .???
20 / 21
Conjunctive Normal Form (CNF)
Example:
You are planning a dinner party. Your guest list must have:
I at least one of: Harry, Ron, Hermione, Ginny
Harry ∨ Ron ∨ Hermione ∨ Ginny
I Hagrid only if it also has Norberta
Hagrid⇒ Norberta ¬Hagrid ∨ Norberta
I none, or both, of Fred and George
Fred⇔ George (¬Fred ∨ George) ∧ (Fred ∨ ¬George)
I no more than one of: Voldemort, Bellatrix, Dolores.
¬Voldemort ∨ ¬Bellatrix ∨ ¬Dolores . . .???
20 / 21
Conjunctive Normal Form (CNF)
Example:
You are planning a dinner party. Your guest list must have:
I at least one of: Harry, Ron, Hermione, Ginny
Harry ∨ Ron ∨ Hermione ∨ Ginny
I Hagrid only if it also has Norberta
Hagrid⇒ Norberta ¬Hagrid ∨ Norberta
I none, or both, of Fred and George
Fred⇔ George (¬Fred ∨ George) ∧ (Fred ∨ ¬George)
I no more than one of: Voldemort, Bellatrix, Dolores.
¬Voldemort ∨ ¬Bellatrix ∨ ¬Dolores . . .???
20 / 21
Conjunctive Normal Form (CNF)
Example:
You are planning a dinner party. Your guest list must have:
I at least one of: Harry, Ron, Hermione, Ginny
Harry ∨ Ron ∨ Hermione ∨ Ginny
I Hagrid only if it also has Norberta
Hagrid⇒ Norberta ¬Hagrid ∨ Norberta
I none, or both, of Fred and George
Fred⇔ George (¬Fred ∨ George) ∧ (Fred ∨ ¬George)
I no more than one of: Voldemort, Bellatrix, Dolores.
¬Voldemort ∨ ¬Bellatrix ∨ ¬Dolores . . .???
20 / 21
Conjunctive Normal Form (CNF)
Example:
You are planning a dinner party. Your guest list must have:
I at least one of: Harry, Ron, Hermione, Ginny
Harry ∨ Ron ∨ Hermione ∨ Ginny
I Hagrid only if it also has Norberta
Hagrid⇒ Norberta ¬Hagrid ∨ Norberta
I none, or both, of Fred and George
Fred⇔ George (¬Fred ∨ George) ∧ (Fred ∨ ¬George)
I no more than one of: Voldemort, Bellatrix, Dolores.
(¬Voldemort ∨ ¬Bellatrix) ∧ (¬Voldemort ∨ ¬Dolores) ∧ (¬Bellatrix ∨ ¬Dolores)
20 / 21
Conjunctive Normal Form (CNF)
(Harry ∨ Ron ∨ Hermione ∨ Ginny)
∧ (¬Hagrid ∨ Norberta)
∧ (¬Fred ∨ George) ∧ (Fred ∨ ¬George)
∧ (¬Voldemort ∨ ¬Bellatrix) ∧ (¬Voldemort ∨ ¬Dolores) ∧ (¬Bellatrix ∨ ¬Dolores)
Challenge: how long would an equivalent DNF expression be?
Reading
See Sipser, pp. 14–15, and top paragraph of p. 302.
21 / 21