Proof by Deduction#
Logical Deduction is a method of formalizing the process of drawing conclusions from a set of premises.
You are read more at the links below
We will use a Proof Checker Website. This will allow you to check that all your steps are correct and you reach the correct conclusion.
Logical Deduction#
A premise is a statement that is known to be true at the start of the deduction. We assume these facts are true. Deduction is the process of deriving new conclusions based on our premises and the rules of logic.
Let us assume that all men are mortal. Let us further assume that Socrates is a man. These are our two premises. We can then conclude that Socrates, since he is a man, must also be mortal. We combined the information from our premises to learn something new.
All men are mortal
Socrates is a man
Socrates is mortal
We often use chained conditionals. Larry is a student in a class. If he gets sick, then he will be absent from class. If he is absent from class, then he will miss his classwork. These are our new premises. We realize that these combine to tell us that if Larry is sick, then he will miss his classwork.
If Larry is sick, then he will be absent.
If Larry is absent, then he will miss his classwork.
If Larry is sick, then he will miss his classwork.
These makes sense, but is not formal. It requires human intuition to figure out the new statements based on the premise. We want to formalize this into something that has a fixed set of rules. That way everyone can convey information in a consistent manner. With a formal set of rules, we can also verify the deduction. This way we can ensure no mistakes are made, we could even automate some deductive proofs.
A deductive proof starts with any premises. These are things we assume to be true within the proof. If they are true in practice is not part of the deduction. We just work under the assumption they are true. Our proof is only correct if the premises are actually true. If the premises turn out to be false, the proof is worthless.
The last line of the proof is the conclusion. This is what we are proving is true because of the premises. In between, we use the Laws of Deduction to get from the premises to the conclusion.
The “thing” we a proving is called an argument. An argument is a set of premises followed by a conclusion. The proof verifies that the conclusion must be True
if the premises are true.
Argument’s have a fixed format. A general template is given below.
The premises are separated by commas. These are shown as
Let us return to the example from earlier, but add variables to the statements.
is true when Larry is sick. is true when Larry is absent. is true when Larry completes his classwork.
We can rewrite each sentence as a logical expression.
means “If Larry is sick, then he will be absent.” means “If Larry is absent, then he will miss his classwork.” means “If Larry is sick, then he will miss his classwork.”
We can write this as an argument.
Once we have an argument, we need to use a proof to verify it is true.
Basic Deductive Rules#
The Rules of Deduction are built around the Boolean operators we have already seen. Deduction is a kind of logical reasoning. We will start with rules related to three Boolean operations. We will introduce the negation in the next sections. Using the negative operator in proofs adds a significant level of complexity.
As we saw with truth tables, we can make up and prove any rules we want. This may be useful in some contexts, but it can also prove problematic. If everyone is using different rule sets, it is hard to communicate proofs. The Rules of Deduction provide a small, complete, and consistent set of rules that can be used in proofs.
Note
The basic Rules of Deduction are complete in the sense that they can be used to prove anything that could be proven by a truth table. Since all boolean algebra statements can be proven by truth tables, the Rules of Deduction are exactly as powerful as truth tables.
We will start with the rules for conjunctions, disjunctions, and conditionals. Each operator has a rule to introduce a new operator into the proof. It also has an elimination rule that removes the operator from the proof.
Operation |
Add Operator |
Remove Operator |
---|---|---|
Conjunction Introduction |
Conjunction Elimination |
|
Disjunction Introduction |
Disjunction Elimination |
|
Conditional Introduction |
Conditional Elimination |
We will introduce the rules based on their complexity to use.
Conjunction Introduction#
If we have two statements that are true, we can say they are both true together. Imagine it is a rainy day. You could look outside and verify the premise Rainy=True
. Next, you look at the calendar at see it is Wednesday. You have verified the premise Wednesday=True
. The rule of Conjunction Introduction states that you can say
It is a rainy day and a Wednesday.
You verified both premises independently, you are now allowed to use a conjunction to say they are both true together.
In deduction, we are proving an argument. The argument has two sides. The first is the list premises. The second is a conclusion.
We can formally write the above argument. Let
The argument is formally written as
When writing a proof, every statement except the premises must be justified by a rule. The premise is justified by stating that it is a premise. In these examples, we will specific the premise in our proofs. Sometimes a premise just has no justification written at all.
Our first rule is Conjunction Introduction. This rule states that if two lines are true, we may combine the two lines using the conjunction operator. The justification is written in shorthand as
The proof is shown below.
This proof justifies the argument
If we know that
Note
Just because a proof is true, does not mean the argument is useful for anything. Conceptually, we could prove that if cakes were intelligent then it would be wrong to eat cakes. It may be possible to prove this argument. Regardless, cakes are not intelligent. We can’t actually use the proof in real life. It just because a thought exercise.
In the proof, the right side of the each step specifies which rules was used. The first two lines are premises and assumed to be true. The
Disjunction Introduction#
If we want to introduce the disjunction operator, we need to know one of the two sides is true. Let us again imagine a rainy day. We know for a fact it is rainy out. It would be true to say
It is rainy or Monday today.
It doesn’t matter at all if it is actually Monday. We know it is rainy, therefore the statement is true.
The argument we are proving is
If we know that
This is true because the argument is really just an implies.
The truth table for this expression is as follows
T |
T |
T |
T |
F |
T |
F |
T |
T |
F |
F |
T |
If we know
The justification for Disjunction Introduction only takes one line number, the half of the disjunction that is known to be true.
Conjunction Elimination#
Conjunctions can also be eliminated. Since we know both sides of the conjunction must be true, we can determine that either side is true independently.
It is snowing and windy.
You can draw the conclusion that it is snowing. The windy part might not be relevant to your life. If we know a conjunction statement is true, then its two parts must also be true. We can prove that it is snowing by discarding the windy part of the clause.
We can prove that
The justification is
We can prove the commutative property of the conjunction operator using the rules we have seen so far. We will prove
To fully justify the commutative property we need to also provide a proof in the opposite direction
With both these proofs, we know that
Conditional Elimination#
What if our premises contain a conditional statement? We are told ``if it rains then it pours’’. We verify that it is raining. We can draw the conclusion that it is pouring.
The argument we are making it
If we know that an implies is true and we know the left side is true, we can draw the conclusion that the right side must be true. The justification symbol is
Conditional Introduction#
What if we want to make an assumption? This happens in a subproof. We imagine a world in which something is true, even though we have not verified it. We can use rules in this imaginary world to justify arguments. We can then draw conclusions from the subproof.
You have probably seen this already in mathematics. We write things like “let us assume x is even”. We aren’t verifying
One case where we need assumptions is to create a new conditional. This rule is called conditional introduction.
What if we want to prove that if
If Larry is sick, then he will be absent.
If Larry is absent, then he will miss his classwork.
If Larry is sick, then he will miss his classwork.
We can create variables again.
is true when Larry is sick. is true when Larry is absent. is true when Larry completes his classwork.
The argument is
The proof is written as follows
The subproof is draw with a special box or symbol. This tells the reader that the lines in the subproof only work because of the assumption. It is an imaginary world where
This subproof is justifying a conditional statement. We said “assume S is true” and that lead us to the subproof’s conclusion
The shorthand name for the justification is
When we leave the imaginary world of the subproof, we still have no idea if
Disjunction Elimination#
What if we want to take apart a disjunction statement? If a disjunction is true, it could be for multiple reasons. Either of the two inputs could be true and the other false. The could also both be true.
To break apart a disjunction, we need to make two assumptions and see what happens. If we know a disjunction,
The subproof based in the assumptions is again drawn in a box. We prove the argument
The disjunction elimination has the most complex justification we have seen so far. If both our imaginary worlds lead to the same conclusion, then it doesn’t matter which is true. Either leads to the correct conclusion.
The justification starts with the shorthand
Proof Terminology#
An argument is valid if it is impossible for the premises to be true and the conclusion to be false. Any complete proof by deduction makes the argument valid. An argument is invalid if there exists at least one case where the premises are all true by the conclusion is false. If a proof by deduction is completed correctly, it’s argument cannot be invalid.
Remember, we never actually verify the premises in our proof. A proof can be valid and the premise can still be wrong. An argument is sound if the proof is valid and the premises are confirmed to be true.
Examples#
Below are some additional example proofs by deduction.
Argument:
Argument: