Problem 1 (Predicate Logic, Rules and inference)
1. Represent the argument
If I study hard, then I get A’s
I study hard.
I get A’s
Symbolically and determine whether the argument is valid.
2. Suppose that the implication “If the last digit of this number is a 5, then this number is
divisible by 5” and its hypothesis, “The last digit of this number is a 5” are true. Then, by
modus ponens, it follows that the conclusion of the implication, “This number is divisible
by 5” is true.
3. Represent the argument
If it rains today, then we will not have party today.
If we do not have party today, then we will have a party tomorrow.
Therefore, if it rains today, then we will have a party tomorrow.
Symbolically and determine whether the argument is valid.
Problem 2 (Basic Proofs)
1. Show that 𝑡 is a valid conclusion from the premises 𝑝 → 𝑞, 𝑞 → 𝑟, 𝑟 → 𝑠, ¬𝑠 and 𝑝 ∨ 𝑡.
2. 𝑠 is a valid conclusion form the premises 𝑝 → 𝑞, 𝑝 → 𝑟, ¬(𝑞 ∧ 𝑟) and 𝑠 ∨ 𝑝.
3. Prove the validity of the following argument “If I get the job and work hard, then I will get
promoted. If I get promoted, then I will be happy. I will not be happy. Therefore, either I
will not get the job or I will not work hard”.
4. Show that the following argument is invalid:
If Sidra solved this problem, then she obtained the answer 5.
Sidra obtained the answer 5.
Therefore, Sidra solved the problem correctly.
5. Test the validity of the following argument
If two sides of triangle are equal, then the opposite angles are equal.
Two sides of a triangle are not equal.
Therefore, the opposite angles are not equal.
Problem 3 (Direct Proof)
1. Prove that if 𝑥 and 𝑦 are rational numbers then 𝑥 + 𝑦 is a rational number.
2. Prove that product of two odd integers is an odd integer.
3. Prove that sum of two odd integers is even.
4. Give a direct proof of the following statement. For all integers 𝑚 and 𝑛, if 𝑚 is odd and 𝑛
is even, then 𝑚 + 𝑛 is odd.
5. Give a direct proof of the theorem “If 𝑛 is odd integer, then 𝑛2 is odd.”
6. Give a direct proof that if 𝑚 and 𝑛 are both perfect squares, then 𝑛𝑚 is also a perfect
square.
Hint: An integer 𝑎 is a perfect square if there is an integer 𝑏 such that 𝑎 = 𝑏 2
Problem 4 (Proof by Contrapositive)
1. Prove that if 𝑛 is an integer and 3𝑛 + 2 is odd, then 𝑛 is odd.
2. Prove that if 𝑛 = 𝑎𝑏, where 𝑎 and 𝑏 are positive integers, then 𝑎 ≤ √𝑛 or 𝑏 ≤ √𝑛.
3. Let 𝑛 be an integer. Prove that if 𝑛2 is odd then 𝑛 is also odd by giving a proof by
contrapositive.
4. Use proof by contrapositive to show that for all 𝑥 ∈ ℝ, if 𝑥 2 is irrational, then 𝑥 is irrational.
5. Prove that if 𝑥 2 is divisible by 4, then 𝑥 is even by giving a proof by contrapositive.
6. Prove that if 𝑥 2 is even, then 𝑥 is even by giving a proof by contrapositive.
Problem 5 (Proof by Contradiction)
1. Give a proof by contradiction of the statement, “For every 𝑛 ∈ 𝑍, if 𝑛2 is even, then 𝑛 is
even”
2. Prove that if 𝑛 is an integer and 𝑛3 + 5 is odd then 𝑛 is even.
Problem 6 (Mathematical Induction)
1. Show that
𝑛(𝑛+1)(2𝑛+1)
12 + 22 + 32 + ⋯ + 𝑛2 = ,𝑛≥1
6
by mathematical induction.
2. Show that
1 1 1 𝑛
+ 2.3 + ⋯ + 𝑛(𝑛+1) = 𝑛+1 , 𝑛 ≥ 1
1.2
by mathematical induction.
3. Use induction to show that 𝑛! ≥ 2𝑛−1 for all 𝑛 ≥ 1.