Results 1 to 10 of 10

Math Help - Math Logic Proving Proofs

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    9

    Math Logic Proving Proofs

    Give a proof of
    A ^ (A V B) A.

    I have an additional question. I do not really understand what means, as sometimes I have seen it placed in the middle of proofs and sometimes I see it has no influence to the answer to the question at all.

    A ^ (AVB)
    By Golden Rule
    => A A V B A V A V B
    By Idempotency of V
    => A A V B A V B
    By symmetry of
    => A


    I need a lot of clarification for these steps as they do not make sense to me. I understand the last part of every step, but do not understand the rest of it.
    Last edited by Bungkai; April 4th 2010 at 11:54 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    The symbol \vdash (called "turnstile", maybe because it looks like a turnstile in the subway) separates assumptions from conclusions. For example, A,A\to B\vdash B is a correct statement. In your example, there are no assumptions.

    A ^ (AVB)
    By Golden Rule
    => A A V B A V A V B
    Judging by Axioms for propositional logic E, The Golden Rule is "p /\ q == p == q == p \/ q". We instantiate p = A and q = A V B to get

    (A\land (A\lor B)\equiv A)\equiv ((A\lor B)\equiv (A\lor A\lor B))

    Now, A\land (A\lor B)\equiv A is what we need to show. So, the right-hand side A\lor A is rewritten as A by the idempotency of disjunction. So we get A\lor B\equiv A\lor B, which can be rewritten to \mathsf{true}.

    With all due respect to D. Gries, this formulation of propositional logic seems curious but eccentric; I have not seen any serious logician using it these years.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    9
    Ok, I understand most of what you are saying. Regarding the steps I showed though, you mentioned the right hand side.

    A A V B A V A V B

    The middle and left side I do not know where they came from. Only the right side makes sense to me.

    I would also like to throw another question at you since we're on the topic if you don't mind.

    The weakening rule states A \vdash A V B

    How would a hypothesis B become notA v B

    (Sorry I do not know how to use the mathematical symbols on forums.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    A A V B A V A V B

    The middle and left side I do not know where they came from.
    Take the Golden Rule p\land q\equiv p\equiv q \equiv p\lor q. This is an axiom schema, which means that p and q may be replaced by arbitrary formulas. Also, due to associativity of \equiv, parentheses can be distributed in an arbitrary way.

    So, replace p with A and q with A\lor B. We'll get A\land(A\lor B)\equiv A\equiv A\lor B\equiv A\lor(A\lor B). Also, let's surround with parentheses the first \equiv and the rest of the formula: \Big(A\land(A\lor B)\equiv A\Big)\equiv \Big(A\lor B\equiv A\lor(A\lor B)\Big). The left-hand side is what needs to be proved. The right-hand side can be rewritten to "true" after A\lor(A\lor B) is replaced by (A\lor A)\lor B by associativity of \lor and A\lor A is replaced by A due to idempotency of \lor.

    The weakening rule states A A V B

    How would a hypothesis B become notA v B
    Why do you call B a "hypothesis" when it occurs only to the right of the turnstile and not even by itself? Hypotheses are placed to the left of . Second, is this a question about the same problem or not? In the original problem there was no negation (is notA the negation of A?). I am not sure what the question is asking.

    Sorry I do not know how to use the mathematical symbols on forums.
    Not a problem. You can write \/ for \lor, /\ for \land, -> for \to, and (not A) for \neg A (in parentheses). I prefer leaving a space on each side of a binary connective, like this: A /\ B, rather than A/\B. It is only important to parenthesize formulas correctly.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2010
    Posts
    9
    I am stating B as a situational hypothesis.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I am stating B as a situational hypothesis.
    Sorry, I am not sure what "situational" means.

    The weakening rule states A A V B

    How would a hypothesis B become notA v B
    If you want to clarify the question, could you say if it is related to the original problem "A ^ (A V B) A"? Also, I am not sure what "become" here means. I can write anything on paper; the question is whether this would make sense according to the rules of inference, etc. Could you re-state your question, e.g., "How to derive this from this?" or "Is this a legal formula"?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2010
    Posts
    9
    From the weakening rule, is it possible to derive \neg A \lor B using B instead of A as the hypothesis?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Bungkai View Post
    From the weakening rule, is it possible to derive \neg A \lor B using B instead of A as the hypothesis?
    You stated the weakening rule as:

    A |- A v B

    whre 'A', and 'B' are variables ranging over formulas, right?

    So here are instances of the rule:

    ~A |- ~A v B

    B |- B v A

    B |- B v ~A

    Etc.

    That is, the rule is: Given a formula A (of any complexity at all) you can infer the formula A v B (where B is any formula of any complextity at all).

    Now, you asked, "How would a hypothesis B become ~A v B ?"

    In the manner you stated the rule, that wouldn't work, since the hypothesis must be the FIRST conjunct (as you've stated the rule). But, of course, we ordinarily also have commutativity of disjunction so:

    B |- B v ~A (by weakening)
    B v ~A |- ~A v B (by commutativity of disjunction)
    So B |- ~A v B.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    In the manner you stated the rule, that wouldn't work, since the hypothesis must be the FIRST disjunct
    I usually work with system with two disjunction introduction rules: left and right.

    How would a hypothesis B become ~A v B ?
    This is the wording that confused me. If one derives A\vdash B, one may think that A becomes B. However, this is not only extremely personal and informal interpretation, but not even a very accurate one. After all, the hypothesis A did not disappear after B was derived from it; one can still use it to derive further consequences of B.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by emakarov View Post
    I usually work with system with two disjunction introduction rules: left and right.
    Indeed, but I was only responding to the rule as he literally gave it. And then I mentioned that commutativity would do the rest of the job (as would, as you mentioned, the disjunction introduction rule being both left and right).

    Quote Originally Posted by emakarov View Post
    If one derives A\vdash B, one may think that A becomes B. However, this is not only extremely personal and informal interpretation
    Yes, I was not dissuaded by his rather informal descriptions. I took it for granted that it is understand that one thing doesn't "become" another, but rather that one formula allows the derivation of another, etc.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Logic proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 21st 2011, 04:39 PM
  2. Logic Proofs
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: February 11th 2011, 01:42 AM
  3. Logic Proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 21st 2008, 09:02 AM
  4. predicate logic proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 7th 2008, 12:18 AM
  5. Logic & Propositions & Proofs
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 9th 2008, 09:45 AM

Search Tags


/mathhelpforum @mathhelpforum