Predicate Logic: Clarification of Concepts

Does the sentence $\displaystyle \forall x (P(x) \rightarrow Q(x)) $ mean "for all x $\displaystyle (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 $\displaystyle P(x)$ true and hence $\displaystyle ((P(x) \rightarrow Q(x))$ false?

Re: Predicate Logic: Clarification of Concepts

The statement $\displaystyle \forall x(P(x) \rightarrow Q(x))$ is false when its negation is true. What is its negation?

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.

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.

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 $\displaystyle P(x)$ true and hence $\displaystyle ((P(x) \rightarrow Q(x))$ false?

Making $\displaystyle P(x)$ true does not necessarily make $\displaystyle ((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.

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.

Re: Predicate Logic: Clarification of Concepts

Quote:

Originally Posted by

**JohnDoe2013** Does the sentence $\displaystyle \forall x (P(x) \rightarrow Q(x)) $ mean "for all x $\displaystyle (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 $\displaystyle P(x)$ true and hence $\displaystyle ((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.

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.