Results 1 to 2 of 2

Math Help - FOL satisfiability of a sentence

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    1

    FOL satisfiability of a sentence

    Hi Everyone! I've been revising for my exams and got stuck at this question:

    The following sentence of First-Order Logic
    ((\forall X p(X)) \to (\forall X q(X))) \wedge p(a) \wedge \neg q(a)
    is
    A. valid and satisfiable
    B. valid and unsatisfiable
    C. valid but its satisfiability cannot be determined
    D. invalid and satisfiable
    E. invalid and unsatisfiable
    F. invalid but its satisfiability cannot be determined
    I would think it's E as I can't really find a model which would satisfy this sentence, though the answer is D. Could you please give me a hint as how I should approach this? Assuming that D is the correct answer I must be missing something.

    My thinking: if p(a) is to be true then \forall X p(X) must be true as well. This implies that \forall X q(X) must be true and \neg p(q) will inevitably be false.

    EDIT:
    OK, if we change ((\forall X p(X)) \to (\forall X q(X))) into ((\neg \forall X p(X)) \vee (\forall X q(X))) I can indeed see that the sentence is satisfiable.
    Could someone please tell me why I couldn't see it without transforming the implication into disjunction?
    Last edited by Szyszec; June 12th 2011 at 08:19 AM. Reason: I finally worked out how to get the answer plus minor LaTeX changes
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Quote Originally Posted by Szyszec View Post
    My thinking: if p(a) is to be true then \forall X p(X) must be true as well.
    The fact that my neighbor, say, John is a horrible person does not imply that all people are horrible. Then a large part of life would lose meaning.

    Both the premise and the conclusion of ((\forall X p(X)) \to (\forall X q(X))) can be false in a particular interpretation, so p(a) can be true and q(a) can be false in that interpretation.

    You also need to show that the sentence is invalid, i.e., you need to find a counter-interpretation.

    Quote Originally Posted by Szyszec View Post
    OK, if we change ((\forall X p(X)) \to (\forall X q(X))) into ((\neg \forall X p(X)) \vee (\forall X q(X))) I can indeed see that the sentence is satisfiable.
    Could someone please tell me why I couldn't see it without transforming the implication into disjunction?
    I am not sure why you could not see it. In fact, I am not sure how changing ((\forall X p(X)) \to (\forall X q(X))) into ((\neg \forall X p(X)) \vee (\forall X q(X))) helps in seeing that the original sentence is satisfiable. The problem with your post before "EDIT," as I pointed out above, is that p(a) can be true and \forall X p(X) can still be false.

    Edit: Additional remark. I don't see how B can be true for any sentence except when one considers validity and satisfiability with respect to an empty class of interpretations. If one considers all interpretations and a sentence is valid, then it is true in all interpretations, so it can't be unsatisfiable. Similarly, "satisfiable" is unnecessary in A since it is implied by "valid."
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. testing (sentence)
    Posted in the LaTeX Help Forum
    Replies: 0
    Last Post: December 15th 2011, 02:39 AM
  2. V-sentence
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 4th 2011, 12:11 PM
  3. Help with logic sentence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 10th 2009, 03:26 AM
  4. Negation of a sentence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 23rd 2009, 06:27 PM
  5. Boolean satisfiability and NP-Completness
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 5th 2006, 10:17 PM

Search Tags


/mathhelpforum @mathhelpforum