Which symbolization is right for the following statements ?

The statements:

  1. Some computer science students are not regular.
  2. Every user in this website has some rank.
  3. All the questions related to programming has an answer on stackoverflow.


For 1st statement:

a. $\exists$xP(x)$\rightarrow\neg$Q(x) (P(x) = cs students, Q(x) = are regular)

b. is it $\exists$xP(x)$\land\neg$Q(x)

which one is it "a" or "b" ?

For 2nd statement:

a.$\forall$P(x)$\rightarrow$Q(x) (P(x) = user in this website, Q(x) = has some rank)


which one is it "a" or "b" ?

For 3rd statement:

a.$\forall$P(x)$\rightarrow$Q(x) (P(x) = questions related to programming, Q(x) = has an answer on stackoverflow)


which one is it "a" or "b" ?



The wording of your statements isn't quite correct. For example, '$P(x)=$ cs students' and '$Q(x)=$ are regular'. What on earth do these statements mean? They're not statements - they don't say anything. They don't mention $x$ in them and we don't even know what $x$ is.

Instead, you should have something like: let $X$ be the set of all students and let $P(x)=$ '$x$ is a cs student', $Q(x)=$ '$x$ is regular'.

You'll then see both

$$(\exists x\in X)\quad P(x)\implies\lnot Q(x)$$


$$(\exists x\in X)\quad P(x)\land\lnot Q(x)$$

hold true for the first one.

Note that


$$P(x)\land\lnot Q(x)$$ $\implies$ $$\lnot Q(x)$$ $\implies$ $$\lnot P(x)\lor\lnot Q(x)$$ $\iff$ $$(P(x)\implies\lnot Q(x))$$

so the first is just a weaker statement than the second.

Similar problems with wording of your statements apply for the other two, and yet again you'll see each time that both are true with one of the statements being implied by the other.

Edit: In conclusion, only the b statements are equivalent to the original statement. So although a is true in each case, it isn't what you're after.

  • $\begingroup$ @Ahtisham In fact, taking away the context, you have exactly the same pairs of statements in all three cases (with different quantifiers and substituting $Q(x)$ for $\lnot Q(x)$ in the first), so just apply the above again to see one implies the other in each case. $\endgroup$ – Shuri2060 Aug 13 '17 at 12:25
  • $\begingroup$ really is there no difference between $\exists$P(x)$\rightarrow\neg$Q(x) and $\exists$P(x)$\land\neg$Q(x) ? $\endgroup$ – Ahtisham Aug 13 '17 at 12:30
  • $\begingroup$ @Ahtisham No - as shown above, one is a weaker statement than the other. The second implies the first. Eg. $(\forall x\in X)\quad \lnot P(x)\Rightarrow (P(x)\implies\lnot Q(x))$ but $(\forall x\in X)\quad \lnot P(x)\not\Rightarrow (P(x)\land\lnot Q(x))$. $\endgroup$ – Shuri2060 Aug 13 '17 at 12:56
  • $\begingroup$ @Ahtisham Ah I see - yes, in which case $ ∃P(x)→¬Q(x)$ isn't what you're after, although it is true. Only the b statements are equivalent to the original statement. This is because the a statements hold true when $P(x)$ is false regardless of the original statements. $\endgroup$ – Shuri2060 Aug 13 '17 at 13:03

Technically, in all 3 cases, it is neither a) nor b), since all statements contain free variables due to missing parentheses.

For example, the statement $\exists x P(x) \rightarrow Q(x)$ will be interpreted as $(\exists x P(x)) \rightarrow Q(x)$, meaning that the $x$ in $Q(x)$ is free, meaning that this is a formula, but not a sentence.

So, to be a sentence, you have to add parentheses, and make it $\exists x (P(x) \rightarrow Q(x))$

Similar for all the other expressions.

Now, in general, you typically want to use a $\land $ in combination with a $\exists$, and a $\rightarrow$ in combination with a $\forall$. There are always exceptions of course, but if you ever see a $\rightarrow$ in combination with a $\exists$, then most likely something is wrong.

And so it is in this case. Do yourself a favor and remember the following 4 'Aristotelean Categorical sentence forms':

  1. 'All P are Q'. This translates as $\forall x (P(x) \rightarrow Q(x))$

  2. 'Some p are Q'. This is $\exists x ( P(x) \land Q(x))$

  3. 'No P are Q' (or, what is the same thing: 'All P are not q'): $\forall x (P(x) \rightarrow \neg Q(x))$

  4. 'Some P are not Q': $\exists x (P(x) \land \neg Q(x))$

Notice how for these 4 very common sentence patterns, you indeed get a $\land$ whenever you have a $\exists$, and a $\rightarrow$ whenever you have a $\forall$


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.