Dec 1998 MA214: Discrete Mathematics (Question 3)

(a)

Let p and q be statements.

(i) What is tautology?

[1]

A tautology is a compound statement that is always true.

(ii) Write down the truth table for the compound statement

(p ~q) ((~p~q) v (pq)).You may wish to copy and complete the truth table below:

p	q	~p	~q	p ~q	~p~q	pq	(~p~q) v (pq)	(p ~q) ((~p~q) v (pq))
T	T
T	F
F	T
F	F

[5]

Comment on your result.

[1]

p	q	~p	~q	p ~q	~p~q	pq	(~p~q) v (pq)	(p ~q) ((~p~q) v (pq))
T	T	F	F	F	F	T	T	F
T	F	F	T	T	F	F	F	F
F	T	T	F	T	F	F	F	F
F	F	T	T	F	T	F	T	F

One mark for each of the last five rows.
(p ~q) ((~p~q) v (pq)) is a contradiction.
Candidates do not get the mark if they simple say that it always evaluates to false. They must use the word "contradiction".

(b)

Use the Principle of Mathematical Induction to prove that the proposition P(n) is true for all positive integers n, when P(n) is the statement.

[5]

1 mark for correctly proving that the base case holds.
Base Case:
When n = 1, LHS = 1/((2 - 1) * (2 + 1)) = 1/(1 * 3) = 1/3.
When n = 1, RHS = 1/(2+1) = 1/3
So, P(1) is true.

Inductive Step:
1 mark for correctly starting the inductive hypothesis, i.e. suppose, for some positive integer, k, P(k) is true i.e.

1/((2x - 1)(2x + 1)) = k/(2k + 1)

Now consider n = k + 1
LHS

= 1/((2x - 1)(2x + 1)

= 1/((2x - 1)(2x + 1)) + 1/((2(k + 1) - 1)(2(k + 1) + 1))

= k/(2k + 1) + 1/((2(k + 1) - 1)(2(k + 1) + 1))
1 mark for this step using inductive hypothesis

= k/(2k + 1) + 1/((2k + 1)(2k + 3))

= (k(2k + 3) + 1)/((2k + 1)(2k + 3))
1 mark for putting both terms over a common denominator

= (2k² + 3k + 1)/((2k + 1)(2k + 3))

= ((2k + 1)(k + 1))/((2k + 1)(2k + 3))

= (k + 1)/(2k + 3)

= (k + 1)/(2(k + 1) + 1)
1 mark for rearranging to this form

(c)

Consider the following argument:

If I am on holiday then I am relaxed. If it is not August then I am not on holiday. I am not relaxed therefore it is not August.

Defining a, h and r as follows:

a It is August
h I am on holiday
r I am relaxed

deduce whether or not this argument is valid, showing your working in truth tables.

[6]

Our hypotheses are

If I am on holiday then I am relaxed.
If it is not August then I am not on holiday.
I am not relaxed.

We wish to prove that it is not August.
Translating this we want to prove.

1 mark each for the last five columns.
1 mark for observing that the final column is not entirely ts and so the argument is not valid.

(d)

Find counter examples to provide that the following statements are false.

(i)

x (x is odd

x is prime)

[1]

Possible counter examples are 2 or any odd number that is not a prime number e.g. 1,9,15,21,25,27,etc

(ii) ~ (

x² = 49))

[1]

The only possible example is -7.