Skip to main content
Mathematics LibreTexts

1.6: Tautologies and contradictions

  • Page ID
    23876
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Tautologies and contradictions

    Most assertions are true in some situations, and false in others. But some assertions are true in all situations, and others are false in all situations.

    Definition \(1.6.1\).
    • A tautology is an assertion of Propositional Logic that is true in all situations; that is, it is true for all possible values of its variables.
    • A contradiction is an assertion of Propositional Logic that is false in all situations; that is, it is false for all possible values of its variables.
    Example \(1.6.2\).

    The assertion \(A \lor B\) is true when \(A\) is true (or \(B\) is true), but it is false when \(A\) and \(B\) are both false. Thus, the assertion is sometimes true and sometimes false; it is neither a contradiction nor a tautology.

    Example \(1.6.3\).

    Show that the assertion \(\bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q)\) is neither a tautology nor a contradiction.

    Scratchwork.

    We need to find values of the variables that make the assertion true, and other values that make the assertion false.

    It is easy to make the assertion true, because an implication is true whenever its conclusion is true, so we just need to make \(P \Rightarrow \lnot Q\) true. And we can make this true by making \(\lnot Q\) true. So we let \(Q\) be false. Then we can let \(P\) and \(R\) be whatever we want: it’s probably simplest to let them both be false (the same as \(Q\)).

    To make the assertion false, we need to make its hypothesis true and its conclusion false.

    • Let’s start with the conclusion \(P \Rightarrow \lnot Q\). To make this false, we need to make \(P\) true and \(\lnot Q\) false. Thus, we let \(P = \mathsf{T}\) and \(Q = \mathsf{T}\).
    • Now, we consider the hypothesis \(P \& (\lnot Q \lor \lnot R)\). Fortunately, we already decided to make \(P\) true, but we also need to make \(\lnot Q \lor \lnot R\) true. Since we already decided to make \(Q\) true, we need to make \(\lnot R\) true, so we let \(R = \mathsf{F}\).

    Solution

    If \(P\), \(Q\), and \(R\) are all false, then \[\begin{aligned} \bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q) & \quad = \quad \bigl( \mathsf{F} \& (\lnot \mathsf{F} \lor \lnot \mathsf{F}) \bigr) \Rightarrow (\mathsf{F} \Rightarrow \lnot \mathsf{F}) \\& \quad = \quad \bigl( \mathsf{F} \& (\mathsf{T} \lor \mathsf{T}) \bigr) \Rightarrow (\mathsf{F} \Rightarrow \mathsf{T}) \\& \quad = \quad \bigl( \mathsf{F} \& \mathsf{T} \bigr) \Rightarrow (\mathsf{T}) \\& \quad = \quad \mathsf{F} \Rightarrow \mathsf{T} \\& \quad = \quad \mathsf{T} , \end{aligned}\]
    whereas if \(P\) and \(Q\) are true, but \(R\) is false, then \[\begin{aligned} \bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q) & \quad = \quad \bigl( \mathsf{T} \& (\lnot \mathsf{T} \lor \lnot \mathsf{F}) \bigr) \Rightarrow (\mathsf{T} \Rightarrow \lnot \mathsf{T}) \\& \quad = \quad \bigl( \mathsf{T} \& (\mathsf{F} \lor \mathsf{T}) \bigr) \Rightarrow (\mathsf{T} \Rightarrow \mathsf{F}) \\& \quad = \quad \bigl( \mathsf{T} \& \mathsf{T} \bigr) \Rightarrow (\mathsf{F}) \\& \quad = \quad \mathsf{T} \Rightarrow \mathsf{F} \\& \quad = \quad \mathsf{F} . \end{aligned}\]
    Thus, the assertion is sometimes true and sometimes false, so it is neither a tautology nor a contradiction.

    Exercise \(1.6.4\).

    Show that each of the following assertions is neither a tautology nor a contradiction.

    1. \(A \Rightarrow (A \& B)\)
    2. \((A \lor B) \Rightarrow A\)
    3. \((A \Leftrightarrow B) \lor (A \& \lnot B)\)
    4. \((X \Rightarrow Z) \Rightarrow (Y \Rightarrow Z)\)
    5. \(\bigl( P \& \lnot(Q \& R) \bigr) \lor (Q {\Rightarrow} R)\)
    Example \(1.6.5\) (Law of Excluded Middle).

    It is easy to see that the assertion \(A \lor \lnot A\) is true when \(A\) is true, and also when \(A\) is false. Thus, the assertion is true for both possible values of the variable \(A\), so it is a tautology:

    Solution

    \[\begin{aligned} A \lor \lnot A \text{ is a tautology} \end{aligned}\]

    Remark \(1.6.6\).

    The above tautology is called the “Law of Excluded Middle” because it says every assertion is either true or false: there is no middle ground where an assertion is partly true and partly false.

    Example \(1.6.7\).

    It is easy to see that the assertion \(A \& \lnot A\) is false when \(A\) is true, and also when \(A\) is false. Thus, the assertion is false for both possible values of the variable \(A\), so it is a contradiction:

    Solution

    \[\begin{aligned} A \& \lnot A \text{ is a contradiction} \end{aligned}\]

    Remark \(1.6.8\).

    The assertions \(A \lor \lnot A\) and \(A \& \lnot A\) are the most important (and most common) examples of tautologies and contradictions. However, they will usually arise with some other expression plugged into the variable \(A\). For example, by letting \(A\) be the assertion \((P \lor Q) \Rightarrow R\), we obtain the tautology \[\bigl( (P \lor Q) \Rightarrow R \bigr) \lor \lnot \bigl( (P \lor Q) \Rightarrow R \bigr) ,\]
    which is a more complicated example of the Law of Excluded Middle, and we also obtain the contradiction \[\bigl( (P \lor Q) \Rightarrow R \bigr) \& \lnot \bigl( (P \lor Q) \Rightarrow R \bigr) .\]

    Example \(1.6.9\).

    We can also give examples in English, rather than in symbols; consider these assertions:

    1. It is raining.
    2. Either it is raining, or it is not.
    3. It is both raining and not raining.

    In order to know whether Assertion 27 is true, you would need to check the weather. Logically speaking, it could be either true or false, so it is neither a tautology nor a contradiction.

    Assertion 28 is different. You do not need to look outside to know that it is true, regardless of what the weather is like. So it is a tautology.

    You do not need to check the weather to know about Assertion 29, either. It must be false, simply as a matter of logic. It might be raining here and not raining across town, or it might be raining now but stop raining even as you read this, but it is impossible for it to be both raining and not raining in any given situation (at any particular time and place). Thus, the third assertion is false in every possible situation; it is a contradiction.

    Exercise \(1.6.10\).

    Which of the following are possible? For those that are possible, give an example. For those that are not, explain why.

    1. A valid deduction whose conclusion is a contradiction.
    2. A valid deduction whose conclusion is a tautology.
    3. A valid deduction that has a tautology as one of its hypotheses.
    4. A valid deduction that has a contradiction as one of its hypotheses.
    5. An invalid deduction whose conclusion is a contradiction.
    6. An invalid deduction whose conclusion is a tautology.
    7. An invalid deduction that has a tautology as one of its hypotheses.
    8. An invalid deduction that has a contradiction as one of its hypotheses.

    This page titled 1.6: Tautologies and contradictions is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

    • Was this article helpful?