# Logical Deduction

How to get new true proposition from other true propositions.

## Discover Bridges #

Click on an **arrow** to get a description of the connection!

Click on an **arrow** to get a description of the connection!

__Show requirements__

__Show requirements__

Concept | Content |
---|---|

Logical Statements and Operations | Logic is the foundation to formulate proofs and to understand the language of mathematics. |

__Show consequences__

__Show consequences__

Concept | Content |
---|---|

Cauchy Criterion | A series converges if its partial sums form a Cauchy sequence. As a consequence, for a convergent series, the underlying sequence necessarily needs to converge to zero. |

Leibniz Criterion | A convergence criterion for sums based on an alternating sequence. |

Predicates and Quantifiers | Formal mathematical statements are often built by predicates. |

## 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.
}