Results 1 to 8 of 8

Thread: Basic predicate logic exercises

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Basic predicate logic exercises

    Quote Originally Posted by Lepzed View Post
    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 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    Re: Basic predicate logic exercises

    Thanks again
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    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?
    Last edited by Lepzed; Oct 7th 2011 at 08:40 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jul 2011
    Posts
    53

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

    Edit: Oh I see I didn't use the '[' and ']' in my solutions,
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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.

    Taking this difference in notation in account, my formulas were correct?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Mar 23rd 2011, 12:05 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 5th 2010, 07:53 AM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 21st 2010, 08:39 PM
  4. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Feb 6th 2010, 06:23 AM
  5. basic predicate logic question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 23rd 2009, 03:55 PM

Search Tags


/mathhelpforum @mathhelpforum