Proof method 2: replacement rules
* Note: this part of the tutorial uses embedded LaTex scripts which sometimes don’t render. If you encounter weird code in the rules section, just refresh the page and the scripts should load properly
Introduction
By now we have 8 inference rules under our belt. Now we’re going to learn 10 more rules. These are referred to as replacement rules. [If I haven’t edited this tutorial:] You may have noticed that I have previously referred to these as association rules. This is wrong. soz :(. Anyways, the function of the replacement rules differs from that of the inference rules in that they don’t rely on referencing multiple propositions to generate a new one. Rather, as the name would have you believe, they function as replacements for individual propositions you already have. Let’s say you have some proposition. Think of this as a word in a dictionary. You go to look up the word in the dictionary and you see a synonym to that word. In this analogy, the synonym is the replacement rule.
So basically, replacement rules range over specific forms of propositions. If you have some instance of the form x, and there is a replacement rule for it, then the replacement rule says that you can write x in another way y while preserving the truth function of the original form. This will prove to be very useful in the proof method. For instance, some replacement rules state that you can rewrite some complex proposition using different operators. This is great because it would allow us to potentially use inference rules we previously could not. So it will provide a method to avoid reaching (some) dead ends that we would derive if we only had the inference rules.
These rules are symmetric, meaning that the replacement goes both ways: form x can be replaced with y and vice versa. This is a key difference between the replacement rules and inference rules. Some inference rules will be intuitive and easy to understand. Others may be a bit weirder. But in my experience, the replacement rules are easier to learn and remember than the inference rules. And, if you’re still not entirely clear on the inference rules (shame on you), then you will see these in action again. As you may have noticed, everything new we learn builds upon the earlier stuff. For the proofs in this part of the tutorial, we will be utilizing the inference rules and sprinkle in the replacement rules.
Cast of Characters
A note on convention
Instead of writing out ‘is replaced by/can be written as’ every time we demonstrate a replacement rule, we’re going to use a symbol. I thought about using = as the symbol, but in case this tutorial talks about the logic of identity relations, that’s only going to become more confusing. Instead, we’re going to use 🌭. This is not standard notation. For instance: p ^ q 🌭q ^ p (which is the replacement rule known as commutation) will be parsed as p ^ q can be replaced with q ^ p.
And, just like with the inference rules, the replacement rules will have their own little abbreviation that will be written on the side of the relevant step derived in the proof. For instance, the rule known as Association will be abbreviated as Butt. You thought I’d abbreviate it “Ass.,” didn’t you? What I did there is a common comedic device known as a subversion of expectation. Stick around, you might learn something.
10 inference rules
The rules we’re going to go through are:
Commutation (Comm.)
Double negation (D.N.)
Association (Butt.)
Duplication (Dup.)
DeMorgan’s Laws (D.M.)
Contraposition (Contrap.)
Biconditional Exchange (B.E.)
Conditional Exchange (C.E.)
Distribution (Dist.)
Exportation (Exp.).
1. COMMUTATION (COMM.)
This one should be familiar from arithmetic. For conjunction and disjunction, you can swap around the terms. Just like 1 + 2 can be replaced by 2 + 1. You will notice that some of these replacement rules have analogous rules in mathematics.
2. double negation (D.N.)
This rule should also be intuitive, as you’ve undoubtedly encountered its linguistic analogue in natural language. Basically, a doubly negated term is the same as the term itself; Not Not p is the same as p, and vice versa. So, you can drop a double negation or you can add a double negation if you wish. This may not seem like a particularly useful rule, but it can be invaluable when you want to open up possibilities to use inference rules that require a negation (e.g. modus tollens, disjunctive syllogism).
3. Association (Butt.)
Like commutation, this rule also has an analogue in arithmetic. Moreover, it too applies to conjunction and disjunction (not conditionals). It essentially states that if you have a complex expression (many brackets) and all the operators are either disjunction or conjunction, you are allowed to around the brackets a little bit. Note that this is only allowed when all the operators are either disjunction or conjunction. You cannot apply this rule if you have an expression with mixed operations like ((p or q) ^ r).
4. Duplication (dup.)
Yet another simple rule that applies to conjunction and disjunction. It states that if you have some term you are allowed to either disjoin it or conjoin it with itself. Alternatively, if you have a conjunction/disjunction of the same term, then you can simplify it to just the term itself. There’s a bit of overlap with this rule and the inference rule of Addition (in which we’re allowed to infer any arbitrary disjunct to some term we already have). This rule says that we are allowed not only to disjoin it with itself but also conjoin it with itself. If this sounds more complicated than it is, then just disregard this blurb and look at the symbolization below.
5. DeMorgan’s laws (d.m.)
This one is a little bit trickier than the preceding ones - but you’ll surely be using it loads. It’s basically two rules, but they’re commonly talked about as a set. The first form of the law says that if you have a negated disjunction (negation on the outside of the brackets), you may replace it with a conjunction of two negated conjuncts. It may be easier to grasp by expressing it in natural language. Consider the complex disjunction Neither P nor Q. This can be written in two logically equivalent ways: 1) Not (P or Q) and 2) (Not-P and Not-Q). This is the first form of DeMorgan’s law (see below):
The second form says that if you have a negated conjunction you may replace it with a disjunction with negated disjuncts. So it’s the same deal as with the first rule, only with a negated conjunction as its starting point. Again, let’s look at the rule in natural language. Consider the complex conjunction Not both P and Q. This can be written in two equivalent ways: 1) Not (P and Q) and 2) (Not-P or Not-Q). See the symbolized second form below:
Hot Tip #3 DeRive DeConjuncts: When you encounter a negated disjunction, it’s pretty much always a good idea to apply DeMorgan’s law on it. Why? Because this will yield a conjunction, from which you can doubly Simp your way to yielding standalone terms. Remember Hot Tip #2: don’t ever pass on the opportunity to find hot singles in your area.
6. Contraposition (contrap.)
This rule states that if we have a conditional, we are allowed to reverse the order of the antecedent and consequent and negate both of them. As is probably the case with a lot of these replacement rules, they are easier to grasp by just looking at the symbolizations. If these descriptions are confusing, I invite you to look at the symbolizations first and then read the explanation
In any case, to intuit this equivalence, let’s look at another natural language expression. John will go into credit card debt only if he buys Sifu’s get-rich-quick online course. The operator here (conditional) is ‘only if’ (which is not the same as ‘if and only if’"). Let the antecedent (the expression before ‘only if’) be J and the consequent (the expression after ‘only if’) be D. There are two ways this conditional can be symbolized: 1) J → D and 2) ¬D → ¬J. The first (if allowing some room for grammar) can be parsed as If John has credit card debt then John has bought Sifu’s get-rich-quick online course. The second can be parsed as If John does not buy Sifu’s get-rich-quick online course then John will not go into credit card debt. These two expressions are equivalent because the “only if” signifies that D is a necessary condition for J to happen. If D doesn’t happen, then J doesn’t happen.
(Editor’s note to self [that’s me, actually]: add a thing about necessary and sufficient conditions in Part 2 to clean this section up. Kthanksbai)
7. Biconditional Exchange (b.e.)
If you did your due diligence and practiced the 8 inference rules from the previous part with your own proofs, then you might have noticed that there’s not much you can do with biconditionals. If you encountered that problem then you’ll love this rule. Basically, this rule states that a biconditional is the same thing as a conjunction of two conditionals, one with the antecedent and consequent in one direction, the other in the reverse direction.
Let’s consider this newly learned rule in a proof context: now we know how to break up a biconditional into a conjunction of two conditionals. The fact that the main operator is a conjunction will allow us to use the Simplification rule to isolate each conditional, which in turn may allow us to finally isolate the individual terms in the original biconditional (using other inference rules, e.g. modus tollens). This is great news: we now have a method to find hot singles in your biconditionals. Can I get a ‘sunglasses emoji’?*
*😎
8. conditional exchange (c.e.)
Conditional exchange states that if we have a run-of-the-mill, garden-variety, middle-of-the-road, penis-in-the-vagina, humdrum conditional like p → q, we can replace it with a disjunction of the two terms, where the first term is negated. In other words, we can replace the conditional p → q with ¬p ∨ q. Here’s a natural language example: “If I tell other people how to live their lives at galas then I’m a Hollywood actor“ (L → H) is the same as saying “Either I don’t tell people how to live their lives at galas, or I’m a Hollywood actor” (¬L v H).
9. Distribution (dist.)
This rule is probably the most complicated. In recognition of this, I’ll try to use it in the proof examples later on in this part of the tutorial. I could give you a nice explanation of it, but it would require rather complex metalogical proofs to do so. Therefore, I will skip that (for now anyhow - maybe I’ll go through some metalogic later*). For now, let’s just say that this rule states that if you have a complex statement with a disjunction and a conjunction, you can switch around the main operator (either to a disjunction or disjunction). Here’s a symbolization of the rule:
10. Exportation (exp.)
This is the final replacement rule. If you look at the lefthand formula, it says that if both p and q happen then r will also happen. The righthand formula says the same thing but slightly differently, i.e. if p happens then - if q also happens - q also happens.
Back 2 school: Examples of Proofs
Let’s practice these new rules with some proofs. Where appropriate, I will reference the Hot Tips from Part Four. For the more complex derivations I will also highlight useful steps that we can use for future derivations (so you don’t get lost in the mass of steps). For the final proof (Example 3), which is the longest one, I will also have a blue/purple-ish (depending on image compression…) dividing line to show you where we left of in the previous section.
Example 1
We’re starting with a simple example. We have one premise, and from that we’re supposed to derive the conditional If X then Y.
Hot Tip #1: Gain intuition by thinking backwards
Well, there’s not much to look back to. But we can tell that the conclusion and the premise are almost the same: both are conditionals, and the X and Y are antecedent and consequent respectively in both cases. The only difference is the Z conjoined to the Y in the premise. So, somehow we need to get rid of the Z. Since we only have one premise, and that premise is a conditional, we cannot use any of our inference rules at the moment. So, we know that we’re going to have to use a replacement rule and somehow break up the formula. We can break up the formula using conditional exchange. Let’s do that.
Okay, now what? It’s important to remember that we need to end up with a conditional again, and now we have a disjunction. What this means is that at some point (once we get rid of the Y) we likely need to apply conditional exchange again. But we’re not quite there yet. I want you to take a look at the replacement rules. Which ones are applicable to either of these steps? One should stand out to you - distribution. We can readily apply distribution on step 2 to yield a conjunction, like this:
Hot Tip #2: Find hot singles in your area
Let me remind you why conjunctions are good: they allow us to simp the conjuncts and give us more to work with. It’s always a good idea to isolate individual terms in case you’re lost. But, if you’re well-versed with all the rules at this point, you may notice that we don’t necessarily need to do that: after all, we surmised that we will probably need to use conditional exchange once more - and that requires a disjunction with a negated first disjunct. Looking at the first conjunct in Step 3, we have exactly that. So, let’s simp it.
Do we need to simp the other conjunct? Nah. Look at the move between 1-2 and step 4. The form of Step 2 and Step 4 is the same: a disjunction with a negated first disjunct. We got Step 2 from Step 1, using conditional exchange. And remember, the replacement rules are bidirectional. So, nothing is stopping us from applying conditional exchange on Step 4 to yield the conditional of our dreams.
Aaaaaaaand we’re done. These next two proofs are going to be quite long. Don’t worry, we’re still just using the rules we’ve learned - the only difference is the complexity of the proof. At this point, I’m hoping you’re able to see how you can divide derivation strategies into ‘chunks’. Just as you would remember a phone number in chunks of 3-4 digits, or words in their shapes as opposed to individual characters, so too can you identify and organize patterns in derivation strategy. In fact, the Hot Tips are meant to help you create these chunks. For instance, one strategy chunk you’ve encountered at this point is this: first derive a conjunction; and then simp it twice. In order for us not to get lost in the sea of derived steps, we’ll highlight in red the relevant steps in each description section.
Example 2
We have 4 premises here. Using Hot Tip #1: We know that we have to prove a disjunction between H and X. We could easily derive the final step using the Addition rule, as long as we’ve derived either H and/or X. However, there is no X in the premises. So this confirms our suspicion that we will need to use the addition rule (because it allows us to disjoin any arbitrary term regardless of whether it exists in the premises). Moreover, because X doesn’t exist in the premises, we know that we will have to derive H at some point in the proof. Let’s get it.
Based on the inference rules + the replacement rules we’ve used in the examples so far, it seems like we could do stuff with premises 2-4. Premise 1, however, is a biconditional; and the only way we can break that up is to use Biconditional Exchange. This is a good idea because we need to derive H on its own (recall Hot Tip #2: find hot singles in your area). Biconditional exchange will yield a conjunction, so we can simp the conjuncts immediately after that. This brings us closer to getting H. So let’s do that. That brings us up to Step 7.
Okay, so we still don’t have H on its own. And, looking at the steps in the derivation so far, H is still tied up in complex statements. So it looks like we’re going to have to find some more hot singles in order to free H from its bondage. We only have one single term at the moment - B. But it looks like we can free up C and/or D (or their negations) via Premise 3. How do we do that? I’m glad you asked. Premise 3 is a disjunction, right? If we can gather all the ingredients for one of the disjuncts and then negate this thing, we can apply Disjunctive Syllogism to get the other disjunct. We have all the ingredients for the second disjunct: using B we will apply the addition rule and arbitrarily disjoin B with E. So now we have (B v E) (Step 8). Then, we apply double negation to yield ¬¬(B v E). Remember, that’s the same thing as just (B v E). So, then we just apply D.S., which brings us up to Step 10.
Okay super suave. Now what? Well, let’s apply Hot Tip #3 and #2 on our newly derived ¬(C v D). If we apply DeMorgan’s on ¬(C v D) we will get a conjunction between ¬C and ¬D. We can simp these! Super suave. We’re now at Step 13.
Okay, we’re very close now. We can start looking at ways to single out H. Looking at the steps (highlighted below), I can see one series of actions we can do to single out H. This is how we do it: we can get ¬E from Premise 2 via Modus Tollens (using ¬D from Step 13). Then, we use Modus Ponens on 7 to yield H. AND FINALLY: we arbitrarily add X to H. And we’re done.
Example 3
This is going to be a long one. But that’s good: we’re approaching the length limit of whatever textbook exercises you may encounter - so, you’ll be hardy after this example. 4 premises; and the conclusion is a negated disjunction. Thinking backward (Hot Tip #1): It may just be my faulty piece of crap aromatherapy essential oil diffuser malfunctioning (London Drugs - refund, please), but I smell DeMorgan’s Law on the step before our conclusion. In that case, the last step will have to be a conjunction between ¬B and ¬Φ. Let’s go.
Look at the premises: to me, Premise 3 stands out because there’s only one rule we can apply to break it up: Biconditional Exchange. If you don’t know where to start, it’s usually a good idea to start with breaking up a premise that has the fewest possible rule manipulations available. So let’s apply B.E. to premise 3 and simp it twice. This brings us up to Step 7.
For the record: I don’t even think there are any health benefits to essential oils or whatever; I just wanted it to smell nice in here. But this piece of crap diffuser stopped working after LITERALLY 1 minute. I’m aware that the whole essential oils industry is a grift, but I thought the crazy demand for that stuff would create enough market competition to warrant decent complementary products. Bloody hell. London Drugs should rename themselves to London ASS.
Okay, now we’ve simped Premise 3 as much as we can (at this point). Now we got to look elsewhere. Looking at steps 1-7, Premise 2 looks like it may get us somewhere. Remember Hot Tip #3: we have a negated disjunction that we can turn into a conjunction using DeMorgan’s Law. This will then allow us to simp the conjuncts such that we get ¬D and ¬(G ^ H) . This brings us up to Step 10.
Now what? Because the premises (1-4) are quite complex statements, we’re going to keep breaking these up as much as possible (Hot Tip #2: Find hot singles in your area). Let me remind you of why we’re doing this: breaking up individual terms will give us the largest pool of possible strategies to be used at a later date. With complex proofs, it can be hard to see what you need to do from beginning to end. Therefore, you can look at Hot Tip #2 as cleaning up. In data science, a lot of analysis depends on your “cleaning” the raw data set first. Similarly, we’re cleaning up the proofs by individuating terms as much as possible. For the sake of organization, it’s best to do this in the beginning, so that you have all your cleaning derivations in one chunk (as opposed to being scattered all over the place).
So: let’s clean up Premise 4. Looks like we can use Conditional Exchange on it to yield a negated disjunction. This allows us to then use Hot Tip #2 to simp a conjunction (Steps 12-14).
Now, for the sake of cleaning up, let’s just apply the Double Negation rule on Step 13. We may end up using it, we may not. Next, let’s try to think ahead a little bit: we know we need to end up proving ¬(B v Φ). We have ¬Φ (Step 14) so if we can derive ¬B, we can conjoin these two and then apply DeMorgan’s Law to yield the conclusion. So, knowing this, we’re going to have to single out ¬B somehow. B only occurs in Premise 1, so that’s where we’re going to turn eventually. Moreover, B is not negated, and it’s the antecedent, so it looks like we’re going to have to use Modus Tollens on Premise 1. To do that, we’ll need a negation of the consequent, i.e. ¬(D v H). We’ve got ¬D, so we’ll need ¬H, so that we can conjoin them and then apply DeMorgan’s in order to yield ¬(D v H).
So how can we get ¬H? Well, G occurs alongside H in a few steps. Moreover, G occurs with B in Premise 1. So, in order to break up the antecedent in Premise 1 (which we decided is the thing we need to do), we will need G anyway. So let’s try to derive G. Looking at what terms we have so far, it looks like we can get G from Step 7 via DeMorgan’s and then Modus Ponens. We have ¬Φ already, so let’s arbitrarily add ¬Ψ using addition. Then, apply DeMorgan’s to it. Now we have the antecedent to the conditional in Step 7, so Modus Ponens will allow us to get G. We’re now at Step 18.
Now that we have G, we can turn our attention to finding ¬H. G and H occur in Step 10 as a negated conjunction. If we apply DeMorgan’s on Step 10, we’ll get a disjunction between ¬G and ¬H. Because we have G, we know that ¬G cannot be true. So we’ll do the following: first apply Double Negation on G (19), then apply Disjunctive Syllogism on the DeMorgan-ified version of Step 10 (Step 20). This yields ¬H (Step 21).
Great, now we can turn our attention to Premise 1 (its consequent, to be specific). We now have both ¬D and ¬H. If we conjoin them and apply DeMorgan’s Law we get ¬(D v H) - i.e. the negation of Premise 1’s consequent. Then we simply use Modus Tollens to yield ¬(B ^ G). We’re really close now.
You can probably see where this is going now. We’ll take Step 24, apply DeMorgan’s, then (using our ¬¬G from Step 19) we’ll apply Disjunctive Syllogism to yield ¬B. Now it’s just a matter of piecing it together. Just as we did in Steps 22-23, we’ll apply conjunction on ¬B and ¬Φ and then FINALLY apply DeMorgan’s Law. AAAAAAAND WE’RE DONE.
That was a very long boi. Pat yourself on the back, that was a lot of work. Good job.
Part Four Wrap-Up
What we have learned
We have learned 10 basic replacement rules and how these can be used in concert with the inference rules. The rules are:
Commutation (Comm.)
Double negation (D.N.)
Association (Butt.)
Duplication (Dup.)
DeMorgan’s Laws (D.M.)
Contraposition (Contrap.)
Biconditional Exchange (B.E.)
Conditional Exchange (C.E.)
Distribution (Dist.)
Exportation (Exp.).
In our proofs, we used Double Negation, DeMorgan’s Laws, Conditional Exchange, Biconditional Exchange, and Distribution. As always, I recommend practicing these rules on your own (especially the ones we didn’t encounter in the 3 examples). All these rules will surely show up in future proofs.
Also, as mentioned before, the length of Example 3 is about as long as we will go through in this tutorial series. Given how long it was, I’m hoping you’re seeing the value of applying the Hot Tips scattered throughout the tutorial. When proofs become this complex, it’s important to have some strategic scaffolding, so that you don’t get lost in all the steps. It should be noted, however, that proofs can become MUCH LONGER than 28 lines; in fact, there are computer programs that are dedicated to solving very long proofs. Such proofs can be several thousand steps. So, in the grand scheme of things, we’re keeping it pretty chill with the lengths of our proofs.
Where we are going next
We’re fast approaching the end of the sentential logic section of this tutorial. In the next part, we’re going to look at 2 more proof methods: conditional and indirect proofs. This will round out the thinking tools we’ll use for sentential logic. After that, we’re going to up the ante and get into predicate logic. However, given the iterative nature of formal logic, everything that we’ve learned so far (and will learn in the next part) will still be relevant to predicate logic. Of course, predicate logic will come with its own set of rules and such - so it’s imperative that you know all the rules well before moving onto predicate logic.