Results 1 to 10 of 10

Math Help - [LOGIC] Consequence of A and not A

  1. #1
    Junior Member
    Joined
    Sep 2011
    Posts
    30

    [LOGIC] Consequence of A and not A

    Hello,

    it always seemed clear to me that we can not conclude lets say B from A, and also conclude B from ~A. Lets assume that i have a set of sentences S that are logically valid. Over that set of sentences i introduce a sentence A and i get a contradiction, so i say that ~A must be true (reductio ad absurdium). So if ~B was always a fact in S, how can i prove that i can not obtain B from both A and ~A? I know that ~A is the negation of A, but how can i prove that there cant exist a single thing that is true in A and also true in the presence of ~A?

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: [LOGIC] Consequence of A and not A

    It is recommended to post logic questions in the Discrete Math subforum.

    Quote Originally Posted by DarkFalz View Post
    it always seemed clear to me that we can not conclude lets say B from A, and also conclude B from ~A.
    [(A -> B) /\ (~A -> B)] <-> B is a tautology, so we can conclude B from A and conclude B from ~A iff we actually don't need any assumptions and can conclude B outright.

    Quote Originally Posted by DarkFalz View Post
    Lets assume that i have a set of sentences S that are logically valid. Over that set of sentences i introduce a sentence A and i get a contradiction, so i say that ~A must be true (reductio ad absurdium). So if ~B was always a fact in S, how can i prove that i can not obtain B from both A and ~A?
    You can conclude B from A because A together with ~A, which is true, gives a contradiction, which implies everything. You can't conclude B from ~A because, since ~A is true, B would also be true and S would not be valid (since it contains ~B).

    Quote Originally Posted by DarkFalz View Post
    I know that ~A is the negation of A, but how can i prove that there cant exist a single thing that is true in A and also true in the presence of ~A?
    I am not sure I understand the question. What does "true in A" mean?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: [LOGIC] Consequence of A and not A

    if A is true, and B is true, then BOTH A→B AND ~A→B are true.

    if A is true, and B is false, then only ~A→~B is true.

    in other words, from a false premise, you can always derive anything.

    what CANNOT happen, is that both A→B AND A→~B are true.

    let's look at reductio ad absurdium a bit more closely:

    B is known to be true.
    if A, then ~B, is also known to be true (by a valid chain of reasoning).

    since A→B is ALWAYS true (even if A is false), we have:

    (A→B)&(A→~B)

    so if A is true, we have:

    B&~B, a contradiction.

    since our only assumption is on A (we already knew B to be true), we conclude A is false. this keep us from being able to invoke modus ponens to reach the contradiction. now, look at our "components":

    A→B true, since A is false.
    A→~B, also true, since A is false.
    (A→B)&(A→~B), also true, being the conjunction of two true statements.
    B&~B...not derivable, since we cannot "detach" A.

    the whole point is to "contradict the B's", not the "A's".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: [LOGIC] Consequence of A and not A

    Quote Originally Posted by Deveno View Post
    if A is true, and B is true, then BOTH A→B AND ~A→B are true.

    if A is true, and B is false, then only ~A→~B is true.
    What do you mean by "only"? ~A -> B is also true, as well as ~A -> A /\ B and infinitely many other formulas.

    Quote Originally Posted by Deveno View Post
    what CANNOT happen, is that both A→B AND A→~B are true.
    If A is true.

    Quote Originally Posted by Deveno View Post
    B is known to be true.
    Which B? In the original post, ~B ∈ S, which is a set of true formulas, so B is false.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2011
    Posts
    30

    Re: [LOGIC] Consequence of A and not A

    I think that i probably complicated the topic. My question might seem stupid, but all i want is to know why it is impossible for both A to make us arrive to a conclusion B, and ~A to make us arrive at the same conclusion B. How can i prove this?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: [LOGIC] Consequence of A and not A

    Quote Originally Posted by DarkFalz View Post
    why it is impossible for both A to make us arrive to a conclusion B, and ~A to make us arrive at the same conclusion B. How can i prove this?
    Quote Originally Posted by emakarov View Post
    [(A -> B) /\ (~A -> B)] <-> B is a tautology, so we can conclude B from A and conclude B from ~A iff we actually don't need any assumptions and can conclude B outright.
    .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2011
    Posts
    30

    Re: [LOGIC] Consequence of A and not A

    Oh, i get it. Thats a way to prove, although i was kind thinking about something related to the boolean operators, like if A is a complicated formula with lots of conjunctions and disjunctions, why applying the negation operator and fliping the ANDs to ORs and negating the atoms prevents the conclusion from being reached in the set S.

    I would for instance imagine S as a set in CNF (Clausal Normal Form) and if A had a clause (A or B) and S contained (~A or B) /\ ~B and the resolution of (A or B) with (~A or B) derived B and contradicted, i can indeed see that ~( A or B) = ~A & ~B in fact disabled the possibility to produce B since the A from the clause (A or B) could no longer be eliminated to produce B. The thing is, this example seems clear... but i start to wonder about bigger formulas and how the overall mechanism would be... Is it supposed to be crystal clear that A cannot say a single thing that ~A also says?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: [LOGIC] Consequence of A and not A

    Sorry, I don't understand this.

    Quote Originally Posted by DarkFalz View Post
    I would for instance imagine S as a set in CNF (Clausal Normal Form) and if A had a clause (A or B)
    CNF usually stands for Conjunctive Normal Form. Is A an element of S? Perhaps the clause of A should be denoted (A' or B) to avoid variable name clash?

    Quote Originally Posted by DarkFalz View Post
    and S contained (~A or B) /\ ~B and the resolution of (A or B) with (~A or B) derived B and contradicted, i can indeed see that ~( A or B) = ~A & ~B in fact disabled the possibility to produce B since the A from the clause (A or B) could no longer be eliminated to produce B.
    Is ~A & ~B also an element of S? In what sense it "disabled" the possibility to produce B? I thought that during resolution, formulas are not destroyed but left in the set. What does it all have to do with impossibility of deducing B from A and from ~A?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2011
    Posts
    30

    Re: [LOGIC] Consequence of A and not A

    I was referring to the Clausal Formal (conjuntion of clauses (which in turn are composed by disjunctions only)). What i meant is, lets say that when A & B is inserted into S, it causes a contradiction, so we conclude ~A or ~B, why is it that ~A or ~B prevents a contradiction from being reached? Is it because if we were previously asserting A and B, now we are like saying "oh no no, i was wrong, so either A is wrong, or B is wrong or both, but i am no longer asserting any of them"?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: [LOGIC] Consequence of A and not A

    So, if S, A ⊢ ⊥ (⊢ means "derive" and ⊥ means "contradiction"), then S ⊢ ČA. It seems that you are asking why it is not the case that S, ČA ⊢ ⊥. An easy answer is, "Why would it be the case?" We derived a certain formula ⊥ from S and A. Then we removed A, so it is not surprising that S alone does not derive ⊥. Even if we added some other formula ČA, it is not guaranteed that ⊥ becomes derivable again.

    A better answer is that S, A ⊢ ⊥ and S, ČA ⊢ ⊥ if and only if S ⊢ ⊥. (So it is possible that S, A ⊢ ⊥ and S, ČA ⊢ ⊥, but only if S itself is inconsistent.) This is because S, A ⊢ ⊥ iff S ⊢ A → ⊥; S, ČA ⊢ ⊥ iff S ⊢ ČA → ⊥, and (A → ⊥) ∧ (ČA → ⊥) ↔ ⊥ is derivable (this is a special case of the tautology from post #2).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Not logical consequence (First-order logic)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 18th 2010, 07:07 AM
  2. Consequence of the closed graph theorem
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 2nd 2009, 07:33 AM
  3. Consequence relation
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 22nd 2009, 01:34 PM
  4. Cauchy Mean Value Theorem Consequence problem
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 25th 2008, 01:14 PM
  5. consequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 12th 2005, 05:22 PM

Search Tags


/mathhelpforum @mathhelpforum