Understanding and using Strengthening/Weakening theorems

logicpropositional-calculus

In A Logical Approach to Discrete Math by Gries p.58, appears this passage.

Each of the theorems (3.76a)-(3.76e) is called weakening or strengthening , depending on whether it is used to transform the antecedent into the consequent, thus weakening it, or to transform the consequent into the antecedent, thus strengthening it.

I have two questions:

  • What the significance of weakening and strengthening in this context?
  • I know how to use theorems that have equals replacing “equals by equals” with Leibniz rule of Inference. But, how can I use theorems that have an implication? Do I need to use modus ponens or use an implication in my reasoning?

Best Answer

See footnote 10 (page 58) :

Suppose $P \to Q$. We say that $P$ is stronger than $Q$ because $Q$ is true in more (or at least the same) states that $P$.

This means (see the truth table for $P \to Q$) that when $P$ is TRUE, also $Q$ must be.

Here "stronger" in the sense that it "exclude more possibilities" : "the strongest formula is false".

The theorems of (3.76) are obtained from $p \to p$ either by replacing a "weaker" formula into the consequent : $p \vDash (p \lor q)$, and this is weakening, or by replacing a "stronger" formula in the antecedent : $(p \land q) \vDash p$, and this is strengthening.

And from them we get $(p \land q) \to (p \lor q)$ from the first one by strengthening or from the second one by weakening.

The fact that $p \vDash p \lor q$ must be checked with truth-table.

But the issue is : how to prove $p \to (p \lor q)$ with Gries' proof system ?

We can use the hint of Ex.60, page 65 and follow the strategy explained in the proof of the theorems of Ch.3.

Note that the law we want to prove is not an equivalence; in Gries' system, to prove that a formula $\varphi$ is theorem (i.e. a tautology) amounts to prove : $\varphi \equiv \top$ [using $\top$ for $\text {true}$].

We start with (3.43b) Absorption [page 52]: it is a theorem; thus it is equivalent to $\top$ :

$p \land (p \lor q) \equiv p$.

Then we use (3.60) Definition of implication [page 56] : $(p \to q) \equiv ((p \land q) \equiv p)$.

Replacing $q$ with $p \lor q$ in it we get, by Substitution rule [page 41] : $p \to (p \lor q) \equiv (p \land (p \lor q)) \equiv p$.

Thus, by transitivity of $\equiv$ :

$\top \equiv p \to (p \lor q)$.

Related Question