Understanding and using Strengthening/Weakening theorems

Question

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?

Answer 1

What the significance of weakening and strengthening in this context?

By weakening and strengthening we change the amount of possible outcomes for some proposition. By weakening a proposition we include in general more possibilities for the outcome. By strengthening a proposition we exclude in general more possibilities. We can use the strength or weakness of a proposition to express it's relative strength to another proposition (stronger or weaker).

Suppose we have two propositions $P$ and $Q$. Then if we would say $P$ is stronger than $Q$ it would mean that: in every case $P$ is true, $Q$ is also true.

This can be written as: $P \vDash Q$

Note that in case $P$ and $Q$ are equivalent it means that the "stronger than" works in both directions. So $P \vDash Q$ and $Q \vDash P$.

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?

Edit: I am trying to say, how can I invoke those theorems in a proof ? Suppose I want to "strength" a certain proposition; how can I introduce theorem 3.76 (a)

We can use the properties of the "stronger than" to derive logical connectives between propositions.

1. $P \vDash Q$ and $Q \vDash P$ means that the truth tables are exact the same. Thus we can conclude that $P$ and $Q$ are therefore equivalent.

2. If we only have $P \vDash Q$, then $P \implies Q$ must be a tautology.

3. We can conclude that "stronger" and "weaker" are opposites.

Strengthening is done by decreasing the possible "1" for a proposition. The more it tends to $FALSE$ the stronger it is, with $FALSE$ being the most extreme strongest and $TRUE$ being the weakest.

Note that 3.76(A) as a whole is a tautology since $P \vDash P \lor Q $.

Using the $\lor$ connective that part of a proposition weaker since it creates more possibilities that the truth value will be true. Hence , using the $\land$ will make that part of the proposition stronger since we have less different possibilities that the truth value will be true. This is what you can see in the theorems in (3.76)

In (a) the right part of the implication is weakened by the $\lor$

In (b) the left part of the implication is made stronger by the $\land$

In (c) the left part of the implication is made stronger by the $\land$ and the right part weaker by the $\lor$

In (d) and (e) the connectives $\land$ $\lor$ in each part create more strength or weakness.

In the end it just comes down to the truth tables and that the stronger proposition indicates that the weaker proposition must always have a 1 or true in the truth table whenever the stronger proposition has a true or 1

Answer 2

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)$.