Discrete Mathematics Answers

State whether the following statements are true or false. Justify yourself with the help of a short proof or a counter example. (1) There are at least two ways of describing the set {7, 8....}. (2) Any function with domain R®R is a binary operation.

A is sufficient for B’ is equivalent to ‘the negative of A is necessary for the

negative of B’. is it true or false?

Obtain the order of each element of S(℘) where S={1,2,3}

4.2: For the proposition pairs below, create a truth table and compare each proposition’s truth profile: determine whether the pair is logically equivalent, contradictory, consistent or inconsistent.


Example: (¬J ≡ K) with [(J → ¬K) ∧ (¬K → J)]


Write your answer as follows:

Step 1

J K (¬J ≡ K) [(J → ¬K) ∧ (¬K → J)]

T T (F) ≡ T (T → F) ∧ (F → T)

T F (F) ≡ F (T → T) ∧ (T → T)

F T (T) ≡ T (F → F) ∧ (F → F)

F F (T) ≡ F (F → T) ∧ (T → F)


Step 2

J K (¬J ≡ K) [(J → ¬K) ∧ (¬K → J)]

T T F (F) ∧ (T)

T F T (T) ∧ (T)

F T T (T) ∧ (T)

F F F (T) ∧ (F)


Step 3

J K (¬J ≡ K) [(J → ¬K) ∧ (¬K → J)]

T T F F

T F T T

F T T T

F F F F


Answer: (¬J ≡ K) and [(J → ¬K) ∧ (¬K → J)] are logically equivalent



34. (P ∧ Q) ∨ P with (P ∨ Q) ∧ Q



35. [(S → W) → X] with [(S ∧ W) ∨ (W ∧ X)]

QUESTION 2


Which of the following statements motivate the use of informal proof? Answer true or false to the

following informal proof statements:


a) Truth tables cannot demonstrate logical consequence for formulas containing more than 10

atoms.


b) Informal proof can sometimes explain why a logical consequence holds better than alternative

methods.


c) Not all connectives are truth functional, and hence truth tables do not capture the fully general

case of logical consequence.


d) Informal proofs contain no symbols and so can be understood by everyone.

QUESTION 4


Below are a number of expressions. State which are terms, some are atomic wffs (well-formed formulae) and some are neither.


a) Tet(y)


b) Logician(john)


c) father_of(quinn)


d) 2 + y = z2


e) Angry(x; y;2:00)

‘A is sufficient for B’ is equivalent to ‘the negative of A is necessary for the

negative of B’.

Using Rules of Inference, can you show step by step that this argument is valid?

NOT(IF p THEN q) AND p = NOT(q)

‘A is sufficient for B’ is equivalent to ‘the negative of A is necessary for the

negative of B’. Is it true or false? give reasons.

Let R be a relation on ℤ given by xRy if and only if x²-y² is divisible by 3. Show that this relation is an equivalence relation and find its corresponding equivalence classes.