# The use of weakening

• Oct 4th 2011, 10:19 AM
Lepzed
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 (Nod)
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 :)
• Oct 4th 2011, 12:47 PM
emakarov
Re: The use of weakening
There is no need to worry, there are no ambiguities in the formal language (Smile)

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\$.
• Oct 5th 2011, 02:39 AM
Lepzed
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 (Worried)

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?

• Oct 5th 2011, 03:14 AM
emakarov
Re: The use of weakening
Quote:

Originally Posted by Lepzed
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.
• Oct 5th 2011, 03:34 AM
Lepzed
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 :)