What is the difference between ∧ and → in propositional logic

Question

I don't really understand the difference between → (implication) and ∧ (conjunction) in propositional logic. As far as I know:

• A ∧ B is only true when both A and B are true.
• A → B is only true when it's not the case that A is true and B is false.

However, when we have to translate English sentences into mathematical expressions with quantifiers I have some problems. For example:

T(x,y): "student x likes cuisine y"

U: All the students at your school and all the cuisines.

∀x∀z∃y( (x≠z) → ¬ (T(x,y) ∧ T(z,y) ))

The solution of this is: "Two different students don't like a cuisine".

I don't understand this, though. Because the expression between the parenthesis ((x≠z) → ¬ (T(x,y) ∧ T(z,y)) could also be true if x≠z was false (Since FALSE → TRUE is TRUE). Therefore, I think the right answer should be as follows:

∀x∀z∃y( (x≠z) ∧ ¬T(x,y) ∧ ¬T(z,y) ))

So, the expression would only be true if x≠z is true and T(x,y) and T(z,y) are not true (Since TRUE ∧ ¬ FALSE ∧ ¬ FALSE is TRUE).

You see what I mean? It's very confusing. Could anybody help me?

Thank you.

Answer 1

As I see it, a correct answer would be

$\qquad$For any two students, there is some cuisine not liked by at least one the two students.

Explanation:$\;\,$In the context of the given statement,

$\qquad (x \ne z)\;$translates to:$\;$"two (distinct) students $x,z$".

$\qquad T(x,y) \land T(z,y)\;$translates to:$\;$"both $x,z\;$like cuisine $y$".

$\qquad\lnot\bigl(T(x,y) \land T(z,y)\bigr)\;$translates to:$\;$"at least one of $x,z\;$doesn't like cuisine $y$".

Then just apply the quantifiers, and interpret the implication $P\rightarrow Q$ as:$\;$"For $P$, then $Q$".

Edit:

As Mauro ALLEGRANZA pointed out in the comments, there should be predicates to indicate that in given expression, $x,z\;$are students, and $y\;$is a cuisine.

Thus, a corrected version of the symbolic statement might be cast as:

$\qquad\forall x\forall z\;\Bigl[\bigl(S(x)\land S(z) \land (x \ne z) \bigr) \rightarrow \Bigr[\exists y\; \Bigl(C(y) \land \lnot\bigl(T(x,y) \land T(z,y)\bigr)\Bigr)\Bigr]\Bigr]$

where

$\qquad S(s)\;$is the predicate:$\;$"$s\;$is a student".

$\qquad C(c)\;$is the predicate:$\;$"$c\;$is a cuisine".

Answer 2

Just to show the basic difference between $\land$ and $\rightarrow$ in the context of quantifiers:

Domain: $\mathbb{N}$: the natural numbers

$E(x)$: '$x$ is even'

$O(x)$: '$x$ is odd'

$\forall x (E(x) \rightarrow \neg O(x))$: 'Every even number is not odd' .... True!

$\forall x (E(x) \land \neg O(x))$: 'Every number is both even and not odd' .... False!

And for existentials:

$\exists x (E(x) \land O(x))$: "Some number is both even and odd' ... False!

$\exists x (E(x) \rightarrow O(x))$: "There is some number such that if it is even then it is odd" ... True! Because if you pick any odd number for $x$, the antecedent is false, and the consequent true, and hence the whole conditional is true. (this way of making conditionals 'vacuously' true simply by picking something that makes the antecedent false is exactly why you hardly ever see the $\rightarrow$ used as the main connective inside an existential).

Answer 3

"Two different students don't like a cuisine."

I would translate this as follows:

$$\exists s_1, s_2, x, y: [Student(s_1) \land Student(s_2) \land Cuisine(x) \land Cuisine(y) \land s_1\neq s_2 \land \neg Likes(s_1,x) \land \neg Likes(s_2,y)]$$

I hope this is self-evident. There is no implication.