I'm currently looking at first order logic and I'm having a difficult time with the following question:

enter image description here

Now I don't want answer cause that wont really help me. What I am looking for is help, with the best approaches or techniques used that can help solve these types of questions. I've sat now for about 2 hours and I just come up blank. Any help from experienced members would really help.

  • $\begingroup$ It would be nice if you could provide the source of that question $\endgroup$ – Zamu Aug 30 '14 at 15:59
  • $\begingroup$ It was a question from a tutorial from university $\endgroup$ – user481610 Aug 30 '14 at 16:11

It is difficult to give hints without essentially solving the problems, but here goes!

We will take the natural numbers as meaning $1,2,3,\dots$. If you are using $0,1,2,\dots$ (which I prefer) the examples either need no adjustment or can be trivially adjusted.

Finding interpretations in which the given sentences are true should not be difficult. Your sentences all have the basic structure $A\to B$, and in each case it is easy to find interpretations under which $A$ is false and therefore the implication is true. More simply, use for $p(x,y)$, $p(x)$, and $q(x)$ relations that are always true.

Or else you can proceed like this. For each of the sentences, make up some simple interpretation for the predicate symbols, and check whether under that interpretation the given sentence is true or false. Whatever the result, you will have done half the problem!

We now give some specific hints. We hope that they help lead to answers, but leave some work to you.

a) To make this false, recall the example you were undoubtedly given, which looks like this. Let $p(s,t)$ hold if $s$ is the mother of $t$. Everybody has a mother, but it is not true that there is someone who is everybody's mother.

Imitate "mother" in the natural numbers. But there is a simpler example involving $\le$, and an even simpler example using $=$.

b) For a falsifying interpretation, let $q(x)$ be the expression $x=17$. You can find a suitable $p(x)$.

c) For a falsifying interpretation, for $p(x)$ use $x\le 17$. You can find a suitable $q(x)$.


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.