Results 1 to 5 of 5

Math Help - Proving satisfiability and validity

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Proving satisfiability and validity

    Hi,

    I am struggling to prove whether the following statements are true or false, and consequently to prove why that is.
    Mainly because I don't understand the difference between satisfiable and valid, so if someone could explain that, I'd highly appreciate it!

    (i) For all F, F is satisfiable or ~F is satisfiable.

    (ii) For all F, F is valid or ~F is valid.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,619
    Thanks
    592

    Re: Proving satisfiability and validity

    Hey aprilrocks92.

    Have you got a definition of satisfiable and/or valid? What kind of structures do these objects have?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Proving satisfiability and validity

    F is satisfiable if F is true in at least one interpretation. For example, 1 + 1 = 0 is satisfiable because it is true in \mathbb{Z}_2. F is valid if it is true in all interpetations. For example, 1 + 1 = 0 and 1 + 1 = 2 are not valid, but 1 = 1 is. Obviously, if a formula is valid, it is satisfiable. (This assumes that there is at least one interpretation.)

    Concerning the first claim, a stronger one is true: F is satisfiable or ~F is valid for all F.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Re: Proving satisfiability and validity

    So far, I have the following:
    Statement (i) is true, as for all F, F will either be satisfiable, or ~F will be satisfiable (truth table). However, how do I go about solving for statement (ii)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Proving satisfiability and validity

    First, I have to ask. Have you learned the definitions of formulas, interpretations and when a formula is true in an interpretation? Without it, it's meaningless to go forward.

    Quote Originally Posted by aprilrocks92 View Post
    Statement (i) is true, as for all F, F will either be satisfiable, or ~F will be satisfiable (truth table).
    What do you mean by "truth table" here?

    Quote Originally Posted by aprilrocks92 View Post
    However, how do I go about solving for statement (ii)?
    Let's take this in steps. Let P(i) say "i is prime" where i is a natural number. Does the following disjunction hold:

    (for all i, P(i) holds) or (for all i, P(i) does not hold)?

    Now, let i range over interpretations instead of numbers and let P(i) say that the given formula F is true in an interpretation i.

    (1) F is valid ⇔ F is true in all interpretations i ⇔ for all i, P(i) holds .

    Similarly,

    (2) ~F is valid ⇔ ~F is true in all interpretations i ⇔ F is false in all i ⇔ for all i, P(i) does not hold.

    Does it have to be that (1) or (2) holds?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. FOL satisfiability of a sentence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 12th 2011, 07:57 AM
  2. Validity Problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 27th 2010, 06:00 PM
  3. validity
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 16th 2009, 03:11 PM
  4. Proving the Validity of an Argument in Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 12th 2009, 02:04 PM
  5. Boolean satisfiability and NP-Completness
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 5th 2006, 09:17 PM

Search Tags


/mathhelpforum @mathhelpforum