Logical Deduction
How to get new true proposition from other true propositions.
Discover Bridges
Study Logical Deduction
Definition 1 (Conditional \(A \rightarrow B\) (“If \(A\) then \(B\)”)). \(A \rightarrow B\) is only false if \(A\) is true but \(B\) is false.
\[\mbox{ Truth table }\qquad \begin{array}{cc|c} A & B & A \rightarrow B \\ \hline T & T& T\\ T & F & F\\ F & T & T\\ F & F & T \end{array}\]
Definition 2 (Biconditional \(A \leftrightarrow B\) (“\(A\) if and only if \(B\)”)). \(A \leftrightarrow B\) is true if and only if \(A \rightarrow B\) and \(B \rightarrow A\) is true.
\[\mbox{ Truth table }\qquad \begin{array}{cc|c} A & B & A \leftrightarrow B \\ \hline T & T& T\\ T & F & F\\ F & T & F\\ F & F & T \end{array}\]
If a conditional or biconditional is true, we have a short notation for this that is used throughout the whole field of mathematics:
Definition 3 (Implication and equivalence). If \(A \rightarrow B\) is true, we call this an implication and write: \[A \Rightarrow B \,.\] If \(A \leftrightarrow B\) is true, we call this an equivalence and write: \[A \Leftrightarrow B \,.\]
This means that we speak of equivalence of \(A\) and \(B\) if the truth values in the truth table are exactly the same. For example, we have \[A \leftrightarrow B ~~ \Leftrightarrow ~~ (A \rightarrow B) \wedge (B \rightarrow A) \,.\]
Now one can ask: What to do with truth-tables? Let us show that \(\neg B \rightarrow \neg A\) is the same as \(A \rightarrow B\). \[\mbox{ Truth table }\qquad \begin{array}{cc|cc|c} A & B & \neg A & \neg B &\neg B \rightarrow \neg A \\ \hline T & T & F & F & T\\ T & F & F & T & F\\ F & T & T & F & T\\ F & F & T & T & T \end{array}\] Therefore: \[(A \rightarrow B) ~~ \Leftrightarrow ~~ (\neg B \rightarrow \neg A) \,.\] This is the proof by contraposition:
“Assume that \(B\) does not hold, then we can show that \(A\) cannot hold as well”. Hence \(A\) implies \(B\).
Concept 4 (Contraposition). If \(A \Rightarrow B\), then also \(\neg B \Rightarrow \neg A\).
Rule of Thumb 5 (Contraposition). To get the contraposition \(A\Rightarrow B\), you should exchange \(A\) and \(B\) and set a \(\neg\)-sign in front of both: \(\ \neg B\Rightarrow\neg A\).
It is clear: The contraposition of the contraposition is again \(A\Rightarrow B\).
The contraposition is an example of a deduction rule, which basically tells us how to get new true proposition from other true propositions. The most important deduction rules are given just by using the implication.
Concept 6 (Modus ponens). If \(A \Rightarrow B\) and \(A\) is true, then also \(B\) is true.
Concept 7 (Chain syllogism). If \(A \Rightarrow B\) and \(B \Rightarrow C\), then also \(A \Rightarrow C\).
Concept 8 (Reductio ad absurdum). If \(A \Rightarrow B\) and \(A \Rightarrow \neg B\), then \(\neg A\) is true.
One can easily prove these rules by truth tables. However, here we do not state every deduction in this formal manner. We may still use deduction in the intuitive way as well. Try it here:
Exercise 9. Let “All birds can fly” be a true proposition (axiom). Are the following deductions correct?
If Seagulls are birds, then Seagulls can fly.
If Penguins are birds, then Penguins can fly.
If Butterflies are birds, then Butterflies can fly.
If Butterflies can fly, then Butterflies are birds.
Discuss your questions by typing below.
Solve the WeBWorK Exercise
The data for the interactive network on this webpage was generated with pntfx Copyright Fabian Gabel and Julian Großmann. pntfx is licensed under the MIT license. Visualization of the network uses the open-source graph theory library Cytoscape.js licensed under the MIT license.