Discrete Mathematics

Running head: DISCRETE MATHEMATICS 1
Discrete Mathematics
Name
Institution

DISCRETE MATHEMATICS 2
1. The logical connective “ NOT OR” denoted by , is true only when neither p nor q are true.
a. Write the truth table for p q.
p q p ↓ q
1 1 0
1 0 0
0 1 0
0 0 1
b. Write down the truth table for (p q) (p q).
p q p ↓ q p ↓ q (p ↓ q) ↓ (p ↓ q)
1 1 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 1 1
What do you notice?
The result for the (p ↓ q) is equivalent to (p ↓ q) ↓ (p ↓ q).
c. Show that both negation, as well as AND, can be written using only↓s.
“p and q”, denoted (p ∧ q)
p ~p q ~q (p ∧ q) (~ p ∧ ~q)
1 0 1 0 1 0
1 0 0 1 0 0
0 1 1 0 0 0
0 1 0 1 0 1
Both negation as well as AND have only one truth instance.
2. Suppose we are considering all computers at Macquarie. Let P(x) is the statement “x is
connected to the network” and let Q(x) be the statement “x has at least 100 Terabytes of
storage”. Express each of the following sentences in terms of P(x), Q(x), quantifiers, and logical
connectives.
a) No computer at Macquarie is connected to the network, and also has at least 100 Terabytes of
storage.
Solution
∀x ¬P(x) ∧ ∃x ( Q(x))

DISCRETE MATHEMATICS 3
b) There is a computer at Macquarie which is either not connected to the network or has less than
100 Terabytes of storage.
Solution
∃x (¬P(x)) ∨ ∃x (¬Q(x))
3. Let P(x, y) be the proposition x2= y, where x and y are in the universe of integers.
Determine the truth value of each of the following propositions.
a. x P(6,x)ⱻ
Solution
This is not true; when x = −6, there is no y with y2= x = −6
b. x P(x,6)ⱻ
Solution
This is true; the rule y = x 2 determines a function, and hence the quantity y exists for any
x.
c. ꓯ x y P(x, y)ⱻ
Solution
This is true; the rule y = x 2 determines a function, and hence the quantity y exists for any
x.
d. yⱻ ꓯ x P(x, y)
Solution
This is not true; when x = −1, there is no y with y2= x = −1.
4. Prove or disapprove each of the following propositions.
a. If n2 is a multiple of 4, then n is a multiple of 4.
Solution
Consider n = 2. Then n2 = 4 = 4 · 1, so n 2 is a multiple of 4. However, n is not a multiple of 4.
b. If n3 is a multiple of 2, then n is a multiple of 2.
Solution
For n3 to be a multiple of 2, n = even number, hence n is divisible by 2 as all even numbers are
divisible by 2.