Results 1 to 10 of 10
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By johng

Math Help - Predicate Calculus with Domains

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Predicate Calculus with Domains

    Hello, I have the following problem, but I don't know how to approach this.

    Given the domain: {a, b, c},
    and the following predicates:
    P is interpreted as {(a,b), (b,c), (b,b)}
    Q is interpreted as {(a,a), (c,c)}

    Find the truth values of the following formulae under this interpretation,briefly justifying your answer:
    (a) x(P(x,c)Q(x,x))
    (b) xy(P(x,y)Q(x,x))
    (c) x(Q(x,x)⇒∀y(P(c,y)P(x,y)))




    ************************************************** ********
    So far, I have attempted to solve this problem by renaming the domain values and predicates, to make it "easier" to comprehend.

    Domain: {ann, bob, carmen}

    Predicates:
    P- Parties{(ann,bob), (bob, carmen), (bob, bob)}
    Q- Questions{(ann, ann),(carmen, carmen)}

    (a) For all people x, it is the case that x parties with carmen given that x questions himself/herself.
    We see that this is false, since the only person who parties with carmen does not question himself.


    This seems like a rather complicated and not mathematical approach. How can I approach this problem in a different way?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Predicate Calculus with Domains

    Quote Originally Posted by aprilrocks92 View Post
    (a) For all people x, it is the case that x parties with carmen given that x questions himself/herself.
    We see that this is false, since the only person who parties with carmen does not question himself.
    I believe that "A given B" means "If B, then A". So, "x parties with carmen given that x questions himself" means "if x questions himself, then x parties with carmen", while the formula has the converse implication. But you are right that b is a counterexample.

    You are free to come up with an interpretation for abstract symbols to get a better intuitive idea of what the formulas say. I do this myself sometimes when formulas are complicated. For this problem, it is probably easier for me to think "as is". For example, Q is "almost" reflexive; the only exception is b. If Q were reflexive, then ∀x(P(x,c) ⇒ Q(x,x)) would be true just because the conclusion is true. So, the only x to check is b. And indeed, x = b makes the premise true, so the implication is false. For (c), we can take x = b again; then the premise of the implication is false and the implication is therefore true.
    Thanks from aprilrocks92
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    663
    Thanks
    274

    Re: Predicate Calculus with Domains

    First, you must understand truth value of predicates. What's the truth value of P(a,c)? Why, it's false. The only values for which P is true are P(a,b), P(b,c) and P(b,b).

    Now for part c), \exists x(Q(x,x)\Rightarrow ...). The implication is false only when Q(x,x) is false; so take two values a and c for which Q is true. Now P(c,y) is false for all y, so the only way \forall y(P(c,y)\vee P(x,y)) is true is P(x,y) true for all y. When x=a, this is not true since P(a,c) is false. When x=c, both disjuncts are false. So there does not exist x for which the implication is true. Hence the statement is false.

    Here's what I used to tell my students. To prove a statement with "for all", give an arbitrary instance; i.e. let ...; to prove a statement with "there exists", you need to name the quantity in terms of other values. Example:
    The definition of uniform continuity for a function f is
    \forall\epsilon>0,\exists\delta>0,\,\forall x_1\forall x_2\,\,  |x_1-x_2|<\delta\Rightarrow|f(x_1)-f(x_2)|<\epsilon.

    Let f(x)=2x+1. Then f is uniformly continuous:

    Let \epsilon>0. Now I must name \delta>0. Set (name) \delta=\epsilon/2. Let x_1 and x_2 be arbitrary and assume |x_1-x_2|<\epsilon/2. (Now come the "guts" of the proof which is trivial in this case.) Then |2x_1+1-(2x_2+1)|<\epsilon or |f(x_1)-f(x_2)|<\epsilon.
    Last edited by johng; February 18th 2013 at 04:46 PM.
    Thanks from aprilrocks92
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Re: Predicate Calculus with Domains

    This far I have understood that (a) is true, whereas (b) and (c) are both false, since there exist counterexamples to the predicates. Would a counterexample be regarded sufficient "proof"?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Predicate Calculus with Domains

    Quote Originally Posted by johng View Post
    Now for part c), \exists x(Q(x,x)\Rightarrow ...). The implication is false only when Q(x,x) is false
    You probably mean "only when Q(x, x) is true". In fact, (c) is true for x = b.

    Quote Originally Posted by aprilrocks92 View Post
    This far I have understood that (a) is true, whereas (b) and (c) are both false
    I thought we agreed that b is a counterexample to (a). Both (b) and (c) are true. In (b), you can take y = b or y = c for all x.

    Quote Originally Posted by aprilrocks92 View Post
    Would a counterexample be regarded sufficient "proof"?
    Yes, a counterexample (together with an explanation why it actually makes the formula false if this explanation is not trivial) is a sufficient proof that the formula is false.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Re: Predicate Calculus with Domains

    My bad, I meant to write (a) as false, (b) as true.

    I still do not understand how (c) is true.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Predicate Calculus with Domains

    For (c), there exists an x, namely x = b, which makes the implication true because it makes the premise false.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,041
    Thanks
    1675

    Re: Predicate Calculus with Domains

    Quote Originally Posted by aprilrocks92 View Post
    This far I have understood that (a) is true, whereas (b) and (c) are both false, since there exist counterexamples to the predicates. Would a counterexample be regarded sufficient "proof"?

    Thank you.
    A counter example is always sufficient proof that a general statement is false.

    However, I get that only (b) is true while (a) and (b) are false.

    P is interpreted as {(a,b), (b,c), (b,b)}
    Q is interpreted as {(a,a), (c,c)}

    (a) ∀x(P(x,c)⇒Q(x,x))
    If x= b then P(x, c)= P(b,c) but NOT Q(x,x)= Q(b,b).

    (b) ∀x∃y(P(x,y)∨Q(x,x))
    This, however, is true. For x= a or x= C, Q(x,x). For x= b, there exist y= c so that P(x, y)= P(b, c)

    (c) ∃x(Q(x,x)⇒∀y(P(c,y)∨P(x,y)))
    A counterexample is x= c. We have Q(c, c) but never P(c, y) for any y.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Re: Predicate Calculus with Domains

    I initially thought (c) was false.

    (c) ∃x(Q(x,x)⇒∀y(P(c,y)∨P(x,y)))

    The statement is false only if ∀y(P(c,y)∨P(x,y)) evaluates to be false.
    We know that P(c,y) is false for all y, since P {(a,b), (b,c), (b,b)}. Hence, the only way ∀y(P(c,y)∨P(x,y)) is true, is if P(x,y) is true for all y.

    When x = a, this is not the case since P(a,c) is false. When x = c, bust disjunctions evaluate to false. Hence, the statement is false.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Predicate Calculus with Domains

    Quote Originally Posted by HallsofIvy View Post
    A counter example is always sufficient proof that a general statement is false.
    Strictly speaking, to disprove a general statement, one needs a counterexample (an object, such as a number, a set or a function) and a proof that this object falsifies the statement. If one wants to disprove ∀x P(x), it is sufficient to come up with some concrete n and a proof that P(n) is false, i.e., a proof of P(n). Now, a proof of a universal statement is usually significantly more complicated than a proof of its instance (or the negation of an instance), so the latter proof is often taken for granted. For example, when P(x) is a property of natural numbers that uses only standard arithmetic operators, then the truth of P(n) for some concrete n can be verified by a simple calculation, whereas a proof that P(x) holds for each of infinitely many numbers can be very complex. Still, P(n) is itself a theorem and thus requires a proof.

    Quote Originally Posted by HallsofIvy View Post
    (c) ∃x(Q(x,x)⇒∀y(P(c,y)∨P(x,y)))
    A counterexample is x= c. We have Q(c, c) but never P(c, y) for any y.
    This statement starts with an existential quantifier, not a universal one.

    Quote Originally Posted by aprilrocks92 View Post
    I initially thought (c) was false.

    (c) ∃x(Q(x,x)⇒∀y(P(c,y)∨P(x,y)))

    The statement is false only if ∀y(P(c,y)∨P(x,y)) evaluates to be false.
    We know that P(c,y) is false for all y, since P {(a,b), (b,c), (b,b)}. Hence, the only way ∀y(P(c,y)∨P(x,y)) is true, is if P(x,y) is true for all y.

    When x = a, this is not the case since P(a,c) is false. When x = c, bust disjunctions evaluate to false. Hence, the statement is false.
    You are using the following logic. If the implication is false, the conclusion is false. The conclusion is false; therefore, the implication is false.

    Quote Originally Posted by emakarov View Post
    For (c), there exists an x, namely x = b, which makes the implication true because it makes the premise false.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: August 11th 2012, 07:53 AM
  2. derivations in predicate calculus
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 23rd 2010, 07:44 AM
  3. predicate calculus
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 13th 2009, 11:01 AM
  4. Predicate Calculus
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 21st 2009, 05:19 PM
  5. Predicate Calculus help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 6th 2009, 10:19 PM

Search Tags


/mathhelpforum @mathhelpforum