Mathematical reasoning and discrete structures

Number Mathematical Reasoning and Discrete Structures Question a) (A – B) – C = A – (B ᴗ C) Let 2, 3, a) ϵ A
Let (2, a) ϵ B
Let (3) ϵ C
[(1, 2, 3, a) – (2, a)] – (3) = (1, 2, 3, a) – [(2, a) ᴗ (3)]
(1, 3) – (3) = (1, 2, 3, a) – (2, 3, a)
1 = 1
Therefore this theoretic statement is true.
b) p= x ϵ A, q = x ϵ B and r = x ϵ C
p ¬q ¬r → p ¬ (q ˅ r)
Question 2
Let P(x) be the propositional function “ x is perfect”
Let Q(x) be the propositional function “ x is a friend”
Let ﻻ be “ for every”
a) No one is perfect
­­­ ﻻx ­­­­­¬ P(x)
b) Not everyone is perfect
Ǝx ¬ P(x)
c) All your friends are perfect
ﻻx (Q(x) → P(x))
d) At least one of your friends is perfect
Ǝx (Q(x) → P(x))
e) Not everyone is your friend or someone is not perfect
Ǝx ¬ Q(x) ˅ Ǝx ¬ P(x)
Question 3
Negations of question 2
a) Ǝx P(x)
b) ﻻx P(x)
c) Ǝx (Q(x) → ¬ P(x))
d) ﻻx (Q(x) → ¬ P(x))
e) ﻻx Q(x) ˅ ﻻx P(x)
Question 4
Proof by contradiction
n / n + 1 ˂ n + 1 / n + 2
let n = 3
3 / 3 + 1 ˃ 3 + 1 / 3 + 2
3 / 4 ˃ 4 / 5- this is however not true.
Therefore, n / n + 1 ˂ n + 1 / n + 2 is true
Question 5
a) f(x) = 2 – x if x ≤ 1, f(x) = 1/x if x ˃ 1 is one-to-one but not onto R
f(x) = 2 – x if x ≤ 1
This function is both one-to-one and onto R.
Suppose that f(x) = f(y,) then 2 – x = 2 – y, thus x = y. Therefore f is one-to-one.
Since x ≤ 1, then all values of x are real numbers thus the function is onto R.
f(x) = 1/x if x ˃ 1
Suppose that f(x) = f(y), then 1/x = 1/y, thus x = y. Therefore f is one-to-one.
Since x ˃ 1, then all values of x are real numbers and the function is onto R.
b) f(x) = x + 4 if x ≤ -2, f(x) = -x if -2 ˂ x ˂ 2, f(x) = x – 4 if x ≥ 2 is onto R but not one-to-one.
f(x) = x + 4 if x ≤ -2
This function is both one-to-one and onto R.
Suppose that f(x) = f(y,) then x + 4 = y + 4, thus x = y. Therefore f is one-to-one.
Since x ≤ -2, then all values of x are real numbers thus the function is onto R.
c) f(x) = x – 2/x – 4 if x ≠ 4, f(x) = 1 if x = 4 is one-to-one and onto R.
f(x) = x – 2/x – 4 if x ≠ 4
Suppose that f(x) = f(y), then x – 2/x – 4 = y – 2/y – 4, thus x = y. Therefore f is one-to-one.
Since x ≠ 4, then all other values of x are real numbers and the function is onto R.
f(x) = 1 if x = 4
f(4) = 4 therefore the function is not one-to-one but is onto R since x = 4
d) f(x) = | x| if x ≤ 2, f(x) = x-3 if x ˃ 2 is neither one-to-one nor onto R.
f(-1) = | 1| = f(1) therefore, the function is one-to-one but it is onto R since x ≤ 2
f(x) = x-3 if x ˃ 2
Suppose that f(x) = f(y), then x-3 = y-3, thus x = y. Therefore f is one-to-one.
Since x ˃ 2, then all other values of x are real numbers and the function is onto R.
Question 6
a) This relation is transitive because if p → q is true, then it follows that if (p, q) and (q, r) ϵ R, then (p, r) ϵ R.
b) The relation is a reflective relationship since the truth of p ˄ q makes it that (p, p) ϵ R for every p ϵ S.
c) This relationship is also a transitive one because if (p, q) and (q, r) ϵ R, then (p, r) ϵ R. Since p ˅ q is also true.
d) The relation is symmetric since for all p, q ϵ S, if (p, q) ϵ R, then (q, p) ϵ R is also true. This is all because p ↔ q.
Question 7
“ If a relation is symmetric and transitive, it must be reflective.”
“ Proof” – Since xRy implies yRx by symmetry, and since xRy and yRx imply xRx by transitivity, xRx must be true, which makes R reflective.
A relation is said to be symmetric when for all x, y ϵ X, if (x, y) ϵ R, then (y, x) ϵ R. Therefore xRy implies yRx by symmetry, if and only if the elements x and y are from the same set. It is thus worth noting that there could be a symmetric relation on this account.
A transitive relation is one where then it follows that, for all (x, y, z) ϵ X, if (x, y) and (y, z) ϵ R, then (x, z) ϵ R. Therefore there is transitivity in that part of the chain since if (x, y) and (y, x) ϵ R, then (x, x) ϵ R is also the case.
A relation R on a set X is reflective if (x, x) ϵ R for every x ϵ X. therefore, if x ϵ X in this case then R is reflective.
Question 8
Prove – “ It is not sunny this afternoon and it is colder than yesterday. We will go swimming only if it is sunny. If we do not go swimming, then we will take a canoe trip. If we take a canoe trip, then we will be home by sunset. Therefore, we will be home by sunset.”
p: It is sunny
q: Going swimming
r: Taking the canoe trip
¬p ˄ ¬q ˄ r
Question 9
a) Determination of Euler paths
Graphs (i), (iii) and (iv) have Euler cycles since a cycle in each of these graphs includes all of the edges and all of the vertices. The degree of vertices is also even.
b) Determination of minimum number of colors required to color each one of them
i) 3 colors
ii) 2 colors
iii) 2 colors
iv) 2 colors
v) 5 colors
vi) 4 colors
Question 10
Let ƽ mean “ subset of”
a) Grade A
b) Grade A
c) Grade A
d) Grade F – this is because if x ϵ C, it is not a must that x ϵ B also. Even if B ƽ C, only select elements of set B are in set C.
e) Grade A
f) Grade F – this is because if x ϵ A, then x ƽ A is false. An element cannot be a subset of another set.
g) Grade C – reason being that if x ϵ A, then {x} ƽ A is true since a set containing element x only, is a subset of set A. However, a set containing element x only cannot be an element of another set P(A).
h) Grade A
i) Grade A
j) Grade A
Works Cited
Johnsonbaugh, Richard. Discrete Mathematics 7th Edition. New Jersey: Prentice Hall
International, 2009. Print.