Logical Implication: Rules of Inference
The following section will now do a formal study of what an argument is and when an argument is valid. This will help investigate how to prove theorems in later sections.
Definition of an Argument and Valid Argument The following is the general form of an argument:
(p₁ ᴧ p₂ ᴧ ... ᴧ pn) → q
Where n is a positive integer, p₁, p₂, ..., pn are called premises of the argument, and the statement q is called the conclusion of the argument. Note that q can be a compound statement.
This argument is a valid argument if, whenever each of the premises p₁, p₂, ..., pn is true, then the conclusion is also true. One way to determine if an argument is valid is to show the that the statement (p₁ ᴧ p₂ ᴧ ... ᴧ pn) → q is a tautology. This can be done using truth tables, but later, it will be realized that truth tables are not useful for larger arguments.
Note that, if any one of the premises p₁, p₂, ..., pn is false, then the hypothesis (p₁ ᴧ p₂ ᴧ ... ᴧ pn) is automatically false, and just like with any implication, a false hypothesis will always make the implication true, regardless of what the conclusion q's truth value is.
Example Let p,q,r denote the following primitive statements: p: Roger studies. q: Roger plays racquetball. r: Roger passes discrete mathematics. Let p₁,p₂,p₃ denote the following premises: p₁: If Roger studies, then he will pass discrete mathematics. p₂: If Roger doesn't play racquetball, then he'll study. p₃: Roger failed discrete mathematics. To determine whether the argument (p₁ ᴧ p₂ ᴧ p₃) → q is a valid argument, first write out the premises in symbolic form: p₁: p → r p₂: ¬q → p p₃: ¬r These are then substituted in the argument: (p₁ ᴧ p₂ ᴧ p₃) → q [(p → r) ᴧ (¬q → p) ᴧ ¬r] → q The following is this argument's truth table:
Therefore, since the argument is a tautology, the argument is a valid argument.
The above example demonstrated that for any primitive statements p,q,r, the implication [(p → r) ᴧ (¬q → p) ᴧ ¬r] → q is a tautology. The truth of the conclusion q is inferred, or deduced, from the truth of the premises (p → r), (¬q → p), and ¬r.
Logical Implication If p,q are arbitrary statements such that p → q is a tautology, then p logically implies q, denoted as p => q. To indicate that the implication p → q is not a tautology and therefore not a logical implication, the notation p ≠> q is used.
When p,q are statements and p => q, the implication p → q is a tautology, where p → q is referred to as a logical implication. Therefore p => q if q is true whenever p is true. If p were false, q will always be true.
Logical Implication and Logical Equivalence Let p,q be arbitrary statements. If p <=> q, then the statement p ↔ q is a tautology, and so the statements p,q have the same truth values. Therefore, under these conditions, p → q and q → p are tautologies, and so p => q and q => p.
Suppose that p => q and q => p. The logical implication p => q states that the statement p will never have a truth value of 1 when the statement q has a truth value of 0. Additionally, since q → p is also a logical implication, the statement p will never have a truth value of 0 when the statement q has a truth value of 1.
Example Recall that DeMorgan's law is a biconditional statement that is a tautology: ¬(p ᴧ q) <=> ¬p ᴠ ¬q Therefore, for all statements p,q, ¬(p ᴧ q) => (¬p ᴠ ¬q) and (¬p ᴠ ¬q) => ¬(p ᴧ q). Additionally, since both implications ¬(p ᴧ q) → (¬p ᴠ ¬q) and (¬p ᴠ ¬q) → ¬(p ᴧ q) are tautologies, they can both be rewritten as the following: [¬(p ᴧ q) → (¬p ᴠ ¬q)] <=> T₀ [(¬p ᴠ ¬q) → ¬(p ᴧ q)] <=> T₀
Rules of Inference The problem with truth tables in determining whether an argument is a logical implication or a valid argument is, as the number of premises increases, the more rows and columns needed for the truth table, which loses its appeal.
Recall that to establish an argument being valid, only the rows in the truth table where all the premises have a truth value of 1 are considered, because the implication, or argument, will automatically be true if all of the premises have a truth value of 0 and hence a hypothesis with a truth value of 0. Therefore, the rows on the truth table that have at least one truth value of 0 in one of the premise columns is not necessary to consider. Note that there may be more rows than one that contain all truth values of 1 for every premise. This observation shows that a great amount of the truth table can be eliminated.
The following are two explanations on why the rules of inference is helpful in avoiding large truth tables:
1. The only rows for which the conclusion of the argument is considered are the rows where each premise all have a truth value of 1. 2. The rules of inference are fundamental in the development of a step-by-step validation of how the conclusion q logically follows from the premises p₁, p₂, ..., pn in an implication of the form (p₁ ᴧ p₂ ᴧ ... ᴧ pn) → q.
Additionally, another way to express an argument is in tabular form:
This development will establish the validity of the given argument, because it will show how the truth of the conclusion can be deduced from the truth of the premises.
Many rules of inference come from logical implication or from the study of logic. The following are the twelve rules of inference:
1. Rule of Detachment, Modus Ponens
2. Rule of Denial, Modus Tollens
3. Law of Syllogism
4. Rule of Conjunction
5. Rule of Disjunctive Syllogism
6. Rule of Contradiction
7. Rule of Conjunction Simplification
8. Rule of Disjunctive Amplification
9. Rule of Conditional Proof
10. Rule for Proof by Cases
11. Rule of the Constructive Dilemma
12. Rule of the Destructive Dilemma
Rule of Detachment or Modus Ponens Consider the rule of inference called Modus Ponens, or the Rule of Detachment. In symbolic form, this rule is expressed as the following logical implication:
[p ᴧ (p → q)] => q
This logical implication is verified in the following truth table:
Note that there is only one row to consider, which is the fourth row, where both premises p and p → q have a truth value of 1. Since the conclusion is also true, the argument is valid.
The Rule of Detachment is written in tabular form:
The three dots beside the conclusion is read as, "therefore," indicating that the statement q is the conclusion for the premises p and p → q.
The Rule of Detachment is used to argue that if (1) p is true and (2) p → q is true, then the conclusion q must also be true.
The following example demonstrates the Rule of Detachment [p ᴧ (p → q)] => q:
Example p: Lydia wins a ten-million-dollar lottery. p → q: If Lydia wins a ten-million-dollar lottery, then Kay will quit her job. q: Therefore, Kay will quit her job.
The following example demonstrates that the order of the premises in any rule of inference does not matter:
Example p → q: If Allison vacations in Paris, then she will have to win a scholarship. p: Allison is vacationing in Paris. q: Therefore, Allison won a scholarship.
Note that, although the rules of inferences were written with primitive statements, compound statements can be replaced using the first substitution rule, where all occurrences of a particular primitive statement can be replaced and still yield a tautology. This is because all rules of inference are tautologies, and so the first substitution rule can be applied.
Therefore, if all the occurrences of p in the Rule of Detachment were replaced by r ᴠ s, and all occurrences of q were replaced by ¬t ᴧ u, then the following is still a valid argument:
Example Consider the following argument: 1. Rita is baking a cake. 2. If Rita is baking a cake, then she is not practicing her flute. 3. If Rita is not practicing her flute, then her father will not buy her a car. 4. Therefore, Rita's father will not buy her a car. This argument can be rewritten in symbolic form:
The following establishes the validity of the argument using rules of inference and laws of logic:
Note that there are alternative ways to validate this argument.
Example To validate the following argument:
Laws of logic and rules of inference are used. Each premise can be simplified using these techniques.
Note that, although a hypothesis can logically imply a conclusion, hence resulting in a logical implication, it does not mean that the hypothesis and conclusion are logically equivalent. Therefore, the second rule of substitution cannot always be used with confidence.
Modus Ponens versus Modus Tollens The Modus Ponens [(p → q) ᴧ p] → q and the Modus Tollens [(p → q) ᴧ ¬q) → ¬p are related rules of inference, however other forms of these two rules are invalid arguments, where the premises are true but the conclusion is false.
For Modus Ponens, a similar form is [(p → q) ᴧ q] → p. However, this form is not a tautology. This invalid argument results from the fallacy, or error in reasoning, from trying to argue by the converse. Therefore, [(p → q) ᴧ p] => q, but [(p → q) ᴧ q] ≠> p.
For Modus Tollens, a similar form is [(p → q) ᴧ ¬p] → ¬q. However, this form is not a tautology. This invalid argument results from the fallacy, or error in reasoning, from trying to argue by the inverse. Therefore, [(p → q) ᴧ ¬q) => ¬p, but [(p → q) ᴧ ¬p] ≠> ¬q.
The Rule of Contradiction Let p denote an arbitrary statement and F₀ denote a contradiction. The following truth table demonstrates that (¬p → F₀) → p is a tautology called the Rule of Contradiction:
This rule states that, if p is a statement and F₀ is a contradiction, and ¬p → F₀ is true, then ¬p must be false, because F₀ is always false. Therefore, the statement p is definitely true.
Proof by Contradiction The Rule of Contradiction is the basis of a method used in establishing the validity of an argument. This method is referred to as the Proof by Contradiction, or Reductio ad Absurdum.
The idea behind the method of Proof by Contradiction is to establish a statement, which is the conclusion of the argument, by showing that, if the statement, or conclusion, is false, then an impossible consequence can arrive.
In general, given the form of an argument:
(p₁ ᴧ p₂ ᴧ ... ᴧ pn) → q
To establish its validity, the following logically equivalent argument's validity can be established instead:
(p₁ ᴧ p₂ ᴧ ... ᴧ pn ᴧ ¬q) → F₀
The following truth table demonstrates that (p → q) ↔ [(p ᴧ ¬q) → F₀] is a tautology and therefore logically equivalent:
The first substitution rule is used on p → q, where all occurrences of p are replaced with (p₁ ᴧ p₂ ᴧ ... ᴧ pn). And so (p → q) ↔ [(p ᴧ ¬q) → F₀] becomes (p₁ ᴧ p₂ ᴧ ... ᴧ pn) → q <=> [(p₁ ᴧ p₂ ᴧ ... ᴧ pn ᴧ ¬q) → F₀].
When the Proof by Contradiction method is used, it is first assumed that what is trying to be proven, or validated, is actually false. This assumption is used as an additional premise to produce a contradiction, or impossible situation of the form s ᴧ ¬s for some statement s. Once this contradiction is derived, then the statement given can be concluded to be true, which validates the argument or completes the proof.
Example Given the following argument:
To validate this argument:
Example Given the following argument:
To validate this argument:
The following example will provide a way to show a given argument is valid:
Example Consider the following situation: If the band could not play rock music or the refreshments were not delivered on time, then the New Year's party would have been canceled and Alicia would have been angry. If the party were canceled, then refunds would have been made. No refunds were made. Therefore, the band could play rock music. For validating this argument, write out each primitive statement: p: The band plays rock music. q: The refreshments were delivered on time. r: The New Year's party was canceled. s: Alicia was angry. t: Refunds have been made. Note that the negation "not" does not make a primitive statement. All primitive statements are written as assumed if they were true. The symbolic form of this argument is then:
To validate the argument:
The following example uses the method of Proof by Contradiction:
Example Given the following argument:
To validate this argument:
Note that r was shown to be logically equivalent to the contradiction F₀, which created the contradiction ¬p → F₀ that concludes p.
Consider the following truth table:
This truth table demonstrates that for the primitive statements p,q,r that [p → (q → r)] <=> [(p ᴧ q) → r].
Using the first substitution rule and associative law, let every occurrence of p be replaced by the compound statement (p₁ ᴧ p₂ ᴧ ... ᴧ pn).
[p → (q → r)] <=> [(p ᴧ q) → r] [(p₁ ᴧ p₂ ᴧ ... ᴧ pn) → (q → r)] <=> [(p₁ ᴧ p₂ ᴧ ... ᴧ pn ᴧ q) → r]
This substitution shows that, to establish the validity of the following argument:
Then it can be done by establishing the validity of the following corresponding argument:
If the problem was to show that q → r had the truth value of 1 when each premise p₁, p₂, ..., pn has a truth value of 1, and if the truth value for q is 0, then q → r has the truth value of 1. This is easy, and so the real problem is to show that q → r has a truth value of 1 when each premise p₁, p₂, ..., pn has a truth value of 1, and also q has a truth value of 1. In other words, it is needed to be shown that when p₁, p₂, ..., pn, q each have truth values of 1, then the truth value of r must be 1.
Example Consider the following argument:
The conclusion is an implication and so it corresponds to the following argument, because [(p₁ ᴧ p₂ ᴧ ... ᴧ pn) → (q → r)] <=> [(p₁ ᴧ p₂ ᴧ ... ᴧ pn ᴧ q) → r]:
Then, to validate this argument:
Invalid Arguments Consider the following general form of an argument:
(p₁ ᴧ p₂ ᴧ ... ᴧ pn) → q
An argument is considered invalid if it is possible for each premise p₁, p₂, ..., pn to be true with a truth value of 1, while the conclusion q is false with a truth value of 0.
Example Consider the following argument:
To show that this is an invalid argument, there only needs to be one assignment of truth values for each of the statements p,q,r,s such that the conclusion ¬s → ¬t is false (has the truth value of 0), while the four premises are all true (have a truth value of 1). The only time the conclusion ¬s → ¬t is false is when ¬s is true and ¬t is false. This implies that the truth value for s is 0 and the truth value for t is 1. Since the statement p alone is a premise, it's automatically assigned the truth value of 1. For the premise p ᴠ q to have the truth value of 1, q can be either true or false, since p is already true. Instead, consider the other premise t → r. It is known that t has a truth value of 1, and so for t → r to be true, then the statement r must have a truth value of 1. Now with r true and s false, then r → s is false, and so q must have a truth value of 0 for the implication q → (r → s) is true. Therefore, the following truth assignments have been established for each statement such that each premise will have a truth value of 1: s: 0 t: 1 p: 1 r: 1 q: 0 These statements were assigned these truth values such that the premises create a true hypothesis while the conclusion is false. Therefore, the argument is invalid.
It should be realized now that in trying to show an implication presents a valid argument, all cases of where the premises in the implication are true must be considered. In order to cover all of these cases without creating a truth table, rules of inference, laws of logic, and other logical equivalences are used.
To cover all necessary cases, one specific case cannot be used to establish the validity of an argument for all possible cases. However, to show an argument is not a tautology, only one case needs to be found to make the implication false, which is when all the premises are true but the conclusion is false. This one case provides a counterexample for the argument, which shows the argument is invalid.
Example Given the following argument:
To determine its validity or invalidity, the conclusion is only false if p is true. Then, if p is true, then for p → q to be true, q must also be true. If q is true, then for q → s to be true, s must also be true. Is s is true, then ¬s is false, and so for r → ¬s to be false, r must be false as well. This means that p => (¬r ᴧ r), which is a contradiction. Since ¬p is false and r is false, this argument is valid, because ¬p ⊻ r is false, making the entire hypothesis false.
PDF reference: 105
For a), only one row is considered, which is when all three primitive statements p,q,r are true.
This is because for the hypothesis to be assumed true, the three premises p, p → q, and r need to be true. For p → q to be true, q must be true, because p is assumed true. Since r is assumed true, the conclusion (p ᴠ r) → r is true, since p ᴠ r is true and r is true.
For c), three rows are considered, which is when the two premises p ᴠ (q ᴠ r) and ¬q are true. Since ¬q is true, then q is always false. Then for p ᴠ (q ᴠ r) to be true, p or r has to be true or both have to be true, which creates three rows: p: 0, q: 0, r: 1, p: 1, q: 0, r: 0, and p: 1, q: 0, r: 1.
For a), if the conclusion p has a truth value of 0, then p ᴧ q must also have a truth value of 0 as well. Therefore, the argument can never be invalid with a true hypothesis and a false conclusion.
For b), if the conclusion p ᴠ q has a truth value of 0, then both p and q cannot have a truth value of 1. Therefore, p has a truth value of 0, and so the argument can never be invalid with a true hypothesis and a false conclusion.
For c), if the conclusion q has a truth value of 0, then for the premise p ᴠ q to be true, p has a truth value of 1. However, if p is true and ¬p is true, that is a contradiction F₀, which makes the entire hypothesis false. Therefore, the argument can never be invalid with a true hypothesis and a false conclusion.
For a), let the following be primitive statements:
c: Andrea can program in C++. j: Andrea can program in Java.
Argument written in tabular form:
This argument uses the Rule of Conjunctive Simplification, and so the argument is valid.
For b), let the following be primitive statements:
b: Bubbles wins. m: Meg sinks a birdie on the last hole.
Argument written in tabular form:
This argument is invalid, because its fallacy is the attempt to argue with Modus Ponens' converse.
For c), let the following be primitive statements:
p: Ron's computer program is correct. a: Ron completes his computer science assignment in at most two hours.
Argument written in tabular form:
This argument uses Modus Tollens, and so the argument is valid.
For d), let the following be primitive statements:
p: Eileen's car keys are in her purse. k: Eileen's purse is on the kitchen table.
Argument written in tabular form:
This argument uses the Rule of Disjunctive Syllogism, and so the argument is valid.
For e), let the following be primitive statements:
i: Interest rates are falling. s: The stock market rises.
Argument written in tabular form:
This argument is invalid, because its fallacy is the attempt to argue with Modus Tollens' inverse.