Thread: 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) ∀x∃y(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?

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.

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), . 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 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


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

Let . Now I must name . Set (name) . Let and be arbitrary and assume . (Now come the "guts" of the proof which is trivial in this case.) Then or .

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.

Originally Posted by johng

Now for part c), . 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.

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.

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.

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

I still do not understand how (c) is true.

For (c), there exists an x, namely x = b, which makes the implication true because it makes the premise false.

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.

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.

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.

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.

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.

Originally Posted by emakarov

For (c), there exists an x, namely x = b, which makes the implication true because it makes the premise false.