3
$\begingroup$

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)$ ?

$\endgroup$
1
  • 1
    $\begingroup$ Hint: What about students who took mathematical logic but were not in the AI class? $\endgroup$
    – Laray
    Jan 17 '17 at 11:10
7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Yeah in the first one, there can be people other than women in the room but in the second one everyone in the room must be a woman. $\endgroup$
    – PeeBee
    Jan 17 '17 at 12:28
  • $\begingroup$ So is this a sufficiently clear answer to your question? $\endgroup$ Jan 17 '17 at 13:37
  • $\begingroup$ I believe so. I learned a lot of stuff from all the answers here so it's difficult to award the best answer to one person but I gave it away to one person. Sorry about that. I can't upvote answers either because I'm new. Thanks for your answer $\endgroup$
    – PeeBee
    Jan 17 '17 at 13:39
  • $\begingroup$ I added a rule of thumb which I give to my students. $\endgroup$ Jan 17 '17 at 13:53
  • $\begingroup$ I think that's exactly what I was looking for. Thank you so much $\endgroup$
    – PeeBee
    Jan 17 '17 at 14:14
2
$\begingroup$

$$\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)

$\endgroup$
1
  • $\begingroup$ Thank you. I understand the difference clearly now. $\endgroup$
    – PeeBee
    Jan 17 '17 at 13:16
1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Can there be a case where both implies and AND can be used interchangeably? $\endgroup$
    – PeeBee
    Jan 17 '17 at 11:27
  • $\begingroup$ Not that I can think of. $\endgroup$
    – David
    Jan 17 '17 at 11:34
  • $\begingroup$ Then how about any tip in understanding which one to go for, implies or AND, when an argument is given as an English statement? How do you generally differentiate? Is there a definitive way? $\endgroup$
    – PeeBee
    Jan 17 '17 at 11:55
  • $\begingroup$ Not sure I can suggest anything because the difference is completely obvious to me... sorry if that sounds rude. "And" is a situation when two (or more) statements are definitely true. "Implies" is a hypothetical, if something is true, then so is something else. $\endgroup$
    – David
    Jan 17 '17 at 13:12
  • $\begingroup$ Don't know if this will help - do you understand the difference between the following? (1) I have \$3 and I will buy a coffee. (2) If I have \$3, then I will buy a coffee. $\endgroup$
    – David
    Jan 17 '17 at 13:14
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I see. Is there any case where logical AND and implies are interchangeable ? Can you give me any clue on finding whether to go for implies or for an AND by reading a statement in English, where the choice is not so obvious? $\endgroup$
    – PeeBee
    Jan 17 '17 at 11:21
  • $\begingroup$ Or can you write a correct answer for my problem by using AND instead of implies? $\endgroup$
    – PeeBee
    Jan 17 '17 at 11:22
  • $\begingroup$ I don't think that's possible. What you can do however, is use an or to construct something logically equivalent: $p \Rightarrow q \equiv ~p \lor (p\land q)$ $\endgroup$ Jan 17 '17 at 12:50
  • $\begingroup$ Thank you for helping me out $\endgroup$
    – PeeBee
    Jan 17 '17 at 13:17

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.