# Predicate Calculus with Domains

• Feb 18th 2013, 12:04 PM
aprilrocks92
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?
• Feb 18th 2013, 12:50 PM
emakarov
Re: Predicate Calculus with Domains
Quote:

Originally Posted by aprilrocks92
(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.
• Feb 18th 2013, 03:39 PM
johng
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$.
• Feb 22nd 2013, 01:37 PM
aprilrocks92
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.
• Feb 22nd 2013, 03:38 PM
emakarov
Re: Predicate Calculus with Domains
Quote:

Originally Posted by johng
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
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
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.
• Feb 24th 2013, 04:04 AM
aprilrocks92
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.
• Feb 24th 2013, 04:45 AM
emakarov
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.
• Feb 24th 2013, 06:12 AM
HallsofIvy
Re: Predicate Calculus with Domains
Quote:

Originally Posted by aprilrocks92
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.
• Feb 24th 2013, 07:57 AM
aprilrocks92
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.
• Feb 24th 2013, 10:33 AM
emakarov
Re: Predicate Calculus with Domains
Quote:

Originally Posted by HallsofIvy
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
(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
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
For (c), there exists an x, namely x = b, which makes the implication true because it makes the premise false.