Difference between AND & Implies

Question

I have problem understanding the difference between using Implies and and in first order logic expressions.

If we take a statement "everyone in this A. I class has taken a course in mathematical logic" and "John is a student in this class" leads to "John has taken a course in mathematical logic".

Let, $D(x)$ - $x$ is in this AI class $C(x)$ - $x$ has taken a course in mathematical logic.

Then the premises are, $∀x(D(x)⇒C(x))$ and $D(\text{John})$.

Can this also be written as, $∀x D(x) \land C(x)$ ?

Answer 1

Logic is easier when it is about people's natural instincts. Consider:

1. Every person in this room that is a woman has long hair: $$\forall p \in \mathrm{Room} \; (\mathrm{Woman}(p) \Rightarrow \mathrm{HasLongHair}(p))$$
2. Every person in this room is a woman and has long hair: $$\forall p \in \mathrm{Room} \; (\mathrm{Woman}(p) \land \mathrm{HasLongHair}(p))$$

Do you think there is a difference between these two statements?

Supplemental: The question you asked is a common one among students of mathematics. As a rule of thumb, you should use $\exists$ with $\land$ and you should use $\forall$ with $\Rightarrow$. For instance:

• Every matrix $M$ whose determinant is non-zero has an inverse: $$\forall M (\det M \neq 0 \Rightarrow \exists N (\text{$N$ is inverse of $M$)})$$
• There exists an odd number $x$ which is greater than $42$ $$\exists x (\text{$x$ is odd}) \land x > 42$$

Let us see what goes wrong if we use the wrong combination. The formula $$\forall M (\det M \neq 0 \land \exists N (\text{$N$ is inverse of $M$)})$$ says: every matrix $M$ has a non-zero determinant and an inverse. This is obviously false, as the zero matrix is a counter-example.

The formula $$\exists x (\text{$x$ is odd}) \Rightarrow x > 42$$ says: there is a number $x$ such that if $x$ is odd then $x > 42$. An example of such a number is $x = 6$. This is not what was intended.

Answer 2

What happens if we take $x\in C$ and $x\notin D$? I encourage you to try this before reading on!

In that case $\exists x\in C : x\notin D$ so $\forall x: D \&C$ is false. But $\forall x: D \rightarrow C$ might still be true.

Answer 3

No. The statement with implication is not the same as the statement with "and".

In your example, the latter statement means that absolutely everyone in your chosen universal set satisfies both $D$ and $C$. For example it might be that everyone in the whole world both is in your class and has studied logic. This is clearly not what the "implies" version is saying.

It is true that in common language, "and" can mean "implies". Thus: "you don't start studying right now, and you will fail for sure". But this is not the correct mathematical-logical meaning of "and".

Answer 4

$$\begin{array} \hline p&|&q&|& p\implies q &|& p\wedge q \\ \hline 0&|&0&|& 1 & | & 0\\ 0&|&1&|& 1 & | & 0\\ 1&|&0&|& 0 & | & 0\\ 1&|&1&|& 1 & | & 1\\\hline \end{array}$$

We see, that there is difference when $(p,q)=(0,0)$ (eg. Frank is not a student in AI class and Frank didn't take mathematical logic course) and $(p,q)=(1,0)$ (eg. Mike is not a student in AI class, but he took mathematical logic course)