415 Review for Midterm - DePaul University
415 Review for Midterm
1. For propositions P and Q below, state whether or not P ( Q. Write a truth table to justify your answer.
P: p ( q ( r
Q: (p ( r) ( (q ( r)
ANSWER: P ( Q. Truth table is as follows.
| p | q | r | p ( q ( r |(p ( r) ( (q ( r) |
|T |T |T |T |T |
|T |T |F |F |F |
|T |F |T |T |T |
|T |F |F |F |F |
|F |T |T |T |T |
|F |T |F |F |F |
|F |F |T |T |T |
|F |F |F |T |T |
2. Determine the truth value of the following proposition. If it is true, prove it using direct proof. If it is false, state the negation explicitly and give a counterexample.
Proposition: The sum of any three consecutive integers is divisible by 3.
ANSWER: True.
Proof: Let three consecutive integers a, b, c be (n+1), (n+2) and (n+3) respectively. Then,
a + b + c = (n+1) + (n+2) + (n+3)
= 3n + 6
= 3(n+2)
Since n+2 is an integer, 3(n+2) is divisible by 3.
3. Determine the truth value of the following proposition. If it is true, prove it using direct proof. If it is false, state the negation explicitly and give a counterexample.
Proposition: (a(b such that a, b are real numbers, sqrt(a+b) = sqrt(a) + sqrt(b).
ANSWER: False.
Negation of the proposition is (a(b such that a, b are real numbers, sqrt(a+b) != sqrt(a) + sqrt(b). Examples of such a, b are a =1 and b = 2.
4. Prove the following proposition by using proof by contradiction.
Proposition: If a product of two positive real numbers is greater than 100, then at least one of the numbers is greater than 10.
ANSWER: Proof by contradiction.
The proposition states that, (a(b. such that a, b are real numbers, if a * b > 100, then a > 10 or b > 10. We show this by contradiction.
[Negation of the proposition] Suppose not, that is, (a(b. such that a, b are real numbers, a * b > 100 and a = 1 + nx, for x >= -1 and n = 1,2,...
ANSWER: Proof by induction
Basic Step (n = 1):
LHS = 1+x
RHS = 1+x So, LHS >= RHS ... (A)
Inductive Step:
Assume (1 + x)n >= 1 + nx, for n >= 1.
Show (1 + x)n+1 >= 1 + (n+1)x
LHS = (1 + x)n+1 = (1 + x)(1 + x)n
>= (1 + x) (1 + nx) by inductive hypothesis
= 1 + (n + 1)x + nx2
>= 1 + (n + 1)x since nx2 >= 0
= RHS
So, LHS >= RHS ... (B)
By (A) and (B), the theorem is true.
7. (Section 1.6, #22; p. 47) By experimenting with small values of n, guess a formula for the given sum:
1 1 1
--- + --- + .. + -----
1*2 2*3 n(n+1)
then use induction to verify your formula.
ANSWER:
First we claim that
1 1 1 n
--- + --- + .. + ----- = ---
1*2 2*3 n(n+1) n+1
for n = 1, 2, ...
Proof: by induction.
Basic Step (n = 1):
LHS = 1/2
RHS = 1/2 So, LHS = RHS ... (A)
Inductive Step:
Assume
1 1 1 n
--- + --- + .. + ----- = ---
1*2 2*3 n(n+1) n+1
Show
1 1 1 1 n
--- + --- + .. + ----- + ---------- = ---
1*2 2*3 n(n+1) (n+1)(n+2) n+1
LHS
1 1 1 1
--- + --- + .. + ----- + ----------
1*2 2*3 n(n+1) (n+1)(n+2)
n 1
= --- + ----------
n+1 (n+1)(n+2)
n(n+2) + 1
= ----------
(n+1)(n+2)
n^2 + 2n + 1
= ------------
(n+1)(n+2)
(n+1)^2
= ----------
(n+1)(n+2)
n+1
= ---
n+2
= RHS So, LHS = RHS ... (B)
By (A) and (B), the formula is true.
8. Write an algorithm that counts the number of even numbers in a sequence s = {s1, s2, .., sn}, where si (1 ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- performance review for a supervisor
- sample annual review for employees
- stock market review for today
- performance review for employees
- performance review for hr manager
- positive review for car salesman
- grammar review for 5th grade
- free pharmacology review for nurses
- annual review for sales rep
- peer review for nurses examples
- sample progress review for employees
- sample review for mortgage lender