ProSet_MT2_App

MODULE TWO PROBLEM SET

This document is proprietary to Southern New Hampshire University. It and the problems within may not be posted on any non-SNHU website.

Christian Rojas

1

Directions: Type your solutions into this document and be sure to show all steps for arriving at your solution. Just giving a final number may not receive full credit.

Problem 1

Part 1. Indicate whether the argument is valid or invalid. For valid arguments, prove that the argument is valid using a truth table. For invalid arguments, give truth values for the variables showing that the argument is not valid.

(1)

(p ∧ q)→ r

∴ (p ∨ q)→ r

• An argument is valid when premises are True while the conclusion is also True.

• The argument becomes invalid when there is at least one row that is False while the conclusion is True.

• Here, our premise are (p ∧ q) → r and (p ∨ q) → r is the conclusion.

• (p ∨ q) → r is our conclusion. Since it is false, this argument is invalid.

Part 2. Converse and inverse errors are typical forms of invalid argu- ments. Prove that each argument is invalid by giving truth values for the variables showing that the argument is invalid. You may find it eas- ier to find the truth values by constructing a truth table.

(a) Converse error

p→ q q

∴ p

• Since we are given p → q • ∴ p • (p → q) ∧ q ≡ p

• p q p→ q (p→ q) ∧ q q F F T F F F T T T T T F F F F T T T T T

• Given the Truth Table, we can see that the last two columns are iden- tical, thus making this statement valid.

(b) Inverse error

p→ q ¬p

∴ ¬q

• Given (p→ q) • ¬p • (p→ q) ∧ ¬p ≡ ¬q • Truth Table

p q p→ q ¬p (p→ q) ∧ ¬p ¬q F F T T T T F T T T T F T F F F F T T T T F F F

• From the truth table we are able to observe the last two columns which are not equivalent; therefore, the given argument is invalid.

Part 3. Which of the following arguments are invalid and which are valid? Prove your answer by replacing each proposition with a variable to obtain the form of the argument. Then prove that the form is valid or invalid.

(a)

The patient has high blood pressure or diabetes or both. The patient has diabetes or high cholesterol or both.

∴ The patient has high blood pressure or high cholesterol.

• The Patient has high blood pressure(p) or diabetes(q) or both: • This is represented by p ∨ q • The patient has diabetes or high cholesterol(r) or both can be repre-

sented by: • q ∨ r • This can be written as (p ∨ q) ∨ (q ∨ r) =⇒ p ∨ q ∨ r • Given the statement, it is invalid.

Problem 2

Part 1. Which of the following arguments are valid? Explain your reasoning.

(a) I have a student in my class who is getting an A. Therefore, John, a student in my class, is getting an A.

• Let s represent a student • A(x) represents getting an A • b represents John • I have a student in my class who is getting an A: ∃s A(s) • John needs to not be that student: b 6= s • Since we do not know if John is that student, so the argument is

invalid. (b) Every Girl Scout who sells at least 30 boxes of cookies will get a prize.

Suzy, a Girl Scout, got a prize. Therefore, Suzy sold at least 30 boxes of cookies.

• P(x): Girl X who is selling 30 boxes of cookies. • Q(x): Girl X got a prize • ∀x (P (x) ∧ Q(x)) • Suzy ∈ so: ∀x Q(x) ∧ ∀x P (x) • With Q(Suzy) is true, P(Suzy) does not need to be true. Hence this

statement is invalid.

Part 2. Determine whether each argument is valid. If the argument is valid, give a proof using the laws of logic. If the argument is invalid, give values for the pred- icates P and Q over the domain a, b that demonstrate the argument is invalid.

(a)

∃x (P (x) ∧ Q(x))

∴ ∃xQ(x) ∧ ∃xP (x)

(∃x) [P (x) ∧ Q(x)] =⇒ ((∃x) Q(x)) ∧ ((∃x) P (x)) 1.) Premise: (∃x) [P (x) ∧Q(x)] 2.) Existential Instantiation 1: P (y) ∧ Q(y) 3.) Simplification 2: P(y) 4.) Simplification 2: Q(y) 5.) Existential Generalization 3: (∃x) P (x) 6.) Existential Generalization 4: (∃x) Q(x) 7.) ((∃x)Q(x)) ∧ ((∃x)P (x)) =⇒ The argument given is valid.

(b)

∀x (P (x) ∨ Q(x))

∴ ∀xQ(x) ∨ ∀xP (x)

∀x (P (x) ∨ Q(x)) =⇒ ∀x Q(x) ∨ ∀x P (x) 1.) Premise: ∀x (P (x) ∨ Q(x)) 2.) Universal Instantiation: P (c) ∨Q(c) =⇒ The given argument is not valid.

Problem 3

Prove the following using a direct proof. Your proof should be expressed in com- plete English sentences.

If a, b, and c are integers such that b is a multiple of a3 and c is a multiple of b2, then c is a multiple of a6.

• As it is given that b is a multiple of a3

• Thus: b = a3k • Given that c is a multiple of b2

• These will be some integer ’m’, thus c = mb2

• Put the value of b =⇒ c = mb2 = m(ka3)2

• =⇒ c = mk2(a3)2 = mk2a6

• m and k are integers so mk2 is integer n. • =⇒ c = mk2a6 = na6

• Based on this, c is a multiple of a6

Problem 4

Prove the following using a direct proof:

The sum of the squares of 4 consecutive integers is an even integer.

• Let n, n+1, n+2, n+3 be consecutive integers • Claim: n2 + (n + 1)2 + (n + 2)2 + (n + 3)2 is an even integer. • That is n2 + (n + 1)2 + (n + 2)2 + (n + 3)2 = 2m for integer m. • Consider: n2 + (n + 1)2 + (n + 2)2 + (n + 3)2

= n2 + (n2 + 2n + 1) + (n2 + 4n + 4) + (n2 + 6n + 9) = 4n2 + 12n + 14 = 2 * m, for m = 2n2 + 6n + 7 ∈ Z

Problem 5

Prove the following using a proof by contrapositive:

Let x be a rational number. Prove that if xy is irrational, then y is irrational.

Let x, y be rational.

• x = p/q and y = r/s • Where p, q, r, s ∈ Z and (p, q) = (r, s) = 1

• xy = p q X

r s

pq rs

• Since, p, q, r, s ∈ Z, pq, rs ∈ Z

• pq rs ∈

• x and y are rational, then xy are rational. If x is rational, and xy is rational, then y is irrational.

Problem 6

Prove the following using a proof by contradiction:

The average of four real numbers is greater than or equal to at least one of the numbers.

• Let a, b, c, d be four real numbers.

• a+b+c+d 4 < a

• a+b+c+d 4 < b

• a+b+c+d 4 < c

• a+b+c+d 4 < d

• =⇒ a + b + c + d > (a+b+c+d 4 )4

• a+b+c+d 4 > a+b+c+d

4 Is not possible.

• a+b+c+d 4 ≥ at least one of a,b,c,d

Problem 7

Let q = a

b and r =

c

d be two rational numbers written in lowest terms. Let

s = q + r and s = e

f be written in lowest terms. Assume that s is not 0.

Prove or disprove the following two statements.

a. If b and d are odd, then f is odd.

b. If b and d are even, then f is even.

Since q = a/b and r = c/d, let s = q+r s = a/b + c/d = (ad + bc)/bd = e/f e = ad + bc and f = bd

a) If b and d are odd, we can be sure that the product of two odd numbers is always odd. Therefore, f = b*d is odd. Proof: b(d-1+1) = b(d-1)+b Since d is odd, d-1 is even. Therefore b(d-1) is even. Since b is odd, the sum of an odd number and even number will always be odd. statement a) is odd so we can prove this to be true.

b) If b and d are even then we know a product of two even numbers is even, thus making f=b*d even. This statement is also true.

Problem 8

Define P (n) to be the assertion that:

n∑ j=1

j2 = n(n + 1)(2n + 1)

6

(a) Verify that P (3) is true.

12 + 22 + 32 = (3(3 + 1)(2 ∗ 3 + 1))/6 1 + 4 + 9 = 3* 4* 7/6 14 = 14 means P(3) is true.

(b) Express P (k).

12 + 22 + 32 + (k − 1)2 + k2 = (k ∗ (k + 1)(2 ∗ k + 1))/6

(c) Express P (k + 1).

12 + 22 + 32 + (k − 1)2 + k2 = ((k + 1) ∗ (k + 1 + 1)(2 ∗ (k + 1) + 1))/6

(d) In an inductive proof that for every positive integer n,

n∑ j=1

j2 = n(n + 1)(2n + 1)

6

what must be proven in the base case?

We need to prove that the formula is true for n = 1 12 = (1(1 + 1)(2 ∗ 1 + 1))/6 1=1, thus the statement is true.

(e) In an inductive proof that for every positive integer n,

n∑ j=1

j2 = n(n + 1)(2n + 1)

6

what must be proven in the inductive step?

In the induction proof we must start with a base case: 1.) Show true for n=1 2.) Assume true for n=k assumption 3.) Show true for n=k+1. This is an inductive step, so n=k+1 must be proven.

(f) What would be the inductive hypothesis in the inductive step from your previous answer?

• We must prove our assumption(induction hypothesis) n=k by the hy- pothesis(assumption). By proving that we can say n=k+1 is true.

(g) Prove by induction that for any positive integer n, n∑

j=1

j2 = n(n + 1)(2n + 1)

6

• As seen in previous answers, n=1 • Assume this is true for n=k, we can also assume: • Sk + ak+1 = k(k + 1)(2k + 1)/6 + ak+1

• Replace ak+1 by (k + 1)2

• Sk+1 = k(k + 1)(2k + 1)/6 + (k + 1)2

• To get a common denominator, multiply the last term by 6/6: • Sk+1 = k(k + 1)(2k + 1)/6 + 6(k + 1)2/6 • Simplify: • Sk+1 = (k + 1)[k(2k + 1) + 6(k + 1)]/6 • Sk+1 = (k + 1)(2k2 + k + 6k + 6)/6 • Sk+1 = (k + 1)(2k2 + 7k + 6)/6 • Sk+1 = (k + 1)(k + 2)(2k + 3)/6 • By mathematical induction, 1 + 4 + 9 + .... + n2 = n(n + 1)(2n + 1)/6

for positive integers ’n’.