Question

(2 pts each) Find a different equivalent form of the statements. Justify your answers using Laws of equivalence or otherwise. (a) Not all men are Scientists. (b) If you are a computer science major you will need discrete mathematics.

Answer 1

Let us first answer the second question concerning Equivalence relations and partitions.


Let x be in X. Since R is reflexive, hence (x,x) $\in$ R. Thus, x $\in$ R[x]. Thus, for all x in X, x $\in$ R[x].

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Now, let x,y $\in$ X. Then, there are two cases :

$\bullet$ Case 1 : R[x] $\cap$ R[y] = $\varnothing$ . In this case, we are done.

$\bullet$ Case 2 : R[x] $\cap$ R[y] is nonempty. Then, there exists z $\in$ X such that z $\in$ R[x] $\cap$ R[y]. By definition of an R-equivalence class, (x,z) $\in$ R and (y,z) $\in$ R. Since R is symmetric, hence (z,y) $\in$ R. Finally, since R is transitive, hence (x,z) $\in$ R and (z,y) $\in$ R implies that (x,y) $\in$ R. Now, for any a $\in$ X, a $\in$ R[x] $\Leftrightarrow$ (x,a) $\in$ R $\Leftrightarrow$ (x,a) $\in$ R and (x,y) $\in$ R
$\Leftrightarrow$ (y,x) $\in$ R and (x,a) $\in$ R $\Leftrightarrow$ (y,a) $\in$ R $\Leftrightarrow$ a $\in$ R[y]. Since a $\in$ X is arbitrary, hence R[x] = R[y].

This proves the second assertion.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Since for every x in X, R[x] is contained in X, hence $\cup$ _{x $\in$ X} R[x] is contained in X.
Finally, since for every x $\in$ X, we have x $\in$ R[x], hence X = $\cup$ _{x $\in$ X} R[x].


This shows that the distinct equivalence classes corresponding to R form a partition of X.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



Now for the first question :

(a) There exists a man who is not a scientist.
Explanation : The existential quantifier ' $\exists$ ' is the negation of the universal quantifier ' $\forall$ '.

(b) If you don't need discrete mathematics you are not a computer science major.
Explanation : The contrapositive of an implication ' P $\Rightarrow$ Q ' is ' Not Q $\Rightarrow$ Not P '
An implication and its contrapositive are equivalent statements.