COMPSCI 225 Mathematics for Computer Science 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMPSCI 225
SEMESTER 1, 2021
Mathematics for Computer Science
1. Prove that
((A A -B) - (-B - -A)) =号 (B ^ -A)
[7 marks]
There are two approaches to prove this question: the first is to use the logical equivalency and the second is to write the truth table. To prove that ((A A -B) - (-B - -A)) =号 (B ^ -A) is the same as proving that ((A A -B) - (-B - -A)) - (B ^ -A) is a tautology. Approach 1:
((A A -B) - (-B - -A)) - (B ^ -A) 兮 兮 -[-(A A -B) ^ (-(-B) ^ -A)] ^ (B ^ -A) 兮 兮 -[-(A A -B) ^ (B ^ -A)] ^ (B ^ -A) 兮 兮 [--(A A -B) A -(B ^ -A)] ^ (B ^ -A) 兮 兮 [(A A -B) A (-B A A)] ^ (B ^ -A) 兮 兮 [A A -B A -B A A] ^ (B ^ -A) 兮 兮 (A A -B) ^ (B ^ -A) 兮 兮 -(-A ^ B) ^ (B ^ -A) 兮 T Here T is a statement which is always true. Approach 2:
|
(a) Use proof by contrapositive to prove the following:
For every real x, if x7 + x4 + x5 + 3 < 0, then x < 0.
[4 marks]
Contrapositive claim: For every real x, if x 2 0, then x7 + x4 + x5 + 3 2 0. Since x 2 0 any power of x will be non-negative, that is, x7 2 0, x4 2 0, x5 2 0. So x7 + x4 + x5 + 3 2 0. |
(b) Prove or disprove the following statement:
There exist prime numbers p and q for which p _ q = 97.
[3 marks]
This statement is not correct. In other words you need to prove that
For any prime numbers p and q you have p _ q 97.
All primes except 2 are odd, so you need to consider 3 cases: Case 1: p, q are odd. In this case p _ q is even and cannot be 97, which is odd Case 2: p is odd and q = 2. Then p = 97 + q = 97 + 2 = 99. 99 is not prime. Hence p cannot be prime. Case 3: q is odd and p = 2. Then q = 97 _ p = 97 _ 2 = 95. 95 is not prime. So q cannot be prime. In all cases p _ q 97. Therefore such p and q do not exist. |
3. (a) Let a, b, c be three positive integer numbers. Prove that
gcd(gcd(a, b), c) = gcd(a, gcd(b, c)).
[5 marks]
2022-09-06