Results 1 to 5 of 5

Math Help - The use of weakening

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    The use of weakening

    I'm a bit confused by the use of /\ and \/ weakening, I've the following exercise.
    Show that (P \implies Q) \implies \lnot P \models \lnot P \lor \lnot Q
    Now I can go about the lefthand part as follows:
    (P \implies Q) \implies \lnot P \;=\;\{\; by\; implication,\; twice\; \} \\ \lnot(\lnot P \lor Q) \lor \lnot P  \;=\;\{\; by\; demorgan\;  \} \\ (\lnot\lnot P \land \lnot Q) \lor \lnot P  \;=\;\{\; by\; double \;negation,\;  \} \\  (P \land \lnot Q) \lor \lnot P  \;=\;\{\; by\; distribution,\;  \}\\ (\lnot P \lor \lnot Q) \land (\lnot P \lor P)  \;=\;\{\; by\; excluded \;middle\; \} \\ (\lnot P \lor \lnot Q) \land True  \;=\;\{\; by\; true/false\;elimination,\;  \} \\ \lnot P \lor \lnot Q \;\ \models \lnot P \lor \lnot Q
    Seems fair enough, but where I distributed the \lnot P over P and \lnot Q, I could've applied \land-weakening, which would've given a totally different outcome:
     (P \land \lnot Q) \lor \lnot P  \;=\;\{\; by\; \land weakening,\;  \} \\  (P  \lor \lnot P)  \;=\;\{\; by\; excluded \;middle,\;  \} \\ True \models \lnot P \land \lnot Q

    which is a false statement.

    This all seems a bit ambiguous to me, and I was under the impression we used a formal language in the hopes of getting rid of just that
    Any tips on the subject? Are there more rules I should adhere to? Do I have to prioritize distribution over \land weakening for example?
    When is using weakening more appropriate? Some (links to) good examples would be excellent
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: The use of weakening

    There is no need to worry, there are no ambiguities in the formal language

    If we start with a formula that (as we know from the first derivation) is equivalent to \neg P\lor\neg Q and start rewriting it while preserving equivalence, then obviously all resulting formulas will be equivalent to \neg P\lor\neg Q. If, however, at some point we rewrite some A, which is equivalent to \neg P\lor\neg Q, to B such that A\models B but B\not\models A, then \neg P\lor\neg Q\models B, but B\not\models\neg P\lor\neg Q. In your case, you weakened (P\land\neg Q)\lor\neg P to True.

    This is the same as when we want to prove (x+y)^2+(x-y)^2=2(x^2+y^2). If we rewrite the left-hand side exactly, then we can make it equal to the right-hand side, but if we drop (x-y)^2, we can only prove (x+y)^2\le2(x^2+y^2) and not the other way around.

    In fact, dropping a conjunct is appropriate only when the conjunction is the topmost connective and when you prove implication, not equivalence. Otherwise, sometimes you get a weaker formula (e.g., P\land Q\models P) and sometimes a stronger one (e.g., P\Longrightarrow R\models (P\land Q)\Longrightarrow R). This is similar to how a+b\ge a but c-(a+b)\le c-a when b\ge0.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    Re: The use of weakening

    I'm not sure I quite understand quite right yet. Might be open doors, but I think I need my thoughts validated

    Since \lnot P \lor \lnot Q \models \lnot P \lor \lnot Q means the left-hand side is stronger (or in this case as strong as and thus equivalent) than the right-hand side.
    Thus the left-hand side implies the right-hand side: whenever the left-hand side is true, the right-hand side is true, but vice versa is not necessary the case (except in examples like this when there is actually a logical equivalence between the left- and right-hand side).
    If I were to write a \implies in stead of the \models, the truth tables would lead me to the conclusion this is always a tautology. Right?

    Now when I apply weakening I've just to be cautious?
    Say I have P \land Q \models P, weakening would allow me to rewrite this to P \models P, but according to the standard weakening rules I'm (in theory anyway) able to rewrite P \models P to P \lor Q \models P, but that would give me a false proposition, since P \lor Q \not\models P. So don't isn't allowed in practice. I could however weaken the right-hand, making it legal again?
    I've just to be cautious about where I apply weakening and check if the left-hand side still is stronger than/implies the right-hand side?

    Is this about right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: The use of weakening

    Quote Originally Posted by Lepzed View Post
    Since \lnot P \lor \lnot Q \models \lnot P \lor \lnot Q means the left-hand side is stronger (or in this case as strong as and thus equivalent) than the right-hand side.
    Thus the left-hand side implies the right-hand side: whenever the left-hand side is true, the right-hand side is true, but vice versa is not necessary the case (except in examples like this when there is actually a logical equivalence between the left- and right-hand side).
    If I were to write a \implies in stead of the \models, the truth tables would lead me to the conclusion this is always a tautology. Right?
    That's correct.

    First, you need to be careful about the direction of informal implications. When you have a chain of statements of the form P\models Q, it is important to understand whether the previous statement implies the next one or vice versa. For example, when in the first post you were trying to prove (P \implies Q) \implies \lnot P \models \lnot P \lor \lnot Q, you ended up with a true statement \lnot P \lor \lnot Q \;\ \models \lnot P \lor \lnot Q, and each subsequent statement implied the previous one (in fact, was equivalent to the previous one because the formulas to the left of \models were equivalent). If you weaken P to some P' and go from P ⊨ Q to P' ⊨ Q, the latter statement implies the former, but not vice versa. So, you could very well end up with a false statement (which implies everything). This is like going from 0 * x = 0 * y to x = y: the latter equality implies the former and not the other way around because that would require division by zero. This way, you can end up with a false statement starting with a true one.

    When you want to prove P ⊨ Q, you need to write a chain of stronger and stronger statements that will end up with a true statements. Conversely, you can start with a true statement and write weaker and weaker statements until you come to P ⊨ Q. So, to prove P ⊨ R, it is sufficient to prove P ∨ Q ⊨ R. However, if in going from P ⊨ R to P ∨ Q ⊨ R you get to a dead end, it is not a contradiction; it's just a wrong way to prove the original statement.

    The rule is the following. If you have P ⊨ Q and you strengthen P or weaken Q, you weaken the whole statement (this is appropriate when you start with P ⊨ Q to prove something else). Conversely, if you weaken P or strengthen Q, you strengthen the whole statement (this is appropriate when you need to prove P ⊨ Q and you rewrite it to something true). Note that P ⊨ Q in this sense behaves like Q - P in arithmetic: increasing Q or decreasing P increases (strengthens) the whole expression.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2011
    Posts
    53

    Re: The use of weakening

    I think I understand a bit better now, thank you. Do you have access to or know of some worked examples? Or exercises with answers, so I can practice and check my work
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum