Discrete MathematicsMathematical LogicLogical Implication and Rules of Inference
Valid Arguments and Logical Implication
Having tested tautologies, contradictions, and valid arguments by final truth-table columns, the next step is to express argument validity as logical implication. Valid arguments and logical implication give a precise way to say that a conclusion is forced by given premises. In ordinary reasoning, students often accept a conclusion because it sounds plausible; in mathematical logic, plausibility is not enough. In this lesson, valid arguments and logical implication will be studied through implication forms, truth conditions, and short formal deductions.
:::definition[Premises and Conclusion]
Let p1,p2,p3,…,pn and q be statements. In an argument of the form
p1,p2,p3,…,pn∴q,
the statements p1,p2,p3,…,pn are called the premises, and the statement q is called the conclusion.
:::
:::definition[Implication Form of an Argument]
Let p1,p2,…,pn be premises and let q be a conclusion. The implication form corresponding to the argument
p1,p2,…,pn∴q
is the conditional statement
(p1∧p2∧⋯∧pn)→q.
:::
:::definition[Valid Argument]
Let p1,p2,…,pn be premises and let q be a conclusion. The argument
p1,p2,…,pn∴q
is called a valid argument if whenever all the premises are true, the conclusion is also true. Equivalently, the argument is valid if
(p1∧p2∧⋯∧pn)→q
is a tautology.
:::
A valid argument does not require that the premises are actually true in the real world. It requires that no truth-value assignment makes all premises true while making the conclusion false. Thus, to disprove validity, one searches for a row where every premise has value 1 and the conclusion has value 0. To prove validity, one may show directly that such a row cannot occur. This is why valid arguments and logical implication are closely connected.
A valid argument fails only if one row makes every premise true while the conclusion is false. Use the controls to choose truth values for the statements in the Roger studies argument. The display evaluates each premise and the conclusion for that single row. Notice that a row with a false premise does not disprove validity, but a row with all true premises and a false conclusion would be a counterexample.
:::scientific-preview[Validity Row Explorer]
Learn valid arguments and logical implication in mathematical logic for VU Semester 6 MATHDSE2 with clear notes, examples, solved problems, and practice blocks.
Having tested tautologies, contradictions, and valid arguments by final truth-table columns, the next step is to express argument validity as logical implication. Valid arguments and logical implication give a precise way to say that a conclusion is forced by given premises. In ordinary reasoning, students often accept a conclusion because it sounds plausible; in mathematical logic, plausibility is not enough. In this lesson, valid arguments and logical implication will be studied through implication forms, truth conditions, and short formal deductions.
Core definition02
Premises and Conclusion
Let p1,p2,p3,…,pn and q be statements. In an argument of the form
p1,p2,p3,…,pn∴q,
the statements p1,p2,p3,…,pn are called the premises, and the statement q is called the conclusion.
Core definition03
Implication Form of an Argument
Let p1,p2,…,pn be premises and let q be a conclusion. The implication form corresponding to the argument
p1,p2,…,pn∴q
is the conditional statement
(p1∧p2∧⋯∧pn)→q.
Core definition04
Valid Argument
Let p1,p2,…,pn be premises and let q be a conclusion. The argument
p1,p2,…,pn∴q
is called a valid argument if whenever all the premises are true, the conclusion is also true. Equivalently, the argument is valid if
(p1∧p2∧⋯∧pn)→q
is a tautology.
A valid argument does not require that the premises are actually true in the real world. It requires that no truth-value assignment makes all premises true while making the conclusion false. Thus, to disprove validity, one searches for a row where every premise has value 1 and the conclusion has value 0. To prove validity, one may show directly that such a row cannot occur. This is why valid arguments and logical implication are closely connected.
A valid argument fails only if one row makes every premise true while the conclusion is false. Use the controls to choose truth values for the statements in the Roger studies argument. The display evaluates each premise and the conclusion for that single row. Notice that a row with a false premise does not disprove validity, but a row with all true premises and a false conclusion would be a counterexample.
Visual laboratory
Validity Row Explorer
VALIDITY ROW EXPLORER
Dynamic Sandbox
Initializing Workspace
Guided example07
Roger Studies Argument
Let p mean “Roger studies,” q mean “Roger plays tennis,” and r mean “Roger passes discrete mathematics.” Consider the argument
p→r,¬q→p,¬r∴q.
The corresponding implication form is
[(p→r)∧(¬q→p)∧¬r]→q.
Assume that all premises are true. Since ¬r is true, r is false. Since p→r is true and r is false, p must be false. Since ¬q→p is true and p is false, ¬q must be false. Therefore q is true. Hence, the argument is valid.
Core definition08
Logical Implication
Let p and q be statements. If p→q is a tautology, then p is said to logically imply q. This is denoted by
p⇒q.
Thus p⇒q means that whenever p is true, q must also be true.
Core definition09
Failure of Logical Implication
Let p and q be statements. The statement p does not logically imply q, written
p⇒q,
if p→q is not a tautology. Equivalently, there exists at least one truth-value assignment for which p is true and q is false.
Key result10
Logical Equivalence by Mutual Logical Implication
Let p and q be statements. Then p and q are logically equivalent if and only if p logically implies q and q logically implies p. That is,
p⇔qif and only if(p⇒q)and(q⇒p).
Reasoning pathway11
Given that p and q are statements.
To prove that p⇔q if and only if (p⇒q) and (q⇒p).
[1] Suppose p⇔q. Then p and q have the same truth value for every truth-value assignment. Therefore, whenever p is true, q is true, so p⇒q. Also, whenever q is true, p is true, so q⇒p. Hence, (p⇒q) and (q⇒p).
[2] Conversely, suppose p⇒q and q⇒p. Then whenever p is true, q is true, and whenever q is true, p is true. Therefore p and q have the same truth value under every truth-value assignment.
Hence p⇔q if and only if (p⇒q) and (q⇒p).
□
Guided example12
Logical Implication from Disjunction
For any statements p and q,
p⇒(p∨q).
Given that p is true. To prove that p∨q is true. Since a disjunction is true when at least one component is true, p∨q is true regardless of the truth value of q. Therefore p→(p∨q) is a tautology. Hence p⇒(p∨q).
Guided example13
De Morgan Implications
For any statements p and q,
¬(p∧q)⇒(¬p∨¬q)
and
(¬p∨¬q)⇒¬(p∧q).
Therefore,
¬(p∧q)⇔(¬p∨¬q).
This shows that De Morgan’s law may be expressed through two opposite logical implications.
Worked problem14
Verify that [p∧((p∧r)→s)]→(r→s) is a tautology.
Complete solution15
Let p and (p∧r)→s be true. To prove that r→s is true, assume that r is true. Since p is true and r is true, p∧r is true. Since (p∧r)→s is true and p∧r is true, s is true. Therefore, whenever r is true, s is true. Hence r→s is true, and the given implication is a tautology.
Worked problem16
Verify that [(p→q)∧(q→r)]→(p→r) is a logical implication.
Complete solution17
Let p→q and q→r be true. To prove that p→r is true, assume that p is true. Since p→q is true and p is true, q is true. Since q→r is true and q is true, r is true. Therefore, whenever p is true, r is true. Hence p→r is true, and the given implication is a tautology.
Mathematical insight18
Truth tables can always be used to test valid arguments and logical implication. However, if an argument contains n primitive statements, then its truth table contains 2n rows. For arguments with many primitive statements, a truth table becomes lengthy. This motivates the use of rules of inference, which prove validity without listing every truth-value assignment.
Independent practice19
Establish the validity of each argument by means of a truth table: (1) [p∧(p→q)∧r]→[(p∨q)→r]. (2) [((p∧q)→r)∧¬q∧(p→¬r)]→(¬p∨¬q). (3) [[p∨(q∨r)]∧¬q]→(p∨r).
Answer20
Each statement is tested by constructing a full truth table and checking whether the final conditional column contains only 1's. In each case, if no row has true premises and false conclusion, the argument is valid.
Independent practice21
Use truth tables to verify the following logical implications: (1) [(p→q)∧(q→r)]→(p→r). (2) [(p→q)∧¬q]→¬p. (3) [(p∨q)∧¬p]→q. (4) [(p→r)∧(q→r)]→[(p∨q)→r].
Answer22
The four implications correspond respectively to the Law of the Syllogism, Modus Tollens, Disjunctive Syllogism, and Proof by Cases. Each is a tautology.
Questions to consolidate
Frequently Asked Questions
3
1Does a valid argument require true premises?
No. Validity says that if all premises are true, then the conclusion must be true.
2What makes an argument invalid?
One truth-value assignment with all premises true and the conclusion false makes the argument invalid.
3Is logical implication the same as an ordinary conditional?
Logical implication means the corresponding conditional is a tautology, not merely true in one assignment.
Continue learning
Practise Logical Consequence
Review valid arguments and logical implication before learning the named rules used to build formal deductions.