Transcript Philosophy 120 Symbolic Logic I H. Hamner Hill

Today’s Topics
• Thinking about proofs
• Strategies and hints
• Conditional and Indirect Proof (Reductio ad
Absurdum)
– Solving puzzles with IP
• Common errors to avoid
• Notes on symbolization and proof construction
Thinking About Proofs
• Proofs in logic work just like proofs in
geometry
• The 18 rules we have allow us to
manipulate a basic set of assumptions (the
premises) so as to show that the conclusion
is a logical consequence of them.
• A proof is a set of instructions on how to get
from the premises to the conclusion.
• Constructing a proof is like giving
instructions. The question is “How do I get
there (the conclusion) from here (the
premises)?”
• The rules are the allowable moves or turns
you can take.
• Proceed stepwise. Suppose you want to get
to D from A, B, and C. Well, if from A and
B you can get to E, and from E and C you
can get to D, you have your instructions.
• That is all there is to constructing proofs
Basic Strategic Hints
• Argument forms are patterns. Learn the
patterns and look for them.
• Inference rules can be grouped according to the
types of statements on which they operate.
• Short statements are your friends!
• Work backwards from the conclusion.
• BE FLEXIBLE. When stuck, experiment. Try
steps and then search for familiar patterns.
Develop Goal Lines and work
toward them.
• Ask yourself, “What line, if I had it, would
allow me to get to the conclusion?”
• Make that line a goal and work towards it.
• Think in terms of equivalences—ask
yourself “To what is the conclusion (or the
line you want) equivalent?” Can you get to
that Version?
• If you need one disjunct of a disjunction, scan the
remaining lines for the negation of the other
disjunct and use DS
• If you need the consequent of a conditional, look
for the antecedent and use MP
• If you need the negation of the antecedent of a
conditional, think MT
• If there is a statement letter in the conclusion that
occurs nowhere in the premises, use addition
A Few More Strategic Hints
• Simplify conjucntions
• Use DeMorgan to turn negations of disjunctions
into conjunctions that can be simplified
• Use commutation and association to isolate
components that fit other patterns (DS or Simp)
• To derive a conditional, think HS or MI
• To derive a disjunction, think ADD or CD
Here’s How It Works
• Consider the argument A  (B ▼ C), A, ~B 
CvE
• The first thing to notice is that since ‘E’ does
not occur in the premises, you will have to use
Addition on ‘C’ to get the conclusion. So, how
to get ‘C’?
• Since you have ‘~B’ if you could get the
consequent of ‘A  (B ▼ C)’ then you could
use DS to get ‘C’.
•
But since you have ‘A’, the antecedent of
the conditional, you can get ‘B v C’.
1.
2.
3.
4.
5.
6.
•
A  (B v C) pr
deduce C v E
A
pr
~B
pr
(B v C)
1,2 MP
C
3,4 DS
CvE
5 addition
And that’s the proof!
Try a Few
• Download the Handout on Constructing Proofs
and work a few problems. Discuss your answers
on the bulletin board.
• Remember, there are ALWAYS several correct
ways to construct a proof. That you see one path,
and I see another says more about us
psychologically than it says about us logically.
Constructing proofs is NOT a mechanical activity,
it requires creativity and artistry.
• OK, now move on and try the Constructing Proofs
(difficult) Handout.
Consider the following argument:
• A  B  A  (A  B)
• Some systems include us the rule absorption that enables us to
construct a proof for this argument, but many systems of logic do
not include that rule.
• If there is valid argument for which one cannot construct a
proof, one’s system of logic is incomplete.
• Such systems need additional rules or methods to guarantee that
a proof can be constructed for any valid argument.
• Conditional Proof and Reductio Ad Absurdum are 2 such
methods
Conditional Proof and Reductio
Ad Absurdum
• Download the Handout Conditional Proof
Study Guide and read it carefully. This is a
deceptively simple method, but it takes time
to master.
• In the history of the West, Conditional and
Indirect proof are of major importance.
Indirect Proof lead directly to the
development of non-Euclidean geometry
Conditional Proof
• Conditional Proof allows you to construct
ANY conditional.
• First, you are allowed to make new
ASSUMPTIONS
• You can assume anything, any time
• HOWEVER, you must discharge your
assumptions before your proof is complete
• To use Conditional Proof, begin by
assuming the antecedent of the conditional
you want.
• Then, using our 18 rules of inference and
equivalence, derive a line identical to the
consequent of the conditional you want.
• Now, discharge the assumption by deriving
a conditional whose antecedent was your
assumption and whose consequent is the
preceding line
• Justify the new conditional as following
from a series of lines (e.g. 2-5) and the rule
CP.
• The scope of the assumption you made is
marked by a vertical line beginning at the
assumption and ending with a horizontal
line directly above the conditional you
derive.
Here’s How It Works:
1. A  B
2. A
3. B
4. A  B
 A  (A  B)
AP
1,2
2,3
5. A  (A  B)
2-4 CP
MP
Conj
Lines 2-4 serve to justify line 5,
but they cannot be used in any
subsequent line of the proof, they
are closed off from the rest of the
proof, but you are free to use line
5 as you need it.
When using conditional proof, all
you are doing is showing that IF
a particular claim is true (the
assumption) then another claim
follows from it. But that is all
that the derived conditional says.
Points to remember:
• CP can only be used to justify a conditional
• The antecedent of that conditional MUST be the
assumption you made
• The consequent of that conditional MUST be the
line immediately preceding the discharge of the
assumption
• You can make multiple assumptions and nest
them, but the assumption made last must be
discharged first
Conditional Proof greatly
simplifies the task of deriving
many conditionals.
1. p  (q  r)
pr prove p  q
2. ~p v (q  r)
1 MI
3. (~p v q)  (~p v r)
4. ~p v q
5. p  q
2 Dist
3 Simp
4 MI
Here’s the CP version:
1. p  (q  r)
>2. p
3. q  r
4. q
5. p  q
Premise
Assumption (AP)
1,2 MP
3 Simp
2-4 CP
Yes, the CP takes the same
number of steps, but you don’t
need distribution and 2 steps of
implication.
Reductio Ad Absurdum (RAA)
• Recall that we can show an argument valid
by showing that the negation of the
conclusion is inconsistent with the truth of
the premises.
• This method of argument called Reductio ad
Absurdum or Indirect Proof (IP) formalizes
this insight
• Indirect Proof is one of the most powerful
tools available to the mathematician. We
know what must be the case by showing
what cannot be the case!
Begin an RAA by assuming the negation of
the conclusion of the argument.
Then, using the standard rules, derive a
contradiction (a line of the form 'p  ~p').
Now, discharge the assumption and derive the
conclusion of the argument by a sequence
of lines beginning with the assumption of
the negation of the conclusion and ending
with the derived contradiction.
A vertical line beginning with the assumption
and ending with the contradiction marks the
scope of the assumption.
RAA works because the derived contradiction
is obviously false. Since it is impossible to
derive falsity from truth (and the premises
are assumed to be true), the source of the
falsity obvious in the contradiction must be
the assumption of the negation of the
conclusion. But if that assumption is false,
then the conclusion is true if the premises
are, and that is just the definition of a valid
argument.
Hints for using CP:
• Remember, the line derived MUST be a
conditional whose antecedent was your
assumption.
• Use 2 CP subproofs followed by CONJ and
MEI to derive a biconditional.
• You can do multiple steps of CP, including
nesting assumptions
Hints for using RAA:
• Scan the premises to identify a likely contradiction.
• Remember that you are looking for a contradiction—
IP provides you with an overall strategy.
• Remember to discharge your assumption!
Sometimes you may derive what you are looking for
(your overall goal) within the scope of the
assumption, but you cannot use it.
• Download the Handout Conditional and Indirect
Proof Exercises and work the problems.
RAA and Problem Solving
• Many standardized intelligence or aptitude
tests (e.g. the LSAT, the GRE, the MCAT)
include problems which can be solved
easily using indirect proof as a strategy.
• Use the strategy to discover when certain
claims can’t be right (namely, when they
lead directly to contradictions), and then use
that information to determine which claims
are correct.
Solving Puzzles Using IP
• Messrs. Fireman, Guard, and Driver are the
fireman, guard, and driver on a train. Each man
has only one job. When I tried to find out who
was what, I was given these four "facts":
•
(1) Mr. Driver is not the guard.
•
(2) Mr. Fireman is not the driver.
•
(3) Mr. Driver is the driver.
•
(4) Mr. Fireman is not the guard.
• It then transpired that, of the above four
statements, only one is true. Who is what?
• Solve this puzzle by applying IP. In order
to determine which of the 4 statements is
true, begin by assuming one to be true and
then look for a contradiction. Finding it lets
you know that statement is false. If you
assume (1) to be true, it leads to the
contradiction that Mr. Fireman is both the
driver and the guard, which is impossible.
Do you have it yet?
• Mr. Driver is the guard
• Mr. Fireman is the driver
• Mr. Guard is the fireman
Common Errors to AVOID:
• Trying to use an inference rule on a part of a
line
• Errors concerning the scope of a negation
• Confusing the role of tildes in WFF’s with
their role in argument forms
• Reluctance to use addition and distribution
• Reluctance to use CP and IP
• Attempting the impossible
Symbolizing Arguments and
Constructing Proofs
• Symbolize carefully—correctly identify the
premises and the conclusion
• Pay attention to detail, particularly when
symbolizing conditionals
• Symbolize in ways that suit your strengths
and preferred strategies (e.g., if you like DS,
symbolize ‘unless’ with a wedge)
Remember: You can always go
back and change your
symbolization.
HINT: Test your symbolization
for validity with a truth value
analysis. If you have symbolized
incorrectly and the argument for
which you are attempting to
construct a proof is non-valid,
you will lose your mind.