The use of weakening

Printable View

October 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 $(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 (Nod)
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 :)
October 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 $\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$ .
October 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 $\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?
October 5th 2011, 03:14 AM
emakarov

Re: The use of weakening

Quote:

Originally Posted by Lepzed

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.
October 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 :)