Discrete Mathematics Answers

Express each of these statements using quantifiers: a) Every student in this class has taken exactly two mathematics classes at this school.

Let A, B, and C be sets. Show that (A − B) − C =

(A − C) − (B − C).

1. Show, by the use of the truth table/matrix, that the statement 

(P ⇒ Q) ⇔ (!Q ⇒ !P) is a tautology.

1. Show that P ⇔ Q ≡ (P ^ Q) v (!P ^ !Q) are logically equivalent.

Use the Laws of Logic to prove the following equivalence and state the laws used for each step.

p → (p ⋀ q), p → q

What is the truth value of each of the following formulas where the domain consists

of the integers? Justify your answers.

(a) ("\\forall"x)("\\forall"y)(x < y "\\lor" y < x)

(b) ("\\exists"9y)("\\forall"x)(x + y = 0)

7. Express these system specifications using the propositions

p “The message is scanned for viruses”

and q “The message was sent from an unknown system” together with logical connectives (including negations).

a) “The message is scanned for viruses whenever the message was sent from an unknown system.”

b) “The message was sent from an unknown system but it was not scanned for viruses.”

c) “It is necessary to scan the message for viruses whenever it was sent from an unknown system.”

d) “When a message is not sent from an unknown system it is not scanned for viruses.”

Consider the following relations on {1, 2, 3, 4}.

R₁ = {(2,2), (2,3),(2,4),(3,2),(3,3),(3,4)}

R₂ = {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}

R₃ = {2,4),(4,2)}

R₄ = {(1,2),(2,3),(3,4)}

R₅ = {(1,1),(2,2),(3,3),(4,4)}

a)   Which of these relations are reflexive? Justify your answers.

b)   Which of these relations are symmetric? Justify your answers.

c)   Which of these relations are antisymmetric? Justify your answer.

d)   Which of these relations are transitive? Justify your answers.

Let R₁ and R₂ be the relations on {1,2,3,4} given by

R₁ = {(1,1), (1,2), (3,4), (4,2)}

R₂ = {(1,1), (2,1), (3,1), (4,4), (2,2)}

List the elements of R_{1 °} R₂ and R_{2 °} R₁