Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Propositional Logic

No description
by

Adam Rosenfeld

on 2 July 2018

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Propositional Logic

Propositional Logic
Negation
~F
~P
~S
She's not French.
It's not the case that
Pluto is a planet.
It's false that tomorrow
is Sunday.
Conjunction
Gene made a machine and
Joe made it go.

Gene made a machine but
Frances did some dances.

Gene made a machine, however
Heather found a feather.
G & J
G & F
G & H
Disjunction
H
v
G
H
v
T
H
v
L
You can have homefries or you
can have grits.

You can have either homefries
or tater-tots.

Unless you're going to have some
homefries, you should just leave.
Conditional
If it fits, then I sits.

I sits if it fits.

It fits only if I sits.

I sits, provided that
it fits.

It don't always fits, but
when it does, I sits.
F S
F S
F S
F S
F S
Truth Tables for Propositions
Truth Table - A representation of every possible
combination of truth values for the simplest
components of a complex statement.

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

F
T F

T
T F

F
F T

F
F T

F
F T

F
F T

F
2
Rule
n
&
&
Truth Tables for Arguments
We can use truth tables to determine whether or not an argument is valid.
Valid - if the premises
are true the con-
clusion MUST be
true.
OR
Valid - there's no way
for the conclusion to
be false if the pre-
mises are true.
If they serve pork at the dinner, then I won't eat.
If I don't eat, then we'll need to stop for food on the way home.
Therefore, if they serve pork at the dinner, then we'll need to stop for food on the way home.
If Darren knowingly plagiarizes an assignment, then he deserves a grade of zero for that assignment.
Darren did not knowingly plagiarize this assignment.
Therefore, Darren does not deserve a grade of zero for that assignment.
T
F
T
T
F
F
T
T
F
T
F
T
INVALID!
F
F
T
T
F
F
T
T
F
F
T
T
T
T
T
T
F
F
T
T
F
F
T
T
T
T
T
F
T
T
T
F
T
F
T
F
T
T
T
T
VALID!
Which means...
If we can find a line on the truth table where the premises are TRUE and the conclusion is FALSE, then we know the argument is INVALID!!!
Proofs by "Natural Deduction"
Say we want to prove a certain conclusion from a collection of premises, but it's not immediately clear how, and a truth table would be inconvenient...
We can prove that our conclusion follows validly from its premises by taking a series of smaller steps that we know are valid.
Some Basic Rules of Inference
Modus Ponens
P Q
P
Q
P Q / P // Q
T
T
T
T T
T
F
F
T F
F
T
T
F T
F
T
F
F F
Valid!!!
Modus Tolens
P Q
~Q
~P
P Q / ~Q // ~P
T
T
T
F
T
F
T
T
F
F
T
F
F
T
F
T
T
F
T
T
F
F
T
F
T
F
T
F
Valid!!!
Disjunctive Syllogism
P v Q
~P
Q
P v Q / ~P // Q
T
T
T
F
T
T
T
T
F
F
T
F
F
T
T
T
F
T
F
F
F
T
F
F
Valid!!!
(MP)
(MT)
(DS)
Hypothetical Syllogism
P Q
Q R
P R
P Q / Q R // P R
T
T
T T
T
T T
T
T
T
T
T T
F
F T
F
F
T
F
F F
T
T T
T
T
T
F
F F
T
F T
F
F
F
T
T T
T
T F
T
T
F
T
T T
F
F F
T
F
F
T
F F
T
T F
T
T
F
T
F F
T
F F
T
F
Valid!!!
(HS)
If Aaron gets the job, then Ben won't get the job.
If Carol gives him a good recommendation, then Ben will get the job. Aaron does get the job. Therefore, Carol did not give Ben a good recommendation.
Is this valid?
1) A ~B
2) C B
3) A // ~C
4) ~B 1,3 MP
5) ~C 2,4 MT
VALID!!!
Prove conclusion:
T
from premises:
F v (D T)
,
~F
,
D
1) F v (D T)
2) ~F
3) D // T
4) D T 1,2 DS
5) T 4,3 MP
1) (C M) (R P)
2) (C R) (R M)
3) (C P) ~M
4) C R // ~C
5) R M 2,4 MP
6) C M 4,5 HS
7) R P 1,6 MP
8) C P 4,7 HS
9) ~M 3,8 MP
10) ~C 6,9 MT
More Rules of Inference
Conjunction
(Conj)
P
Q
P & Q
~A
B v C
~A & (BvC)
T U
R S
(T U) & (R S)
Simplification
(Simp)
P & Q
P
(P Q) & (R S)
P Q

~B & (C v D)
C v D
Addition
(Add)

P
P v Q
P & Q
(P & Q) v (R S)
~B
~B v ~(C v D)
Constructive Dilemma
(CD)
(P Q) & (R S)
P v R
Q v S
[H (K v L)] & [(EvF) G]
H v (E v F)
(K v L) v G
~M v N
(~M S)&(N ~T)
S v ~T
1) (N B) & (O C)
2) Q (N v O)
3) Q // B v C
4) N v O 2,3 MP
5) B v C 1,4 CD
1) N (D & W)
2) D K
3) N // N & K
4) D & W 1,3 MP
5) D 4 Simp
6) K 2,5 MP
7) N & K 3,6 Conj
1) (C N) & E
2) D v (N D)
3) ~D // ~C v P
4) N D 2,3 DS
5) ~N 4,3 MT
6) C N 1 Simp
7) ~C 6,5 MT
8) ~C v P 7 Add
Using Assumptions in Formal Proofs
The basic principle behind any natural deduction is to show that the conclusion must be true without making any other assumptions besides the truth of the premises.
However...
There are some very useful natural deduction strategies that make use of
additional
assumptions.
We just have to make sure we're very careful about how we use these additional assumptions.
Conditional Proof
If high-tech products are exported to Russia, then domestic industries will benefit. If the Russians can effectively utilize high-tech products, then their standard of living will improve. Therefore, if high-tech products are exported to Russia and the Russians can effectively utilize them, then their standard of living will improve and domestic industries will benefit.
1) H D
2) U S // (H & U) (S & D)
3) H & U ASSUMP
4) H 3 Simp
5) D 1,4 MP
6) U 3, Simp
7) S 2,6 MP
8) S & D 7,5 Conj
9) (H&U) (S&D) 3-8 CP
If I can prove that something (S) follows from an assumption (A), then I can prove the conditional statement, "If A, then S."
Proof by Cases
If I have a disjunction, and I can show that the same statement follows if I assume
either
disjunct, then I can prove the statement must follow.
1) P v ~Q
2) P R
3) ~R Q // R
4) P ASSUMP
5) R 2,4 MP
6) ~Q ASSUMP
7) R 3,6 MT
8) R 1,4-7 PBC
Reductio Ad Absurdum
If I can show that assuming the negation of my conclusion leads to a naked contradiction, then I can prove my conclusion.
1) (A v B) (C & D)
2) C ~D // ~A
3) A ASSUMP
5) C & D 1,4 MP
6) C 5 Simp
7) ~D 2,6 MP
8) D 5 Simp
4) A v B 3 Add
9) D & ~D 7,8 Conj
10) ~A 3-9 RAA
n=1
T
F
T
F
T
F
n=2
T
F
T
F
T
F
T
F
n=3
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
n=4
Every time we add a new variable,
we double the number of lines in our truth table
Conditional Proof
If I can prove that something (S) follows from an assumption (A), then I can prove the conditional statement, "If A, then S."
Proof by Cases
If I have a disjunction, and I can show that the same statement follows if I assume
either
disjunct, then I can prove the statement must follow.
Reductio Ad Absurdum
If I can show that assuming the negation of my conclusion leads to a naked contradiction, then I can prove my conclusion.
Full transcript