Question

Let S(x, y) denote the statement "x has seen y" and D denote the set of all students in our class and M be the set of all movies.
a. Express the following English sentence as a quantified proposition using the definitions above:
"For every movie there is a pair of students in our class who have both seen it." Hint: Use three quantifiers - one for the movie and two for a pair of students.

b. Negate the quantified proposition you wrote for part (a) (i.e., place a "¬" in front of it). Use de Morganâs law for quantifiers to move the negation inside the quantifiers.
c. Translate you answer for part (b) back to plain English.

Answer 1

Answer:

Step-by-step explanation:

a) Recall the quantifiers $\forall, \exists$.

Then, we can translate the proposition as follows

$\forall m \in M \exists x \in D \exists y \in D S(x,m)\land S(y,m)$

b) Recall that an expression of the form $\exists x P(x)$ its negation is of the form $\forall x \neg P(x)$ which means that it is not true that for all elements the proposition P holds. Equivalently, we have that the negation of an expression of the form $\forall x P(x)$ is $\exists x \neg P(x)$ which means that there is at least one x such that P doesn't hold. Using this, we get the following

$\neg(\forall m \in M \exists x \in D \exists y \in D S(x,m)\land S(y,m))= \exists m \in M \neg (\exists x \in D \exists y \in D S(x,m)\land S(y,m))= \exists m \in M \forall x \in D \neg (\exists y \in D S(x,m)\land S(y,m))= \exists m \in M \forall x \in D \forall y \in D \neg(S(x,m)\land S(y,m))$

By De Morgan's law, we have that $\neg (A \land B) = \neg A \lor \neg B$

So, the final statement is

$\exists m \in M \forall x \in D \forall y \in D \neg S(x,m) \lor \neg S(y,m)$

c)

This statement means: There is a movie that for every pair of students, at least one of the students hasn't seen the movie yet.