## Chapter 19Notes for the fifth week: review

Notes also available as PDF.

### 19.1 Review

Structure of the upcoming test:

• Ten questions. Chose six and solve them.
• Thus expect about seven minutes per question.
• Closed book, etc. Calculators are fine but not necessary.
• Bring scratch paper and paper for writing up your results. Separately.
• Answers and explanations need to be indicated clearly.
• No questions are intended to be “trick” questions.
• Will cover the following topics:
• inductive v. deductive reasoning with sequences,
• problem solving,
• set theory,
• symbolic logic.
• Remember that solutions for the homework problems are available on-line: //jriedy.users.sonic.net/VI/math131-f08/:http://jriedy.users.sonic.net/VI/math131-f08/.

### 19.2 Inductive and deductive reasoning

Two primary forms of reasoning:

inductive
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.

### 19.3 Problem solving

Pólya’s principles:

1. Understand the problem.
2. Devise a plan.
3. Carry out the plan.
4. Look back at your solution.

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.

#### 19.3.1 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.

• 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.

#### 19.3.2 Devise a plan

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.

#### 19.3.3 Carry out the plan

Attention to detail is critial here.

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.

#### 19.3.4 Look back at your solution

Can you check your result? Sometimes trying to check reveals new relationships that could lead to a better solution.

### 19.4 Sequences

A sequence is an ordered list of numbers. Two common kinds are:

arithmetic
Adds a constant increment at each step.
geometric
Multiplies by a constant at each step.

One method for extending a sequence is through successive differences. Consider the sequence

To compute the next term, form differences until you find a constant column:

 i {A}_{i} {Δ}_{i}^{(1)} = {A}_{i} - {A}_{i-1} {Δ}_{i}^{(2)} = {Δ}_{i}^{(1)} - {Δ}_{i-1}^{(1)} 1 11 2 22 11 3 39 17 6 4 62 23 6 5 91 29 6

### 19.5 Set theory

set
An unordered collection of unique elements.

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\}. & & }

### 19.6 Symbolic logic

logical statement
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.

#### 19.6.1 From truth tables to functions

Consider the truth table:

 p q f(p,q) 1 1 1 1 0 0 0 1 1 0 0 0

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.

#### 19.6.2 De Morgan’s laws and forms of conditionals

De Morgan’s laws are two very useful methods for negating terms symbolically:

\begin{array}{cl} \mathrel{⊧}\mathop{¬}(p ∨ q) ≡\mathop{¬}p ∧\mathop{¬}q,\text{ and}& \\ \mathrel{⊧}\mathop{¬}(p ∧ q) ≡\mathop{¬}p ∨\mathop{¬}q. & \end{array}

As an example, consider negating the conditional. Use the equivalent form \mathrel{⊧}p → q ≡\mathop{¬}p ∨ q. Then

\eqalignno{ \mathop{¬}(p → q) & = \mathop{¬}(\mathop{¬}p ∨ q) & & \cr & = \mathop{¬}(\mathop{¬}p) ∧\mathop{¬}q & & \cr & = p ∧\mathop{¬}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

#### 19.6.3 Quantifiers

quantifier
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.

can translate to

 \mathop{∃}s\kern 1.66702pt \mathop{∀}t : \mathop{¬}\mathop{understands}\nolimits (s,t)

because we don’t measure how many but rather that there is or is not one.

#### 19.6.4 Nesting and negating quantifiers

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 t for 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.

and its translation

 \mathop{∃}s\kern 1.66702pt \mathop{∀}t : \mathop{¬}\mathop{understands}\nolimits (s,t).

The symbolic negation is

\eqalignno{ \mathop{¬}(\mathop{∃}s\kern 1.66702pt \mathop{∀}t : \mathop{¬}\mathop{understands}\nolimits (s,t)) & = \mathop{∀}s\kern 1.66702pt \mathop{¬}(\mathop{∀}t : \mathop{¬}\mathop{understands}\nolimits (s,t)) & & \cr & = \mathop{∀}s\kern 1.66702pt \mathop{∃}t : \mathop{¬}(\mathop{¬}\mathop{understands}\nolimits (s,t)) & & \cr & = \mathop{∀}s\kern 1.66702pt \mathop{∃}t :\mathop{ understands}\nolimits (s,t). & & }

Translating back to English,

All students understand some symbolic logic topic.

It may be true that no two students understand the same topic, but every student understands some topic.