Results 1 to 8 of 8

Math Help - Predicate Logic: Clarification of Concepts

  1. #1
    Junior Member
    Joined
    Oct 2013
    From
    Canada
    Posts
    31
    Thanks
    8

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2013
    From
    Canada
    Posts
    31
    Thanks
    8

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Predicate Logic: Clarification of Concepts

    Quote Originally Posted by JohnDoe2013 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    682
    Thanks
    281

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Predicate Logic: Clarification of Concepts

    Quote Originally Posted by JohnDoe2013 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 04:51 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 09:39 PM
  3. predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 6th 2009, 02:06 AM
  4. More predicate logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 07:45 PM
  5. Help with predicate logic
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 10th 2008, 06:05 PM

Search Tags


/mathhelpforum @mathhelpforum