Results 1 to 6 of 6

Math Help - Satisfying Truth Assignment

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    Satisfying Truth Assignment



    So I have to show: \Sigma is complete \iff \Sigma has a unique satisfying truth assignment. So my proof has to go in both directions...

    To show the " \Leftarrow", we can try proving its contrapositive:

    "If \Sigma is not complete then it has no unique truth assignment."

    If there is a truth assignment f_{\Sigma} then for an arbitrary A the following is one of the options that must be true:

    f_{\Sigma}(A)=0 then f_{\Sigma}(\neg A) = 1.

    And in order for that to be true we need \Sigma to be complete (because if we have f_{\Sigma}(A)=0, then A \notin \Sigma so \neg A \in \Sigma so f_{\Sigma}(\neg A) = 1).

    Suppose \Sigma is not complete, then if f_{\Sigma}(A)=0 then f_{\Sigma}(\neg A) \neq 1. So there's no truth assignment. Is this right?


    To show the " \Rightarrow", similarly I'll try proving its contrapositive:

    "If \Sigma doesn't have a unique satisfying truth assignment, then it is not complete."

    Suppose \Sigma doesn't have a unique satisfying truth assignment. Then how could we prove that \Sigma is therefore not complete? Here's where I'm stuck...

    P.S: By the truth assignment f_{\Sigma}(A): form(L) \to \{ 0,1 \} I meant:

    f_{\Sigma}(A)= \left\{\begin{matrix}1 \ if A \in \Sigma \\ 0 \ if \ A \notin \Sigma\end{matrix}\right.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Satisfying Truth Assignment

    Quote Originally Posted by demode View Post
    So there's no truth assignment.
    No, the link in your post stipulates that sigma is consistent. Moreover, the assumption of incompleteness does NOT imply unsatisfiability. If you use the contrapositive approach, then what you have to show is that there is more than one assignment that satisfies sigma.

    Question: May we use the completeness theorem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    224

    Re: Satisfying Truth Assignment

    Quote Originally Posted by MoeBlee View Post
    No, the link in your post stipulates that sigma is consistent. Moreover, the assumption of incompleteness does NOT imply unsatisfiability. If you use the contrapositive approach, then what you have to show is that there is more than one assignment that satisfies sigma.
    That's exactly what I wanted to show, that the truth assignment is not unique and there are more than one that satisfy sigma. But HOW can I prove that? I think this is the most diificult part...

    Question: May we use the completeness theorem?
    Yes, we can use any other method to prove this.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Satisfying Truth Assignment

    I think using contrapositive is unnecessarily roundabout.

    First, though, just for exactness, do you mean that S (sigma) is complete in the sense that for every formula P, either P or ~P is in S, or do you mean that S is complete in the sense that for every formula P, either S |- P or S |- ~P ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2009
    Posts
    224

    Re: Satisfying Truth Assignment

    Quote Originally Posted by MoeBlee View Post
    I think using contrapositive is unnecessarily roundabout.
    So how else would you prove that?

    First, though, just for exactness, do you mean that S (sigma) is complete in the sense that for every formula P, either P or ~P is in S, or do you mean that S is complete in the sense that for every formula P, either S |- P or S |- ~P ?
    We say that \Sigma is compelete if for every P \in \ form(L) we have either P \in \Sigma or \neg P \in \Sigma.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Satisfying Truth Assignment

    That definition of 'S is complete' is correct.

    However, if I'm not mistaken, in this problem, S should not be just a set of formulas, but rather S should be a set of formulas closed under deduction (S is closed under deduction iff for any formula P, if S proves P then P is in S).

    We can NOT prove:

    If S is consistent and there is a unique assigment that satisfies S, then S is complete

    since we have this counterexample:

    Let S be the set of all atomic formulas. Then there is a unique assigment that satisfies S (viz., the assignment f such that f(P) = 1 for all atomic P) but S is not complete since, for example, for any formula P, neither ~P nor ~~P are in S.

    But we CAN prove

    If S is closed under deduction and there is a unique assigment that satisfies S, then S is complete.

    Proof:

    Let f be the unique assigment. Let f' be the truth evaluation for all the formulas determined by the truth assignment f of the atomic formulas.

    Suppose f'(K) = 1. Then, since f is the only assignment that satisfies S, we have S |= K, so, by the completeness theorem, S |- K, so, since S is closed under deduction, K is in S.

    Suppose f'(K) = 0. So f'(~K) = 1. Then, since f is the only assignment that satisfies S, we have S |= ~K, so, by the completeness theorem, S |- ~K, so, since S is closed under deduction, ~K is in S.

    Note: The proof is even simpler, in an obvious way, and does not require the completeness thereom if we change to:

    If S is closed under entailment and there is a unique assigment that satisfies S, then S is complete.


    /

    Next we want to prove:

    If S is consistent and S is complete, then there is a unique assigment that satisfies S

    There might be more elegant proofs, but the following is straightforward and routine:

    Proof:

    Let f be the assignment to the atomic formulas by f(P) = 1 iff P is in S. Let f' be the extension of f.

    By induction on formulas K, we show K is in S iff f'(K) = 1.

    The induction is straightforward and routine, even if tedious. (Note that, at least for me, it only works out by proving it as an 'iff').

    And it's trivial to show that f is unique:

    If g, different from f, also satisfies S, then let P be an atomic formula on which f and g disagree. Let g' be the extension of g.

    Suppose f(P) = 0 and g(P) = 1. So P is not in S. Since S is complete, ~P is in S. But g'(~P) = 0. So g does not satisfy S.

    Suppose f(P) = 1 and g(P) = 0. So P is in S. So g does not satisfy S.
    Last edited by MoeBlee; August 18th 2011 at 08:33 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. measure of set satisfying ~CH
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 1st 2011, 09:26 PM
  2. Replies: 3
    Last Post: February 3rd 2010, 04:29 AM
  3. Replies: 1
    Last Post: February 2nd 2010, 09:32 AM
  4. My curiosity needs satisfying
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 25th 2008, 08:21 PM
  5. Satisfying the equation
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: September 12th 2005, 04:37 AM

Search Tags


/mathhelpforum @mathhelpforum