Logic Review. FYI
only. This is a draft document written to accompany a miserable Mat 310 text I
should never have been talked into using.
If I ever teach the class again or have other cause to, I will revise
it. My concern is whether or not a
proof is valid not what name it is called. If I ever do rewrite this, I will probably throw out most of
the names like " ad absurdam" or " modus ponens," . etc.
contains
Strategies of proof and summary of Fallacies
1.To read and understand the following draft document,
it is expected that you know each of the following:
|
i. How to
read (decipher and interpret ) and write logic symbols and statements,
e.g.  says that p is
true and q is true, both are true at the same time.
|
|
ii. How to read
and fill-out logic tables (truth tables) to prove logic statements,
i.e.  says that p is
false.
|
|
iii. How to read and represent statements
symbolically, especially negation statements,
e.g. I am going unless I fall down. 
|
|
iv. How to write and use quantifiers, e.g.  , etc. see “For All/There…sheet.”
|
In
addition, you need to know:
i. The strategies of proof contained in
the following discussion.
ii. How to read, interpret and work with
defined logic systems – e.g. S is an axiom with rule S2=S,
etc.
Vocabulary: Note:
Different texts may use other words to define one or more of the vocabulary
terms.
Axiom: A
mathematical concept that is accepted without a formal definition, e.g. two
points uniquely determine a straight line.
Statement: Any
sentence that can be classified as true or false. For example:
i. George Washington was the first president of the United
States is a true statement.
ii. The moon is made of green cheese is a false statement.
iii. "Shut the door!" is a command and not a statement.
iv. "Why do you want to go?" is a question and
not a statement.
v. "Two Points" is a two-word expression and not a
statement.
Conjecture: A statement one has reason to strongly suspect
is true. Conjectures are statements that one has yet proven to be true.
Proposition (Depends): i.) A true statement.
Note: A true statement,
for example a conjecture that is proven to be true, is the most common term
used to describe a proposition. In this case, a false statement is exactly that, a false statement.
But some books define a proposition as follows:
ii.) A statement
that could be true or false, just not both.
Theorem: A
theorem is always true and is used for notable results.
|
Theorems often are stated in the
of the form of a implication, i.e.
|
|
Premise:A true proposition on which a theorem or other
result is based.
Lemma: A true proposition used most often to support
a claim in the proof of a theorem.
Corollary: A true proposition that follows immediately
from the result of a theorem.
Logic connectives:
Either, Or i.e. something is true or it is not true i.e. 
v 
, a.k.a. Law of the Excluded Middle
(Nothing
can be both not true at the same.
There is no allowance for any maybe case or gray
area).
Know Analogies between
logic and set statements:
p
® q p Ù q p v q p v q
Know
DeMorgan’s Laws, Distributivity properties of È, Ç, complementation (negation), etc,
Know how to work with
Quantifiers c.f. Quantifier table
Know how to negate
Quantifiers
i.
~[" x, p(x)]
=
[$ x, ~p(x)]
ii.
iii.
~[$ x, p(x)]
=
[" x, ~p(x)]
iv.
~[(" xÎ[a b] and " Î>0) ® ( $ ∂Î>0 ' |x-xo| < ∂ ® |f(x)-f(xo)| < Î)] º
v.
º ~[(E xÎ[a b] and $ Î>0) ® (" ∂Î>0 ' |x-xo| < ∂ ® |f(x)-f(xo)| ≥ Î)]
Strategies
of proof:
1. Reasonable Proofs: Tautology: 
often worded in
the context that a premise if true if and only if (IFF) the conclusion is true.
2. Either or proofs:
Law
of the Excluded Middle – 
, see logic connectives above, specifically the exclusive
"or."
Law
of Double Negation: ~(~p)=p. This says that to show a
proposition p (x) is true, follow through on the law of the
excluded middle (p is true or it is not true). That is show that 
is false.
3. Direct: 
.
This says that if, by valid rules
of logic, p implies q is a
true implication and you are given p as true, then q must be true. a.k.a.
modes ponens, Law of Detachment, Reasoning by Assuming the Antecedent.
Disjunctive Syllogism: 
vice
versa of above. If one of p or q
is true, and you know p is false, then necessarily q is true. (name disjunctive follows from logic or, v, symbol).
5.
The three (basoc) “contradiction” proofs
a. Contrapositive: 
The equivalence of the implication and the contrapositive is a tautology that
is clear directly from a Truth Table.
b. Indirect Reasoning or Reasoning by Negating the Consequent, etc.
.
I have found that students understand and do better
on thislast type of proof when it is symbolically written as
Using a
Venn diagram to represent one of the four possible cases, pèq means that the set p is sitting inside the circle
of the set q. Given that p is
true, then anything outside of the circle for q, i.e. ~q, cannot turn around
and also be in p which is a q –contradiction. Therefore, ~q true (or q not true) means that p cannot be
true, so ~p must also be true. The
other three Venn diagrams can be discussed in the same way. Some books refer to
an indirect reasoning as a passive
(lit’l) contradiction and the following as an active (big) contradiction
b. Contradiction: there are several ways to write
a proof by contradiction depending on what is to be proven. Also
called indirect, argue ad absurdam
(to nonsense)
Essentially a Law of the Excluded Middle except the
proposition to be shown true is itself in the form of an implication;. To show
a proposition of the form, 
, is true, show 
is false.
That is, show, 
and
because 
(set up
truth table to prove) this is the same as showing 
. Therefore, the
long and the short of it is, show the statement,
, is false using only valid (true) logical processes. The difference between this “Big” contradiction
versus “Litl” contradiction (contrapositive) is that the last has the added guns of assuming the
hypothesis p as well as ~q are true, then showing this leads to
a false conclusion.
*Comment: A proof
by contradiction does not need to find a specific something that works; it merely says that if
you have a p that is true, then it must be the case that q is also true.
c.f. Intermediate Value Theorem: Given a continuous f(x) on a closed
interval, [a,b], then
" xÎ[a b] and " Î>0 ® $ ∂Î>0 ' |x-xo| < ∂ ® |f(x)-f(xo)| < Î.
6. Proofs involving
Quantifiers: (Refer to the Quantifier
Discussion Sheet)
proofs: –
just adds an extra step to any
procedure above that involve a “there exists” factor.
Example,
most Max/Min proofs require a proposition p(x) be converted
to a quantified, 
, statement.
Know
how to work with Quantifiers c.f. Quantifier table sheet.
Know
how to negate Quantifiers
i.
~[" x, p(x)] 
[$ x, ~p(x)]
ii.
~[$ x, p(x)] 
[" x, ~p(x)]
iii.
example:
~[(" xÎ[a,b] and " Î>0) ®
( $ ∂Î>0 ' |x-xo| < ∂ ® |f(x)-f(xo)| < Î)] º
~[ " xÎ[a,b] and " Î>0] ® ~[( $ ∂Î>0 ' |x-xo| < ∂ ® |f(x)-f(xo)| < Î)] º
[($ xÎ[a b] or $ Î>0) ®
(" ∂Î>0 ' |x-xo| < ∂ ® |f(x)-f(xo)| ≥ Î)]
7.
Induction: To show a general proposition P(n) is true for all integers
n≥k, for some positive integer k,
i. Show
P(k) is true
(i.e. show the statement (proposition)is true at some starting integer k>0).
ii. Assume
P(n) is true for some positive integer n, n≥k,
iii. Show
P(n+1) is true (i.e. based on
assumption P(n) is true for some number n≥k, show P(n+1) is true.
(i.e. Assuming P(n) is true, prove that the
proposition also holds for the very next number n+1, arb n≥k).
iv. Conclude
P(n) is true for all natural
numbers (positive integers ) greater than or equal to k.
FALLACIES of PROOF:
1.
Fallacy of the
converse, 
.
A.k.a. Fallacy of assuming the
consequent 
. I prefer to
say that p èq does not
also mean qèp. If p èq and qèp are both true, then we write p«q. Just
because P is true does not mean you can always turn the statement around, e.g. Use Crest è Fewer cavities. Could have fewer cavities, even if used brand X instead of
Crest toothpaste.
In
short: THIS
è THAT
does not necessarily mean THAT èTHIS.
2.
Fallacy of the
inverse, 
.
A.k.a. Fallacy of denying the antecedent 
NOT
using THIS (toothpaste) does not guarante you will have THAT (cavities)
3.
False Chain, 
.
Just because p implies two or more things says nothing about how those two
things are related. Consider the following:
According to the latest report,
i. THIS
toothpaste means you will have fewer cavities.,
is true, and
ii THIS
toothpaste is also good for gluing paper dolls together, 
.
Iii. Clearly,
having fewer cavities has nothing
to do with whether you do or do not play with paper dolls.
SUMMARY of
False Proofs:
i. Fallacy
of the converse: 
ii. Fallacy
of the inverse: 
.
iii. False
Chain: 
.
See
the Relations and Functions review sheets to tie the symbolic set theory and
logic notation together and to see more about relations that are also functions.
