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]