Title



Chapter One Notes

The Foundations: Logic and Proofs

Based on: Discrete Math & Its Applications - Kenneth Rosen

CSC125 - Spring 2010

As MS document

  

1.1 - Propositional Logic

Concepts::

Proposition

Propositional variables

Propositional logic (calculus)

Logical connectives (operators) ( ( ( ( ( (

Compound propositions

Logical operations

Negation (p not p

Conjunction p ( q p and q

Disjunction p ( q p or q (or both)

Exclusive Or p ( q p xor q

Conditional (implication) p ( q if p, then q (p implies q)

Converse of p ( q

is q ( p (p ( q)

The converse does not necessarily follow.

Example:

If it rains then the streets are wet – true

If the streets are wet then it rained – false

Contrapositive of p ( q

is (q ( (p

The contrapositive does necessarily follow.

If it rains then the streets are wet – true

If the streets are not wet then it did not rain – true

Inverse of p ( q

is (p ( (q

The inverse does not necessarily follow.

Example:

If it rains then the streets are wet – true

If it does not rain then the streets are not wet – false

Biconditional p ( q if p, then q and if q, then p

p implies q and q implies p

p if and only if q

p iff q

Truth tables

| p | (p |

| T | F |

| F | T |

| p | q |p ( q |p ( q |p ( q |p ( q |p ( q |

| T | T | T | T | F | T | T |

| T | F | F | T | T | F | F |

| F | T | F | T | T | T | F |

| F | F | F | F | F | T | T |

Bitwise And, Or, Xor

And 0 0 1 1

0 1 0 1

0 0 0 1

Or 0 0 1 1

0 1 0 1

0 1 1 1

Xor 0 0 1 1

0 1 0 1

0 1 1 0

How many Boolean operations?

|x |y |f0 |f1 |f2 |

| T | T | F | T | T |

| T | F | F | F | F |

| F | T | T | T | T |

| F | F | T | T | T |

| p | q |(p |(q |(p ( (q |p ( q |((p ( q) |

| T | T | F | F | F | T | F |

| T | F | F | T | T | F | T |

| F | T | T | F | T | F | T |

| F | F | T | T | T | F | T |

Compare the above to Tables 3 and 4 on pp. 22 & 23 of Rosen. These are examples of important equivalences which we will study. Before we do, we need to learn some terminology.

Tautology – a proposition that is always true

Example: p ( (p

Contradiction (inconsistency) – a proposition that is always false

Example: p ( (p

Contingency – a proposition that is neither a tautology nor a contradiction, i.e., it is sometimes true and sometimes false.

Example: p ( q

For verification of these examples, look at Table 1, p. 22 and Table 7, p. 10.

Logical Equivalences::

p & q are logically equivalent if p ↔ q is a tautology

In that case we can write: p ≡ q

Truth tables can be used to establish whether or not p & q are logically equiv.

DeMorgan's Laws – Table 2 {on quiz }

Tables of important logical equivs. – Table 6 {on quiz}

Table 7 – involving conditionals {on quiz}

Table 8 – involving biconditionals {on quiz}

Constructing New Logical Equivalences::

Given a small set of logical equivalences, we can derive new ones in a step by step process. Examples 6→8, pp. 26-27 illustrate how this is done. This process of derivation of new propositions from old is very useful and forms the basis of a lot of work in automated theorem proving.

  

1.3 - Predicates and Quantifiers

Predicate logic

predicate (propositional function)

variable

truth value of propositional function

n-place predicate or n-ary predicate

Quantifiers

quantification - expresses extent to which a predicate is true over a range of elements

predicate calculus

domain OR domain of discourse OR universe of discourse

universal quantifier

(xP(x)

counterexample – one single x for which P(x) is false

existential quantifier

(xP(x)

establishing example – one single x for which P(x) is true

See Table 1, p. 34

uniqueness quantifier

(!xP(x) {or (1xP(x) }

quantifiers with restricted domains

precedence of quantifiers

(xP(x) ( Q(x) ≡ ((xP(x)) ( Q(x) !≡ (x(P(x)) ( Q(x))

binding variables

variable within scope of quantifier is bound

variable not within scope of quantifier is free

Logical equivalences

(x(P(x) ( Q(x)) ≡(xP(x) ( (xQ(x), if same domain is used

throughout

Negating quantified expressions (DeMorgan's Laws)

((x P(x) ≡ (x(P(x)

((xP(x) ≡ (x(P(x)

Quantifiers related to ( and (

(xP(x) operates like a super (

Let domain be {1,2,3}

(xP(x) ≡ P(1) ( P(2) ( P(3)

(xP(x) operates like a super (

Let domain be {1,2,3}

(xP(x) ≡ P(1) ( P(2) ( P(3)

That is why the negation laws above are called DeMorgan's Laws

((x P(x) ≡ ((P(1) ( P(2) ( P(3))

≡ (P(1) ( (P(2) ( (P(3) ≡ (x(P(x)

And

((xP(x) ≡ ((P(1) ( P(2) ( P(3))

≡ (P(1) ((P(2) ( (P(3) ≡ (x(P(x)

See Table 2, p. 41

Translating to & from English

Let T(x) represent "x is tall"

Everyone is tall:: (x T(x)

It is not true that everyone is tall:: ((x T(x), is the same as

Someone is not tall:: (x(T(x)

Someone is tall:: (x T(x)

It is not true that someone is tall:: ((x T(x), is the same as

No one is tall:: (x(T(x), which is the same as

Everyone is not tall {although this is ambiguous; see below}

Ambiguity and subtlety of natural languages

It is important to realize that one of the difficulties in translating back and forth from English (or any other natural language) to symbolic logic comes from the fact that some expressions are used in more than one way, logically speaking. In addition it is difficult to disambiguate because closely related expressions are used to express subtle nuances of meaning.

Everyone is not tall is a good example. It can be taken to mean no one is tall, as we took it to mean above.

(x(T(x)

Or it can be taken to mean not everyone is tall

((x T(x)

or someone is not tall (which is logically equivalent)

(x (T(x)

That meaning comes out clearly in the following interchange.

Person A: Everyone is tall.

Person B: No, everyone is not tall.

Attempts to disambiguate by changing our wording lead to other problems. We could try to express

(x(T(x)

as everyone is short, but that changes the meaning. If we have a basketball team where the heights range from 5'9" to 6'6", we can say everyone is not tall; but we could not say everyone is short. We could make up new words and say everyone is untall, but that is not likely to be welcomed by the general population of English speakers.

It soon becomes pretty clear that there is no cleancut solution to the translation problem. In fact, that is one of the reasons for using symbolic logic – to eliminate the ambiguity inherent and widespread in natural language. Read the examples below to see how prevalent ambiguity and subtlety are in our use of "the king's English."

Everyone goes

No, everyone does not

Everyone stays away

Everyone does not go

Everyone is going

Everyone is not going

Everyone is so not going

Someone goes

No, someone does not go

Some do not go

Some stay away

Everyone thinks

Everyone is unthinking

Everyone does not think

Everyone is thoughtful

Everyone is not thoughtful

Everyone is thoughtless

Someone thinks

Someone does not think

Some is thoughtless

Someone is thoughtless

Everyone is caring

Everyone is uncaring

Everyone is not caring

Not everyone is caring

Everyone is careless

Everyone is careful

Everyone is not careful

Not everyone is careful

Not everyone is careless

Quick Summary

Realizing that there will still be ambiguous cases, here are some rules of thumb

(x D(x) – everyone does

(x (D(x) – everyone does not; i.e., for everyone does not is true

((x D(x) – not everyone does; i.e., for some does not is true

(x D(x) – someone does

(x (D(x) – someone does not; there is someone who does not

((x D(x) – no one does

Equivalences

((x D(x) ≡ (x (D(x)

No one does is the same as everyone does not

((x D(x) ≡ (x(D(x)

Not everyone does is the same as someone does not

  

1.4 - Nested Quantifiers

Think of quantification as loops

Example 2

Order of Quantifiers

Does not matter if all of same type

Example 3

Very important when of mixed type

Examples 4 & 5

Let domain be {1,2,3}

(x (y P(x,y) ≡ (y(x P(x,y)

≡ P(1,1) ( P(1,2) ( P(1,3) ( P(2,1) ( P(2,2) ( P(2,3) ( P(3,1) (

P(3,2) ( P(3,3)

(x (y P(x,y) ≡ (y(x P(x,y)

≡ P(1,1) ( P(1,2) ( P(1,3) ( P(2,1) ( P(2,2) ( P(2,3) ( P(3,1) (

P(3,2) ( P(3,3)

(x (y P(x,y) ≡ (P(1,1) ( P(1,2) ( P(1,3)) (

(P(2,1) ( P(2,2) ( P(2,3)) (

(P(3,1) ( P(3,2) ( P(3,3))

In other words,

for x = 1, (y P(x,y) ( for x = 2, (y P(x,y) ( for x = 3, (y P(x,y)

(x (y P(x,y) ≡ (P(1,1) ( P(1,2) ( P(1,3)) (

(P(2,1) ( P(2,2) ( P(2,3)) (

(P(3,1) ( P(3,2) ( P(3,3))

In other words,

either for x = 1, (y P(x,y) ( for x = 2, (y P(x,y) ( for x = 3, (y P(x,y)

Similarly,

(y (x P(x,y) ≡ (P(1,1) ( P(2,1) ( P(3,1)) (

(P(1,2) ( P(2,2) ( P(3,2)) (

(P(1,3) ( P(2,3) ( P(3,3))

In other words,

either for y = 1, (x P(x,y) ( for y = 2, (x P(x,y) ( for y = 3, (x P(x,y)

Therefore, (x (y P(x,y) ≠ (y (x P(x,y) ≠ (x (y P(x,y)

See Table 1, p. 53

Translating mathematical statements

Examples 6 & 7

Translating nested quantifiers into English

Examples 9 & 10

Translating English into logical expressions

Examples 11 & 13

Negating nested quantifiers

Example 14

((x (y (xy = 1) ≡

(x ( (y (xy = 1) ≡

(x (y ( (xy = 1) ≡

(x (y (xy ≠ 1)

Example 15

( (w (a (f (P(w,f) ( Q(f,a))

(w ((a (f (P(w,f) ( Q(f,a))

(w (a ((f (P(w,f) ( Q(f,a))

(w (a (f ((P(w,f) ( Q(f,a))

(w (a (f ((P(w,f) ( (Q(f,a))

Doubly quantified expression examples:

Let W(x,y) be the statement “student x watched Eagles game y,” where the domain for x consists of all students in this class and the domain for y consists of all Philadelphia Eagles games last season. Express each proposition in English.

1. ∃x ∃y W(x,y)

A student from this class watched an Eagles game last season.

2. (∃x ∃y W(x,y)

No student from this class watched an Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ (x (∃y W(x,y) ≡ (x (y (W(x,y)

Note: Equivalent to #18

{For all students and all Eagles games, it not true that any student

watched any game}

3. ∃x ∀y W(x,y)

A student from this class watched every Eagles game last season.

4. (∃x ∀y W(x,y)

No student from this class watched every Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ (x ((y W(x,y) ≡ (x ∃y (W(x,y)

Note: Equivalent to #16

5. ∀y ∃x W(x,y)

Every Eagles game last season was watched by a student in this class.

6. (∀y ∃x W(x,y)

Not every Eagles game last season was watched by a student in this class.

Here are equivalent forms, by DeMorgan's Law

≡ ∃y ((x W(x,y) ≡ ∃y (x (W(x,y)

Note: Equivalent to #17

7. ∀x ∃y W(x,y)

Every student from this class watched an Eagles game last season.

8. (∀x ∃y W(x,y)

Not every student from this class watched an Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ ∃x (∃y W(x,y) ≡ ∃x ∀y (W(x,y)

Note: Equivalent to #14

{A student from this class did not watch any Eagles games last season;

OR: It is not true that every student watched an Eagles game last season}

9. ∃y ∀x W(x,y)

There is an Eagles game last season that every student watched.

10. (∃y ∀x W(x,y)

None of the Eagles games last season were watched by every student.

Here are equivalent forms, by DeMorgan's Law

≡ ∀y (∀x W(x,y) ≡ ∀y (x (W(x,y)

Note: Equivalent to #15

11. ∀x ∀y W(x,y)

Every student from this class watched every Eagles game last season.

12. (∀x ∀y W(x,y)

Not every student from this class watched every Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ ∃x ((y W(x,y) ≡ ∃x ∃y (W(x,y)

Note: Equivalent to #13

13. ∃x ∃y (W(x,y)

A student from this class who missed an Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ ∃x ((y W(x,y) ≡ ((x (y W(x,y)

Note: Equivalent to #12

{There is a student from this class who did not watch every Eagles game last season;

OR: Not every student from this class watched every Eagles game last season.}

14. ∃x ∀y (W(x,y)

A student from this class did not watch any Eagles games last season.

Here are equivalent forms, by DeMorgan's Law

≡ ∃x (∃y W(x,y) ≡ ((x ∃y W(x,y)

Note: Equivalent to #8

{Not every student from this class watched an Eagles game last season;

OR: It is not true that every student watched an Eagles game last season}

15. ∀y ∃x (W(x,y)

No Eagles game was watched by every student in this class.

Here are equivalent forms, by DeMorgan's Law

≡ (y ((x W(x,y) ≡ (∃y (x W(x,y)

Note: Equivalent to #10

16. ∀x ∃y (W(x,y)

Every student from this class missed an Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ ∀x (∀y W(x,y) ≡ (∃x ∀y W(x,y)

Note: Equivalent to #4

{No student watched every Eagles game last season;

OR: For every student, there is an Eagles game they did not watch}

17. ∃y ∀x (W(x,y)

There is an Eagles game that no one watched.

Here are equivalent forms, by DeMorgan's Law

≡ ∃y (∃x W(x,y) ≡ (∀y ∃x W(x,y)

Note: Equivalent to #6

18. ∀x∀y (W(x,y)

No student watched any Eagles game last season.

Here are equivalent forms, by DeMorgan's Law

≡ ∀x (∃y W(x,y) ≡ (∃x ∃y W(x,y)

Note: Equivalent to #2

Every student in this class missed watching every Eagles game last season.

1.5 Rules of Inference

Valid arguments in propositional logic

p → q

p .

( q

Definitions:

argument - sequence of propositions

premises - all the propositions in the sequence except the final one

conclusion - the final proposition in the sequence

argument form - sequence involving propositional variables

valid - an argument form is valid if conclusion follows from premises, no

matter what values the variables have.

conclusion follows from premises - conclusion is true if all premises are true

Rules of inference for propositional logic

Study Table 1

Examples 1, 3, 4, 5

Using rules of inference to build arguments

Example 6

Hypotheses:

H1: (p ( q

H2: r ( p

H3: (r ( s

H4: s ( t

Argument:

1: (p ( q H1

2: (p Simp (1)

3: r ( p H2

4: (r MT (2,3)

5: (r ( s H3

6: s MP (4,5)

7: s ( t H4

8: t MP(6,7)

Example 7

Hypotheses:

H1: p ( q

H2: (p ( r

H3: r ( s

Argument:

1: p ( q H1

2: (q ( (p Contrapos (1)

3: (p ( r H2

4: (q ( r HypSyl (2,3)

5: r ( s H3

6: (q ( s HypSyl (4,5)

Resolution

((p ( q) ( (~p ( r)) → (q ( r)

Clause - disjunction of variables or their negations

Resolvent - conclusion of application of resolution rule

Fallacies

Affirming the conclusion

Denying the hypothesis

Rules of inference for quantified statements

Study Table 2

Examples 12 & 13

Example 12

Premises:

P1: (x (D(x) ( C(x))

P2: D(Marla)

Argument:

1: (x (D(x) ( C(x)) P1

2: D(Marla) ( C(Marla) UI (1)

3: D(Marla) P2

4: C(Marla) MP (2,3)

Example 13

Hypotheses:

P1: (x (C(x) ( (B(x))

P2: (x (C(x) ( P(x))

Argument:

1: (x (C(x) ( (B(x)) P1

2: C(a) ( (B(a) EI (1)

3: C(a) Simp (2)

4: (x (C(x) ( P(x)) P2

5: C(a) ( P(a) UI (4)

6: P(a) MP (3,5)

7: (B(a) Simp (2)

8: P(a) ( (B(a) Conj (6,7)

9: (x (P(x) ( (B(x)) EG (8)

Combining rules of inference for propositions and quantified statements

Universal modus ponens

Universal modus tollens

Summary of Valid Rules of Inference (Valid Argument Forms)

Modus Ponens

p

p → q

( q

Modus Tollens

(q

p → q

( (p

Hypothetical Syllogism

p → q

q → r

( p → r

Disjunctive Syllogism

p ( q

(p .

( q

Addition

p .

( p ( q

Simplification

p ( q

( p

Conjunction

p

q

( p ( q

Resolution

p ( q

(p ( r

( q ( r

Universal Instantiation

(x P(x)

( P(c) for any element c

Universal Generalization

P(c) for an arbitrary c

( (x P(x)

Existential Instantiation

(x P(x)

( P(c) for some element c

Existential Generalization

P(c) for some element c

( (x P(x)

Universal Modus Ponens

(x (P(x) → Q(x))

P(a), where a is any element in the domain

( Q(a)

Universal Modus Tollens

(x (P(x) → Q(x))

(Q(a), where a is any element in the domain

( (P(a)

Summary of Fallacies (Invalid Argument Forms)

Affirming the conclusion

q

p → q

( p

Denying the hypothesis

(p

p → q

( (q

Unwarranted addition

p .

( p ( q

Unwarranted simplification

p ( q

( p

Unwarranted Universal Generalization

P(c) for a particular c

( (x P(x)

Existential Instantiation

(x P(x)

( P(c) for a particular element c

Universal Affirming the conclusion

(x (P(x) → Q(x))

Q(a), where a is any element in the domain

( P(a)

Universal Denying the Hypothesis

(x (P(x) → Q(x))

(P(a), where a is any element in the domain

( (Q(a)

 

1.6 Introduction to Proofs

Terminology

Theorem – statement that can be proven to be true.

Propositions, facts, results – less important true statements.

Proof – valid argument that establishes truth of a theorem.

Axiom, postulate – a statement taken to be true, though not proven (e.g., Appendix 1)

Lemma – intermediate result proven, then used in proof of a theorem.

Corollary – a theorem that can be established directly as the result of another theorem

Conjecture – statement thought to be true, but not proven to be,

E.g., Collatz Conjecture, twin primes conjecture, Goldbach's conjecture

Definitions

Even integer

n is even if ( integer k, s.t., n = 2k.

Odd integer

n is odd if ( integer k, s.t., n = 2k+1.

Rational number

real number r is rational if ( integers p,q, q ≠ 0, s.t., r = p/q.

Irrational number

real number r is irrational if it is not rational.

FOREWORD: QUANTIFIERS, UI, UG

Quantifiers – yes or no? :: p. 76

– use of UI followed by UG requires choice of arbitrary element.

– this is not the same as choosing any specific element.

Fallacious proof

– To Prove: All integers are even.

– Proof:

UI: Choose any element of the domain, say 44.

Proof step: 44 = 2*22; therefore 44 is even.

UG: Since true of element chosen, it is true for all elements;

therefore all integers are even!

– Analysis:

The UI/UG combination requires choice of arbitrary element; choosing

a specific element, even if chosen at random, does not satisfy that

requirement.

A correct proof using UI/UG:

Prove: The sum of two odd integers is even.

       

Proof:

UI:

    Let:

a = 2k + 1, where k is any integer

b = 2 l + 1, where l is any integer

Comment: Since we are using the definition of odd integer and k & l are any arbitrary integers, this sets the stage allowing us to use UG later in the proof.

     Then:

     Then:

a + b = 2k + 1 + 2 l + 1 = 2(k + l +1)

    Let:

m = k + l +1

    Then:

a + b = 2m, which is even by definition.

UG:

    For all odd integers, a & b, a + b is even.

Comment: We can apply UG here because a and b were chosen to be arbitrary odd integers. By using a representation which adheres strictly to the definition of odd integer, our representation fits all odd integers. And therefore, anything we derive as true of a and b is also true of all odd integers.

       

Mathematicians shorthand:

Because the above proof process is used so often, mathematicians usually omit mentioning all of the things that are obvious by virtue of their frequent use. Thus, the above proof can be stated much more succinctly, as below.

1. Prove: The sum of two odd integers is even.

Proof:

Let:

a = 2k + 1

b = 2l + 1

Then:

a + b = 2k + 1 + 2 l + 1 = 2(k + l +1) ( EVEN

PROOF METHODS

Direct Proof

Direct proofs start with a proposition (mathematical fact) known to be true and proceed, step by step, to derive the conclusion directly. The above proof is a good example of direct proof. It starts with the definition of odd integer and then uses laws of arithmetic to derive other facts, leading eventually to the desired conclusion.

Indirect Proof – Proof by Contraposition

Proof by contraposition can be used when the proposition to be proved is of the form: p ( q. Recall that the Law of Contraposition states that p ( q is equivalent

to (q ( (p. Sometimes the latter is easier to prove than the former. A proof by contraposition proceeds by showing that if (q is true, then (p must also be true. Here is Example #3 from Rosen, p. 78.

Prove: For integer n: 3n + 2 is odd ( n is odd.

Prove contrapositive: For integer n: n is even ( 3n + 2 is even.

Proof:

Let:

n = 2k (definition of even integer)

Then:

3n+2 = 6k+2 = 2(3k+1) ( EVEN

Indirect Proof - Proof by Contradiction

Proof by contradiction is based upon the axiom that every proposition must be either True or False (Rosen, p. 1). Therefore, if we show that a proposition cannot be false, then it must be true. Here is Example #10 from Rosen, p. 80.

Prove: (2 is irrational.

Proof by contradiction:

Assume:

(2 is rational.

Then:

There exist integers p & q, q ≠ 0, s.t., (2 = p/q.

WOLG, we assume p & q have no common factors since, any common

factors can be eliminated by expressing p/q in lowest terms.

By the laws of arithmetic:

((2)2 = (p/q)2

2 = p2/q2

2q2 = p2

Thus:

p2 is even

By Exercise 16 (to be done later):

p is even

By definition:

p = 2k, for some integer k.

Therefore:

2q2 = (2k)2= 4k2

q2 = 2k2

And so:

q2 is even; and q is even.

q = 2l for some l.

But we now have a contradiction:

Since p = 2k and q = 2l, they have a common factor, namely 2. ξ

Therefore:

our assumption that (2 is rational is false; and we have proven that:

(2 is irrational.

This proof can also be written in an abbreviated form, as below.

Prove: (2 is irrational.

Proof by contradiction:

Assume:

(2 is rational.

Then:

There exist integers p & q, q ≠ 0,

s.t., (2 = p/q, with no common factors for p & q.

By the laws of arithmetic:

((2)2 = (p/q)2

2 = p2/q2

2q2 = p2 (p is even, i.e., p = 2k, for some integer k.

Then:

2q2 = (2k)2= 4k2

q2 = 2k2 (q is even, i.e., q = 2 l, for some integer l.

Therefore:

p and q have a common factor, namely 2. ξ

Therefore:

(2 is irrational.

Mistakes in proofs:

Division by zero

Example #15, p. 83

Logical fallacies

Affirming the conclusion, Example #16, pp. 83-84

Denying the hypothesis, Example #17, p. 84

Begging the question (circular reasoning), Example #18, p. 84

   

1.7 Proof Methods and Strategies

PROOF METHODS

Exhaustive Proof

Examine all of a relatively small number of cases; show true to all.

 

Prove: The only consecutive perfect powers less than 100 are 8 & 9.

{Example 2, p. 87}

Exhaustive proof:

List all powers < 100:

N N2 N3 N4 N5 N6 N7

1 1 1 1 1 1 1

2 4 8 16 32 64

3 9 27 81

4 16 64

5 25

6 36

7 49

8 64

9 81

Examine this list. The only consecutive integers in that list are 8 & 9.

Proof by Cases:

Use when no obvious way to prove for all values, but can individual cases readily provable.

Caveat: Make sure all cases are considered.

 

Prove: n2 ≥ n, for all integers.

{Example 3, p. 88}

Proof, by cases:

Integers naturally fall into 3 categories: negative, zero, and positive.

Case 1: n < 0.

Then n = -k, for some k ≥ 1.

And n2 = (-k)2 = k2 ≥ 1 > 0 > n.

So n2 ≥ n.

Case 2: n = 0.

Then n2 = 02 = 0 = n.

So n2 ≥ n.

Case 3: n > 0.

Then n ≥ 1.

And n*n ≥ 1*n.

So n2 ≥ n.

Exhaustive Proof Errors

1. Draw a conclusion for some, but not all instances. No matter how many instances are considered, no conclusion is warranted unless all instances are considered. Mathematicians sometimes call this the "Law of Small Numbers".

Example 8, p. 90.

2. Attempt proof by cases, but omit some cases.

Example 9, p. 90.

Existence Proofs - Constructive

Provide an element a such that P(a) is true.

 

Show: There is a positive integer that can be written as the sum of cubes of positive integers in two different ways.

{Example 10, p. 91}

Proof:

1729 = 103 + 93 = 123 + 13

Existence Proofs - Nonconstructive

Prove that (xP(x) is true. Often this is done via proof by contradiction. I.e., derive a contradiction from ((xP(x).

 

Show: There exist irrational numbers x and y such that xy is rational.

{Example 11, p. 91}

Proof:

We know (2 is irrational.

Consider (2(2. Either it is rational or irrational.

Case 1: (2(2 is rational.

Then let x = (2 and y = (2.

Case 2: (2(2 is irrational.

Then let x = (2(2 and y = (2.

So xy = ((2(2)(2= (2(2*(2= (22= 2.

So either in case 1 or in case 2 we have xy rational, though x and y are both irrational. Although we do not know which case meets the specification, we know that one must.

 

Exercise: Use the calculator to determine which of the two cases meets the specification.

Uniqueness Proofs

There are two parts to uniqueness proofs:

Existence: Show element with desired property exists.

Uniqueness: Show (x ≠ y, x does not have desired property;

or, show if x and y both have desired property, then x = y.

 

Show: For odd integers a & b, a ≠ b, (! integer c, s.t. |a – c| =|b – c|.

{Exercise 15, p. 103}

Proof:

Existence: We show existence constructively.

WOLG, assume a > b.

If |a – c| = |b – c|, then either a – c = b – c or a – c = c – b.

But a – c = b – c ( a = b, so a – c = c – b.

Reworking the equation:

a – c = c – b

a + b = 2c

c = (a + b)/2

Finally, we know c is an integer since a+b, the sum of two odd integers, is even.

Uniqueness:

Solutions of linear equations are unique.

Forward and Backward Reasoning:

Start with what you want to prove and working backward derive the premises. If that succeeds, we construct the proof by reversing the reasoning steps.

Caveat: This only works if at each step we produce statements that are equivalent, and therefore reversible.

Examples 14 & 15, p. 95 illustrate this process.

Adapting existing proofs:

Often a known proof can be adapted to prove a similar (or parallel) conclusion. This is illustrated in Example 16, p. 96. Also, in 1.6 homework answers, the proof of Exercise 1 was adapted in the proofs of Exercises 2 and 6.

Proof strategy in action

On p. 97 Rosen presents many strategies for generating hypotheses and conjectures and for seeking proofs or counterexamples. Among others, this includes "trying it on for size," the method applied to Exercise 7 of 1.6. In general, before we attempt a proof we should look at enough examples to convince us that what we are attempting to prove is indeed true. Sometime this may surprise us (see immediately below).

Look for counterexamples:

Sometimes, in the process of looking at examples, we will be surprised to find an example for which the proposed proposition does not hold. This will, of course, be a counterexample and will enable us to disprove by counterexample. Exercise 38 of 1.6 illustrates this.

Tilings:

Tiling problems can be fiendishly difficult, but sometimes a single observation can lead to a simple and easy solution. Examples 18-22, pp. 98-100 illustrate.

Role of Open Problems

There are some fascinating stories in the history of mathematics involving attempts to solve open problems. Among these are: Fermat's Last Theorem and the Collatz Conjecture.

One of keen interest to computer scientists is this question: is P = NP, where P is the set of problems that can be solved in polynomial time and NP is the set of problems which can be solved in non-deterministic polynomial time. Most computer scientists and mathematicians think that P ≠ NP, and that problems in the class NP require exponential (or worse) time. We will look at some exponential and factorial algorithms later in this course.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download