Skip to main content

Section 2.4 Properties of Logic

Subsection 2.4.1 De Morgan's Laws

In general, the negation of a conjunction of two statements, \(P \land Q\text{,}\) is logically equivalent to the disjunction of their negations, or \(\neg P \lor \neg Q\text{.}\) This can be verified using truth tables,

\begin{equation*} \begin{array}{cc|ccc|cc} P \amp Q \amp \neg P \amp \neg Q \amp P \land Q \amp \neg (P \land Q) \amp \neg P \lor \neg Q \\ \hline T \amp T \amp F \amp F \amp T \amp F \amp F \\ \hline T \amp F \amp F \amp T \amp F \amp T \amp T \\ \hline F \amp T \amp T \amp F \amp F \amp T \amp T \\ \hline F \amp F \amp T \amp T \amp F \amp T \amp T \end{array} \end{equation*}

Notice that the two right-most columns have the same truth values. Similarly, in general, the negation of a disjunction of two statements, \(P \lor Q\text{,}\) is logically equivalent to the conjunction of their negations, or \(\neg P \land \neg Q\text{.}\) Again, using a truth table,

\begin{equation*} \begin{array}{cc|ccc|cc} P \amp Q \amp \neg P \amp \neg Q \amp P \lor Q \amp \neg (P \lor Q) \amp \neg P \land \neg Q \\ \hline T \amp T \amp F \amp F \amp T \amp F \amp F \\ \hline T \amp F \amp F \amp T \amp T \amp F \amp F \\ \hline F \amp T \amp T \amp F \amp T \amp F \amp F \\ \hline F \amp F \amp T \amp T \amp F \amp T \amp T \end{array} \end{equation*}

In summary,

These logical equivalences are named after Augustus De Morgan (1806-1871), British mathematician, who was the first to state them in formal mathematical terms.

Subsection 2.4.2 Properties of Compound Statements

This means that parentheses are unnecessary for a sequence of only conjunctions or only disjunctions.

This intuitively means that order doesn't matter for disjunctions and conjunctions.

Subsection 2.4.3 Tautologies and Contradictions

Definition 2.4.5.

A tautology is a statement form that is always true regarless of the truth values of the individual statements substituted for its statement variables. A statement whose form is a tautology is a tautological statement.

A contradiction is a statement form that is always false regarless of the truth values of the individual statements substituted for its statement variables. A statement whose form is a contradiction is a contradictiory statement.

For example, \(P \lor \neg P\) is a tautology, and \(P \land \neg P\) is a contradiction. If \(T\) is a tautology, then \(P \land T \equiv P\) and \(P \lor T \equiv T\text{.}\) If \(C\) is a contradiction, then \(P \land C = C\) and \(P \lor C = P\text{.}\)

Subsection 2.4.4 Truth Tables for Compound Propositions

In general, there are \(2^n\) rows in a truth table for \(n\) simple statements.

Subsection 2.4.5 Logical Inference

Logical inference rules are basically tautologies. They are used to construct valid arguments. The validity of an argument is completely dependent on the validity of its logical form.

  • Modus Ponens, \(((P \rightarrow Q) \land P) \rightarrow Q\)

  • Modus Tollens, \(((P \rightarrow Q) \land (\neg Q)) \rightarrow (\neg P)\)

  • Elimination, \(((P \lor Q) \land (\neg P)) \rightarrow Q\)

Modus Ponens is basically the definition of conditional. Modus Tollens works because the contrapositive is logically equivalent to the original conditional.

  • Transitivity (hypothetical syllogism), \(\brac{(P \rightarrow Q) \land (Q \rightarrow R)} \rightarrow (P \rightarrow R)\)

  • Elimination (disjunctive syllogism), \(\brac{(P \lor Q) \land \neg P} \rightarrow Q\)

  • Addition, \(P \rightarrow (P \lor Q)\)

  • Simplication, \((P \land Q) \rightarrow P\text{.}\)

  • Resolution, \(\brac{(\neg P \lor R) \land (P \lor Q)} \rightarrow (Q \lor R)\)