Results 1 to 8 of 8

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780

    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: \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.

    Quote Originally Posted by Lepzed View Post
    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.
    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: \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?
    Last edited by Lepzed; October 7th 2011 at 08:40 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780

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

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780

    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.
    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: March 23rd 2011, 12:05 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2010, 07:53 AM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 08:39 PM
  4. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 6th 2010, 06:23 AM
  5. basic predicate logic question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 03:55 PM

Search Tags


/mathhelpforum @mathhelpforum