I've read some examples about the differences between using AND and the implication in FOL, but I have a specific example where I can't intuitively notice the difference between the two:

"Every student able to solve every logic exercise will get an A in AI"

I see that the solution is:

$\forall X\ [\forall P\ exercise(P)\implies solves(X,P)]\implies getsAasgrade(X)$

and I don't understand what's the difference with:

$\forall X\ \forall P\ exercise(P)\cap solves(X,P)\implies getsAasgrade(X)$

since I would read the latter as "for every P which is an exercise and for every entity X such that X solves every exercise P then this entity X gets A", which seems fine to me, but I guess it shouldn't be. Instead I would never express my problem as a nested implication, I really don't even understand how to "read" it in natural language.


Assuming that your second formula is bracketed like:

$$\forall X \lbrack \forall P \lbrack (exercise(P) \wedge solves(X, P)) \implies getsA(X) \rbrack \rbrack $$

Then if some $X$ solves any exercise $P$, then $X$ gets an A. If there is some exercise $P$ that $X$ does not solve, then the conjunction is false and the implication is true.

If you meant for it to be bracketed like

$$\forall X \lbrack \forall P \lbrack (exercise(P) \wedge solves(X, P)) \rbrack \implies getsA(X) \rbrack $$

Then if there is any $P$ such that $\neg exercise(P)$, then the implicant is false and the implication is trivially true and tells us nothing; otherwise, $exercise(P)$ can be replaced by $\top$, and the formula reduced to $$\forall X \lbrack \forall P \lbrack solves(X, P) \rbrack \implies getsA(X) \rbrack$$

In any event, neither of these interpretations correctly capture the requirement.

To understand why the first formula is the correct interpretation, it might help to change $exercise(P) \implies solves(X, P)$ to $\neg exercise(P) \vee solves(X, P)$. Basically, "for all $X$, if (for all $P$, either $P$ is not an exercise or $X$ solves $P$) then $X$ gets an A"

  • 1
    $\begingroup$ changing the implication does help, thanks. I may have a follow-up question at this point though: what if we slightly change the requirement. Something along the lines of "A student able to to solve a difficult logic problem will get an A". At first it seems very similar to me, but I see that the formula given as a solution is $ \forall X\forall P problem(P)\wedge solves(X,P) \wedge hard(P) \implies getsA(X)$ which is very different from the one in my first question and I don't really understand why. Going through it with the reasoning you suggested me makes it seems a wrong solution. $\endgroup$ – Mattz Feb 12 at 0:45
  • $\begingroup$ The difference in the new requirement is that we no longer require that $X$ solves every hard problem $P$. Now, as long as $X$ solves one such $P$, $X$ gets an A, which is how the first bracketing in the answer is interpreted $\endgroup$ – R Swan Feb 12 at 11:57

The problem with your version of the statement is that it translates to "for every entity X, for every P, if P is an exercise and X can solve P, then X gets an A." This would imply that if some P was NOT an exercise, entity X might not get an A even if X could solve all exercises, which is not the desired implication. The given solution is instead "For every entity X, for every P, if P being an exercise implies that X can solve P, then X will get an A." This has the correct meaning that any entity which can solve all exercises will get an A.

  • $\begingroup$ I'm quite confused: could you elaborate on how would my statement with the AND imply that if P is not an exercise, entity X wouldn't get an A? I mean: let's say P is not an exercise, then "P is an exercise" is false, whatever value, true of false of "X can solve P" the premise for the implication is false, meaning "X gets A" is true nontheless. Exactly as the solution with the double implication, I would say. What am I misunderstanding? $\endgroup$ – Mattz Feb 11 at 12:38
  • $\begingroup$ @Mattz Well, I guess there are two ways to read your statement. I was reading it with implied parentheses around the "for all P, P is an exercise and X solves P" part. It seems like you didn't intend that. If it's read as $\forall X\ (\forall P\ (exercise(P)\cap solves(X,P)\implies getsAasgrade(X)))$, this would imply that the existence of even one P which was an exercise that X could solve means X would get an A, for the same reason you mentioned: if the premise is false, it doesn't make the conclusion automatically false. So the premise being true even once would make the conclusion true. $\endgroup$ – CyborgOctopus Feb 11 at 14:03
  • $\begingroup$ I just realized that my answer made it sound like the premise being false did make the conclusion false ("This would imply that if some P was NOT an exercise, entity X wouldn't get an A.") I edited it to change the wording. $\endgroup$ – CyborgOctopus Feb 11 at 14:06

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.