2
$\begingroup$

I have a question about predicate logic. Suppose we have the following predicates:

$\text{Study}(x,y)$: x studies y

$\text{Comp}(x)$: x is a computing student

I want to encode the following sentence in predicate logic: "Some, but not all computer students study logic."

A potential answer is:

$$\exists x(\text{Comp}(x)\land \text{Study}(x,l))\land\neg \forall x(\text{Comp}(x)\implies \text{Study}(x,l))$$

Why is there an $\implies$ and not a $\land$? Is this formulation correct?

$\endgroup$
  • $\begingroup$ A useful thing to remember is that usually the $\exists$ is using a $\land$ where the $\forall$ uses a $\rightarrow$. There is a philosopher who drinks vs. all philosophers drink: $\exists x P(x) \land D(x)$ vs $\forall x P(x) \rightarrow D(x)$. Note that $\forall x P(x) \land D(x)$ means that everybody are drinking philosophers whereas $\exists P(x) \rightarrow D(x)$ is true if there are no philosophers! $\endgroup$ – Pål GD Feb 11 '14 at 12:04
4
$\begingroup$

Because $\neg\forall x\,(\text{Comp}(x) \wedge \text{Study}(x,l))$ means "It is not true that every student is both a computing student and studying logic." In particular, that would be true if there is at least one student who is not a computing student, regardless of whether all computing students do or do not study logic.

$\endgroup$
  • $\begingroup$ Thank you, but how would the first segment differ in meaning if there was an implication instead of an and? Eg if the first segment said ∃x(Comp(x) → Study(x,l)) $\endgroup$ – Natu Myers Feb 11 '14 at 1:05
  • 2
    $\begingroup$ I think you need to revise the definition of implication ($X\rightarrow Y$ means that either $X$ is false or $Y$ is true or both.) $\endgroup$ – David Richerby Feb 11 '14 at 1:07

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.