# What is the difference between ∧ and → in propositional logic

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

• The second formulation asserts (among other things) that for all $x$ and all $z$, there is some $y$ such that $x\ne z$. This is plainly not true (choose $x$ and $z$ to be the same student). – rogerl Oct 25 '17 at 18:52
• I agree with you that the proposed solution is wrong. "Two different students don't like a cuisine" (IMO) msut be read: "there are two different students and there is a cuisine such that...": ∃x∃z∃y( (x≠z) ∧ ¬T(x,y) ∧ ¬T(z,y) )). But, still due to the fact that the universe is made of student and cuisines, we need addiotional predicates: S(x), S(y), C(z). – Mauro ALLEGRANZA Oct 25 '17 at 18:53

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

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

• Thank you for your explanation. But I have the feeling that the logic that these expressions have don't related to the logic of the English language. Because this 'T implies F is false' thing doesn't make any sense. If for example I say: "If I am man, then I am a human" and you say that the first part is false and the second one is true, then the statement should be false, right? – Arnau Oct 26 '17 at 6:24
• @Arnau The material conditional $\rightarrow$ is defined in such a way that $P \rightarrow Q$ is false only when the antecedent $P$ is true and the consequent $Q$ is false. So, as soon as the antecedent $P$ is false, the whole conditional $P \rightarrow Q$ is true. And you're right, that doesn't always jibe with our intutions regarding conditionals. For example, if I say If I live in Paris, then I live in Germany, then most people would say that that is a false statement, but it turns out that I don,t live in Paris, then the material conditional is set to true. – Bram28 Oct 26 '17 at 11:23
• @Arnau Thus, we see a discrepancy between the mathematically defined material conditional and the way we use conditionals in Natural language. Search for 'Paradox of material implication' for further thoughts and comments on this ... it's a long story ... – Bram28 Oct 26 '17 at 11:26

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