Working from examples and intuiting how to extend them. Inductive
reasoning does not prove anything.
deductive
Extending hypotheses with rules to reach a conclusion. Deductive
reasoning generates proofs (even if simple).
An example of inductive reasoning:
It has been sunny all week, so it will be sunny tomorrow.
There are no explicit rules or assumptions. We just assume the pattern continues.
An example of deductive reasoning:
The weather forecasts state that if the storm turns northward, it
will rain tomorrow. The storm has turned northward, so it will rain
tomorrow.
This sets up a rule from the weather forecast. Then the rule is applied to data, the
storm turning northward, to reach a conclusion about tomorrow.
There rarely are clean-cut distinctions. Consider extending the sequence
35,45,55,\mathop{\mathop{…}}
Reasoning inductively, we might assume that the numbers jump by ten. The next
number will be 65, then 75, and so on.
Reasoning deductively, we assume this is an arithmetic sequence starting at 35 with
an increment of 10. Under this assumption, the next two numbers will be
35 + 10 ⋅ 3 = 65 and
35 + 10 ⋅ 4 = 75.
The difference between the two forms is subtle. Deductive reasoning sets
up explicit rules. The rules themselves may be discovered inductively, but
making the rules specific and applying them carefully renders the result
deductive.
This is not a simple 1-2-3-4 recipe. Understanding the problem may include playing
with little plans, or trying to carry out a plan may lead you back to trying to
understand the problem.
One comment about the homeworks: Most people answer only part of any
given problem.
Determine what you have and what you want.
To indicate an answer clearly to someone else (like me), you need to know
what the answer is.
Consider rephrasing the problem, either in English or symbolically.
Rephrasing the problem may help you remember solution methods.
Try some examples.
This is close to devising a plan. Sometimes you may stumble upon an
answer.
Look for relationships between the data.
Examples may help find relationships. The relationships may help
you decide on a plan. Mathematics is about relationships between
different entities; symbolic mathematics helps abstract away the entities
themselves.
Sometimes plans are “trivial,” or so simple it seems pointless to make them specific.
But write it out anyways. Often the act of putting a plan into words helps find flaws
in the plan.
Try to devise a plan that you can check along the way. The earlier you detect a
problem, the easier you can deal with it.
Some plans we’ve considered:
Guessing and checking.
Try a few combinations of the data. See what falls out. This is good for
finding relationships and understanding the problem.
Searching using a list.
If you know the answer lies in some range, you can search that range
systematically by building a list.
Finding patterns.
When trying examples, keep an eye open for patterns. Sometimes the
patterns lead directly to a solution, and sometimes they help to break a
problem into smaller pieces.
Following dependencies / working backwards.
Be sure to understand what results depend on which data. Look for
dependencies in the problem. Sometimes pushing the data you have
through all the dependencies will break the problem into simpler
sub-problems.
When building a list, be sure to carry out a well-defined procedure. Or when looking
for patterns, be systematic in the examples you try. Don’t jump around
randomly.
You can write a set by listing its entries, \{1,2,3,4\},
or through set builder notation, \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is a positive integer},x < 5\}.
empty set
The unique set with no elements: \{\}
or ∅.
Be sure to know the relations between the empty set and other sets, and
also how the empty set behaves in operations.
element of
You write x A
to state that x
is an element of A.
The symbol is not an “E” but is almost a Greek ϵ.
Think of a pitchfork.
Note that 1 \{1,2\}
and \{1\} \{\{1\},\{2\}\},
but \{1\}∉\{1,2\}.
subset
Given two sets A
and B,
A ⊂ B
if every element of A
is also an element of B.
So A ⊂ B
is equivalent to x A → x B.
One implication is that ∅⊂ A
for all sets A.
This statement is vacuously true.
Here \{1\} ⊂\{1,2\}
and \{1\}⊄\{\{1\},\{2\}\}.
superset
Given two sets A
and B,
B ⊃ A
if every element of A
is also an element of B.
proper subset or superset
A subset or superset relation is proper if it implies
the sets are not equal. An equivalent symbolic logic statement would be
(x A → x B) ∧ (\mathop{∃}x B : x\mathrel{∉}A).
Venn diagram
A blobby diagram useful for illustrating operations and
relations between two or three sets.
union
A ∪ B = \{x\kern 1.66702pt |\kern 1.66702pt x A ∨ x B\}.
The union contains all elements of both sets.
intersection
A ∩ B = \{x\kern 1.66702pt |\kern 1.66702pt x A ∧ x B\}.
The intersection contains only those elements that exist in both sets.
set difference
A \ B = \{x\kern 1.66702pt |\kern 1.66702pt x A ∧ x\mathrel{∉}B\}.
The set difference contains elements of the first set that are not in the
second set. It cannot contain any elements of the second set.
You can use symbolic logic to write the result of multiple operations.
\eqalignno{
(A ∩ B) ∪ C & = \{x\kern 1.66702pt |\kern 1.66702pt x A ∧ x B\} ∪ C & &
\cr
& = \{x\kern 1.66702pt |\kern 1.66702pt (x A ∧ x B) ∨ x C\}. & &
}
Some clear statement that is either true or false.
Some different ways of writing true or false are acceptable:
true
false
T
F
1
0
\mathop{⊤}
⊥
The test’s questions use 1 and 0.
logical variable
A variable standing for some logical statement. Common variables are
p,
q,
r.
truth table
A systematic listing of all possible input truth values for an
expression.
negation
True when the variable is false and false when the variable is true. Will be written
\mathop{¬}p.
and
True only when all variables are true. Will be written
p ∧ q.
or
False only when all variables are false. Will be written
p ∨ q.
equivalence
The logical form of equality. Will be written
p ≡ q.
conditional
If p
then q.
True whenever true implies true or when false implies anything. Will be written
p → q.
tautology
A statement that always is true. Will be written
\mathrel{⊧}, as
in \mathrel{⊧}p ∨\mathop{¬}p.
This is just for emphasis; there is no real difference with
(p ∨\mathop{¬}p) ≡ 1.
A truth table defining four operations above:
p
q
\mathop{¬}p
p ∧ q
p ∨ q
p → q
1
1
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
1
0
0
1
0
0
1
Note that \mathop{¬}p
did not need all four lines. It does not depend on
q and has the same value
regardless of whether q
is false or true.
We can derive an expression for f(p,q)
in two ways. Obviously, any expressions must simplify to
q.
One method is to work from the true values. You or together and expressions.
There is one and expression per true value. In this case, we have
\mathrel{⊧}f(p,q) ≡ (p ∧ q) ∨ (\mathop{¬}p ∧ q). Pulling out
the q, this
simplifies \mathrel{⊧}f(p,q) ≡ (p ∨\mathop{¬}q) ∧ q ≡ 1 ∧ q ≡ q.
The other method is to work from the false values. You and together
or expressions. There is one or expression per false value. Here,
\mathrel{⊧}f(p,q) ≡ (\mathop{¬}p ∨ q) ∧ (p ∨ q). Pulling
out q
again, \mathrel{⊧}f(p,q) ≡ (\mathop{¬}p ∧ p) ∨ q ≡ 0 ∨ q ≡ q.
So the negation of a conditional is not a conditional itself.
There are four related forms of conditional:
conditional
p → q:
If you grew up in Alaska, you have seen snow.
inverse
\mathop{¬}p →\mathop{¬}q:
If you did not grow up in Alaska, you have not seen snow.
converse
q → p:
If you have seen snow, you grew up in Alaska.
contrapositive
\mathop{¬}q →\mathop{¬}p:
If you have not seen snow, you did not grow up in Alaska.
Only the contrapositive has the same meaning as the original conditional, so
\mathrel{⊧}p → q ≡\mathop{¬}q →\mathop{¬}p.
The converse and inverse are related to each other but are not equivalent to
the original conditional. The inverse is the contrapositive of the converse:
\mathrel{⊧}q → p ≡\mathop{¬}p →\mathop{¬}q
A statement regarding some or all possible entries of some set.
existential
Declares that some entry exists, so \mathop{∃}x : x A
states that A
is not empty.
universal
Declares some property is true for every value. So \mathop{∀}x A : x B
is another way of writing A ⊂ B.
predicate
Or property. A symbolic way of expressing that some property holds. For example,
\mathop{understands}\nolimits (s,t) may state
that student s
understands topic t.
A less obtuse but still acceptable statement for a simple predicate is just
“s\mathop{understands}\nolimits q.”
The translation of phrases from English to quantified symbolic logic can be
tricky.
Almost every student understands all symbolic logic topics.
Nested quantifiers are not operators. Each quantifier applies to the entire remaining statement.
\mathop{∀}s\mathop{∃}t states that for
every s, there
exists a tfor that\mathbf{s}. Meanwhile,
\mathop{∃}t\mathop{∀}s states that there
exists one single t
for every and all s.
Two rules for negating quantifiers:
\mathop{¬}\mathop{∀}s : P(s)
is the same as \mathop{∃}s : \mathop{¬}P(s),
and
\mathop{¬}\mathop{∃}s : P(s)
is the same as \mathop{∀}s : \mathop{¬}P(s).
So saying “not all” is the same as “there exists one for not”, and saying “there does
not exist” is the same as “for all, not”.
As an example, we negate the statement above,
Almost every student understands all symbolic logic topics.
A
to state that x
is an element of A.
The symbol is not an “E” but is almost a Greek ϵ.
Think of a pitchfork.