Results 1 to 8 of 8

Math Help - Propositional Logic Proof

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Propositional Logic Proof

    I was wondering if this proof was ok or if (as I suspect) I am wrong and if you could help point me in the right direction.

    thanks for any help

    Suppose that \mathcal{F} is an inconsistent set of sentences. For each G\epsilon\mathcal{F} let \mathcal{F}_G be the set obtained from removing G from \mathcal{F}.

    Prove that for any G\epsilon\mathcal{F} \mathcal{F}_G\vdash\lnot G.


    Proof


    We can split into two cases.

    1. \mathcal{F}_G is still an inconsistent set and so it can prove anything, namely \lnot G


    2. \mathcal{F} is now consistent in which case G was false in the cases that \mathcal{F}_G was satisfied and so \lnot G is true when \mathcal{F}_G is satisfied and so by definition \mathcal{F}_G\models\lnot G and by completness \mathcal{F}_G\vdashz\lnot G
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Propositional Logic Proof

    Your first case is correct. I think you're on the right path with the second case, but I don't believe it is \mathcal{F}_G that is satisfied. We say that \mathcal{F}_G satisfies or models or is a model of the formula on the RHS of the turnstile. Furthermore, satisfiability is a semantic concept, and your proof, as you've written with the single-turnstile, is a proof about provability. I think you should keep to the syntactical proof theory in your proof.

    I would approach the problem from this perspective. Ask yourself, what happens when our set of sentences proves G? (i.e., \mathcal{F}_G \vdash G) Since our assumption is that \mathcal{F}_G is consistent, and it is precisely so because of the removal of G, I think the answer to that question will provide your solution: it eliminates the case of proving G and leaves us with only one other option, i.e., that it proves G. Do you see why?
    Follow Math Help Forum on Facebook and Google+

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

    Re: Propositional Logic Proof

    Quote Originally Posted by hmmmm View Post
    2. \mathcal{F} is now consistent in which case G was false in the cases that \mathcal{F}_G was satisfied and so \lnot G is true when \mathcal{F}_G is satisfied and so by definition \mathcal{F}_G\models\lnot G and by completness \mathcal{F}_G\vdashz\lnot G
    It's pretty hard to understand this sentence. It would help if you break it into several sentences and/or insert punctuation.

    In any case, you can't say that G is false. In which interpretation? This problem is not about semantics at all.

    In fact, \mathcal{F}_G\vdash\neg G just by the deduction theorem if you use Hilbert-style system, or by negation introduction or implication introduction if you use natural deduction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Propositional Logic Proof

    Yeah sorry it is I will try to clarify:

    \mathcal{F}_G is now a consistent set of sentences.

    It must then have been the case that \mathcal{F} was inconsistent because G was false when the rest of the sentences in \mathcal{F} were true ( \mathcal{F}_G)

    So when all the sentences in \mathcal{F}_G are true G is false.

    So when all the sentences in \mathcal{F}_G are true \lnot G is true

    By definition \mathcal{F}_G\models\lnot G

    By the completness of propositional logic \mathcal{F}_G\vdash\lnot G

    Is this any better?

    thanks for the help
    Follow Math Help Forum on Facebook and Google+

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

    Re: Propositional Logic Proof

    Quote Originally Posted by hmmmm View Post
    It must then have been the case that \mathcal{F} was inconsistent because G was false when the rest of the sentences in \mathcal{F} were true ( \mathcal{F}_G)
    First, I would say, "G is false in any interpretation where the rest of the sentences in \mathcal{F} are true." Note that you use soundness theorem here. Indeed, " \mathcal{F} is inconsistent" means that \mathcal{F}\vdash\bot, so \mathcal{F}\models\bot by soundness, i.e., \mathcal{F} is unsatisfiable.

    So when all the sentences in \mathcal{F}_G are true G is false.

    So when all the sentences in \mathcal{F}_G are true \lnot G is true

    By definition \mathcal{F}_G\models\lnot G

    By the completness of propositional logic \mathcal{F}_G\vdash\lnot G
    Yes, this works. In fact, there is no need to consider the case when \mathcal{F}_G is inconsistent; the proof above goes through for that case as well.

    However, I am still saying that doing this problem through soundness and completeness is a huge detour.
    Quote Originally Posted by emakarov
    In fact, \mathcal{F}_G\vdash\neg G just by the deduction theorem if you use Hilbert-style system, or by negation introduction or implication introduction if you use natural deduction.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Propositional Logic Proof

    Thanks very much. Yeah I see that now thanks but having started like this I just wanted to know if this was right.

    thanks for the help
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: Propositional Logic Proof

    Quote Originally Posted by emakarov View Post
    " \mathcal{F} is inconsistent" means that \mathcal{F}\vdash\bot, so \mathcal{F}\models\bot by soundness, i.e., \mathcal{F} is unsatisfiable.
    Just for technical clarification, is it correct to say that \mathcal{F} is unsatisfiable? Don't we say,

    (Definition) A theory is satisfiable if it has a model: \mathcal{M} \models \mathcal{T}

    So a theory is unsatisfiable if it lacks any model (i.e., it is not true under any interpretation). If we're saying \mathcal{F} \models \bot, isn't this saying that F models a contradiction or F satisfies a contradiction?
    Follow Math Help Forum on Facebook and Google+

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

    Re: Propositional Logic Proof

    Quote Originally Posted by bryangoodrich View Post
    If we're saying \mathcal{F} \models \bot, isn't this saying that F models a contradiction or F satisfies a contradiction?
    Yes, but \mathcal{F} \models \bot iff \mathcal{F} has no model.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. propositional logic
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 30th 2011, 10:52 AM
  2. propositional logic equivalence proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 11th 2010, 01:20 AM
  3. Propositional Logic Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 8th 2009, 09:34 AM
  4. Replies: 15
    Last Post: June 3rd 2008, 04:58 PM
  5. propositional logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 10th 2007, 10:50 AM

Search Tags


/mathhelpforum @mathhelpforum