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: $\displaystyle \exists x(C(x, J) \lor C(x, P)) $.

The solution given is:$\displaystyle \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: $\displaystyle \forall x(\exists x(W(z) \land C(x, z)) \land \exists y(M(y) \land C(x, y))$

The given solution: $\displaystyle \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?

Re: Basic predicate logic exercises

Quote:

Originally Posted by

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

I agree.

Quote:

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: $\displaystyle \exists x(C(x, J) \lor C(x, P)) $.

The solution given is:$\displaystyle \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

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

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

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

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

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

Quote:

Originally Posted by

**Lepzed** **Everybody has a father and mother:**

My solution: $\displaystyle \forall x(\exists x(W(z) \land C(x, z)) \land \exists y(M(y) \land C(x, y))$

The given solution: $\displaystyle \forall x \exists y,z(W(z) \land C(x, z) \land M(y) \land C(x, y))$

In the first formula, $\displaystyle \exists x$ should be $\displaystyle \exists z$. Again, these formulas are equivalent because

$\displaystyle 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.

Re: Basic predicate logic exercises

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**: $\displaystyle \exists x[x \in R : x > 0] \land \exists x[x \in R : x < 0] $. And not $\displaystyle \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**: $\displaystyle \forall x[x \in N: x > 10) \lor \forall x(x \in N: x < 25]$ and not $\displaystyle \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**:

$\displaystyle \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**:$\displaystyle \lnot \exists x[x \in R: x > 0 \land x < 0]$.

Is this correct? Am I missing the point?

Re: Basic predicate logic exercises

$\displaystyle x\in R : x > 0$ is not a well-formed formula because ":" is not a connective. It should be $\displaystyle x\in R\land x > 0$. Sometimes $\displaystyle \exists x\in R: x>0$ serves a contraction for $\displaystyle \exists x\,(x\in R\land x>0)$. It is also possible that $\displaystyle \exists x\in R: x>0$ or $\displaystyle \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.

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

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

Re: Basic predicate logic exercises

To elaborate the usage of ':', as far as I'm able to with my knowledge :p

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 $\displaystyle \{ 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: $\displaystyle \exists m,n[(m, n) \in R \times N: 3m + n > 3]$ and $\displaystyle \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 (Nod)

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

Re: Basic predicate logic exercises

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

Edit.

Quote:

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

Yes.

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 :)