Description
Problem 1. (20 points)
Excercise 60 of Section 1.4 (page 56).
Solution.
Universal Discourse of x consists of all English text P(x): x is a clear explanation
Q(x): x is satisfactory
R(x): x is an excuse
a) ∀x(P(x) → Q(x))
b) ∃x(R(x) ∧ ¬Q(x))
c) ∃x(R(x) ∧ ¬P(x))
d)
Step Reason
1. ∃x(R(x) ∧ ¬Q(x)) Premise
2. R(a) ∧ ¬Q(a) Existential instantiation on 1
3. ∀x(P(x) → Q(x)) Premise
4. P(a) → Q(x) Universal instantiation on 3
5. ¬Q(x) By simplification on 2
6. ¬P(x) Modus Tollens of 4 and 5
7. R(a) By simplification of 2
8. R(a) ∧ ¬P(a) Conjunction of 6 and 7
9. ∃(R(x) ∧ ¬P(x)) Existential Generalization of 8
Holding a) and b) as valid premises, c) does follow.
1
Problem 2. (20 points)
Exercise 36 of Section 1.5 (page 68).
Solution.
a) No one has lost more than $1000 playing the lottery
Let L(x, y) represent a person x who has lost y dollars playing the lottery
The statement using quantifiers is:
¬∃x∃y(y > 1000 ∧ L(x, y))
Now negate the statement
¬[¬∃x∃y(y > 1000 ∧ L(x, y))] ≡ ∃x∀y¬(y > 1000 ∧ L(x, y))
This reads as someone has lost less than or equal to $1000 playing the lottery
b) There is a student in this class who has chatted with exactly one other student
Let B(x, y) represent a student in class, x, has chatted with a student in class y but not any of the other
students in class, z
∃x∃y∀z(x 6= y ∧ x 6= z ∧ B(x, y) ∧ ¬B(x, z))
Now Negate the statement:
¬[∃x∃y∀z(x 6= y ∧ x 6= z ∧ B(x, y) ∧ ¬B(x, z))] ≡ ∀x∀y∃z¬(x 6= y ∧ x 6= z ∧ B(x, y) ∧ ¬B(x, z))
This reads as everyone in class has spoken with no one or everyone
c) No student in this class has sent e-mail to exactly two other students in class
Let A(x, y) represent a student in class, x who has sent an email to student in class y
¬∃x∃y∃z(y 6= z ∧ x 6= z ∧ (A(x, y) ∧ A(x, z)))
Now Negate the statement:
¬[¬∃x∃y∃z(y 6= z ∧ x 6= z ∧ (A(x, y) ∧ A(x, z)))] ≡ ∃x∀y∀z¬(y 6= z ∧ x 6= z ∧ (A(x, y) ∧ A(x, z)))
This reads as some student in class has sent email to exactly two other students in class
d) Some student has solved every exercise in this book
Let D(x, y) represents a student in class x who has solved exercise y in the book
∃x∀yD(x, y)
Now negate the statement:
¬[∃x∀yD(x, y)] ≡ ∀∃yD(x, y)
This reads as every student in class has solved an exercise in the book
e) No student has solved at least one exercise in every section of the book
Let P(x, y) represent a student x in class has solved exercise y
Let B(y, z) represent a exercise y in section z of the book
¬∃x∃y∀z(P(x, y) ∧ B(y, z))
Now negate it:
¬[¬∃x∃y∀z(P(x, y) ∧ B(y, z)]) ≡ ∃x∃y∀z(P(x, y) ∧ B(y, z)
This reads as some student has solved at least one exercise in every section of this book
2
Problem 3. (20 points)
Exercise 34 of Section 1.6 (page 80).
Solution.
1. Logic is difficult or not many like logic
2. If mathematics is easy then logic is not difficult
The universal discourse for x is all students
A(x) represents logic is difficult to students
B(x) represents many students like logic
C(x) represents mathematics is easy to students
The premises can be rewritten as
1. A(x) ∨ ¬B(x)
2. C(x) → ¬A(x)
a) That mathematics is not easy, if many students like logic
B(x) → ¬C(x) ≡ ¬B(x) ∨ ¬C(x)
The argument is:
A(x) ∨ ¬B(x)
¬C(x) → ¬A(x)
∴ ¬B(x) ∨ ¬C(x)
Using rules of inference resolution, this conclusion is valid
Since ¬B(x) ∨ ¬C(x) is valid thus B(x) → ¬C(x) is valid as well
b) That not many students like logic, if mathematics is not easy
¬C(x) → ¬B(x) ≡ C(x) ∨ ¬B(x)
The argument is:
A(x) ∨ ¬B(x)
¬C(x) → ¬A(x)
∴ C(x) ∨ ¬B(x)
If the inference is used, by resolution, the correct conclusion would be ¬C(x)∨¬B(x) not C(x)∨¬B(x) ∴
the statement That not many students like logic, if mathematics is not easy is invalid
c) That mathematics is not easy or logic is difficult.
¬C(x) ∨ A(x)
The argument is:
A(x) ∨ ¬B(x)
¬C(x) → ¬A(x)
∴ ¬C(x) ∨ A(x)
If inference by resolution is used, the correct conclusion would be ¬B(x) ∨ ¬C(x) not ¬C(x) ∨ A(x) ∴
the statement That mathematics is not easy or logic is difficult is invalid
d) That logic is not difficult or mathematics is not easy.
¬A(x) ∨ ¬C(x)
A(x) ∨ ¬B(x)
¬C(x) → ¬A(x)
∴ ¬A(x) ∨ ¬C(x)
This statement is ≡ C(x) → ¬A(x) which is exactly the same as the 2nd premise ∴ the statement
¬A(x) ∨ ¬C(x) is valid
3
e) That if not many students like logic, then either mathematics is not easy or logic is not difficult.
¬B(x) → (¬C(x) ∨ ¬A(x)) Initial statement
¬B(x) → ¬(C(x) ∧ A(x)) By DeMorgan’s Law
¬(¬B(x)) ∨ ¬(C(x) ∧ A(x)) By p → q ≡ ¬p ∨ q
¬(¬B(x) ∧ (C(x) ∧ A(x)) By DeMorgans’s Law
Since D(x) and ¬D(x) both appear in the premise, in order for ¬(¬B(x) ∧ (M(x) ∧ A(x)) to be valid,
¬B(x) is false or ¬C(x) is true. This condition follows ¬B(x) ∨ ¬C(x) which was proved to be valid in
a) ∴ ¬B(x) → (¬C(x) ∨ ¬A(x)) is valid
4
Problem 4. (20 points)
Exercises 18 and 30 of Section 1.7 (page 91).
Solution.
18.
a) Proof by contraposition
Assume that n is odd
Then n = 2k + 1 using some integer k
3n + 2 = 3(2k + 1) + 2
= 6k + 3 + 2
= 6k + 5
= 6k + 4 + 1
= 2(3k + 2) + 1 is odd ∴ 3n + 2 is odd thus if n is an integer and 3n + 2 is even then n is even
b) Proof by contradiction
Suppose 3n + 2 is even and n is odd
Let n and m be any two odd integers. Using definition of odd we have that n = 2a+1 and m = 2b+1. Multiplying the two together, the product n·m = (2a+1)(2b+1) = 4ab+2a+2b+1 = 2(2ab+a+b)+1 = 2k+1,
where k = (2ab +a +b ) is an integer. Therefore the product of two odd numbers results in another odd
number.
Since the product of two odds results in an odd number, it follows that 3n is odd thus 3n + 2 is odd.
Therefore, the assumption 3n+ 2 is even and n results in a contradiction. In conclusion, if n is an integer
and 3n + 2 is even then n is even.
30.
Let a and b be real numbers
(i) a is less than b
(ii) The average of a and b is greater than a
(iii) the average of a and b is less than b
(i) → (ii)
Suppose that a < b
⇒ b > a
⇒ b + a > a + a
⇒ b + a > 2a
⇒
b + a
2
>
2a
2
⇒
b + a
2
> a
∴ the average of a and b is greater than a
(ii) → (iii)
Suppose a + b
2
> a
⇒ a + b > 2a
⇒ b > 2a − a
⇒ b > a
⇒ b + b > a + b
⇒ 2b > a + b
⇒ b > a + b
2
5
⇒
a + b
2
< b
(iii) → (i)
Suppose a + b
2
< b
⇒ a + b < 2b
⇒ a < 2b − b
⇒ a < b
Thus the three statements (i), (ii), and (iii) are equivalent.
6
Problem 5. (20 points)
Exercises 2, 4, 6, and 8 of Section 1.8 (page 108).
Solution.
2. Prove that there are no positive perfect cubes less than 1000 that are the sum of the cubes of two
positive integers.
1
3 = 1, 2
3 = 8, 2
3 = 8, 3
3 = 27, 4
3 = 64, 5
3 = 125, 6
3 = 216, 7
3 = 343, 8
3 = 512, 9
3 = 729
The proof must show that m3 + n
3 = a
3
is false where a = 1, 2, 3, 4, 5, 6, 7, 8, 9 and m and n are positive
integers less than a
m3 + n
3 = a
3
m3 = a
3 − n
3
∴ m3 = (a − n)(a
2 + 2an + n
2
)
Using a = 2 and n = 1
(2 − 1)(4 + 2 + 1) = 7 6= m3
By using a Mathematical computation device, the following is shown
If a = 3 then n = 1, 2 which results in 6= m3
If a = 4 then n = 1, 2, 3 which results in 37, 56, 63 6= m3
If a = 5 then n = 1, 2, 3, 4 which results in 61, 98, 117, 124 6= m3
If a = 6 then n = 1, 2, 3, 4 which results in 91, 152, 189, 208, 215 6= m3
If a = 7 then n = 1, 2, 3, 4, 5, 6 which results in 127, 218, 279, 316, 335, 342 6= m3
If a = 8 then n = 1, 2, 3, 4, 5, 6, 7 which results in 169, 296, 387, 448, 465, 504, 511 6= m3
If a = 9 then n = 1, 2, 3, 4, 5, 6, 7, 8 which results in 217, 386, 513, 604, 665, 702, 721, 728 6= m3
∴ by proof of exhaustion, it is shown that there are now positive integers whose sum is a perfect cube
less than 1000
4. Use a proof by cases to show that min(a, min(b, c)) = min(min(a, b), c) whenever a, b, and c are real
numbers
Let a, b,andc be real numbers
Case 1: Suppose min(b, c) = b and a ≤ b
Then min(a, min(b, c)) = min(a, b) = a
Also, min(a, min(b, c)) = min(a, c) = a because min(b, c) = b ∧ a ≤ b → a ≤ c
∴ min(min(a, min(b, c)) = min(min(a, b), c)
Case 2: Suppose min(b, c) = b and b ≤ a
Then min(a, min(b, c)) = min(a, b) = b
Also, min(a, min(b, c)) = min(a, c) = b because min(b, c) = b ∧ b ≤ a → b ≤ c
∴ min(min(a, min(b, c)) = min(min(a, b), c)
Case 3: Suppose min(b, c) = c and a ≤ c
Then min(a, min(b, c)) = min(a, c) = a
Also, min(c, min(b, c)) = min(a, c) = a because min(b, c) = a ∧ a ≤ c → a ≤ b
∴ min(min(a, min(b, c)) = min(min(a, b), c)
Case 4: Suppose min(b, c) = c and c ≤ a
Then min(a, min(b, c)) = min(a, c) = c
7
Also, min(c, min(b, c)) = min(a, c) = c because min(b, c) = c ∧ c < a → a ≤ b
∴ min(min(a, min(b, c)) = min(min(a, b), c)
6. Prove using the notion of without loss of generality that 5x + 5y is an odd integer when x and y are
integers of opposite parity
Case 1: When x is even and y is odd
Then x = 2m and y = 2n + 1 where m and n are integers
5x + 5y = 5(2m) + 5(2n + 1)
= 10m + 10n + 5
= 10m + 10n + 4 + 1
= 2(5m + 5n + 2) + 1
∴ 5x + 5y is odd when x is even and y is odd.
Case 2: When x is odd and y is even
Then x = 2m + 1 and y = 2n where m and n are integers
5x + 5y = 5(2m + 1) + 5(2n)
= 10m + 10n + 5
= 10m + 10n + 4 + 1
= 2(5m + 5n + 2) + 1
∴ 5x + 5y is odd when x is odd and y is even.
8. Prove that there is a positive integer that equals the sum of the positive integers not exceeding it. Is
your proof constructive or nonconstructive?
Suppose that n = sum of positive n integers
n = 1 + 2 + 3 + … + n
n =
n(n + 1)
n
2n = n(n + 1)
2 = (n + 1)
n = 1
∴ there is a positive integer that equals the sum of the positive integers that will not exceed it
The proof is constructive
8
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist:
1. Did you abide by the Aggie Honor Code?
2. Did you solve all problems and start a new page for each?
3. Did you show your work clearly?
4. Did you submit the PDF to eCampus?
9
Powered by TCPDF (www.tcpdf.org)
