Deduction Examples
Contents
Deduction Examples¶
This page shows a number of example deductions. Each proof is given along with the argument and commentary on why the specific approach was used.
Nested Expressions¶
The argument we are proving is \((C \wedge D) \vee E \therefore E \vee D\).
This question starts with only one premise. That one premise combines all the information we need to start. To do our proof, we need to break up the premise. It is a disjunction, so we need two subproofs. The \(E\) subproof starts with just a single variable, so this is done first. It should be easier. The second subproof starts with \(C \wedge D\). We are allowed to assume an entire expression like this.
One the two assumptions are made, their subproofs are straightforward. The key to this problem is to realize an assumption can be anything, not just a single variable.
Disjunction Elimination Example¶
The argument we are proving is \((H \implies G) \vee (Y \implies G), H \wedge Y, G \implies Q \therefore Q\).
Whenever we make assumptions on a disjunction, we double our work load. In this question, we have two conditional statements connected by a disjunction. We can’t get far without splitting up this premise.
The two subproofs are almost mirror images. The use the same three rules in the same order. This is a common feature of disjunction elimination. Often, there is overlap between the two paths. Once you solve one, the other one tends to be easier.
Proof of Double Negative Rule¶
You probably already know that \(\neg \neg P = P\). This is a derived rule called double negative elimination. We don’t need it, it can be built up from simple rules.
If we want to prove an equivalence, we need to prove two arguments. One in either direction.
If we prove both \(\neg \neg P \therefore P\) and \(P \therefore \neg \neg P\), then we can state \(\neg \neg P \iff P\). The two are really exactly the same.
First, we prove \(P \therefore \neg \neg P\). We can look at the conclusion to get some hints. We want to end up with \(\neg \neg P\). There is only one rule that allows us to add a new negative sign, negation introduction. All we need to do in contradict \(\neg P\) and we are allowed to add another negative in front of it.
The second direction is \(\neg \neg P \therefore P\). This time our conclusion target is \(P\). The only way to get this is by using an indirect proof to remove a negative sign from \(\neg P\). Notice that negative elimination can match the two opposites correctly.
Contradicting a Conclusion¶
The argument is \(\neg X, A \implies X, B \implies X \therefore \neg (A \vee B)\).
What is interesting about this proof is that the three premises seem worthless on their own. They don’t provide any hints about what to do. The conclusion is where the biggest hint is. We can look at the conclusion and see that we want to reach \(\neg (A \vee B)\).
There is only one way to create an expression with a negative, we need a contradiction. That means we need to assume the opposite of the conclusion \(A \vee B\). Once we make this assumption, the subproof flows smoothly. It is just a standard disjunction elimination. The key is both paths lead to \(X\) which is a contradiction.
This question could also be solved by ending both inner subproofs with \(\bot\) and using disjunction elimination to move the \(\bot\) into the primary subproof.
The second method of solving the problem is shown below.
Excluded Middle¶
The expression \(K \vee \neg K\) is a tautology. It is always true. We can actually state \((K \vee \neg K) = T\). We can prove this with no premises at all. We can argue \(\therefore (K \vee \neg K)\).
The approach to this problem is to assume \(\neg(K \vee \neg K)\), which we know is impossible. Then just justify that we are right and it is impossible.
The law of the excluded middle states that if something is true for both sides of a tautologic disjunction, it must always be true. This is a derived rule. We don’t need it because we can always introduce the tautology into our proof.
We want to argue \(\neg K \implies M, K \implies M \therefore M\). We notice that this is a law of the excluded middle problem. Both \(K\) and \(\neg K\) cause \(M\) to be true. The variable \(K\) must be either true or false, so one of these conditionals will make \(M\) true.
We first create \(K \vee \neg K\), then show both sides cause \(M\) to happen. The important part of this proof is that we can always introduce a tautology like \(K \vee \neg K\) to a proof.
Explosion in Practice¶
An implies statement can be created by the principle of explosion. We argue that \(\neg X \implies B, B \implies X \therefore \neg X \implies (D \vee R)\).
The two premises make it certain that \(X\) is going to be true. It has to be because \(X\) being false causes a contradiction. If we know that \(X\) Is always true then saying \(\neg X \implies \cdots\) is the same as saying \(\text{False} \implies \cdots\).
Once we reach the contradiction, we can explode anything. Then use conditional introduction to make a statement. The conditional we created may seem pointless, but it is technically correct.
Validity of the Cut Rule¶
If we know that \((P \vee R)\) is true and also \((\neg P \vee Q)\), we can deduce that either \(Q\) or \(R\) is true. If \(P\) is true, then \(Q\) must be true for the other disjunction. Likewise, if \(\neg P\) is true, then \(R\) must to true for the first disjunction. We don’t know which, we just know one is true.
The argument is \((P \vee Q), (\neg P \vee R) \therefore (Q \vee R)\).
Since we are working with two disjunctions, we need to nest them deeply into subproofs. We need to catch every possible situation.
