# Thread: Basic predicate logic exercises

1. ## Basic predicate logic exercises

I'm working through some exercises in preparation of a test, I just have the answers, no motivation for why something is wrong. Which is essential in learning imo, so I hope you could give some pointers

Given:
J: John.
P: Pete.
C(x, y): x is a child of y.
M(x): x is a man.
W(x): x is a woman.

Write as a predicate:

John or Pete has a child:
My solution: $\exists x(C(x, J) \lor C(x, P))$.
The solution given is: $\exists x(C(x, J)) \lor \exists x(C(x, P)$.

Is my solution wrong? And so, why? Am I not allowed to use the scope of the quantifier like this in this context? Is my solution solution actually read as 'There's a child that belongs to either John or Pete' by using scope like this?

Everybody has a father and mother:
My solution: $\forall x(\exists x(W(z) \land C(x, z)) \land \exists y(M(y) \land C(x, y))$
The given solution: $\forall x \exists y,z(W(z) \land C(x, z) \land M(y) \land C(x, y))$
Again, basically the same question: is my use of scoping correct? Should I prefer to rewrite with the quantifiers out? Is this like not simplifying a fraction?

2. ## Re: Basic predicate logic exercises

Originally Posted by Lepzed
I just have the answers, no motivation for why something is wrong. Which is essential in learning imo
I agree.

Originally Posted by Lepzed
Given:
J: John.
P: Pete.
C(x, y): x is a child of y.
M(x): x is a man.
W(x): x is a woman.

Write as a predicate:

John or Pete has a child:
My solution: $\exists x(C(x, J) \lor C(x, P))$.
The solution given is: $\exists x(C(x, J)) \lor \exists x(C(x, P)$...

Is my solution solution actually read as 'There's a child that belongs to either John or Pete' by using scope like this?
Yes. The original sentence sounds more like: John has his own child or Pete has his own. However, both statements are equivalent because

$\exists x\,(A(x)\lor B(x))\Leftrightarrow((\exists x\,A(x))\lor(\exists x\,B(x)))$.

This is because $\exists x\,A(x)$ is essentially a big disjunction $A(x_0)\lor A(x_1)\lor\dots$, and disjunction is commutative and associative. In contrast,

$\exists x\,(A(x)\land B(x))\nLeftrightarrow((\exists x\,A(x))\land(\exists x\,B(x)))$

$\forall x\,(A(x)\lor B(x))\nLeftrightarrow((\forall x\,A(x))\lor(\forall x\,B(x)))$

because $\forall x\,A(x)$ is a big conjunction, and conjunction and disjunction distribute over each other in a more complicated way.

Originally Posted by Lepzed
Everybody has a father and mother:
My solution: $\forall x(\exists x(W(z) \land C(x, z)) \land \exists y(M(y) \land C(x, y))$
The given solution: $\forall x \exists y,z(W(z) \land C(x, z) \land M(y) \land C(x, y))$
In the first formula, $\exists x$ should be $\exists z$. Again, these formulas are equivalent because

$A\land \exists y\,B(y)\Leftrightarrow \exists y\,(A\land B(y))$

provided y is not free in A. Using this fact, you can pull both existential quantifiers up front.

Thanks again

4. ## Re: Basic predicate logic exercises

I hope you (or someone else) wouldn't mind giving this a glimpse, to see if I get this right.

There is a real number which is greater than 0 and there is a real number which is smaller than 0: $\exists x[x \in R : x > 0] \land \exists x[x \in R : x < 0]$. And not $\exists x[x \in R : x > 0 \land x < 0]$, right?

All elements of N are greater than 10 or all elements of N are smaller than 25: $\forall x[x \in N: x > 10) \lor \forall x(x \in N: x < 25]$ and not $\forall x[x \in N: x > 10 \lor x \in N: x < 25]$, right?

There is a number in R which is greater than 10 and smaller than 25:

$\exists x [x \in R: x > 10 \land x < 25]$ is allowed though. Right?

There is no real number which is both greater than 0 and smaller than 0: $\lnot \exists x[x \in R: x > 0 \land x < 0]$.

Is this correct? Am I missing the point?

5. ## Re: Basic predicate logic exercises

$x\in R : x > 0$ is not a well-formed formula because ":" is not a connective. It should be $x\in R\land x > 0$. Sometimes $\exists x\in R: x>0$ serves a contraction for $\exists x\,(x\in R\land x>0)$. It is also possible that $\exists x\in R: x>0$ or $\exists x\in R\, x>0$ is a not a contraction, i.e., the formula syntax requires that every quantified variable has an explicit range, but I think this is less likely in your case. Anyway, double-check the formula syntax.

$\forall x(x \in N: x < 25)$ should be $\forall x(x \in N\to x < 25)$. Common idioms are $\exists x\,(x\in A \land\dots)$ and $\forall x\,(x\in A\to\dots)$.

You are correct about putting conjunctions/disjunctions inside or outside the quantifiers.

6. ## Re: Basic predicate logic exercises

To elaborate the usage of ':', as far as I'm able to with my knowledge
The : is a notation used in a book we're using (Logical Reasoning: A First Course, by Nederpelt), it's derived from the set-notation, and read/used like the '|' in $\{ x \in N | ... \}$.
So we see predicates formulated in a sort of mix between set theory and logic, probably because the book serves as in introduction to both sports in the context of a computer science course. Like: $\exists m,n[(m, n) \in R \times N: 3m + n > 3]$ and $\forall n[n \in N : \exists m[m \in R : 3m + n > 3]]$ for example.

Taking this difference in notation in account, my formulas were correct? Goody

Edit: Oh I see I didn't use the '[' and ']' in my solutions,

7. ## Re: Basic predicate logic exercises

OK, I see. I don't know if blurring the difference between $\forall x\,(x\in A\to\dots)$ and $\exists x\,(x\in A \land\dots)$ is helpful to new readers, but maybe yes. Ultimately, though, $\exists x\,(f(x)\in S:P(x))$ stands for $\exists x\,(f(x)\in S\land P(x))$ and $\forall x\,(f(x)\in S:P(x))$ stands for $\forall x\,(f(x)\in S\to P(x))$.

Edit.

Taking this difference in notation in account, my formulas were correct?
Yes.

8. ## Re: Basic predicate logic exercises

All right, thank you for clarifying. You've been very helpful! I'm going to practice some more and call it a day. Cheers