9/9/14
Proposi'onal
Logic
Proofs
• An
argument
is
a
sequence
of
proposi'ons:
Inference Rules ² Premises
(Axioms)
are
the
first
n
proposi'ons
(Rosen, Section 1.5) ² Conclusion
is
the
final
proposi'on.
TOPICS • An
argument
is
valid
if
(
p
1
∧
p
2
∧
...∧
p
n
)
→
q
is
a
tautology,
given
that
pi
are
the
premises
• Logic Proofs (axioms)
and
q
is
the
conclusion.
² via Truth Tables €
² via Inference Rules
Proof Method #1: Truth Table Example
Proof
by
Truth
Table
s = ((p v q) ∧ (¬p v r)) → (q v r)
n If the conclusion is true in the truth table
whenever the premises are true, it is p q r ¬p p v q ¬p v r q v r (p v q)∧ (¬p v r) s
proved 0 0 0 1 0 1 0 0 1
n Warning: when the premises are false, the 0 0 1 1 0 1 1 0 1
conclusion my be true or false
0 1 0 1 1 1 1 1 1
n Problem: given n propositions, the truth 0 1 1 1 1 1 1 1 1
table has 2n rows 1 0 0 0 1 0 0 0 1
n Proof by truth table quickly becomes 1 0 1 0 1 1 1 1 1
infeasible 1 1 0 0 1 0 1 0 1
1 1 1 0 1 1 1 1 1
3 4
1
9/9/14
Proof
Method
#2:
Rules
of
Inference
Inference
proper'es
n A
rule
of
inference
is
a
pre-‐proved
rela'on:
n Inference
rules
are
truth
preserving
any
'me
the
leJ
hand
side
(LHS)
is
true,
the
n If
the
LHS
is
true,
so
is
the
RHS
right
hand
side
(RHS)
is
also
true.
n Applied
to
true
statements
n Axioms
or
statements
proved
from
axioms
n Therefore,
if
we
can
match
a
premise
to
the
n Inference
is
syntac'c
LHS
(by
subs'tu'ng
proposi'ons),
we
can
n Subs'tute
proposi'ons
assert
the
(subs'tuted)
RHS
n if
p
replaces
q
once,
it
replaces
q
everywhere
n If
p
replaces
q,
it
only
replaces
q
n Apply
rule
5 6
Example
Rule
of
Inference
Rules
of
Inference
Modus
Ponens
p
p→q
( p ∧ ( p → q)) → q
∴ q
p q p → q p ∧ ( p → q) ( p ∧ ( p → q)) → q
€ 0 0 1 0 1
0 1 1 € 0 1
€ € € € €
1 0 0 0 1
1 1 1 1 1
7 8
2
9/9/14
Logical
Equivalences
Modus
Ponens
n If p, and p implies q, then q
Example:
p = it is sunny, q = it is hot
p → q, it is hot whenever it is sunny
“Given the above, if it is sunny, it must
be hot”.
9 10
Modus
Tollens
Hypothe'cal
Syllogism
n If not q and p implies q, then not p n If p implies q, and q implies r, then
Example: p implies r
p = it is sunny, q = it is hot Example:
p → q, it is hot whenever it is sunny p = it is sunny, q = it is hot, r = it is dry
“Given the above, if it is not hot, it p → q, it is hot when it is sunny
cannot be sunny.” q → r, it is dry when it is hot
“Given the above, it must be dry when
it is sunny”
11 12
3
9/9/14
Disjunc've
Syllogism
Resolu'on
n If p or q, and not p, then q n If p or q, and not p or r, then q or r
Example: Example:
p = it is sunny, q = it is hot p = it is sunny, q = it is hot, r = it is dry
p ∨ q, it is hot or sunny p ∨ q, it is sunny or hot
“Given the above, if it not sunny, but it ¬p ∨ r, it is not hot or dry
is hot or sunny, then it is hot” “Given the above, if it is sunny or hot, but
not sunny or dry, it must be hot or dry”
Not obvious!
13 14
Addi'on
Simplifica'on
n If p then p or q n If p and q, then p
Example: Example:
p = it is sunny, q = it is hot p = it is sunny, q = it is hot
p ∨ q, it is hot or sunny p ∧ q, it is hot and sunny
“Given the above, if it is sunny, it must “Given the above, if it is hot and sunny,
be hot or sunny” it must be hot”
Of course! Of course!
15 16
4
9/9/14
A
Simple
Proof
Conjunc'on
Given
X,
X→Y,
Y
→Z,
¬Z
∨ W,
prove
W
n If p and q, then p and q
Example: Step Reason
p = it is sunny, q = it is hot 1. x→y Premise
2. y→z Premise
p ∧ q, it is hot and sunny
3. x→z Hypothetical Syllogism (1, 2)
“Given the above, if it is sunny and it is x
4. Premise
hot, it must be hot and sunny” z
5. Modus Ponens (3, 4)
Of course! 6. ¬z ∨ w Premise
7. w Disjunctive Syllogism (5, 6)
17 18
A
Simple
Proof
Setup
the
proof
“In
order
to
sign
up
for
CS161,
I
must
complete
STEP
2)
Extract
axioms
and
conclusion.
CS160
and
either
M155
or
M160.
I
have
not
completed
M155
but
I
have
completed
CS161.
n Axioms:
Prove
that
I
have
completed
M160.”
n A → B ∧ (C ∨ D)
STEP
1)
Assign
proposi'ons
to
each
statement.
n A
n A
:
CS161
n ¬C
n B
:
CS160
n Conclusion:
n C
:
M155
n D
n D
:
M160
19 20
5
9/9/14
Now
do
the
Proof
Another
Example
STEP
3)
Use
inference
rules
to
prove
conclusion.
Step Reason Given: Conclude:
1. A → B ∧ (C ∨ D) Premise p→q ¬q → s
2. A Premise
¬p → r
3. B ∧ (C ∨ D) Modus Ponens (1, 2)
r→s
4. C∨D Simplification
5. ¬C Premise
6. D Disjunctive Syllogism (4, 5)
21 22
Proof using Rules of Inference and
Proof
of
Another
Example
Logical Equivalences
Step Reason Prove: ¬(p∨(¬p∧q)) ≡ (¬p∧¬q)
1. p → q Premise
¬(p∨(¬p∧q)) ≡ ¬p ∧ ¬(¬p∧q) n By 2nd DeMorgan’s
2. ¬q → ¬p Implication law (1) ≡ ¬p ∧(¬(¬p)∨¬q) n By 1st DeMorgan’s
≡ ¬p∧(p∨¬q) n By double negation
3. ¬p → r Premise ≡ (¬p∧p) ∨ (¬p∧¬q) n By 2nd distributive
4. ¬q → r Hypothetical syllogism (2, 3) ≡ F ∨ (¬p∧¬q) n By definition of ∧
≡ (¬p∧¬q) ∨ F n By commutative law
5. r → s Premise ≡ (¬p∧¬q) n By definition of ∨
6. ¬q → s Hypothetical syllogism (4, 5)
23 24
6
9/9/14
Example
of
a
Fallacy
Example
of
a
fallacy
q n If q, and p implies q, then p
( q ∧ ( p → q )) → p p→q
Example:
∴ p
p = it is sunny, q = it is hot
p q p → q q ∧ ( p → q ) ( q ∧ ( p → q )) → p p → q, if it is sunny, then it is hot
0 0 1 0 1 “Given the above, just because it is
0 1 1 1 0 hot, does NOT necessarily mean it is
€ € €
1 0 0 0 1 sunny.
1 1 1 1 1
This is not a tautology, therefore the argument is not valid
25 26
