Introduction to Logic
Michael Genesereth and Eric Kao
Stanford University
Propositional Logic
1
Talking Head
Talking Head
2
Propositional Logic Syntax
Propositional Sentences
Simple Sentences
express simple facts about the world
Compound sentences
express logical relationships
among simpler sentences of which composed
3
Simple Sentences
In Propositional Logic, simple sentences take the
form of atomic symbols, called proposition constants.
By convention (in this course), proposition constants
are written as strings of letters, digits, and the special
character _.
Examples: Non-Examples:
raining 324567
r32aining raining-or-snowing
rAiNiNg
raining_or_snowing
Compound Sentences I
Negations:
(¬p)
The argument of a negation is called the target.
Conjunctions:
(p ∧ q)
The arguments of a conjunction are called conjuncts.
Disjunctions:
(p ∨ q)
The arguments of a disjunction are called disjuncts.
4
Compound Sentences II
Implications:
(p ⇒ q)
The left argument of an implication is the antecedent.
The right argument is the consequent.
Equivalences / Biconditionals:
(p ⇔ q)
Nesting
Note that compound sentences can be nested inside of
other compound sentences.
((p ∧ q) ∧ r)
((p ∨ q) ∨ r)
(((p ∧ q) ∧ r) ⇒ ((p ∨ q) ∨ r))
5
Parentheses
Parentheses are messy and sometimes unnecessary.
(((p ∧ q) ∨ r) ⇒ ((p ∨ q) ∧ r))
Dropping Parentheses makes things simpler.
(p ∧ q) becomes p ∧ q
But it can lead to ambiguities.
((p ∧ q) ∨ r) becomes p ∧ q ∨ r
(p ∧ (q ∨ r)) becomes p ∧ q ∨ r
Precedence
Parentheses can be dropped when the structure of an
expression can be determined by precedence.
¬
∧
∨
⇒⇔
6
Using Precedence
An operand surrounded by two operators associates
with the operator of higher precedence. If
surrounded by operators of equal precedence, the
operand associates with the operator to the right.
p∧q∨r → ((p ∧ q) ∨ r)
p∨q∧r → (p ∨ (q ∧ r))
p⇒q⇒r → (p ⇒ (q ⇒ r))
p⇔q⇐r → (p ⇔ (q ⇒ r))
¬p ∧ q → ((¬p) ∧ q)
Propositional Languages
A propositional vocabulary is a set/sequence of
proposition constants.
Given a propositional vocabulary, a propositional
sentence is either (1) an individual proposition
constant or (2) a compound sentence formed from
simpler sentences (as previously defined) and that’s
all.
A propositional language is the set of all
propositional sentences that can be formed from a
propositional vocabulary.
7
Exercise
8
Propositional Logic Semantics
Talking Head
9
Truth Assignment
A propositional truth assignment is an association
between the proposition constants in a propositional
language and the truth values true or false. For
simplicity, in what follows we use 1 as a synonym for
true and 0 as a synonym for false.
⎯i →1
p ⎯ pi = 1
⎯i → 0
q ⎯ qi = 0
⎯i →1
r ⎯ ri = 1
Sentential Truth Assignment
A sentential truth assignment is an association
between arbitrary sentences in a propositional
language and the truth values 1 and 0.
pi = 1 (p ∨ q)i = 1
qi = 0 (q ∨ ¬r)i = 0
ri = 1 ((p ∨ q) ∧ ¬(q ∨ ¬r))i = 1
Each propositional truth assignment leads to a
particular sentential truth assignment by application
of operator semantics.
10
Negation
Negation:
φ ¬φ
1 0
0 1
For example, if the truth value of p is 0, then the truth
value of ¬p is 1.€
For example, if the truth value of (p∧q) is 1, then the
truth value of ¬(p∧q) is 0.
Conjunction
Conjunction:
φ ψ φ ∧ψ
1 1 1
1 0 0
0 1 0
0 0 0
11
Disjunction
Disjunction:
φ ψ φ ∨ψ
1 1 1
1 0 1
0 1 1
0 0 0
NB: The type of disjunction here is called inclusive
or, which says that a disjunction is true if and only if
€
at least one of its disjuncts is true. This contrasts with
exclusive or, which says that a disjunction is true if
and only if an odd number of its disjuncts is true.
Implication
Implication:
φ ψ φ ⇒ψ
1 1 1
1 0 0
0 1 1
0 0 1
NB: The semantics of implication here is called
material implication. An implication is true if the
antecedent is€ false, whether or not there is a
connection to the consequent.
If George Washington is alive, I am a billionaire.
12
Equivalence
Equivalence:
φ ψ φ ⇔ψ
1 1 1
1 0 0
0 1 0
0 0 1
Evaluation Procedure
Start with a propositional truth assignment and a
sentence.
(1) Replace proposition constants by their truth
values.
(2) Use operator semantics to simplify compound
sentences with truth values as arguments.
(3) Repeat this inside-out fashion to produce a value
for the sentence as a whole.
13
Evaluation Example
Interpretation i:
pi = 1
qi = 0
ri = 1
Compound Sentence
(p ∨ q) ∧ (¬q ∨ r)
€
More Complex Example
p
pi = 1 q
qi = 1 r
ri = 1
(r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q)
(1 ∧ ((1 ∧ ¬1) ∨ (¬1 ∧ 1))) ∨ (1 ∧ 1)
(1 ∧ ((1 ∧ 0) ∨ (0 ∧ 1))) ∨ (1 ∧ 1)
(1 ∧ (0 ∨ 0)) ∨ 1
(1 ∧ 0) ∨ 1
0∨1
1
14
Exercise
Satisfaction and Falsification
A truth assignment satisfies a sentence if and only if it
assigns the value 1 to the sentence.
A truth assignment falsifies a sentence if and only if it
assigns the value 0 to the sentence.
A truth assignment satisfies a set of sentences if and
only if it satisfies every element in the set.
A truth assignment falsifies a set of sentences if and
only if it falsifies at least one element in the set.
15
Satisfaction
Evaluation Versus Satisfaction
Evaluation:
pi = 1 ( p ∨ q)i = 1
qi = 0 (¬q)i = 1
Satisfaction:
€ €
( p ∨ q)i = 1 pi = 1
i i
(¬q) = 1 q = 0
€ €
16
Example
p
pi = ? q
qi = ? r
ri = ?
((r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q))i = 1
Truth Tables
A truth table is a table of all possible truth assignments
for the proposition constants in a language.
p q r
1 1 1
1 1 0 One column per constant.
1 0 1
1 0 0
One row per truth assignment.
0 1 1
For a language with n constants,
0 1 0 there are 2n truth assignments.
0 0 1
0 0 0
€ 17
Satisfaction Procedure
Method to find propositional truth assignments that
satisfy a given set of sentences:
(1) Form a truth table for the proposition constants
and add columns for each sentence in our set.
(2) Evaluate each sentence for each of the rows of the
truth table.
(3) Any row that satisfies all sentences in the set is a
solution to the problem.
Satisfaction Problem
Find a truth assignment that satisfies the following set
of sentences.
{q ⇒ r, p ⇒ q ∧ r, ¬r}
18
Satisfaction Example (start)
p q r q⇒r p⇒q∧r ¬r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
€
Satisfaction Example (continued)
p q r q⇒r p⇒q∧r ¬r
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 1
0 1 1 1
0 1 0 0
0 0 1 1
0 0 0 1
€
19
Satisfaction Example (continued)
p q r q⇒r p⇒q∧r ¬r
1 1 1 1 1
1 1 0 0 0
1 0 1 1 0
1 0 0 1 0
0 1 1 1 1
0 1 0 0 1
0 0 1 1 1
0 0 0 1 1
€
Satisfaction Example (concluded)
p q r q⇒r p⇒q∧r ¬r
1 1 1 1 1 0
1 1 0 0 0 1
1 0 1 1 0 0
1 0 0 1 0 1
0 1 1 1 1 0
0 1 0 0 1 1
0 0 1 1 1 0
0 0 0 1 1 1
€
20
Exercise
Properties of Sentences
21
Talking Head
Properties of Sentences
A sentence is valid if and only if
Valid
every interpretation satisfies it.
A sentence is contingent if and only if
Contingent some interpretation satisfies it and
some interpretation falsifies it.
Unsatisfiable A sentence is unsatisfiable if and
only if no interpretation satisfies it.
22
Properties of Sentences
Valid
} Aif itsentences is satisfiable if and only
is either valid or contingent.
Contingent
}Aif itsentences is falsifiable if and only
is contingent or unsatisfiable.
Unsatisfiable
Example of Validity 1
p q r ( p⇒q) (q⇒r ) ( p⇒q)∨(q⇒r )
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
€
23
Example of Validity 2
p q r ( p⇒q) (q⇒r ) ( p⇒q)∨(q⇒r )
1 1 1 1 1
1 1 0 1 0
1 0 1 0 1
1 0 0 0 1
0 1 1 1 1
0 1 0 1 0
0 0 1 1 1
0 0 0 1 1
€
Example of Validity 3
p q r ( p⇒q) (q⇒r ) ( p⇒q)∨(q⇒r )
1 1 1 1 1
1 1 0 1 0
1 0 1 0 1
1 0 0 0 1
0 1 1 1 1
0 1 0 1 0
0 0 1 1 1
0 0 0 1 1
€
24
Example of Validity 4
p q r ( p⇒q) (q⇒r ) ( p⇒q)∨(q⇒r )
1 1 1 1 1 1
1 1 0 1 0 1
1 0 1 0 1 1
1 0 0 0 1 1
0 1 1 1 1 1
0 1 0 1 0 1
0 0 1 1 1 1
0 0 0 1 1 1
€
More Validities
Double Negation:
p ⇔ ¬¬p
deMorgan's Laws:
¬(p∧q) ⇔ (¬p∨¬q)
¬(p∨q) ⇔ (¬p∧¬q)
Implication Introduction:
p ⇒ (q ⇒ p)
Implication Distribution
(p ⇒ (q ⇒ r)) ⇒ ((p ⇒ q) ⇒ (p ⇒ r))
25
Exercise
Logical Entailment
26
Talking Head
Logical Entailment
A set of premises Δ logically entails a conclusion ϕ
(written as Δ |= ϕ) if and only if every interpretation
that satisfies the premises also satisfies the
conclusion.
{p} |= (p ∨ q)
{p} |# (p ∧ q)
{p, q} |= (p ∧ q)
27
Logical Entailment ≠ Logical Equivalence
{p} |= (p ∨ q)
{p ∨ q)} |# p
Analogy in arithmetic: inequalities rather than equations
Truth Table Method
Method for computing whether a set of premises
logically entails a conclusion.
(1) Form a truth table for the proposition constants
and add a column for the premises and a column
for the conclusion.
(2) Evaluate the premises for each row in the table.
(3) Evaluate the conclusion for each row in the table.
(4) If every row that satisfies the premises also
satisfies the conclusion, then the premises
logically entail the conclusion.
28
Example
Does p logically entail (p ∨ q)?
p q p p∨q
1 1 1 1
1 0 1 1
0 1 0 1
0 0 0 0
Example
Does p logically entail (p ∧ q)?
p q p p∧q
1 1 1 1
1 0 1 0
0 1 0 0
0 0 0 0
29
Example
Does {p,q } logically entail (p ∧ q)?
p q p q p∧q
1 1 1 1 1
1 0 1 0 0
0 1 0 1 0
0 0 0 0 0
Example
Problem: {(p⇒q), (m ⇒ p∨q), m} |= q?
m p q p⇒q m⇒ p∨q m q
1 1 1 1 1 1 1
1 1 0 0 1 1 0
1 0 1 1 1 1 1
1 0 0 1 0 1 0
0 1 1 1 1 0 1
0 1 0 0 1 0 0
0 0 1 1 1 0 1
0 0 0 1 1 0 0
€ 30
Logical Entailment and Satisfiability
Unsatisfiability Theorem: Δ |= ϕ if and only if Δ ∪
{¬ϕ} is unsatisfiable.
Proof: Suppose that Δ |= ϕ. If a truth assignment satisfies Δ,
then it must also satisfy ϕ. But then it cannot satisfy ¬ϕ.
Therefore, Δ ∪ {¬ϕ} is unsatisfiable.
Suppose that Δ ∪ {¬ϕ} is unsatisfiable. Then every truth
assignment that satisfies Δ must fail to satisfy ¬ϕ, i.e. it must
satisfy ϕ. Therefore, Δ |= ϕ.
Upshot: We can determine logical entailment by
determining unsatisfiability.
31
The Big Game
The Big Game
Stanford people always tell the truth, and Berkeley
people always lie. Unfortunately, by looking at a
person, you cannot tell whether he is from Stanford or
Berkeley.
You come to a fork in the road and want to get to the
football stadium down one fork. However, you do not
know which to take. There is a person standing there.
What single question can you ask him to help you
decide which fork to take?
32
Basic Idea
left su Question Response
1 1
1 0
0 1
0 0
Basic Idea
left su Question Response
1 1 1
1 0 1
0 1 0
0 0 0
33
Basic Idea
left su Question Response
1 1 1 1
1 0 1
0 1 0 0
0 0 0
Basic Idea
left su Question Response
1 1 1 1
1 0 0 1
0 1 0 0
0 0 1 0
34
The Big Game Solved
Question: Is it the case that the left road the way to
the stadium if and only if you are from Stanford?
(left ⇔ su)?
35