SM242 Week 4 Notes based on Epp Chapter 2 and Chapter 3
I. Logic (continued)
38. Arguments With Quantified Statements
An argument with quantified statements is valid iff the truth of the conclusion necessarily follows from the truth of the premises. (This definition of validity is the same as that discussed in propositional calculus.)
Analyzing Arguments with Diagrams (Leibniz) Arguments with quantified statements can often be analyzed be sketching a picture of the premises, showing how the premises are related. The sketch can then be used to analyze the truth of the conclusion.
Example: Is the following argument valid or invalid?
All poodles are dogs
Felix the Cat is not a dog
Felix the Cat is not a poodle
Example: Is the following argument valid?
All Meryl Streep movies are chick-flicks
Texas Chainsaw Massacre is not a chick-flick
Texas Chainsaw Massacre is not a Meryl Streep movie
Example: Is the following argument valid?
All midshipman are under 28
MIDN Mincks is a midshipman
MIDN Mincks is under 28
Example: Is the following argument valid?
All midshipman are deserving of trust
MIDN Waymouth is deserving of trust
MIDN Waymouth is a midshipman
Example: Is the following argument valid?
No midshipman has green skin
The Incredible Hulk has green skin
The Incredible Hulk is not a midshipman
Example: Is the following argument valid?
All prisoners of war are being treated under Geneva Convention rules
Taliban captives are not prisoners of war
Taliban prisoners are not being treated under Geneva Convention rules
39. Examples
1. For each of the following arguments, state if the argument is valid or invalid. If valid, state the applicable rule of inference. If invalid, state the error.
If MIDN Wolz solves this problem correctly then MIDN Wolz says the answer is “Yes.”
MIDN Wolz said the answer is “Yes.”
MIDN Wolz solved this problem correctly.
If I get less than 50 on the next quiz I will throw up.
I scored a 99 on the next quiz
I did not throw up.
All midshipmen must attend morning formation.
MIDN Vandal must attend morning formation.
MIDN Vandal is a midshipman.
All hungry midshipmen think King Hall food tastes good.
MIDN Ogden in not hungry.
MIDN Ogden thinks King Hall food sucks
If MIDN Tublin is a bad logician then MIDN Tublin will say “Invalid.”
MIDN Tublin says “Invalid.”
MIDN Tublin is a bad logician.
If we bomb every cave then we will kill Osama Bin Laden.
We did not kill Osama Bin Laden
We did not bomb every cave.
All Republicans want to increase military spending.
Senator JohnMcCain wants to increase military spending.
Senator John McCain is a Republican.
All midshipmen who are geeks think that playing video games is a waste of time.
MIDN Burkardt is not a geek.
MIDN Burkardt thinks that playing video games is not a waste of time.
2.Express the following statement using symbolic logic:
All midshipmen have a uniform that they hate.
3. Express the negation of your answer question 2 above, using symbolic logic.
4. Express the following statement using symbolic logic:
There is a member of the Brigade of Midshipmen who has dated at least one midshipman in every Company.
5. What would you have to do to determine that the statement in question 5 above is false? (Assume that all midshipmen will answer any questions you ask them honestly.)
6. Express the negation of your answer for question 5 above, using symbolic logic.
7. (This is based on last week’s stunningly poor quiz performance) You are well into your typical 10th hour of sleep, when you hear a commotion on the roof, run up the stairs and see that Martians have landed on Bancroft Hall! They say “Take me to your leader.” You ask how many Martians there are and are given a paper that says: 101. You run to tell your Company Officer, but as you approach the office you realize that Martians have four fingers, so you must have been told the number of Martians in base 4. What is the number of Martians you report to your Company Officer?
8. (Text Section 2.1 Problem 21(d)) Rewrite the statement
The product of any two odd integers is odd
in the form: ______, if ______then ______
9. (Text Section 2.1 Problem 23(b)) Rewrite the statement
Some questions are easy
in the form: ______s.t. ______
10. (Text Section 2.1 Problem 26(b)) Let Real(x) be “x is a real number,” Pos(x) be “x is a positive real number” and Neg(x) be x is a negative real number. Translate the following statement to plain English.
x, Real(x) and Neg(x) → Pos(-x)
11. (Text Section 2.2 Problem 1) Which of the following is a negation of the statement
“All discrete mathematics students are athletic.”
a. There is a discrete mathematics student who is nonathletic.
b. All discrete mathematics students are nonathletic.
c. There is an athletic person who is a discrete mathematics student.
d. No discrete mathematics students are athletic.
e. Some discrete mathematics students are nonathletic
f. Some nonathletic people are not discrete mathematics students.
12. (Text Section 2.2 Problem 4) Write an informal negation of the following statement.
All pots have lids.
All birds can fly
Some pigs can fly
Some dogs have spots.
13. (Text Section 2.2 Problem 8) Consider the statement
“There are no simple solutions to life’s problems.”
Express the statement using symbolic logic.
What is the negation of this statement?
14. (Text Section 2.2 Problem 10) Write a negation for this statement:
computer programs P, if P compiles without error messages, then P is correct.
15. (Text Section 2.2 Problem 11) Determine if the proposed negation is correct:
Statement: The sum of any two irrational numbers is irrational
Proposed negation: The sum of any two irrational numbers is irrational
16. (Text Section 2.2 Problem 18) Write a negation for the statement:
real numbers x, if then x > 0.
17. (Text Section 2.2 Problem 21) Write a negation for the statement:
nZ , if n is prime then n is odd or n = 2.
18. (Text Section 2.2 Problem 39) Write this statement in if-then form.
Being divisible by 8 is a sufficient condition for an integer to be divisible by 4.
19. (Text Section 2.2 Problem 43) Express the statement in symbolic logic:
Having a large income is not a necessary condition for a person to be happy.
20. (Text Section 2.2 Problem 46) The computer scientists Richard Conway and David Gried once wrote:
The absence of error messages during translation of a computer program is only a necessary and not a sufficient condition for reasonable program correctness.
Rewrite this statement without using the words necessary or sufficient.
******************** END OF EPP CHAPTER 2 ********************
II. Methods of Proof and Number Theory (Epp Chapter 3)
1. Some Important Definitions
A. Definition: An integer n is even iff an integer j s.t. n = 2j.
Definition: An integer n is odd iff an integer j s.t. n = 2j + 1.
- Examples
- Is –11 even or odd?
- Is 0 even or odd?
- If x and y are integers is 26x + 38y + 1 even or odd?
- If z is an integer is 2even or odd?
- Is that crazy “Best Kept Buildings” worker who wears sandals odd?
- Definition (prime number)
A positive integer p > 1 is prime iff it cannot be written as the product of 2 smaller positive integers. More formally:
If an integer is not prime, it is said to be composite. We take the negation of the universal conditional statement defining a prime number to obtain the definition of a composite number:
A positive integer c > 1 is composite iff
Note that 1 is not a prime number.
- Example. What are the first 10 prime numbers?
2. Proof Techniques
First, a few quick definitions:
- Theorem: An important statement that is proven true.
- Corollary: A true statement that can be shown to be true using a theorem (e.g., as a special case of a theorem). Usually a corollary is an interesting result which follows immediately from a theorem.
- Lemma: A true statement that is useful in proving a theorem, but is not too terribly interesting in and of itself.
A proof is an argument that demonstrates that a statement is true. In light of the bulleted terms above, a proof is an argument that proves a theorem. We will learn many different techniques for proving theorems, and we will draw our examples from number theory.
So, keep in mind that we are learning two topics at once. We are learning number theory and proof techniques, and using proof techniques to demonstrate theorems from number theory.
3. Proof Technique 1: Constructive Proof of Existence
If we want to prove the statement
x in D s.t. P(x)
we have to
Example:Prove:an integer k s.t. is prime.
4. Proof Technique 2: Disproof by Counterexample
To disprove the universal conditional statement
x in D, if P(x) then Q(x)
we have
Example: Prove or disprove the statement: real numbers x and y, if xy then .
5. Proof Technique 3: Exhaustion
The universal conditional statement
x in D if P(x) then Q(x)
can be proven by
Example: Prove that for all positive even integers less that 7, - n + 41 is prime.
Example (Goldbach’s conjecture): Prove that every even integer greater than 2 is the sum of two primes. (We can’t use the method of exhaustion…the domain is infinite). We suspect this statement is true since it is true for every even integer checked to date. Goldbach’s conjecture has been shown to be true up to, but this doesn’t consist of a proof that the statement is true. There may be an (as yet) unchecked even integer for which Goldbach’s conjecture is false.
Example (Euler’s conjecture): In 1769 Euler stated the following conjecture:
There are no integers a, b, c and d for which .
Example (Fermat’s Last Theorem FLT): In 1637, scribbled in a margin, Fermat wrote his famous conjecture:
There are no positive integers x, y and z such that for 3.
6. Proof Technique 4: Generalizing from the Generic Particular (also called “Direct Proof”)
Suppose we want to prove
P(x)Q(x).
Recall that P(x)Q(x) is true in all cases unless
To do this, we:
- Pick a specific but completely arbitrary x from the domain for which P(x) is true. The x that we choose must be generic, so that it can represent any element of the domain.
- Show that Q(x) is true.
That is, we assume that x is such that P(x) is true, and show that Q(x) must also be true. This proof technique is called direct proof or generalizing from the generic particular.
Example: Prove that the sum of any two even integers is even. That is, prove:
Proof:
At this point, we yell at the top of our lungs:
which means:
We’ll abbreviate this as:
Example. Prove that if n is an odd integer, then is odd. That is, prove:
Proof:
Example: Prove that if x is a number between 0 and 1 then . That is, prove:
Example (Epp Section 3.1 Problem 26):
Prove that the difference between any odd integer minus any even integer is odd.
Prove:
Proof:
Why would it have been wrong to begin the proof this way:
Why would it have been wrong to begin the proof this way:
Example. (Epp Section 3.1 Problem 31):
Prove that this statement is false: There exists an integer m 3 such that is prime.
Prove: an integer m 3 such that is prime.
Proof:
Example Prove that the product of any two even integers is even.
Prove:
Proof (Take 1): Let x = 6 and y = 4. Then = 24 which is even. QED.
Proof (Take 2): Let x be an arbitrary even integer and lety be an arbitrary even integer.
Then, x = 2k and y = 2k for some integer k.
Then
Since k is an integer, then is an integer. Let’s call this integer m.
Thus .
Thus is even. QED.
Example for you to think about: Prove that the product of any even integer with another integer (that might be even or might be odd) is even.
7. Rational Numbers
- We know that if a and b are integers, then a + b, a – b and ab are integers. But a / b may not be an integer.
- Definition. A real number x is rational iff integers j and k such that and k0.
A number that is not rational is said to be irrational.
- Examples:
Is 13 a rational number?
Is 0.7652 a rational number?
Is 0 a rational number?
Is 0.34343434… a rational number?
- Example: Prove that every integer is rational.
Proof.
- Example: Prove that the sum of any two rational numbers is rational.
Prove:
Proof
F. Example (Epp Section 3.2 Problem 27)
Suppose a, b, c and d are integers and Suppose x is a real number that satisfies the equation:
Must x be rational?
G. Example (Epp Section 3.2 Problem 29)
Prove that if one solution to the quadratic equation is rational (where b and c are rational), then the other solution is also rational.
8. Divisibility
- Let n and d be two integers, with . We say n is divisible by d iff an integer k s.t. n = dk. Alternately, n is divisible by d iff is an integer.
Notation: We write n is divisible by d as d | n. This is read “d divides n.” [1]
- If n is divisible by d we say
- d divides n
- d is a factor of n
- d is a divisor of n.
- n is a multiple of d.
- Examples:
- Does 3 | 21?
- Is 5 a factor of –5?
- Is 48 a multiple of –16?
- Does 5 | 0?
- Does –2 divide 2?
- Does 3 | 7?
- If x and y are integers, does 4 divide 8x + 24y?
- Nondivisibility
How would we define nondivisibility?
E. Prime Numbers Revisited A number k > 1 is prime iff its only positive divisors are 1 and k. To put this yet another way: A prime is an integer greater than 1 that is divisible only by 1 and itself.
9. Examples
Example 1: Prove that for integers i, j and k, if i | j and j | k then i | k.
Proof:
Example 2: (Epp Section 3.3 Problem 15)
Prove that for all integers a, b and c, if a | b and a | c then a | (b+c).
Proof:
1
[1] Note that this is the same symbol that is sometimes used for “such that.” The intended use should be clear from the context.