# Alice's Adventures in Wonderland & Through the Looking-Glass

Tags: Deductive Reasoning, Computer Science, Problem Solving, true or false, prime integers, prime integer, Penn Jillette, Bob Murch, hidden assumptions, spirit board, Propositional Logic, John Locke, Zebras, computer scientist, Modus ponens, Socrates, argument, McQuain Validity, Grace Hopper, Giraffes, Conjunction Elimination, Monkeys
Content: Propositional Logic
Deductive Reasoning 1
Logic is the anatomy of thought.
John Locke
When introduced at the wrong time or place, good logic may be the worst enemy of good teaching. George Polya
Contrariwise,' continued Tweedledee, 'if it was so, it might be; and if it were so, it would be; but as it isn't, it ain't. That's logic. Lewis Carroll, Alice's Adventures in Wonderland & Through the Looking-Glass
[email protected]
Intro problem solving in computer science
Propositions
Deductive Reasoning 2
A proposition is a statement that is true or false:
Di-hydrogen monoxide is liquid at a temperature of 0o Fahrenheit.
The Gregorian calendar uses twelve months.
Every even integer greater than 2 can be expressed as the sum of two prime integers.
Not all declarative statements are propositions: Fried chicken livers taste wonderful. This sentence is false. There are a terrible lot of lies going about the world, and the worst of it is that half of them are true. Winston Churchill
[email protected]
Intro Problem Solving in Computer Science
Propositional Logic
Deductive Reasoning 3
Propositional logic is concerned with the "algebra" of propositions.
We may form new propositions from old ones by performing certain "algebraic" operations. Consider the following two rather dull propositions: 51 is a prime integer.
The set {3, 5, 7, 11} contains only prime integers.
Then the following are also propositions: 51 is not a prime integer. 51 is a prime integer or the set {3, 5, 7, 11} contains only prime integers. 51 is a prime integer and the set {3, 5, 7, 11} contains only prime integers.
[email protected]
Intro Problem Solving in Computer Science
Propositional Logic
Deductive Reasoning 4
And so are the following: If 51 is a prime integer, then the set {3, 5, 7, 11} contains only prime integers.
If the set {3, 5, 7, 11} contains only prime integers, then 51 is a prime integer.
If the set {3, 5, 7, 51} contains only prime integers, then 51 is a prime integer.
[email protected]
Intro Problem Solving in Computer Science
Logical Connectives
Deductive Reasoning 5
Suppose that P and Q are propositions, then so are the following:
not P
negation
P
P and Q conjunction P Q
P or Q
disjunction
PQ
if P then Q implication P Q
[email protected]
Intro Problem Solving in Computer Science
True or False?
Deductive Reasoning 6
Suppose that P and Q are propositions, then:
not P P and Q P or Q if P then Q
is true if and only if P is false is true if and only if P is true and Q is true is true if and only if P is true, or Q is true, or both are true is true if and only if P is false or Q is true
P not P TF FT
PQ TT TF FT FF
P and Q T F F F
PQ TT TF FT FF
P or Q T T T F
PQ TT TF FT FF
if P then Q T F T T
[email protected]
Intro Problem Solving in Computer Science
True or False?
Deductive Reasoning 7
Notes:
- "or" is inclusive; that is it's true as long as at least one "side" is true
- "if... then" is false only in the case that the antecedent is true and the consequent is false
- "if... then" has absolutely nothing to do with causation
- If you're confused by the truth table for "if...then", consider such statements as being a contract. If you say
If today is Wednesday then I will give you a dollar.
precisely what are your obligations if today is not Wednesday?
[email protected]
Intro Problem Solving in Computer Science
Tautologies
Deductive Reasoning 8
A propositional expression is a tautology if the expression is always true, no matter what truth values its components may have.
Example:
P or not P.
Now, if P is true then not P must be false, and therefore the expression is true (by definition of "or").
On the other hand, if P is false then not P must be true, and again the expression is true.
This may also be expressed by the construction of a truth table that considers all cases:
P P or not P
T
T
F
T
[email protected]
Intro Problem Solving in Computer Science
Inference Rules
Deductive Reasoning 9
An inference rule is rule that allows us to infer a conclusion from given conditions (the premise).
Inference rules take the following general form:
Premise P1. Premise P2. ... Premise PN. ----------------Therefore, Conclusion.
An inference rule must have the property that the conclusion must be true whenever all the premises are true.
Equivalently, the following expression must be a tautology: (P1 and P2 and ... and PN) Conclusion
[email protected]
Intro Problem Solving in Computer Science
Justifying an Inference Rule
Deductive Reasoning 10
We may form the truth table for the corresponding expression:
P or Q. not P. --------------------therefore, Q.
Modus tollendo ponens
P Q P or Q not P (P or Q) and (not P)
TT
T
F
F
TF
T
F
F
FT
T
T
T
FF
F
T
F
(P or Q) and (not P) Q T T T T
Note that we actually only needed to construct the truth table for the case in which the antecedent of the implication was true (third row).
Why?
[email protected]
Intro Problem Solving in Computer Science
Justifying an Inference Rule
Deductive Reasoning 11
The last observation leads to a somewhat simpler verbal analysis:
P or Q. not P. --------------------therefore, Q.
Modus tollendo ponens
Assume the premises are both true. (This is the only case in which the argument form could possibly be false.) Then from the definition of "not", since "not P" is true, P must be false. But if "P or Q" is true, by the definition of "or", P and Q cannot both be false. Hence, Q must be true. And so, if both premises are true then the conclusion must also be true.
[email protected]
Intro Problem Solving in Computer Science
Modus ponens
Deductive Reasoning 12
Here's one of the most basic inference rules (we assume that P and Q represent specific propositions):
if P then Q. P. ----------------therefore, Q.
Affirming the antecedent (Modus ponens)
For example, if we are given that:
If Cirrus is a cat, then Cirrus is carnivorous. Cirrus is a cat.
Then we may infer:
Cirrus is carnivorous.
[email protected]
Intro Problem Solving in Computer Science
Validity and Soundness
Deductive Reasoning 13
An argument is valid if the conclusion is true whenever the premises are true.
An argument is sound if it is valid and the premises are, in fact, true.
The following argument is valid, but not sound:
Premises: If January has 35 days then January contains 5 Mondays. January has 35 days. Conclusion: January contains 5 Mondays.
Propositional logic is largely concerned with the issue of how to form valid arguments. The soundness of an argument generally depends upon external (domain-specific) knowledge.
[email protected]
Intro Problem Solving in Computer Science
Validity
Deductive Reasoning 14
Note that whether an argument is valid has nothing whatsoever to do with whether its premises are true or its conclusion is true: Premises: If Socrates was bipedal, then Socrates was a philosopher. Socrates was bipedal. Conclusion (via Modus ponens or Affirming the antecedent): Socrates was a philosopher.
Premises: If Grace Hopper was Australian, then she was a computer scientist. Grace Hopper was Australian. Conclusion: Grace Hopper was a computer scientist.
Premises: If Socrates was from Rome, then Socrates spoke Latin. Socrates was from Rome. Conclusion: Socrates spoke Latin.
[email protected]
Intro Problem Solving in Computer Science
A Few More Inference Rules
Deductive Reasoning 15
Again, assume that P and Q represent specific propositions:
if P then Q. not Q. --------------------therefore, not P.
Denying the consequent (Modus tollens)
P or Q. not P. --------------------therefore, Q.
Disjunctive syllogism (Modus tollendo ponens)
not not P. --------------------- Double negation therefore, P.
P and Q. --------------------- Conjunction elimination therefore, P.
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 16
if P then Q. if not P then Q. --------------------therefore, Q. Assume the premises are both true. Also, note that P must be either true or false (although we have no idea which is the case). Now, if P is true, then Q is true from the first premise via modus ponens. And, if P is false, then not P is true, and therefore Q is true from the second premise via modus ponens. Therefore, no matter whether P is true or P is false, Q must be true.
[email protected]
Intro Problem Solving in Computer Science
Why do we care?
Deductive Reasoning 17
If we want to derive results from a collection of alleged facts (premises) that we possess, we must understand what will guarantee that our results do, in fact, follow from the premises we are given.
natural languages, especially English, promote using grammatical constructs that lend themselves to obscuring the underling logic, or lack thereof. And, in any language, there may be implicit assumptions that are required to justify the stated conclusions. If those assumptions are false, then the argument is unsound, even if it is valid (and appears to be sensible when read without a full understanding of the true logic).
Consider the exchange quoted on the following slide...
[email protected]
Intro Problem Solving in Computer Science
Why do we care?
Deductive Reasoning 18
This was taken from an episode of a TV show:
Bob Murch, spirit board collector: "There's been thousands of years of accounts of ghosts and hauntings, and if those are true, you know, surely a spirit board can work." Penn Jillette: "So, if those aren't true, a spirit board can't work? Cool!" Source: Penn & Teller, "Ouija Boards/Near Death Experiences", B.S.!
Is there a flaw in Penn Jillette's logic? How can you be sure? How can you convince anyone of your conclusion?
[email protected]
Intro Problem Solving in Computer Science
Why do we care?
Deductive Reasoning 19
This was taken from the Roanoke Times for January 22, 2011:
Lincoln said the war was about the Union Re: "Slavery was central to Civil War," Jan. 10 commentary: When I read this essay, it became apparent the author is either a Yankee or someone boasting about his background in history. Maybe both, for him to go out of the way to put down the South as he did. Just one question: If slavery was so central to causing the war to prevent Southern independence, why did President Lincoln fire Gen. John Fremont for declaring slaves would be set free after the Battle of Wilson's Creek in August 1861 and make the statement: "This war is being fought for a great national idea, the Union, and the general should not have dragged the Negro into it"?
Is the writer's logic valid? Is it sound? Are there hidden assumptions (premises)?
[email protected]
Intro Problem Solving in Computer Science
Why do we care?
Deductive Reasoning 20
This was taken from Aristotle's Politics:
Every state is a community of some kind, and every community is established with a view to some good; for mankind always act in order to obtain that which they think good. But, if all communities aim at some good, the state or political community, which is the highest of all, and which embraces all the rest, aims at good in a greater degree than any other, and at the highest good.
Is the writer's logic valid? Is it sound? Are there hidden assumptions (premises)?
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 21
This problem was taken from the Puzzlers' Paradise website:
Zookeeper George was in charge of feeding all of the animals in the morning. He had a regular schedule that he followed every day. Can you figure it out from the clues? P1: Feedings begin at 6:30 am. P2: A feeding takes 15 minutes. P3: The last feeding begins no later than 7:30 am. P4: The giraffes were fed before the zebras but after the monkeys. P5: The bears were fed 15 minutes after the monkeys. P6: The lions were fed after the zebras.
A carefully-reasoned analysis will provide a sequence of well-explained inferences, reaching a specific conclusion.
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 22
P4: The giraffes were fed before the zebras but after the monkeys.
By Conjunction Elimination, P4 implies: I1: Monkeys are fed before Giraffes. I2: Giraffes are fed before Zebras.
P1: Feedings begin at 6:30 am. P2: A feeding takes 15 minutes. P2 and I1 imply I3: Giraffes are fed at least 15 minutes after Monkeys. I3 and P1 imply I4: Giraffes are fed no earlier than 6:45 am.
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 23
P4: The giraffes were fed before the zebras but after the monkeys.
By Conjunction Elimination, P4 implies: I1: Monkeys are fed before Giraffes. I2: Giraffes are fed before Zebras.
P1: Feedings begin at 6:30 am. P2: A feeding takes 15 minutes. I4: Giraffes are fed no earlier than 6:45 am. P2 and I2 imply I5: Zebras are fed at least 15 minutes after Giraffes. I5 and I4 imply I6: Zebras are fed no earlier than 7:00 am.
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 24
P1: Feedings begin at 6:30 am. P2: A feeding takes 15 minutes. P5: The bears were fed 15 minutes after the monkeys. I3: Giraffes are fed at least 15 minutes after Monkeys.
P1, P2, P5 and I3 imply I7: Giraffes are fed at least 30 minutes after Monkeys. I7 and P1 imply I8: Giraffes are fed no earlier than 7:00 am.
I2: Giraffes are fed before Zebras. I8 and I2 imply I9: Zebras are fed no earlier than 7:15 am.
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 25
P2: A feeding takes 15 minutes. P3: The last feeding begins no later than 7:30 am. P6: The lions were fed after the zebras. I9: Zebras are fed no earlier than 7:15 am.
P2, P6 and I9 imply I10: Lions are fed no earlier than 7:30 am. P3 and I10 imply I11: Lions are fed at 7:30 am.
I3: Giraffes are fed at least 15 minutes after Monkeys. I4: Giraffes are fed no earlier than 6:45 am. I5: Zebras are fed at least 15 minutes after Giraffes. I6: Zebras are fed no earlier than 7:00 am. I7: Giraffes are fed at least 30 minutes after Monkeys.
I3 ­ I7 imply a linear ordering: I12: Monkeys precede Bears, which precede Giraffes, which precede Zebras, which precede Lions.
[email protected]
Intro Problem Solving in Computer Science
Example
Deductive Reasoning 26
P1: Feedings begin at 6:30 am. P2: A feeding takes 15 minutes. P3: The last feeding begins no later than 7:30 am. P1 - P3 imply I13: There are five possible feeding times: 6:30, 6:45, 7:00, 7:15 and 7:30.
I12: Monkeys precede Bears, which precede Giraffes, which precede Zebras, which precede Lions. So I12 and I13 imply that George feeds Monkeys first at 6:30, then Bears at 6:45, then Giraffes at 7:00, then Zebras at 7:15, and finally Lions at 7:30.
[email protected]
Intro Problem Solving in Computer Science