This question was taken from the MIT OCW Math for Computer Science course.
Translate the following sentences from English to predicate logic. The domain that you are working over is $X$, the set of people. You may use the functions $S(x)$, meaning that “$x$ has
been a student of $6.042$,” $A(x)$, meaning that “$x$ has gotten an ‘$A$’ in $6.042$,” $T(x)$, meaning
that “$x$ is a TA of $6.042$,” and $E(x, y)$, meaning that “$x$ and $y$ are the same person.”
(a) [$6$ pts] There are people who have taken 6.042 and have gotten A’s in $6.042$
(b) [$6$ pts] All people who are 6.042 TA’s and have taken 6.042 got A’s in $6.042$
(c) [$6$ pts] There are no people who are 6.042 TA’s who did not get A’s in $6.042$.
(d) [$6$ pts] There are at least three people who are TA’s in $6.042$ and have not taken $6.042$
What I got thus far:
a) $\exists x(S(x)\wedge A(x))$
b) $\forall x\in X((T(x)\wedge S(x))\Rightarrow A(x))$
c) $\nexists x\in X(T(x)\wedge ¬A(x))$
d) $\exists x\exists y\exists z\in X(¬E(x,y)∧¬E(x,z)∧¬E(y,z)∧(T(x)\wedge ¬S(x))∧(T(y)\wedge ¬S(y))∧(T(z)\wedge ¬S(z)))$
I'm not sure about any of my answers, but c) and d) gave me the most trouble. In regards to c),I am not sure about how to express "there are no people" in predicate logic. In regards to d), I am not sure about how to express "there are at least three people" in predicate logic.
Hints are much better appreciated than an explicit answer. In addition, I would like to know how to tag this type of math. Is it considered discrete mathematics as most colleges/universities call it in the U.S.?
Best Answer
Your answers all look okay. Specifically for part c), you did indeed translate the sentence into predicate logic correctly. However, often times it is customary to not leave any negation symbols before the quantifiers. We can pass the negation symbol through the existential/universal quantifier by swapping them. For example
$$ \neg\exists x\in X(P(x))\iff\forall x\in X(\neg P(x)) $$
and
$$ \neg\forall x\in X(P(x))\iff\exists x\in X(\neg P(x)). $$
Can you see how you can use this to simplify your answer for part c)?
Also, I personally think the discrete math tag is okay for a question like this, especially since you also used the predicate logic tag.