2.2. Boolean Algebra

So far we have discussed how to write and interpret propositions. This section deals with manipulating them. For this, we need algebra. Ordinary algebra, of the sort taught in high school, is about manipulating numbers, variables that represent numbers, and operators such as \(+\) and \(\times\) that apply to numbers. Now, we need an algebra that applies to logical values, propositional variables, and logical operators. The first person to think of logic in terms of algebra was the mathematician, George Boole, who introduced the idea in a book that he published in 1854. The algebra of logic is now called Boolean algebra in his honour.

Person

George Boole (1815–1864) was a largely self-taught British mathematician, philosopher and logician, most of whose short career was spent as the first professor of mathematics at Queen’s College, Cork in Ireland. He worked in the fields of differential equations and algebraic logic, and is best known as the author of The Laws of Thought (1854). Among TU Delft students he is best known for the room named after him in the EEMCS building 36.

Boolean logic is credited with laying the foundations for the information age: essentially, computer science. Boole maintained that: ‘’No general method for the solution of questions in the theory of probabilities can be established which does not explicitly recognise, not only the special numerical bases of the science, but also those universal laws of thought which are the basis of all reasoning, and which, whatever they may be as to their essence, are at least mathematical as to their form.’’

Source: en.wikipedia.org/wiki/George_Boole.

The algebra of numbers includes a large number of rules for manipulating expressions. The distributive law, for example, says that \(x(y+z)=xy+xz\), where \(x\), \(y\), and \(z\) are variables that stand for any numbers or numerical expressions. This law means that whenever you see something of the form \(xy+xz\) in a numerical expression, you can substitute \(x(y+z)\) without changing the value of the expression, and vice versa. Note that the equals sign in \(x(y+z)=xy+xz\) means ‘’has the same value as, no matter what numerical values \(x\), \(y\), and \(z\) have’’.

In Boolean algebra, we work with logical values instead of numerical values. There are only two logical values, true and false. We will write these values as \(\mathbb{T}\) and \(\mathbb{F}\) or \(1\) and \(0\). The symbols \(\mathbb{T}\) and \(\mathbb{F}\) play a similar role in Boolean algebra to the role that constant numbers such as 1 and 3.14159 play in ordinary algebra. Instead of the equals sign, Boolean algebra uses logical equivalence, \(\equiv\), which has essentially the same meaning.^[1] For example, for propositions \(p\), \(q\), and \(r\), the \(\equiv\) operator in \(p\wedge(q\wedge r)\equiv(p\wedge q)\wedge r\) means ‘’has the same value as, no matter what logical values \(p\), \(q\), and \(r\) have’’.

2.2.1. Basics of Boolean Algebra

Many of the rules of Boolean algebra are fairly obvious, if you think a bit about what they mean. Even those that are not obvious can be verified easily by using a truth table. Table 2.2 lists the most important of these laws. You will notice that all these laws, except the first, come in pairs: each law in the pair can be obtained from the other by interchanging \(\wedge\) with \(\vee\) and \(\mathbb{T}\) with \(\mathbb{F}\). This cuts down on the number of facts you have to remember.^[2]

Table 2.2 Laws of Boolean Algebra. These laws hold for any propositions \(p\), \(q\), and \(r\).

Double negation	\(\lnot(\lnot p)\equiv p\)
Excluded middle	\(p\vee\lnot p\equiv\mathbb{T}\)
Contradiction	\(p\wedge\lnot p\equiv\mathbb{F}\)
Identity laws	\(\mathbb{T}\wedge p\equiv p\)
	\(\mathbb{F}\vee p \equiv p\)
Idempotent laws	\(p\wedge p\equiv p\)
	\(p\vee p\equiv p\)
Commutative laws	\(p\wedge q\equiv q\wedge p\)
	\(p\vee q\equiv q\vee p\)
Associative laws	\((p\wedge q)\wedge r\equiv p\wedge(q\wedge r)\)
	\((p\vee q)\vee r\equiv p\vee(q\vee r)\)
Distributive laws	\(p\wedge(q\vee r)\equiv (p\wedge q)\vee (p\wedge r)\)
	\(p\vee(q\wedge r)\equiv (p\vee q)\wedge (p\vee r)\)
DeMorgan’s laws	\(\lnot(p\wedge q)\equiv (\lnot p)\vee(\lnot q)\)
	\(\lnot(p\vee q)\equiv (\lnot p)\wedge(\lnot q)\)

Just as an example, let’s verify the first rule in the table, the Law of Double Negation.
This law is just the old, basic grammar rule that two negatives make a positive. Although the way this rule applies to English is questionable, if you look at how it is used—no matter what the grammarian says, ‘’I can’t get no satisfaction’’ doesn’t really mean ‘’I can get satisfaction’’—the validity of the rule in logic can be verified just by computing the two possible cases: when \(p\) is true and when \(p\) is false. When \(p\) is true, then by the definition of the \(\lnot\) operator, \(\lnot p\) is false. But then, again by the definition of \(\lnot\), the value of \(\lnot(\lnot p)\) is true, which is the same as the value of \(p\). Similarly, in the case where \(p\) is false, \(\lnot(\lnot p)\) is also false. Organized into a truth table, this argument takes the rather simple form

\(p\)	\(\lnot p\)	\(\lnot(\lnot p)\)
0	1	0
1	0	1

The fact that the first and last columns are identical shows the logical equivalence of \(p\) and \(\lnot(\lnot p)\). The point here is not just that \(\lnot(\lnot p)\equiv p\), but also that this logical equivalence is valid because it can be verified computationally based just on the relevant definitions. Its validity does not follow from the fact that ‘’it’s obvious’’ or ‘’it’s a well-known rule of grammar’’.

Note

Students often ask ‘’Why do I have to prove something when it’s obvious?’’ The point is that logic—and mathematics more generally—is its own little world with its own set of rules. Although this world is related somehow to the real world, when you say that something is obvious (in the real world), you aren’t playing by the rules of the world of logic. The real magic of mathematics is that by playing by its rules, you can come up with things that are decidedly not obvious, but that still say something about the real world or the computational world—often, something interesting and important.

Each of the rules in Table 2.2 can be verified in the same way, by making a truth table to check all the possible cases. In one of the pencasts of this course we further discuss how to check the equivalence of two propositions using truth tables.

2.2.2. Substitution laws

It’s important to understand that the propositional variables in the laws of Boolean algebra can stand for any propositions, including compound propositions.
It is not just true, as the Double Negation Law states, that \(\lnot(\lnot p)\equiv p\). It is also true that \(\lnot(\lnot q)\equiv q\), that \(\lnot(\lnot(p\wedge q))\equiv (p\wedge q)\), that \(\lnot(\lnot(p\rightarrow(q\wedge \lnot p)))\equiv(p\rightarrow (q\wedge\lnot p))\), and an infinite number of other statements of the same form. Here, a ‘statement of the same form’ is one that can be obtained by substituting something for \(p\) in both places where it occurs in \(\lnot(\lnot p)\equiv p\). How can I be sure that all these infinitely many statements are valid when all that I’ve checked is one little two-line truth table? The answer is that any given proposition, \(Q\), no matter how complicated, has a particular truth value, either true or false. So, the question of the validity of \(\lnot(\lnot Q)\equiv Q\) always reduces to one of the two cases I already checked in the truth table. (Note that for this argument to be valid, the same \(Q\) must be substituted for \(p\) in every position where it occurs.) While this argument may be ‘obvious’, it is not exactly a proof, but for now we will just accept the validity of the following theorem:

Theorem 2.1 (First Substitution Law)

Suppose that \(Q\) is any proposition, and that \(p\) is a propositional variable. Consider any tautology. If \((Q)\) is substituted for \(p\) in all places where \(p\) occurs in the tautology, then the result is also a tautology.

Since logical equivalence is defined in terms of tautology, it is also true that when \((Q)\) is substituted for \(p\) in a logical equivalence, the result is again a logical equivalence.^[3]

The First Substitution Law lets you do algebra! For example, you can substitute \(p\rightarrow q\) for \(p\) in the law of double negation, \(\lnot(\lnot p)\equiv p\). This allows you to ‘simplify’ the expression \(\lnot(\lnot(r\rightarrow q))\) to \(r\rightarrow q\) with confidence that the resulting expression has the same logical value as the expression you started with. (That’s what it means for \(\lnot(\lnot(r\rightarrow q))\) and \(r\rightarrow q\) to be logically equivalent.) You can play similar tricks with all the laws in Table 2.2. Even more important is the Second Substitution Law, which says that you can substitute an expression for a logically equivalent expression, wherever it occurs. Once again, we will accept this as a theorem without trying to prove it here. It is surprisingly hard to put this law into words:

Theorem 2.2 (Second Substitution Law)

Suppose that \(P\) and \(Q\) are any propositions such that \(P\equiv Q\). Suppose that \(R\) is any compound proposition in which \((P)\) occurs as a sub-proposition. Let \(R'\) be the proposition that is obtained by substituting \((Q)\) for that occurrence of \((P)\) in \(R\). Then \(R\equiv R'\).

Note that in this case, the theorem does not require \((Q)\) to be substituted for every occurrence of \((P)\) in \(R\). You are free to substitute for one, two, or as many occurrences of \((P)\) as you like, and the result is still logically equivalent to \(R\).

The Second Substitution Law allows us to use the logical equivalence \(\lnot(\lnot p)\equiv p\) to ‘simplify’ the expression \(q\rightarrow (\lnot(\lnot p))\) by substituting \(\lnot(\lnot p)\) for \(p\). The resulting expression, \(q\rightarrow p \), is logically equivalent to the original \(q\rightarrow (\lnot(\lnot p))\). Once again, we have to be careful about parentheses: The fact that \(p\vee p\equiv p\) does not allow us to rewrite \(q\wedge p\vee p\wedge r\) as \(q\wedge p\wedge r\). The problem is that \(q\wedge p\vee p\wedge r\) means \((q\wedge p)\vee (p\wedge r)\), so that \((p\vee p)\) is not a sub-expression. This again underlines the importance of always writing parentheses in your propositional formulas.

2.2.3. Simplifications

The final piece of algebra in Boolean algebra is the observation that we can chain logical equivalences together. That is, from \(P\equiv Q\) and \(Q\equiv R\), it follows that \(P\equiv R\). This is really just a consequence of the Second Substitution Law. The equivalence \(Q\equiv R\) allows us to substitute \(R\) for \(Q\) in the statement \(P\equiv Q\), giving \(P\equiv R\). (Remember that, by Definition 2.5, logical equivalence is defined in terms of a proposition.) This means that we can show that two compound propositions are logically equivalent by finding a chain of logical equivalences that lead from one to the other.

Here is an example of such a chain of logical equivalences using Theorem 2.2:

\[\begin{split}\begin{align*} p\wedge(p\rightarrow q) &\equiv p\wedge(\lnot p\vee q) &&\text{definition of $p\rightarrow q$} \\ &\equiv (p\wedge \lnot p)\vee (p\wedge q) &&\text{Distributive Law}\\ &\equiv \mathbb{F}\vee(p\wedge q) &&\text{Law of Contradiction}\\ &\equiv (p\wedge q) &&\text{Identity Law}\\ \end{align*}\end{split}\]

Each step in the chain has its own justification. In several cases, a substitution law is used without stating as much. In the first line, for example, the definition of \(p\rightarrow q\) is that \(p\rightarrow q\equiv \lnot p\vee q\). The Second Substitution Law allows us to substitute \((\lnot p\vee q)\) for \((p\rightarrow q)\). In the last line, we implicitly applied the First Substitution Law to the Identity Law, \(\mathbb{F}\vee p\equiv p\), to obtain \(\mathbb{F}\vee(p\wedge q)\equiv (p\wedge q)\).

The chain of equivalences in the above example allows us to conclude that \(p\wedge(p\rightarrow q)\) is logically equivalent to \(p\wedge q\). This means that if you were to make a truth table for these two expressions, the truth values in the column for \(p\wedge(p\rightarrow q)\) would be identical to those in the column for \(p\wedge q\). We know this without actually making the table. Don’t believe it? Go ahead and make the truth table. In this case, the table is only be four lines long and easy enough to make. But Boolean algebra can be applied in cases where the number of propositional variables is too large for a truth table to be practical.

Example

Let’s do another example. Recall that a compound proposition is a tautology if it is true for all possible combinations of truth values of the propositional variables that it contains. But another way of saying the same thing is that \(P\) is a tautology if \(P\equiv\mathbb{T}\). So, we can prove that a compound proposition, \(P\), is a tautology by finding a chain of logical equivalences leading from \(P\) to \(\mathbb{T}\). For example (using Theorem 2.2):

\[\begin{split}\begin{align*} ((p\vee q) &\wedge \lnot p)\rightarrow q &&\\ &\equiv (\lnot((p\vee q)\wedge\lnot p))\vee q &&\text{definition of $\rightarrow$}\\ &\equiv (\lnot(p\vee q) \vee \lnot (\lnot p))\vee q &&\text{DeMorgan's Law}\\ &\equiv (\lnot(p\vee q) \vee p)\vee q &&\text{Double Negation}\\ &\equiv (\lnot (p\vee q)) \vee (p\vee q) &&\text{Associative Law for $\vee$}\\ &\equiv \mathbb{T} &&\text{Law of Excluded Middle}\\ \end{align*}\end{split}\]

From this chain of equivalences, we can conclude that \(((p\vee q) \wedge \lnot p)\rightarrow q\) is a tautology.

Now, it takes some practice to look at an expression and see which rules can be applied to it; to see \((\lnot (p\vee q)) \vee (p\vee q)\) as an application of the law of the excluded middle for example, you need to mentally substitute \((p\vee q)\) for \(p\) in the law as it is stated in Table 2.2. Often, there are several rules that apply, and there are no definite guidelines about which one you should try. This is what makes algebra something of an art.

2.2.4. More rules of Boolean algebra

It is certainly not true that all possible rules of Boolean algebra are given in Table 2.2. For one thing, there are many rules that are easy consequences of the rules that are listed there. For example, although the table asserts only that \(\mathbb{F}\vee p\equiv p\), it is also true that \(p\vee\mathbb{F}\equiv p\). This can be checked directly or by a simple calculation:

\[\begin{split}\begin{align*} p\vee\mathbb{F} &\equiv \mathbb{F}\vee p &&\text{Commutative Law}\\ &\equiv p &&\text{Identity Law as given in the table}\\ \end{align*}\end{split}\]

Additional rules can be obtained by applying the Commutative Law to other rules in the table, and we will use such rules freely in the future.

Another sort of easy extension can be applied to the Associative Law, \((p\vee q)\vee r\equiv p\vee(q\vee r)\). The law is stated for the \(\vee\) operator applied to three terms, but it generalizes to four or more terms. For example

\[\begin{split}\begin{align*} ((p\vee q)&\vee r)\vee s\\ &\equiv (p\vee q)\vee (r\vee s) &&\text{by the Associative Law for three terms}\\ &\equiv p\vee(q\vee (r\vee s)) &&\text{by the Associative Law for three terms}\\ \end{align*}\end{split}\]

We will, of course, often write this expression as \(p\vee q\vee r\vee s\), with no parentheses at all, knowing that wherever we put the parentheses the value is the same.

Tip

One other thing that you should keep in mind is that rules can be applied in either direction. The Distributive Law, for example, allows you to distribute the \(p\) in \(p\vee(q\wedge\lnot p)\) to get \((p\vee q)\wedge(p\vee\lnot p)\). But it can also be used in reverse to ‘factor out’ a term, as when you start with \((q\vee(p\rightarrow q))\wedge(q\vee(q\rightarrow p))\) and factor out the \(q\) to get \(q\vee((p\rightarrow q)\wedge(q\rightarrow p))\).

So far in this section, we have been working with the laws of Boolean algebra without saying much about what they mean or why they are reasonable. Of course, you can apply the laws in calculations without understanding them. But if you want to figure out which calculations to do, you need some understanding. Most of the laws are clear enough with a little thought. For example, if we already know that \(q\) is false, then \(p\vee q\) will be true when \(p\) is true and false when \(p\) is false. That is, \(p\vee\mathbb{F}\) has the same logical value as \(p\). But that’s just what the Identity Law for \(\vee\) says. A few of the laws need more discussion.

The Law of the Excluded Middle, \(p\vee\lnot p\equiv \mathbb{T}\), says that given any proposition \(p\), at least one of \(p\) or \(\lnot p\) must be true. Since \(\lnot p\) is true exactly when \(p\) is false, this is the same as saying that \(p\) must be either true or false.
There is no middle ground. The Law of Contradiction, \(p\wedge\lnot p\equiv\mathbb{F}\), says that it is not possible for both \(p\) and \(\lnot p\) to be true. Both of these rules are obvious.

Person

There are some who set out to question the law of there being no middle ground. Already in the 1920’s people like Tarski (who we will meet later) talked about other forms of logic where another value representing ‘unknown’ or ‘not proven’ also exists. You can also see this in some programming languages where they are referred to as ‘tri-state booleans’.

These so-called non-standard logics have been developed and have also lead to things like ‘fuzzy logic’, which some consider quite controversial. Lotfi Zadeh is credited as the first person to refer to this type of logic as fuzzy logic in his work on ‘fuzzy sets’ in 1965. Zadeh was later quoted as saying: ‘’Not being afraid to get embroiled in controversy. … That’s part of my character, too. I can be very stubborn. That’s probably been beneficial for the development of Fuzzy Logic.’’

Source: en.wikipedia.org/wiki/Lotfi_A._Zadeh

The Distributive Laws cannot be called obvious, but a few examples can show that they are reasonable. Consider the statement, ‘’This card is the ace of spades or clubs.’’ Clearly, this is equivalent to ‘’This card is the ace of spaces or this card is the ace of clubs.’’ But this is just an example of the first distributive law! For, let \(a\) represent the proposition ‘’This card is an ace’’, let \(s\) represent ‘’This card is a spade’’ and let \(c\) represent ‘’This card is a club’’. Then ‘’This card is the ace of spades or clubs’’ can be translated into logic as \(a\wedge(s\vee c)\), while ‘’This card is the ace of spades or this card is the ace of clubs’’ becomes \((a\wedge s)\vee (a\wedge c)\). And the distributive law assures us that \(a\wedge(s\vee c)\equiv(a\wedge s)\vee (a\wedge c)\). The second distributive law tells us, for example, that ‘’This card is either a joker or is the ten of diamonds’’ is logically equivalent to ‘’This card is either a joker or a ten, and it is either a joker or a diamond’’. That is, \(j\vee(t\wedge d)\equiv(j\vee t)\wedge(j\vee d)\). The distributive laws are powerful tools and you should keep them in mind whenever you are faced with a mixture of \(\wedge\) and \(\vee\) operators.

DeMorgan’s Laws must also be less than obvious, since people often get them wrong. Fortunately you get to practice them both in Reasoning & Logic, as well as in Computer Organisation, so you will soon get them right. More importantly perhaps they do also make sense. When considering \(\lnot(p\wedge q)\), you should ask yourself, how can ‘\(p\) and \(q\)’ fail to be true. It will fail to be true if either \(p\) is false or if \(q\) is false (or both). That is, \(\lnot(p \wedge q)\) is equivalent to \((\lnot p)\vee(\lnot q)\). Consider the sentence ‘’A raven is large and black.’’ If a bird is not large and black, then it is not a raven. But what exactly does it mean to be ‘not (large and black)’? How can you tell whether the assertion ‘not (large and black)’ is true of something? This will be true if it is either not large or not black. (It doesn’t have to be both—it could be large and white, it could be small and black.) Similarly, for ‘\(p\) or \(q\)’ to fail to be true, both \(p\) and \(q\) must be false. That is, \(\lnot(p\vee q)\) is equivalent to \((\lnot p)\wedge (\lnot q)\). This is DeMorgan’s second law.

Recalling that \(p\rightarrow q\) is equivalent to \((\lnot p)\vee q\), we can apply DeMorgan’s law to obtain a formula for the negation an implication:

\[\begin{split}\begin{align*} \lnot(p\rightarrow q)&\equiv \lnot((\lnot p)\vee q)\\ &\equiv (\lnot(\lnot p))\wedge(\lnot q)\\ &\equiv p\wedge\lnot q\\ \end{align*}\end{split}\]

That is, \(p\rightarrow q\) is false exactly when both \(p\) is true and \(q\) is false. For example, the negation of ‘’If you have an ace, you win’’ is ‘’You have an ace, and you don’t win’’. Think of it this way: if you had an ace and you didn’t win, then the statement ‘’If you have an ace, you win’’ was not true.

2.2.5. Exercises

Exercise (1)

Construct truth tables to demonstrate the validity of each of the distributive laws.

Exercise (2)

Construct the following truth tables:

1. Construct truth tables to demonstrate that \(\lnot (p \wedge q)\) is not logically equivalent to \((\lnot p) \wedge (\lnot q)\).

2. Construct truth tables to demonstrate that \(\lnot (p \vee q)\) is not logically equivalent to \((\lnot p) \vee (\lnot q)\).

3. Construct truth tables to demonstrate the validity of both DeMorgan’s Laws.

Exercise (3)

Construct truth tables to demonstrate that \(\lnot(p\rightarrow q)\) is not logically equivalent to any of the following.

1. \((\lnot p) \rightarrow (\lnot q)\)

2. \((\lnot p) \rightarrow q\)

3. \(p \rightarrow (\lnot q)\)

   Refer back to this section for a formula that is logically equivalent to \(\lnot(p\rightarrow q)\).

Exercise (4†)

Is \(\lnot(p\leftrightarrow q)\) logically equivalent to \((\lnot p) \leftrightarrow (\lnot q)\)?

Exercise (5)

In the algebra of numbers, there is a distributive law of multiplication over addition: \(x(y+z)=xy+xz\). What would a distributive law of addition over multiplication look like? Is it a valid law in the algebra of numbers?

Exercise (6)

The distributive laws given in Table 2.2 are sometimes called the left distributive laws. The right distributive laws say that \((p\vee q)\wedge r\equiv (p\wedge r)\vee (q\wedge r)\) and that \((p\wedge q)\vee r\equiv (p\vee r)\wedge (q \vee r)\). Show that the right distributive laws are also valid laws of Boolean algebra. (Note: In practice, both the left and the right distributive laws are referred to simply as the distributive laws, and both can be used freely in proofs.)

Exercise (7)

Show that \(p\wedge(q\vee r\vee s)\equiv (p\wedge q)\vee(p\wedge r)\vee (p\wedge s)\) for any propositions \(p\), \(q\), \(r\), and \(s\). In words, we can say that conjunction distributes over a disjunction of three terms. (Recall that the \(\wedge\) operator is called conjunction and \(\vee\) is called disjunction.) Translate into logic and verify the fact that conjunction distributes over a disjunction of four terms. Argue that, in fact, conjunction distributes over a disjunction of any number of terms.

Exercise (8)

There are two additional basic laws of logic, involving the two expression \(p\wedge\mathbb{F}\) and \(p\vee\mathbb{T}\). What are the missing laws? Show that your answers are, in fact, laws.

Exercise (9)

For each of the following pairs of propositions, show that the two propositions are logically equivalent by finding a chain of equivalences from one to the other. State which definition or law of logic justifies each equivalence in the chain.

1. \(p\wedge (q\wedge p),\quad p\wedge q\)

2. \((\lnot p)\rightarrow q,\quad p\vee q\)

3. \((p\vee q)\wedge\lnot q,\quad p\wedge \lnot q\)

4. \(p\rightarrow(q\rightarrow r),\quad (p\wedge q)\rightarrow r\)

5. \((p\rightarrow r)\wedge(q\rightarrow r),\quad (p\vee q)\rightarrow r\)

6. \(p\rightarrow(p\wedge q),\quad p\rightarrow q\)

Exercise (10†)

For each of the following compound propositions, find a simpler proposition that is logically equivalent. Try to find a proposition that is as simple as possible.

1. \((p\wedge q)\vee\lnot q\)

2. \(\lnot(p\vee q)\wedge p\)

3. \(p\rightarrow\lnot p\)

4. \(\lnot p\wedge(p\vee q)\)

5. \((q\wedge p)\rightarrow q\)

6. \((p\rightarrow q)\wedge(\lnot p\rightarrow q)\)

Exercise (11†)

Express the negation of each of the following sentences in natural English:

1. It is sunny and cold.

2. I will have stroopwafel or I will have appeltaart.

3. If today is Tuesday, this is Belgium.

4. If you pass the final exam, you pass the course.

Exercise (12)

Apply one of the laws of logic to each of the following sentences, and rewrite it as an equivalent sentence. State which law you are applying.

1. I will have coffee and stroopwafel or appeltaart.

2. He has neither talent nor ambition.

3. You can have oliebollen, or you can have oliebollen.

Exercise (13)

Suppose it is simultaneously true that ‘’All lemons are yellow’’ and ‘’Not all lemons are yellow’’. Derive the conclusion ‘’Unicorns exist’’. (If you get stuck, check out en.wikipedia.org/wiki/Principle_of_explosion.)

---

[1]

In ordinary algebra, it is easy to be confused by the equals sign, because it has two very different roles. In an identity such as the distributive law, it means ‘is always equal to’. On the other hand, an equation such as \(x^2+3x=4\) is a statement that might or might not be true, depending on the value of \(x\). Boolean algebra has two operators, \(\equiv\) and \(\leftrightarrow\), that play roles similar to the two roles of the equals sign. \(\equiv\) is used for identity, whereas \(\leftrightarrow\) is used in equations that may or may not be true.

[2]

It is also an example of a more general fact known as duality, which asserts that given any tautology that uses only the operators \(\wedge\), \(\vee\), and \(\lnot\), another tautology can be obtained from it by interchanging \(\wedge\) with \(\vee\) and \(\mathbb{T}\) with \(\mathbb{F}\). We won’t attempt to prove this here, but we encourage you to try it!

[3]

I’ve added parentheses around \(Q\) here for technical reasons. Sometimes, the parentheses are necessary to make sure that \(Q\) is evaluated as a whole, so that its final value is used in place of \(p\). As an example of what can go wrong, consider \(q\wedge r\). If this is substituted literally for \(p\) in \(\lnot(\lnot p)\), without parentheses, the result is \(\lnot(\lnot q \wedge r)\). But this expression means \(\lnot((\lnot q)\wedge r)\), which is not equivalent to \(q\wedge r\). Did we say to always write parentheses if you’re in doubt? See this section.