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

Thread: 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,577
    Thanks
    790

    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
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,141
    Thanks
    475

    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), $\displaystyle \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 $\displaystyle \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
    $\displaystyle \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 $\displaystyle \epsilon>0$. Now I must name $\displaystyle \delta>0$. Set (name) $\displaystyle \delta=\epsilon/2$. Let $\displaystyle x_1$ and $\displaystyle x_2$ be arbitrary and assume $\displaystyle |x_1-x_2|<\epsilon/2$. (Now come the "guts" of the proof which is trivial in this case.) Then $\displaystyle |2x_1+1-(2x_2+1)|<\epsilon$ or $\displaystyle |f(x_1)-f(x_2)|<\epsilon$.
    Last edited by johng; Feb 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,577
    Thanks
    790

    Re: Predicate Calculus with Domains

    Quote Originally Posted by johng View Post
    Now for part c), $\displaystyle \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,577
    Thanks
    790

    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
    19,733
    Thanks
    3012

    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,577
    Thanks
    790

    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: Aug 11th 2012, 07:53 AM
  2. derivations in predicate calculus
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Apr 23rd 2010, 07:44 AM
  3. predicate calculus
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 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: Mar 6th 2009, 10:19 PM

Search Tags


/mathhelpforum @mathhelpforum