Results 1 to 5 of 5

Thread: 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 $\displaystyle (P \implies Q) \implies \lnot P \models \lnot P \lor \lnot Q$
    Now I can go about the lefthand part as follows:
    $\displaystyle (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 $\displaystyle \lnot P$ over $\displaystyle P$ and $\displaystyle \lnot Q$, I could've applied $\displaystyle \land$-weakening, which would've given a totally different outcome:
    $\displaystyle (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 $\displaystyle \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,577
    Thanks
    790

    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 $\displaystyle \neg P\lor\neg Q$ and start rewriting it while preserving equivalence, then obviously all resulting formulas will be equivalent to $\displaystyle \neg P\lor\neg Q$. If, however, at some point we rewrite some A, which is equivalent to $\displaystyle \neg P\lor\neg Q$, to B such that $\displaystyle A\models B$ but $\displaystyle B\not\models A$, then $\displaystyle \neg P\lor\neg Q\models B$, but $\displaystyle B\not\models\neg P\lor\neg Q$. In your case, you weakened $\displaystyle (P\land\neg Q)\lor\neg P$ to True.

    This is the same as when we want to prove $\displaystyle (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 $\displaystyle (x-y)^2$, we can only prove $\displaystyle (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., $\displaystyle P\land Q\models P$) and sometimes a stronger one (e.g., $\displaystyle P\Longrightarrow R\models (P\land Q)\Longrightarrow R$). This is similar to how $\displaystyle a+b\ge a$ but $\displaystyle c-(a+b)\le c-a$ when $\displaystyle 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 $\displaystyle \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 $\displaystyle \implies$ in stead of the $\displaystyle \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 $\displaystyle P \land Q \models P$, weakening would allow me to rewrite this to $\displaystyle P \models P$, but according to the standard weakening rules I'm (in theory anyway) able to rewrite $\displaystyle P \models P$ to $\displaystyle P \lor Q \models P$, but that would give me a false proposition, since $\displaystyle 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,577
    Thanks
    790

    Re: The use of weakening

    Quote Originally Posted by Lepzed View Post
    Since $\displaystyle \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 $\displaystyle \implies$ in stead of the $\displaystyle \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 $\displaystyle 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 $\displaystyle (P \implies Q) \implies \lnot P \models \lnot P \lor \lnot Q$, you ended up with a true statement $\displaystyle \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 $\displaystyle \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