Predicate Logic Challenge Exercice

Question

Hi I just started to teach myself logic but it is really confusing. This is the problem I am struggling with right now:

Give two structures for the following formulas; one such that the truth value of the formula is F and one such that it is T:

∀X •∃Y •(p(X,Y)⇒q(X,Y))

I did not understand anything of this topic and I couldn't find enough explanatory materials online and idk who else to ask. I followed an example to come up with the solution and this is what I came up with (but I have no idea why I have to use U and V, I am just following an example):

For value T: domain of discourse: all humans p(U,V): U is parent of V q(U,V): U is child of V

For value F: domain of discourse: all humans p(U,V): U is parent of V q(U, V ): U is parent of V (interpretations of p and q are the same)

Can someone please tell me why this is wrong and what is the correct answer? Or explain me how to find the right answer?

Many thanks in advance.

P.S. I am here to learn, please don't be too harsh!

Answer 1

Yes, you have the right approach by coming up with some domain and interpreting the predicates over that domain.

However your specific choices leave a lot to be desired ...

The first one does indeed work to make the claim true ... but probably not in the way you intended. That is, for any human $x$ we can choose $y$ to be $x$ itself, and since no one is a parent of themselves, we thus have that $p(x,y)$ is false, and therefore $p(x,y) \rightarrow q(x,y)$ is true.

However, note that we can do the same for the second structure, and so in fact that structure makes the claim true as well...

HINT: what would make a conditional statement false?

Answer 2

$$\forall x\exists y[p(x,y)\implies p(x,y)]$$ is a true statement so for that you can just take $q=p$.

---

Taking $q(x,p)=\neg p(x,y)$ on the other hand we get: $$\forall x\exists y[p(x,y)\implies\neg p(x,y)]$$ which is the same statement as: $$\forall x\exists y[\neg p(x,y)]$$ so it is false if some $x$ exists such that $p(x,y)$ is true for every $y$.

Then you can go for the statement that $y\notin x$ where sets are the domain of discourse.

Then it is the statement: $$\forall x\exists y[y\in x]$$which is false because $x=\varnothing$ has no elements.