Equivalences (Replacement Rules)

This is a work-in-progress. I will be updating this often!

It’s my sincere hope that my website will be useful to you. Logic is a wonderful “science” to learn and, of course, to practice and apply.

Please take a look at my tutorial. It will give you the tools to master logic.
If you profit from it or enjoy it, please consider supporting my work.

— George Wick

Introduction – Rules of Replacement are Economical in Proofs
Introduction – Rules of Replacement versus Rules of Inference

Basic Rules of Replacement in Propositional Logic
with 10 Examples of Using Replacement Rules in Proofs
– Double Negation (DN)
– Commutative Rule (COM)
– Association Rule (ASSOC)
– Distribution Rule (DIS)
– De Morgan’s Rule (DeM)
– Contraposition (CONTRA)
– Implication (IMP)
– Exportation (EXP)
– Biconditional Rule (BI)
– Tautology (TAUT)

Additional Logical Equivalences

Introduction – Rules of Replacement are Economical in Proofs

Writing proofs in propositional logic becomes a lot easier when we incorporate the Rules of Replacement. One proposition can be “replaced” with another proposition in a proof if and only if the two propositions are logically equivalent to each other.

Let’s recall that two propositions are logically equivalent when for every combination of truth value inputs their truth value outputs are identical.

Consider the simple example of P&Q versus Q&P. Clearly, they are logically equivalent! They have the same exact truth values. Ergo, P&Q ≡ Q&P.

When two propositions are logically equivalent we will use the ≡ symbol.

Believe it or not, we can basically do without replacement rules. They are not strictly necessary, as we can derive these rules with the standard rules of inference, conditional proofs, and indirect proofs. Consider that E. J. Lemmon’s classic Beginning Logic doesn’t immediately use them!*

For example, if the simplification rule of inference allows us to derive P or Q from P&Q, then we can make the argument P&Q ⊢Q&P as follows.
(1) P&Q Premise
(2) P SIM 1
(3) Q Sim 1
(4) Q&P CON 3, 2

We can then prove it the other way around, i.e., Q&P ⊢P&Q.

Making that argument is rather tedious, especially if it’s within the context of a complicated proof. Consider the next example with P&Q→R, Q&P ⊢ R.
(1) P&Q→R Premise
(2) Q&P Premise
(3) Q SIM 2
(4) P SIM 2
(5) P&Q CON 4, 3
(6) R MP 1, 5

It would be more economical to “replace” Q&P with Q&P!

*[E. J. Lemmon does use double negation (DN), for example, but he treats it as if it were a rule of inference.]
[However, DN can be derived as a theorem.]
[Lemmon uses replacement rules within the context of his overview of theorems in chapter two.]

Introduction – Rules of Replacement versus Rules of Inference

If Φ and ψ are logically equivalent propositions, then we can “replace” one with the other. What’s more, this means that from Φ we can derive ψ, and that we can go the other way, namely, from ψ we can derive Φ. Consider that from P&Q we can derive Q&P, and from Q&P we can derive P&Q. We can go “both ways.” P&Q ≡ Q&P is the rule of commutativity.

A strict rule of inference is not like this! We cannot go “both ways.” Consider the inference modus ponens. It’s only from the two premises P→Q and P that we can derive Q. It’s impossible to derive P→Q and P from Q.

Basic Rules of Replacement in Propositional Logic

Double negation (DN) is a rule that expresses the truth that P and ~~P are logically equivalent. Two negatives, so to speak, cancel out each other. So, P≡~~P.

“I will not not go to work” is the same as “I will go to work.” “It is not the case that it is not hot outside” is the same as “It is the case that it is hot outside.”

Example 1. . . Proof with DN Application

In order to apply the modus tollens rule of inference, we need to have a line that explicitly denies ~Q. Double negation allows us to do this.

Line 4 uses double negation on line two. Line 5 gives us ~P with modus tollens with lines 1 and 4.

Note that we could “prove” the double negation replacement rule — or any other replacement rule — with truth tables.

The commutative rule (COM) deals with conjunctions and disjunctions. Since the order doesn’t matter, P&Q ≡ Q&P and PvQ ≡ QvP.

Analogously, since 4+5 = 5+4 and 2*3=3*2, addition and multiplication with real numbers is commutative.

Example 2 . . . Proof with COM Application

Given the premises PvQ→R and QvP, we can get the conclusion R. The antecedent to the conditional PvQ→R is PvQ, it’s not QvP. So, we need to work on premise two with the commutative rule.

Here we have the Associative Rule (ASSOC). We can move around the parentheses in a proposition with only conjunctions or only disjunctions.

Though we have moved around those parentheses, they meaning behind these propositions hasn’t ultimately changed. Analogously, 5+(2+3) = (5+2)+3 and 7*(5*6) = (7*5)*6. So, we have P&(Q&R) ≡ (P&Q)&R and Pv(QvR) ≡ (PvQ)vR.

Example 3 . . . Proof with ASSOC
In order to deny R, we must regroup things. Isolate R by association to get (PvQ)vR. Since the disjunctive syllogism has been setup to only allow us to move from Φvψ to ψ by denying Φ (i.e., the first disjunct), we need to resort to the commutative rule to finally apply the disjunctive syllogism inference.

(Note we could have setup the disjunctive syllogism to also allow us to move from Φvψ to Φ by denying ψ. Then we wouldn’t need to resort to the commutative rule in Example 3. When working on problems from a textbook, consult the rules it provides.)

The Distribution (DIS) rule allows us to “distribute.”

With P&(QvR) we can “distribute” the P in conjunctive relations with the Q and R to get (P&Q)v(P&R). Also, with Pv(Q&R) we can “distribute” the P in disjunctive relations with Q and R to get (PvQ)&(PvR). “Today is Saturday, and either it is raining or sunny” is logically equivalent to “Today is Sunday and it is raining, or today is Sunday and it is sunny.”

Analogously with multiplication and addition, 9*(7+4) = (9*7)+(9*4).

Example 4 . . . Proof with DIS application

This proof required the use of distribution twice. In order to use the constructive dilemma inference, we had to get P&Q and P&R in a disjunctive relation. That’s possible when “replacing” line 2 to get the logically equivalent line 4. Since (P&Q)v(P&R) tells us at least one of those options is true, we can affirm a consequent from line 1 or 3 via the constructive dilemma. Finally, we use distribution again to get line 6.

It may be helpful to think about factoring in algebra. Consider the algebraic expression, for instance, x+xy. We can “factor” x out of that to get x(1+y). Similarly, from (R&S)v(R&T) we can “factor” R’s conjunctive relations out to get R&(SvT).

De Morgan’s Rule (DeM) expresses the truth that the denial of a conjunction leads to a disjunction with negative disjuncts and that the denial of a disjunction leads to a conjunction with negative conjuncts.

~Pv~R ≡ ~(P&Q) and ~P&~Q ≡ ~(PvR).

“It is not the case that it is either hot or cold” is logically equivalent to “It is not hot and it is not cold.” Sometimes students falsely think ~(PvQ) is the same as ~Pv~Q. They “distribute” the negation, but don’t turn the disjunction into a conjunction. Likely, they are “blindly” moving around symbols. We need to understand what these propositions are saying!

Example 5 . . . Proof with DeM
De Morgan was twice required in this proof. We derived ~(R&S) from ~Pv~S. Then we resorted to modus tollens. Line 5 used De Morgan again. To get our final conclusion ~Q, we beforehand used the commutative rule (because, as our defined rules have it, we can only use simplification on the first conjunct).

Contraposition (CONTRA) is another important rule of replacement. Probably the best way to “prove” it is through an indirect proof.

Regardless, P→Q ≡ ~Q→~P. We can “flip” the antecedent and consequent of a conditional as long as we negate both the antecedent and consequent. “If it is raining, then it is cloudy” is logically equivalent to “If it is not cloudy, then it is not raining.”

This makes sense when taking into account the distinction between sufficient conditions and necessary conditions. Because the consequent is necessary for the antecedent, this implies that when the consequent is not the case the antecedent cannot be the case.

Example 6 . . . Proof with CONTRA

This is a pretty good proof! It utilizes a lot of rules of inferences and rules of replacement. (Try it on your own.) It starts out simple enough with modus ponens. Contraposition had to be used twice to make this proof work. By “contraposing” both S→R and T→Q, we then were able to use the constructive dilemma inference with lines 10, 9, and 5. From there, we had to think ahead about how we could apply modus tollens. To do that, we had to resort to the commutative rule and De Morgran’s rule.

Implication (IMP) shows a useful logical equivalence because it allows us to easily turn a conditional into a disjunction or vice versa.

P→Q ≡ ~PvQ. A rough way to think of this is to consider the options. P can be true or false. If it true, Q follows. Conversely, P can be false.

Although propositional logic’s interpretation of the conditional proposition doesn’t precisely line up with its standard use in ordinary conversation, it’s not a stretch to apprehend how “if it is raining, then it is cloudy” could be said to be logically equivalent to “it’s not raining or it’s cloudy.”

Example 7 . . . Proof with IMP

This proof requires some ingenuity. Contraposition is used on line 4. Notice that to use implication on line 8, we first need to go from RvP to ~~RvP by double negation. Once we get ~R→P, we use the hypothetical syllogism inference twice to arrive at the desired conclusion.

By the way, it’s best to get out a pencil and paper. When you’re learning this the first time, it’s not enough to read a proof; instead, you need to write it out and think through the steps yourself.

Exportation (EXP) is another logical equivalence dealing with conditionals.

Like any of these equivalences, we could “prove” this through a truth table. It’s a fine method and exercise. Nonetheless, when thinking about exportation, it does make a lot of “intuitive” sense. P&Q→R must be ≡ to P→(Q→R). Insofar as P&Q is the case, R will be the case. Likewise, insofar as P is the case and then Q is the case, R will be the case.

Example 8 . . . Proof with EXP

Note: it’s perfectly OK to apply a rule of replacement within a given proposition.

That’s why line 4 has a legitimate derivation. We went from P&Q→R to Q&P→R with the commutative rule.

That, so to speak, set the stage for our next move with exportation to get Q→(P→R). From there, we applied modus ponens to get P→R. Contraposition was then applied to set the stage for a later hypothetical syllogism. Implication was also used to set that stage.

The biconditional P↔Q has it that P is sufficient and necessary for Q and Q is sufficient and necessary for P.

By definition, therefore, P↔Q ≡ (P→Q)&(Q→P).

Example 9. . . Proof with BI

This is a tricky proof.

The tricky moves include the use of the addition rule of inference.

This was to set the stage for the implication rule of inference.

Line 10 uses addition to then get ready for implication.

Line 13 uses addition to then get ready for implication.

Applying the biconditional rule at the end is the easy part.

en.wikipedia.org/wiki/Pizza_in_the_United_States

The tautology (TAUT) rule expresses the obvious truth that P&P and PvP are both logically equivalent to P.

“I will either eat pizza tonight or eat pizza tonight!”

Example 10 . . . Proof with TAUT

This final example will be simple. Using the tautology rule often will go with using the implication rule.

From a theoretical point of view, the proof is interesting. What does it even mean to claim P→~P? We cannot do a modus ponens without getting a contradiction of P&~P. Therefore, it cannot be the case that P is the case.

In other possible examples, a tautology might pop up when using the constructive dilemma inference, etc. So it does come up from time to time!

Additional Logical Equivalences

There are an endless number of other logical equivalences out there. What is above typically appears in the common introductory logic textbook. Remember, we can prove two propositions are logically equivalent by a truth table or through some sort of proof.

Example . . . Is P&Q logically equivalent to ~(P→~Q)?

Yes, they are logically equivalent!
We derived ~(P→~Q) from P&Q and derived P&Q from ~(P→~Q).

Other logical equivalences involving conditionals include:
~(P→Q) ≡ P&~Q
(P→Q)&(P→R) ≡ P→Q&R
(P→R)v(Q→R) ≡ P&Q→R
(P→R)&(Q→R) ≡ PvQ→R
(P→Q)v(P→R) ≡ P→QvR

Other logical equivalences involving biconditionals include:
P↔Q ≡ ~P↔~Q
~(P↔Q) ≡ P↔~Q
P↔Q ≡ (P&Q)v(~P&~Q)