1
$\begingroup$

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.?

$\endgroup$
  • $\begingroup$ I would leave out the $\in X$ stuff. $\endgroup$ – André Nicolas Apr 25 '16 at 18:51
  • $\begingroup$ Can you please explain why? Wouldn't have to define what $x$ is? $\endgroup$ – Cherry_Developer Apr 25 '16 at 19:16
  • $\begingroup$ The domain is $X$, so it is understood that variables range over $X$. Also, $\in$ is not in the specified language. $\endgroup$ – André Nicolas Apr 25 '16 at 19:46
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure about how to simplify it, but I gave it a shot: $\forall x\in X(¬T(x)\vee A(x))$ I was mostly unsure of how to apply the negation symbol to the predicate, so I typed "not (x and not y)" into Wolfram Alpha and it returned that "not x or y" would be an equivalent statement. $\endgroup$ – Cherry_Developer Apr 25 '16 at 19:13
  • $\begingroup$ Yes, you simplified correctly. Here are the full steps: $\neg \exists x\in X(T(x)\wedge \neg A(x))\iff\forall x\in X\neg(T(x)\wedge \neg A(x))\iff\forall x\in X(\neg T(x)\vee A(x))$. $\endgroup$ – ervx Apr 25 '16 at 19:16
  • $\begingroup$ The negation of $\exists x$ which becomes $\forall x$ is clear to me, but applying the negation to the predicate is where I get lost. I feel like I cheated myself by just resorting to Wolfram Alpha to find the simplified form of $(T(x)\wedge ¬A(x))$. Is $(T(x)\wedge ¬A(x))\Leftrightarrow (\neg T(x)\vee A(x))$ something I should just have memorized? Or is there a way for me to derive it? $\endgroup$ – Cherry_Developer Apr 25 '16 at 19:23
  • $\begingroup$ In general, for expressions $A$ and $B$, we have $\neg(A\vee B)\iff (\neg A\wedge\neg B)$ and $\neg (A\wedge B)\iff (\neg A\vee \neg B)$. You can verify these using truth tables if you like. In general, though, it would be good to memorize them. They are essentially DeMorgan's laws for propositional logic. $\endgroup$ – ervx Apr 25 '16 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.