Some logical statements are “the same.” For example, in the last section, we discussed the fact that a conditional and its contrapositive have the same logical content. Wouldn't we be justified in writing something like the following? \begin{equation*} A \implies B \; = \; {\lnot}B \implies {\lnot}A \end{equation*}

Well, one pretty serious objection to doing that is that the equals sign (\(=\)) has already got a job; it is used to indicate that two numerical quantities are the same. What we're doing here is really sort of a different thing! Nevertheless, there is a concept of “sameness” between certain compound statements, and we need a symbolic way of expressing it. There are two notations in common use. The notation that seems to be preferred by logicians is the biconditional (\(\iff\)). The notation we'll use in the rest of this book is an equals sign with a bit of extra decoration on it (\(\cong\)).

Thus we can can either write \begin{equation*} (A \implies B) \; \iff \; ({\lnot}B \implies {\lnot}A) \end{equation*} or \begin{equation*} A \implies B \; \cong \; {\lnot}B \implies {\lnot}A. \end{equation*}

I like the latter, but use whichever form you like — no one will have any problem understanding either.

The formal definition of logical equivalence, which is what we've been describing, is this: two compound sentences are logically equivalent if in a truth table (that contains all possible combinations of the truth values of the predicate variables in its rows) the truth values of the two sentences are equal in every row.

One could, in principle, verify all logical equivalences by filling out truth tables. Indeed, in the exercises for this section we will ask you to develop a certain facility at this task. While this activity can be somewhat fun, and many of my students want the filling-out of truth tables to be a significant portion of their midterm exam, you will probably eventually come to find it somewhat tedious. A slightly more mature approach to logical equivalences is this: use a set of basic equivalences — which themselves may be verified via truth tables — as the basic rules or laws of logical equivalence, and develop a strategy for converting one sentence into another using these rules. This process will feel very familiar, it is like “doing” algebra, but the rules one is allowed to use are subtly different.

First we have the commutative laws, one each for conjunction and disjunction. It's worth noting that there isn't a commutative law for implication.

The commutative property of conjunction says that \(A \land B \cong B \land A\). This is quite an apparent statement from the perspective of linguistics. Surely it's the same thing to say “the weather is cold and snowy” as it is to say “the weather is snowy and cold.” This commutative property is also clear from the perspective of digital logic circuits.

The commutative property of disjunctions is equally transparent from the perspective of a circuit diagram.

The associative laws also have something to do with what order operations are done. One could think of the difference in the following terms: Commutative properties involve spatial or physical order and the associative properties involve temporal order. The associative law of addition could be used to say we'll get the same result if we add 2 and 3 first, then add 4, or if we add 2 to the sum of 3 and 4 (i.e. that \((2+3)+4\) is the same as \(2+(3+4)\).) Note that physically, the numbers are in the same order (2 then 3 then 4) in both expressions but that the parentheses indicate a precedence in when the plus signs are evaluated.

The associative law of conjunction states that \(A \land (B \land C) \cong (A \land B) \land C\). In visual terms, this means the following two circuit diagrams are equivalent.

The associative law of disjunction states that \(A \lor (B \lor C) \cong (A \lor B) \lor C\). Visually, this looks like:

The next type of basic logical equivalences we'll consider are the so-called distributive laws. Distributive laws involve the interaction of two operations, when we distribute multiplication over a sum, we effectively replace one instance of an operand and the associated operator, with two instances, as is illustrated below.

The logical operators \(\land\) and \(\lor\) each distribute over the other. Thus we have the distributive law of conjunction over disjunction, which is expressed in the equivalence \(A \land (B \lor C) \cong (A \land B) \lor (A \land C)\) and in the following digital logic circuit diagram.

We also have the distributive law of disjunction over conjunction which is given by the equivalence \(A \lor (B \land C) \cong (A \lor B) \land (A \lor C)\) and in the circuit diagram:

Traditionally, the laws we've just stated would be called left-distributive laws and we would also need to state that there are right-distributive laws that apply. Since, in the current setting, we have already said that the commutative law is valid, this isn't really necessary.

The next set of laws we'll consider come from trying to figure out what the distribution of a minus sign over a sum (\(-(x+y) = -x + -y\)) should correspond to in Boolean algebra. At first blush one might assume the analogous thing in Boolean algebra would be something like \({\lnot}(A \land B) \cong {\lnot}A \land {\lnot}B\), but we can easily dismiss this by looking at a truth table.

What actually works is a set of rules known as DeMorgan's laws, which basically say that you distribute the negative sign but you also must change the operator. As logical equivalences, DeMorgan's laws are \begin{equation*} {\lnot}(A \land B) \; \cong \; {\lnot}A \lor {\lnot}B \end{equation*} and \begin{equation*} {\lnot}(A \lor B) \; \cong \; {\lnot}A \land {\lnot}B. \end{equation*}

In ordinary arithmetic there are two notions of “inverse.” The negative of a number is known as its additive inverse and the reciprocal of a number is its multiplicative inverse. These notions lead to a couple of equations, \begin{equation*} x + -x = 0 \end{equation*} and \begin{equation*} x \cdot \frac{1}{x} = 1. \end{equation*}

Boolean algebra only has one “inverse” concept, the denial of a predicate (i.e. logical negation), but the equations above have analogues, as do the symbols \(0\) and \(1\) that appear in them. First, consider the Boolean expression \(A \lor {\lnot}A\). This is the logical or of a statement and its exact opposite; when one is true the other is false and vice versa. But, the disjunction \(A \lor {\lnot}A\), is always true! We use the symbol \(t\) (which stands for tautology) to represent a compound sentence whose truth value is always true. A tautology (\(t\)) is to Boolean algebra something like a zero (\(0\)) is to arithmetic. Similar thinking about the Boolean expression \(A \land {\lnot}A\) leads to the definition of the symbol \(c\) (which stands for contradiction) to represent a sentence that is always false. The rules we have been discussing are known as complementarity laws: \begin{equation*} A \lor {\lnot}A \; \cong \; t \mbox{ and } A \land {\lnot}A \; \cong \; c \end{equation*}

Now that we have the special logical sentences represented by \(t\) and \(c\) we can present the so-called identity laws, \(A \land t \cong A\) and \(A \lor c \cong A\). If you “and” a statement with something that is always true, this new compound has the exact same truth values as the original. If you “or” a statement with something that is always false, the new compound statement is also unchanged from the original. Thus performing a conjunction with a tautology has no effect — sort of like multiplying by 1. Performing a disjunction with a contradiction also has no effect — this is somewhat akin to adding 0.

The number 0 has a special property: \(0 \cdot x = 0\) is an equation that holds no matter what \(x\) is. This is known as a domination property. Note that there isn't a dominance rule that involves 1. On the Boolean side, both the symbols \(t\) and \(c\) have related domination rules. \begin{equation*} A \lor t \cong t \mbox{ and } A \land c \cong c \end{equation*}

In mathematics the word idempotent is used to describe situations where a power of a thing may be equal to that thing. For example, because \((-1)^3 = -1\), we say that \(-1\) is an idempotent. Both of the Boolean operations have idempotence relations that just always work (regardless of the operand). In ordinary algebra idempotents are very rare (\(0\), \(1\) and \(-1\) are the only ones that come to mind), but in Boolean algebra every statement is equivalent to its square — where the square of \(A\) can be interpreted either as \(A \land A\) or as \(A \lor A\). \begin{equation*} A \lor A \cong A \mbox{ and } A \land A \cong A \end{equation*}

There are a couple of properties of the logical negation operator that should be stated, though probably they seem self-evident. If you form the denial of a denial, you come back to the same thing as the original; also the symbols \(c\) and \(t\) are negations of one another. \begin{equation*} \lnot({\lnot}A) \cong A \mbox{ and } {\lnot}t \cong c \end{equation*}

Finally, we should mention a really strange property, called absorption, which states that the expressions \(A \land (A \lor B)\) and \(A \lor (A \land B)\) don't actually have anything to do with \(B\) at all! Both of the preceding statements are equivalent to \(A\). \begin{equation*} A \land (A \lor B) \cong A \mbox{ and } A \lor (A \land B) \cong A \end{equation*}

In Table 2.3.4, we have collected all of these basic logical equivalences in one place.