Chapter 19
Notes for the fifth week: review

Notes also available as PDF.

19.1 Review

Structure of the upcoming test:

19.2 Inductive and deductive reasoning

Two primary forms of reasoning:

Working from examples and intuiting how to extend them. Inductive reasoning does not prove anything.
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


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

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:

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.

Think about how your solution could help with other problems.

19.4 Sequences

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

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

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

11\quad 22\quad 39\quad 64\quad \mathop{\mathop{…}}

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

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

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

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.
A ∪ B = \{x\kern 1.66702pt |\kern 1.66702pt x ∈ A ∨ x ∈ B\}. The union contains all elements of both sets.
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
1 0

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.
True when the variable is false and false when the variable is true. Will be written \mathop{¬}p.
True only when all variables are true. Will be written p ∧ q.
False only when all variables are false. Will be written p ∨ q.
The logical form of equality. Will be written p ≡ q.
If p then q. True whenever true implies true or when false implies anything. Will be written p → q.
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:

pq\mathop{¬}pp ∧ qp ∨ qp → 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:

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:

p → q: If you grew up in Alaska, you have seen snow.
\mathop{¬}p →\mathop{¬}q: If you did not grow up in Alaska, you have not seen snow.
q → p: If you have seen snow, you grew up in Alaska.
\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

A statement regarding some or all possible entries of some set.
Declares that some entry exists, so \mathop{∃}x : x ∈ A states that A is not empty.
Declares some property is true for every value. So \mathop{∀}x ∈ A : x ∈ B is another way of writing A ⊂ B.
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:

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.