# Predicate Logic: Clarification of Concepts

• November 15th 2013, 09:27 AM
JohnDoe2013
Predicate Logic: Clarification of Concepts
Does the sentence $\forall x (P(x) \rightarrow Q(x))$ mean "for all x $(P(x) \rightarrow Q(x))$ is true?
If so, and we are asked to prove that the sentence is not a tautology, does it mean that all we need to do is come up with some interpretation of what x and P(x) are that would make $P(x)$ true and hence $((P(x) \rightarrow Q(x))$ false?
• November 15th 2013, 09:51 AM
SlipEternal
Re: Predicate Logic: Clarification of Concepts
The statement $\forall x(P(x) \rightarrow Q(x))$ is false when its negation is true. What is its negation?
• November 15th 2013, 11:11 AM
JohnDoe2013
Re: Predicate Logic: Clarification of Concepts
Hi SlipEternal, the negation is that there exists some x for which P(x)->Q(x) is false.
I was trying to clarify the how the method of proof where the statement is considered a formula of a first-order language.
Since the statement has no free variables, the proof would only depend on the structure and not the valuation of x.
However, I'm not entirely clear on whether this meant that we could define any structure and interpret/define P(x) and Q(x) in any manner that would suit the proof.
• November 15th 2013, 11:37 AM
SlipEternal
Re: Predicate Logic: Clarification of Concepts
A statement is logically valid if it is true in every interpretation. So, you need to show the existence of an interpretation where the statement is false.
• November 15th 2013, 11:54 AM
emakarov
Re: Predicate Logic: Clarification of Concepts
Quote:

Originally Posted by JohnDoe2013
does it mean that all we need to do is come up with some interpretation of what x and P(x) are that would make $P(x)$ true and hence $((P(x) \rightarrow Q(x))$ false?

Making $P(x)$ true does not necessarily make $((P(x) \rightarrow Q(x))$ false.

Quote:

Originally Posted by JohnDoe2013
However, I'm not entirely clear on whether this meant that we could define any structure and interpret/define P(x) and Q(x) in any manner that would suit the proof.

Yes, we could.
• November 15th 2013, 12:17 PM
johng
Re: Predicate Logic: Clarification of Concepts
Hi,
"Every human is a man" is obviously false. That is "for any x, if x is a human, then x is a man" is false. There is an x such that x is a human and x is not a man. Clearly true for almost any x named Sue.
• November 16th 2013, 05:46 AM
Hartlw
Re: Predicate Logic: Clarification of Concepts
Quote:

Originally Posted by JohnDoe2013
Does the sentence $\forall x (P(x) \rightarrow Q(x))$ mean "for all x $(P(x) \rightarrow Q(x))$ is true?
If so, and we are asked to prove that the sentence is not a tautology, does it mean that all we need to do is come up with some interpretation of what x and P(x) are that would make $P(x)$ true and hence $((P(x) \rightarrow Q(x))$ false?

The sentence is T or F depending on what P(x) and Q(x) are, so it can't be a tautology. Exs
Let P(x)=T and Q(x)=F, the sentence is False.
Let P(x)=T and Q(x)=T, the sentence is True.
• November 16th 2013, 06:18 AM
Hartlw
Re: Predicate Logic: Clarification of Concepts
If the sentence is a definition, it’s a tautology (alwaysTrue).
For ex:
for all x, (P(x)=Q(x))
is a tautology if it’s a definition, otherwise not.