## We Promise to Make your Math Frustrations Go Away!

Try the Free Math Solver or Scroll down to Tutorials!

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# Discrete Structure Homework: Logic II

1. (10) (1.6: 6) Use a direct proof to show that the product of two odd integers is
odd.

Let a, b be odd integers. Then we can write a = 2x + 1 and b = 2y + 1 for
some integers x, y. Multiplying a and b gives:

ab = (2x + 1)(2y + 1)
= 4xy + 2(x + y) + 1
= 2(2xy + x + y) + 1

Therefore the product of two odd integers is odd.

2. (1.6: 12) Prove or disprove that the product of a nonzero rational number and
an irrational number is irrational.

By contradiction: Let x ∈ Q \ {0} and y ∈ R \ Q. Assume that xy = z ∈ Q.
Then there exists a, b, c, d ∈ Z such that Then

xy = z
y = zx-1

y ∈ Q

Since y ∈ R\Q, this contradicts our assumption and the product of a nonzero
rational number and and irrational number is irrational.

3. (1.6: 16) Prove that if m and n are integers and mn is even then m is even or n
is even.

Proof by contradiction: Assume both m and n are odd and mn is even. Then
from the definition of odd integers there exists ∈ Z such that
and . Then , which is an odd integer.
Since mn is even, this contradicts our assumption and at least one of m or n
is even.

4. (1.6: 20)Prove the proposition P(1), where P(n) is the proposition “If n is a
positive integer, then n2 ≥ n”. What kind of proof did you use?

P(1) states that 12 ≥ 1. Since 12 = 1, P(1) is true. Direct proof.

5. (15) (1.6: 28) Prove the m2 = n2 if and only if m = n or m = -n.

If m = n or m = -n, then m2 = (±n)2 = n2. If m2 = n2, then

0 = m2 - n2
= (m - n)(m + n)

Since ab = 0 if and only if a = 0 or b = 0, therefore either m - n = 0, and
m = n or m + n = 0, and m = -n. (NOTE: poorly worded problem as it
doesn't state the domain of m, n. If m, n ∈, for example, and m = 2, n = 6,
then m2 ≡ 4 mod 8 and n2 = 36 = 8(4) + 4 ≡ 4 mod 8)

6. (1.7: 2) Prove that there are no positive perfect cubes less than 1000 that are
the sum of the cubes of two positive integers.

Proof by exhaustion: The only possible values for a, b, c are the integers
1, 2, . . . , 9. The table below gives a, a3, then c3-a3, for all c, a pairs whose result
is greater than zero. None of these produces a perfect cube (b3), therefore
no a, b, c ∈ Z, a, b, c > 0 exists with a3 + b3 = c3 and c < 1000.

7. (10) (1.7: 6) Prove that there is a positive integer that equals the sum of the positive
integers not exceeding it. Is the prove constructive or non-constructive.

1 = 1, therefore this hypothesis is true. This is a constructive proof.

8. (1.7: 8) Prove that either (2 × 10500 + 15) or (2 × 10500 + 16) is not a perfect
square. Is the proof constructive or non-constructive.

Proof by contradiction: Let a = 2 × 10500 + 15 and b = a + 1. Assume
both a, b are perfect squares a = x2, b = y2. Therefore
b - a = y2 - x2 = 1. But y2 - x2 = (y - x)(y + x) = 1, and y - x, y + x ∈ Z.
Therefore y - x = y + x and equals either 1 or -1. But this implies that
-x = x or x = 0, a = 0 which contradicts the definition of a. Therefore both
a and b are not perfect squares

9. (1.7: 12) Prove or disprove that if a, b ∈ Q, then ab ∈ Q.

Proof by counter example: Let a = 2, . We know that , therefore
a, b ∈ Q does not imply that ab ∈ Q.

10. (1.7: 14) Show that if a, b, c ∈ R and a ≠ 0, then there is a unique solution x
of the equation ax + b = c.

Direct proof: Since a ≠ 0, , and x = (c-b)a-1. If x ∈ R is a solution
to ax + b = c, then ax = c - b and x = (c - b)/a, therefore the solution is
unique.

11. (15) (1.7: 28) Prove that there are no solutions x, y ∈ Z to the equation 2x2 +
5y2 = 14.

Proof by contradiction: If x, y ∈ Z and 2x2 + 5y2 = 14 then WLOG we can
assume x, y ≥ 0. We also know x, y ≠ 0 since no x or y exists such that
2x2 = 14 or 5y2 = 14. Thus 0 < x < 3 and 0 < y < 2, and y = 1. This
implies 2x2 = 14 - 5 = 9. But 9 is odd and 2x2 is even, therefore no x, y ∈ Z
exist 5y2 = 14 - 2x2.

12. (1.7: 36) Prove or disprove that if you have an 8 gallon jug (8G) of water and
a 5G and 3G empty jugs, then you can measure 4G by successively pouring
some of or all of the water in one jug into another.

 Start Pour 5g from 8G to 5G Pour 3g from 5G to 3G Pour 3g from 3G to 8G Pour 2g from 5G to 3G Pour 5g from 8G to 5G Pour 1g from 5G to 3G