← Back to Subjects ororo.world

Chapter 1: Boolean Algebra

In 1847 a self-taught mathematician named George Boole, then running a small school in Lincoln in England, published a slim book called The Mathematical Analysis of Logic. Its claim was strange for its time. Boole argued that reasoning itself — the way we join statements with and, or and not — obeys rules as exact as the rules of ordinary arithmetic. Seven years later he set the idea out in full in An Investigation of the Laws of Thought. In Boole’s system a statement had only two possible values, true and false, and the whole algebra was built on those two.

For almost ninety years it stayed a curiosity of pure mathematics. There was nothing to run it on.

Then, in 1937, a young engineering student at the Massachusetts Institute of Technology named Claude Shannon was working with electrical relays — switches that are either closed or open, carrying current or not carrying it. Shannon noticed that a relay has exactly two states, just as a Boolean statement has exactly two values. Wire two switches one after the other and current flows only if both are closed. Wire them side by side and current flows if either is closed. Those are Boole’s and and or, built out of copper.

Shannon’s master’s thesis, published in 1938, showed that any switching network could be written as a Boolean expression, and that shortening the expression shortened the circuit. Boole’s algebra of true and false had found its machine.

Fig. 1.0-1 shows the correspondence Shannon noticed.

Diagram

Fig. 1.0-1 – two-panel figure; left panel headed “Statements”, showing two boxes labelled “It is raining” and “The road is wet” joined by the word “and”, with the result box labelled “true only if both are true”; right panel headed “Switches”, showing a battery, two switches labelled A and B connected one after the other in a single loop, and a lamp, with the caption “lamp glows only if both switches are closed”; a two-headed arrow between the panels labelled “same rule”

NoteCuriosity Corner

Q1. “Is it raining?” and “It is raining” are both ordinary sentences. Why can only one of them be given a value of true or false? Q2. “If it rains, the match is cancelled” is true. Does that mean “If the match is cancelled, it rained” must also be true? Q3. Two expressions can be written with different symbols, different lengths and different operations, yet behave identically for every possible input. How can you be certain that they really are the same? Q4. Boole’s algebra allows a variable to take only two values. Why does that restriction make it fit an electrical switch so exactly, when ordinary algebra does not? Q5. Simplifying a long expression by applying laws one after another can take a dozen steps, and you can never be sure you have reached the shortest form. Is there a way to see the shortest form instead of deriving it?

This chapter answers all five of these questions.

1.1 Propositional Logic

Every argument you have ever made rests on a small number of joining words. And, or, not, if… then, if and only if. Change one of them and the whole argument changes. “The library is open and the catalogue is working” is a very different claim from “The library is open or the catalogue is working”, and you already know the difference without being taught it.

Logic is the study of those joining words, treated as exact rules rather than as habits of speech. What Boole realised is that if you strip away the meaning of the sentences and keep only the joining words, what is left behind is an algebra — a system with symbols, operations and laws that can be worked with on paper.

Propositional logic is the part of logic that deals with whole sentences. It is also called the logic of statements or sentential logic. It does not look inside a sentence to ask who did what; it only asks whether the sentence is true or false, and how the truth of a compound sentence follows from the truth of its parts.

The notation used in this chapter

Propositional logic in this chapter is written with the symbols \(\sim\) (not), \(\wedge\) (and), \(\vee\) (or), \(\Rightarrow\) (implies) and \(\Leftrightarrow\) (if and only if), and the statements are named by lower-case letters such as \(p\), \(q\) and \(r\). From section 1.3 onwards the same ideas are rewritten in the older notation of Boolean algebra, where or is written as \(+\), and as a product, and not as an overbar. The two notations describe the same rules; only the symbols differ.

1.1.1 Propositions, Propositional Constants and Propositional Variables

Consider these four sentences.

  • New Delhi is the capital of India.
  • Every bus on route 12 is late today.
  • Where is the physics laboratory?
  • Please close the window.

The first two can be judged. One of them is true and the other may be true or false depending on the day, but in each case it makes sense to ask “is that so?” The third and fourth cannot be judged at all. A question asks for information and a request asks for an action; neither of them asserts anything, so there is nothing in them to be true or false.

A sentence that asserts something, and is therefore either true or false, is called a proposition.

NoteDefinition

A proposition is a declarative sentence that is either true or false, but not both.

The phrase “but not both” matters. A sentence such as “This sentence is false” cannot be given a single value, so it is not a proposition either, even though it looks like an assertion.

Table 1.1 – sample sentences, whether each is a proposition, and the reason

Sentence Proposition? Reason
Milk is a liquid. Yes It asserts something that is true.
The train from Jaipur reaches Ajmer before noon. Yes It asserts something; it may be true or false.
What is your roll number? No A question asserts nothing.
Draw the truth table. No An instruction asserts nothing.
\(7 + 5 = 11\) Yes It asserts something that is false.

Notice the last row. A proposition does not have to be true. A false statement is still a proposition, because it can be judged; that is the whole requirement.

Q1. “Is it raining?” and “It is raining” are both ordinary sentences. Why can only one of them be given a value of true or false?

A. Because only one of them asserts something. “It is raining” makes a claim about the world, and the world either matches the claim or it does not — so the sentence is true or false, and is a proposition. “Is it raining?” makes no claim; it requests one. There is nothing in it that could match or fail to match the world, so it has no truth value and is not a proposition. Propositional logic works only with sentences of the first kind.

Constants and variables

The value that a proposition takes — true or false — is called its truth value. In propositional logic we usually stop writing the sentence out in full and give it a name instead:

\[p : \text{The reading room is open}\]

Here the sentence itself is a propositional constant: a fixed statement whose truth value is settled by the facts. The letter \(p\) standing in its place is a propositional variable: a symbol that holds a truth value, and can hold either true or false while we reason.

This is exactly the move that turns logic into algebra. Once the sentence has become a letter, the argument can be worked out on paper without any reference to reading rooms.

Q. If \(p\) names the fixed statement “The reading room is open”, how can \(p\) be described as a variable?

A. Because when we reason we do not assume we know whether the room is open. We work out what follows if \(p\) is true and what follows if \(p\) is false. The statement is fixed; our knowledge of its truth value is not, so the symbol is treated as a variable that may take either value.

Simple and compound propositions

A proposition that makes a single assertion, and contains no joining word, is a simple proposition. “The reading room is open” is simple.

When two or more simple propositions are joined by words such as and, or, if… then, the result is a compound proposition. “The reading room is open and the catalogue is working” is compound; it is built from two simple propositions.

The joining words themselves are called connectives, and they are the subject of the next subsection. Everything in propositional logic follows from one central fact: the truth value of a compound proposition is fixed entirely by the truth values of its parts and the connectives used to join them. Nothing else about the sentences matters.

1.1.2 The Logical Connectives

There are five connectives in this syllabus. Each one is defined by stating, for every possible combination of truth values of its parts, what truth value the compound proposition takes. That statement is made in a table, and the table is the definition — there is nothing further to know about a connective once its table is fixed.

Throughout these tables, 1 stands for true and 0 stands for false. The two symbols are shorter to write and they make the connection with binary quantities, in section 1.3, immediate.

Negation

Negation takes a single proposition and reverses its truth value. It is written \(\sim p\) and read “not \(p\)”.

If \(p\) is “The fan is switched on”, then \(\sim p\) is “The fan is not switched on”.

Table 1.2 – truth table of negation; the first column holds \(p\), the second holds \(\sim p\)

\(p\) \(\sim p\)
0 1
1 0

Negation is the only connective here that works on one proposition. The other four join two.

Conjunction

Conjunction joins two propositions with and, and is written \(p \wedge q\). The compound is true only when both parts are true.

Table 1.3 – truth table of conjunction; the last column holds \(p \wedge q\)

\(p\) \(q\) \(p \wedge q\)
0 0 0
0 1 0
1 0 0
1 1 1

Read the last column downwards and the rule is visible: a single 1, in the row where both inputs are 1. If any part of an and fails, the whole claim fails.

Disjunction

Disjunction joins two propositions with or, and is written \(p \vee q\). The compound is true when at least one part is true.

Table 1.4 – truth table of disjunction; the last column holds \(p \vee q\)

\(p\) \(q\) \(p \vee q\)
0 0 0
0 1 1
1 0 1
1 1 1

Look at the last row. When both parts are true, the disjunction is true. This is not always how or is used in speech. “You may take the bus or the train” usually suggests one and not both, but in logic \(\vee\) always allows both, and only the last row of Table 1.4 distinguishes the two readings.

The or of logic is called inclusive, because it includes the case where both parts hold. The everyday or that rules out “both” is called exclusive, and it needs a separate operation, which appears in section 1.3.5 under the name XOR. Where ordinary English is ambiguous, the tables are not: \(\vee\) means the inclusive one, always.

Implication

Implication joins two propositions in the form if… then, and is written \(p \Rightarrow q\), read “\(p\) implies \(q\)” or “if \(p\) then \(q\)”. The part before the arrow, \(p\), is called the antecedent; the part after it, \(q\), is called the consequent.

Table 1.5 – truth table of implication; the last column holds \(p \Rightarrow q\)

\(p\) \(q\) \(p \Rightarrow q\)
0 0 1
0 1 1
1 0 0
1 1 1

This is the one table students find strange, so it is worth reading carefully. There is exactly one row where the implication is false: the third, where the antecedent is true and the consequent is false.

Think of an implication as a promise. Suppose the notice board says: If you submit the form by Friday, you will get a hall ticket. When has that notice been proved wrong? Only in one situation — someone submitted the form by Friday and did not get a hall ticket. If nobody submitted the form, the notice has not been broken; it simply never came into play, and an unbroken promise counts as true. That is rows one and two.

So \(p \Rightarrow q\) is false in one case only, and true in the other three. It claims nothing about what happens when the antecedent is false.

reading an implication as a statement of cause What students write:

p ⇒ q means "p causes q"

What happens: they then reject the first two rows of Table 1.5 as absurd, because a false antecedent seems to cause nothing, and every later truth table involving \(\Rightarrow\) comes out wrong. The fix: \(p \Rightarrow q\) claims only that you will not find \(p\) true with \(q\) false. It says nothing about cause, about time, or about the two statements being related in meaning at all. “If \(2 + 2 = 5\) then the moon is made of cheese” is a true implication, because its antecedent is false.

Biconditional

The biconditional joins two propositions with if and only if, and is written \(p \Leftrightarrow q\). It is true when the two parts have the same truth value, and false when they differ.

Table 1.6 – truth table of the biconditional; the last column holds \(p \Leftrightarrow q\)

\(p\) \(q\) \(p \Leftrightarrow q\)
0 0 1
0 1 0
1 0 0
1 1 1

If \(p\) is “\(x\) is divisible by 2” and \(q\) is “\(x\) is an even number”, then \(p \Leftrightarrow q\) is true whichever number \(x\) happens to be, because the two statements always agree.

The name is a fair description of what the connective does: it holds in both directions at once. Section 1.2.4 makes that precise by showing that \(p \Leftrightarrow q\) is equivalent to the two implications \(p \Rightarrow q\) and \(q \Rightarrow p\) taken together.

The five connectives together

Table 1.7 – the connectives, their symbols, the English form they translate, and their names

English form Symbol Name True when
not \(\sim\) negation the part is false
and \(\wedge\) conjunction both parts are true
or \(\vee\) disjunction at least one part is true
if… then \(\Rightarrow\) implication the antecedent is false or the consequent is true
if and only if \(\Leftrightarrow\) biconditional both parts have the same value

1.1.3 Truth Values and Truth Tables

A truth table is a table that lists every possible combination of truth values of the variables in a compound proposition, together with the value the proposition takes in each case. It is the basic instrument of this subject, and almost every claim made later in the chapter can be settled by building one.

Two things must be got right, or the table proves nothing.

How many rows, and in what order

Each variable can take two values, so \(n\) variables give \(2^n\) different combinations. Two variables give 4 rows, three give 8, four give 16. Every one of those rows must appear; a truth table with a missing row is not a proof of anything, because the missing row may be exactly the one where the claim fails.

The rows are written in standard binary counting order — the combinations are read as binary numbers and listed from 0 upwards. For three variables that gives 000, 001, 010, 011, 100, 101, 110, 111. This is not decoration. It guarantees that no combination is left out and none is written twice, and it lets any two truth tables in the book be compared row against row.

Building the table in columns

The reliable method is to add one column at a time, each column depending only on columns already written.

  1. Write one column for each variable and fill in all \(2^n\) combinations in standard binary counting order.
  2. Add a column for each small part of the expression, working from the innermost bracket outwards.
  3. Fill each new column using only the connective’s own table from section 1.1.2 and the values already standing to its left.
  4. The last column added is the expression itself.

Take \(\sim p \vee (p \wedge q)\). The innermost part is \(p \wedge q\); \(\sim p\) is also needed; then the two are joined by \(\vee\).

Table 1.8 – truth table of \(\sim p \vee (p \wedge q)\), with intermediate columns

\(p\) \(q\) \(\sim p\) \(p \wedge q\) \(\sim p \vee (p \wedge q)\)
0 0 1 0 1
0 1 1 0 1
1 0 0 0 0
1 1 0 1 1

Read the third row across as a check on the method. There \(p\) is 1, so \(\sim p\) is 0; \(q\) is 0, so \(p \wedge q\) is 0; and \(0 \vee 0\) is 0. Every entry came from a table, never from an impression of what the sentence “ought” to mean.

Now compare the final column of Table 1.8 — 1, 1, 0, 1 — with the final column of Table 1.5. They are identical. Two expressions that look nothing alike have turned out to behave identically on every row, and that observation is the seed of the whole of section 1.2.

Three variables

With three variables the table has 8 rows. Here is \((p \wedge q) \vee \sim r\).

Table 1.9 – truth table of \((p \wedge q) \vee \sim r\) in standard binary counting order

\(p\) \(q\) \(r\) \(p \wedge q\) \(\sim r\) \((p \wedge q) \vee \sim r\)
0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 0 1 1
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1

The pattern in the first three columns is worth noticing, because it is how you fill a table quickly and without mistakes. The rightmost variable alternates 0, 1, 0, 1, …; the middle one alternates in pairs; the leftmost in fours. For four variables the leftmost would alternate in eights.

Q. An expression uses five variables. How many rows will its truth table have, and is a truth table still a sensible way to check it?

A. \(2^5 = 32\) rows. It is still a valid method — it will always give the right answer — but it is becoming slow, and with six variables it would be 64 rows. This is the practical reason for the algebraic laws of section 1.2: they let you reach the same conclusion without writing out every case.

Build the truth table of \(p \wedge (\sim q \vee r)\) on paper, in standard binary counting order, adding one column at a time. Then predict, before you check, how many rows will hold a 1. Count them and see whether your prediction was right.

1.1.4 Well-Formed Formulae

Not every string of logical symbols means something. \(p \wedge \vee q\) is as meaningless as \(7 + \times 3\) in arithmetic, and \(\sim \Rightarrow p\) is worse. Before we can reason about expressions we need a rule that separates the ones that say something from the ones that do not.

An expression built correctly from propositional variables and connectives is called a well-formed formula (wff).

NoteDefinition

A well-formed formula (wff) is defined by these rules, and by no others: (a) every propositional variable is a wff; (b) if \(A\) is a wff, then \(\sim A\) is a wff; (c) if \(A\) and \(B\) are wffs, then \((A \wedge B)\), \((A \vee B)\), \((A \Rightarrow B)\) and \((A \Leftrightarrow B)\) are wffs; (d) nothing else is a wff.

The definition is worth reading twice, because of its shape. It does not list the well-formed formulae — there are infinitely many. It gives you a way to build them, starting from single variables and wrapping one connective around what you already have. Rule (d) is what makes the definition useful: it says that if you cannot build an expression by these steps, it is not a wff.

Fig. 1.1-1 shows the building process for \(\sim(p \wedge q) \Rightarrow r\). Reading the figure from the bottom up is exactly reading the definition from rule (a) upwards.

Diagram

Fig. 1.1-1 – tree showing how the wff ~(p ∧ q) ⇒ r is built; at the bottom three leaf nodes labelled p, q and r; p and q join upward into a node labelled ∧ with the label “(p ∧ q) by rule (c)”; that node feeds a single node above it labelled ~ with the label “~(p ∧ q) by rule (b)”; the ~ node and the r leaf join into the top node labelled ⇒ with the label “the whole wff, by rule (c)”; an upward arrow at the side labelled “each step wraps one connective around what is already built”

Table 1.10 – expressions, whether each is a wff, and the reason

Expression wff? Reason
\(p\) Yes A single variable, by rule (a).
\(\sim \sim p\) Yes Rule (b) applied twice.
\((p \vee q) \Rightarrow \sim r\) Yes Built by rules (a), (b) and (c).
\(p \wedge \vee q\) No Two binary connectives with nothing between them.
\(\sim \Rightarrow q\) No \(\Rightarrow\) needs a wff on its left; there is none.
\((p \wedge q\) No The bracket is not closed.
Brackets and precedence

Rule (c) puts brackets around every compound, which quickly becomes unreadable. To cut them down, the connectives are given an order of precedence, exactly as \(\times\) binds more tightly than \(+\) in arithmetic. From tightest to loosest:

\[\sim \quad,\quad \wedge \quad,\quad \vee \quad,\quad \Rightarrow \quad,\quad \Leftrightarrow\]

So \(\sim p \wedge q \Rightarrow r\) means \(((\sim p) \wedge q) \Rightarrow r\), and nothing else. Where the intended reading differs from this order, brackets must be written; \(\sim (p \wedge q)\) and \(\sim p \wedge q\) are different formulae, and section 1.2.3 shows just how different.

Representing word problems as wffs

Most of the work in a logic question is done before any table is drawn, in the step where English becomes symbols. The method is always the same: name each simple statement with a letter, then look for the joining words.

Let \(p\) be “the library is open”, \(q\) be “the catalogue is working” and \(r\) be “Meera can issue a book”.

Table 1.11 – English statements and the wffs that represent them

Statement wff
The library is open and the catalogue is working. \(p \wedge q\)
The library is open but the catalogue is not working. \(p \wedge \sim q\)
Neither the library is open nor the catalogue is working. \(\sim p \wedge \sim q\)
If the library is open and the catalogue is working, Meera can issue a book. \((p \wedge q) \Rightarrow r\)
Meera can issue a book only if the library is open. \(r \Rightarrow p\)
Meera can issue a book if and only if the library is open and the catalogue is working. \(r \Leftrightarrow (p \wedge q)\)

Three of those rows deserve a second look.

But is not a separate connective. It carries a shade of contrast in English, but as far as truth values go it behaves exactly as and does, so it becomes \(\wedge\).

Neither… nor negates both parts, giving \(\sim p \wedge \sim q\). A common alternative answer is \(\sim(p \vee q)\), and in section 1.2.3 you will find that the two are equivalent, so both are correct.

Only if is the one that reverses the arrow. “\(A\) only if \(B\)” says that \(B\) is required for \(A\), so it becomes \(A \Rightarrow B\), not \(B \Rightarrow A\). Compare it with “if”: “Meera can issue a book if the library is open” is \(p \Rightarrow r\), while “Meera can issue a book only if the library is open” is \(r \Rightarrow p\). One small word turns the implication around.

1.1.5 Interpretation of a Well-Formed Formula

A wff by itself has no truth value. \(p \wedge q\) is neither true nor false until something is said about \(p\) and \(q\). Fixing those values is called giving an interpretation.

NoteDefinition

An interpretation of a wff is an assignment of a truth value — true or false — to every propositional variable occurring in it. The interpretation of the wff is the single truth value the wff then takes, computed from the connectives’ tables.

An interpretation is therefore one row of the truth table, taken on its own. A wff with \(n\) variables has exactly \(2^n\) interpretations, one per row.

Take the wff

\[(p \Rightarrow q) \wedge (\sim q \vee r)\]

and the interpretation \(p = 1\), \(q = 0\), \(r = 1\). Work from the inside out.

  • \(p \Rightarrow q\) is \(1 \Rightarrow 0\), which is 0 — the only false row of Table 1.5.
  • \(\sim q\) is \(\sim 0\), which is 1.
  • \(\sim q \vee r\) is \(1 \vee 1\), which is 1.
  • The whole wff is \(0 \wedge 1\), which is 0.

Under this interpretation the wff is false. Under the interpretation \(p = 0\), \(q = 0\), \(r = 0\) the same wff comes out as \((0 \Rightarrow 0) \wedge (1 \vee 0) = 1 \wedge 1 = 1\), so it is true there.

That a single wff can be true under one interpretation and false under another is not a defect. It is the ordinary case, and it is what the next subsection classifies.

1.1.6 Satisfiable, Unsatisfiable and Valid Formulae

Once a wff has been evaluated under every interpretation, the last column of its truth table can look only one of three ways: all 1s, all 0s, or a mixture. Those three possibilities are given names, and they are the most heavily used vocabulary in this part of the syllabus.

Valid formulae, or tautologies

A wff whose final column holds nothing but 1s is called valid, or a tautology.

NoteDefinition

A wff is valid, or a tautology, if it is true under every interpretation — that is, if its truth table has 1 in every row of the final column.

The qualifier “every” cannot be dropped. One row with a 0 in it, out of a hundred, is enough to destroy validity.

Consider \((p \wedge q) \Rightarrow p\). In words: if both statements hold, then the first one holds. That ought to be true whatever \(p\) and \(q\) are, and the table confirms it.

Table 1.12 – truth table showing that \((p \wedge q) \Rightarrow p\) is a tautology

\(p\) \(q\) \(p \wedge q\) \((p \wedge q) \Rightarrow p\)
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 1

The final column is all 1s, so the formula is valid. Notice that rows one, two and three are true for an uninteresting reason — the antecedent \(p \wedge q\) is false there, and Table 1.5 makes any implication with a false antecedent true. Only the last row tests the claim, and it holds.

Unsatisfiable formulae, or contradictions

A wff whose final column holds nothing but 0s is called unsatisfiable, or a contradiction.

NoteDefinition

A wff is unsatisfiable, or a contradiction, if it is false under every interpretation — that is, if its truth table has 0 in every row of the final column.

Take \((p \Rightarrow q) \wedge (p \wedge \sim q)\). The left half asserts an implication; the right half asserts exactly the situation that would break it. No interpretation can make both hold at once.

Table 1.13 – truth table showing that \((p \Rightarrow q) \wedge (p \wedge \sim q)\) is a contradiction

\(p\) \(q\) \(p \Rightarrow q\) \(\sim q\) \(p \wedge \sim q\) \((p \Rightarrow q) \wedge (p \wedge \sim q)\)
0 0 1 1 0 0
0 1 1 0 0 0
1 0 0 1 1 0
1 1 1 0 0 0

Row three is the interesting one. There the right half is true — \(p\) holds and \(q\) fails — but that is precisely the row where the implication is false, so the conjunction still collapses to 0.

Satisfiable formulae and contingencies

A wff whose final column holds a 1 somewhere is called satisfiable.

NoteDefinition

A wff is satisfiable if it is true under at least one interpretation — that is, if its truth table has 1 in at least one row of the final column.

Read that carefully against the two definitions above. A tautology is true in every row, so it is certainly true in at least one row, and every tautology is therefore satisfiable as well as valid. Satisfiable is a weaker requirement than valid, not an alternative to it.

A formula that is satisfiable but not valid — true in some rows and false in others — is called a contingency. Its truth value depends on, or is contingent on, which interpretation you choose.

Table 1.14 – truth table showing that \((p \vee q) \wedge \sim q\) is a contingency

\(p\) \(q\) \(p \vee q\) \(\sim q\) \((p \vee q) \wedge \sim q\)
0 0 0 1 0
0 1 1 0 0
1 0 1 1 1
1 1 1 0 0

There is a 1 in row three, so the formula is satisfiable. There are 0s elsewhere, so it is not valid. It is a contingency, and most formulae you meet are.

Fig. 1.1-2 sets the three terms in their proper relation, which is easier to see as a picture than to hold in words.

Diagram

Fig. 1.1-2 – nested region diagram; a large rectangle labelled “all wffs”; inside it a large oval labelled “satisfiable — true in at least one row”; inside that oval a smaller shaded oval labelled “valid (tautology) — true in every row”; the part of the large oval outside the smaller one labelled “contingency — true in some rows, false in others”; the region of the rectangle outside the large oval labelled “unsatisfiable (contradiction) — false in every row”

Table 1.15 – tautology vs contradiction vs contingency

Feature Tautology (valid) Contradiction (unsatisfiable) Contingency
Final column of the truth table all 1s all 0s both 1s and 0s
Number of interpretations making it true all \(2^n\) none at least one, but not all
Satisfiable? yes no yes
Effect of negating it becomes a contradiction becomes a tautology stays a contingency
Typical use to certify that a law or an argument always holds to show that a set of assumptions cannot all hold together the ordinary case; describes a condition that sometimes holds

The fourth row of Table 1.15 gives a quick check you can apply to your own work. If you believe a formula is a tautology, negate it and build the table again; the column should turn to all 0s. If it does not, one of the two tables has an error.

deciding a formula is a tautology from a few rows What students write:

p ⇒ (p ∨ q)
rows 1 and 2 give 1, so it is a tautology

What happens: the conclusion may even be correct — this particular formula is a tautology — but the reasoning is not, and the same shortcut applied to \(p \Rightarrow (p \wedge q)\) would give a wrong answer, since its first two rows are also 1 while its third row is 0. The fix: a claim of validity is a claim about every interpretation, so every row must be written and checked. Stopping early can only ever disprove validity, never establish it.

1.1.7 Converse, Inverse and Contrapositive

From a single conditional \(p \Rightarrow q\), three further conditionals can be manufactured by swapping the two parts, negating them, or doing both. They have fixed names, and the differences between them decide a great many careless arguments.

  • The converse of \(p \Rightarrow q\) is \(q \Rightarrow p\) — the two parts are interchanged.
  • The inverse of \(p \Rightarrow q\) is \(\sim p \Rightarrow \sim q\) — both parts are negated, in place.
  • The contrapositive of \(p \Rightarrow q\) is \(\sim q \Rightarrow \sim p\) — the parts are interchanged and negated.
NoteDefinition

For the conditional \(p \Rightarrow q\): its converse is \(q \Rightarrow p\); its inverse is \(\sim p \Rightarrow \sim q\); its contrapositive is \(\sim q \Rightarrow \sim p\).

Take the conditional “If the fee is paid, then the receipt is issued”, with \(p\): the fee is paid, and \(q\): the receipt is issued.

Table 1.16 – the four related conditionals, in symbols and in words

Form wff In words
Conditional \(p \Rightarrow q\) If the fee is paid, then the receipt is issued.
Converse \(q \Rightarrow p\) If the receipt is issued, then the fee is paid.
Inverse \(\sim p \Rightarrow \sim q\) If the fee is not paid, then the receipt is not issued.
Contrapositive \(\sim q \Rightarrow \sim p\) If the receipt is not issued, then the fee is not paid.

Read those four sentences one after another and judge them by ordinary sense. The first and the last say the same thing in two ways. The second and third also say the same thing as each other — but something different from the first. The truth table settles what sense suggests.

Table 1.17 – truth table of a conditional together with its converse, inverse and contrapositive

\(p\) \(q\) \(\sim p\) \(\sim q\) \(p \Rightarrow q\) \(q \Rightarrow p\) \(\sim p \Rightarrow \sim q\) \(\sim q \Rightarrow \sim p\)
0 0 1 1 1 1 1 1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 1 0 0 1 1 1 1

Two facts fall out of the table, and both are worth remembering permanently.

The column for \(p \Rightarrow q\) reads 1, 1, 0, 1. The column for its contrapositive \(\sim q \Rightarrow \sim p\) reads 1, 1, 0, 1. They agree in every row, so a conditional and its contrapositive always have the same truth value. Either may be replaced by the other at any point in an argument, and section 1.2 uses this freely.

The column for the converse reads 1, 0, 1, 1, and so does the column for the inverse; the converse and the inverse are equivalent to each other. But neither of them matches the conditional — look at rows two and three, where they disagree. The truth of a conditional tells you nothing about the truth of its converse.

Fig. 1.1-3 summarises which of the four are interchangeable.

Diagram

Fig. 1.1-3 – four boxes arranged in a square; top-left box labelled “conditional p ⇒ q”, top-right “converse q ⇒ p”, bottom-left “inverse ~p ⇒ ~q”, bottom-right “contrapositive ~q ⇒ ~p”; a double-headed arrow along the diagonal from top-left to bottom-right labelled “always equivalent”; a second double-headed arrow along the diagonal from top-right to bottom-left labelled “always equivalent”; the horizontal and vertical sides of the square marked with crossed-out arrows labelled “not equivalent”

Q2. “If it rains, the match is cancelled” is true. Does that mean “If the match is cancelled, it rained” must also be true?

A. No. The second sentence is the converse of the first, and Table 1.17 shows that a conditional and its converse can differ — they disagree in rows two and three. The match might have been cancelled for some other reason entirely, such as a damaged pitch, and the original statement never ruled that out. What does follow from the original is its contrapositive: “If the match was not cancelled, it did not rain.” That one is guaranteed to be true whenever the original is.

writing the contrapositive by negating without swapping What students write:

Conditional:     p ⇒ q
Contrapositive:  ~p ⇒ ~q

What happens: what has actually been written is the inverse, which is equivalent to the converse and not to the original. Any conclusion drawn from it is unsound. The fix: the contrapositive needs both operations — interchange the two parts and negate both, giving \(\sim q \Rightarrow \sim p\). A quick check is to look at which letter now stands first: in the contrapositive it is \(q\), in the inverse it is \(p\).

Write the converse, inverse and contrapositive of “If a number is divisible by 6, then it is divisible by 3.” Then decide, from your own knowledge of numbers, which of the four statements are true. Compare your answer with Table 1.17 and check that the pattern of agreement is the one the table predicts.

1.2 Equivalence Laws and the Simplification of Well-Formed Formulae

At the end of section 1.1.3 something odd happened. The formula \(\sim p \vee (p \wedge q)\) and the formula \(p \Rightarrow q\) have nothing in common to look at — different connectives, different lengths, different shapes — and yet their truth tables agreed in all four rows. The same thing happened again in Table 1.17, where a conditional and its contrapositive matched row for row.

That is not a coincidence, and it is not a curiosity. It is the reason propositional logic is worth studying at all. If two formulae behave identically on every row, one can be replaced by the other wherever it appears, and a long formula can be traded in for a short one that does exactly the same job. This section states the rules that permit those trades, and then uses them.

1.2.1 Logical Equivalence

Two wffs that take the same truth value under every interpretation are said to be logically equivalent.

NoteDefinition

Two wffs \(A\) and \(B\) are logically equivalent, written \(A \equiv B\), if they have the same truth value under every interpretation — that is, if the final columns of their truth tables agree in every row.

The word “every” is doing the same work here that it did in the definition of a valid formula. Agreement in three rows out of four is not equivalence; it is a near miss, and a near miss is useless, because the argument you are building may land on the fourth row.

Note carefully that \(\equiv\) is not a connective. You cannot write \(\equiv\) inside a wff the way you write \(\wedge\) or \(\Rightarrow\). It is a statement about two wffs, made from outside, in the same way that \(=\) is a statement about two arithmetic expressions rather than an operation inside them.

Equivalence and the biconditional

There is a close relative that is a connective, and the two are easy to confuse. \(A \Leftrightarrow B\) is a formula, and like any formula it may be true under some interpretations and false under others. \(A \equiv B\) is a claim that \(A\) and \(B\) never differ.

The link between them is exact: \(A \equiv B\) holds precisely when the formula \(A \Leftrightarrow B\) is a tautology. Building the truth table of \(A \Leftrightarrow B\) and finding 1 in every row is therefore another way of establishing an equivalence, and it is the way most laws in this section will be checked.

Q3. Two expressions can be written with different symbols, different lengths and different operations, yet behave identically for every possible input. How can you be certain that they really are the same?

A. By checking every possible input, and there are only finitely many. A formula with \(n\) variables has exactly \(2^n\) interpretations, so building both truth tables in standard binary counting order and comparing the final columns row by row settles the question completely — there is nothing left over to worry about. This is a luxury that ordinary algebra does not offer, where a variable may take infinitely many values and no amount of checking proves an identity. In propositional logic, exhaustive checking is a genuine proof.

Why bother simplifying

An equivalence is a licence to replace. Every replacement that makes a formula shorter has a practical payoff, and the payoff grows as the chapter goes on:

  • a shorter formula is quicker to evaluate and easier to read without mistakes;
  • in section 1.3 a formula becomes a Boolean expression, and in the following chapter that expression becomes hardware, where every operation removed is a real component removed;
  • an argument can be shown to be sound by reducing it to a formula that is plainly a tautology, without writing out a table of 8 or 16 rows.

1.2.2 Commutativity, Associativity and Distributivity

The first three laws will look familiar from ordinary algebra, and the resemblance is genuine — but only up to a point, as the second distributive law will show.

Commutativity

The commutative laws say that the order of the two parts of a conjunction or a disjunction does not matter:

\[p \wedge q \equiv q \wedge p \qquad\qquad p \vee q \equiv q \vee p\]

This is read straight off Tables 1.3 and 1.4. Swapping \(p\) and \(q\) merely swaps rows two and three of the table, and both of those rows hold the same value in the conjunction column, and the same value in the disjunction column.

Implication is emphatically not commutative. \(p \Rightarrow q\) and \(q \Rightarrow p\) are converses of each other, and Table 1.17 showed that they disagree.

Associativity

The associative laws say that when the same connective is used twice, the bracketing does not matter:

\[(p \wedge q) \wedge r \equiv p \wedge (q \wedge r) \qquad\qquad (p \vee q) \vee r \equiv p \vee (q \vee r)\]

The reason is easy to see without a table. \((p \wedge q) \wedge r\) is true only when all three of \(p\), \(q\) and \(r\) are true, and so is \(p \wedge (q \wedge r)\); a chain of conjunctions demands everything. A chain of disjunctions demands only that something holds, whichever way it is bracketed.

Because of associativity, expressions such as \(p \wedge q \wedge r\) and \(p \vee q \vee r\) can be written with no brackets at all without any risk of ambiguity. Mixed connectives are a different matter: \(p \wedge q \vee r\) is settled by the precedence order of section 1.1.4, not by associativity.

Distributivity

The distributive laws describe what happens when two different connectives meet:

\[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)\]

The first of these matches the familiar rule of arithmetic, with \(\wedge\) playing the part of multiplication and \(\vee\) the part of addition. Table 1.18 verifies it.

Table 1.18 – truth table verifying \(p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\); the fifth and eighth columns are the ones to compare

\(p\) \(q\) \(r\) \(q \vee r\) \(p \wedge (q \vee r)\) \(p \wedge q\) \(p \wedge r\) \((p \wedge q) \vee (p \wedge r)\)
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1

Columns five and eight agree in all eight rows, so the equivalence holds. The first four rows are true for a dull reason — \(p\) is false, so nothing survives on either side — and the real content of the law sits in the last four.

The second distributive law has no counterpart in arithmetic. In numbers, \(2 + (3 \times 4)\) is not \((2 + 3) \times (2 + 4)\); the two come to 14 and 30. In logic the corresponding statement holds exactly, and it will be used repeatedly in section 1.2.7 and again in the product-of-sums work of section 1.5. This is the first sign that logical algebra is a genuinely different algebra, not a rewriting of the one you already know.

Q. Is there any quick way to see why \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\), without a table of eight rows?

A. Split on \(p\). If \(p\) is true, the left side is true, and both brackets on the right are true, so the right side is true as well. If \(p\) is false, the left side reduces to \(q \wedge r\), and the right side reduces to \(q \wedge r\) too. Since \(p\) can only be true or false, the two sides agree everywhere.

1.2.3 De Morgan’s Laws

Suppose someone claims “the hall is booked and the projector is working”, and you want to deny it. What exactly are you claiming when you deny it? Not that both have failed — only that at least one of them has. The denial of an and is an or.

This is the content of De Morgan’s laws, named after Augustus De Morgan, a nineteenth-century mathematician who was a contemporary and correspondent of Boole.

De Morgan’s laws Statement: \(\sim(p \wedge q) \equiv \sim p \vee \sim q\) and \(\sim(p \vee q) \equiv \sim p \wedge \sim q\) In words: the negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations. Why it holds: \(p \wedge q\) is false in exactly the three rows where at least one of \(p\), \(q\) is false, which is exactly where \(\sim p \vee \sim q\) is true; Tables 1.19 and 1.20 set both laws out row by row. Used for: pushing a negation inwards until it sits only on single variables, which is the step that makes almost every simplification possible; and, in the following chapter, for rebuilding a circuit out of one kind of component. Watch out: the connective must change. Writing \(\sim(p \wedge q) \equiv \sim p \wedge \sim q\) leaves the \(\wedge\) untouched and gives a formula that disagrees with the original in two rows out of four.

Table 1.19 – truth table verifying \(\sim(p \wedge q) \equiv \sim p \vee \sim q\); compare the fourth and seventh columns

\(p\) \(q\) \(p \wedge q\) \(\sim(p \wedge q)\) \(\sim p\) \(\sim q\) \(\sim p \vee \sim q\)
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Table 1.20 – truth table verifying \(\sim(p \vee q) \equiv \sim p \wedge \sim q\); compare the fourth and seventh columns

\(p\) \(q\) \(p \vee q\) \(\sim(p \vee q)\) \(\sim p\) \(\sim q\) \(\sim p \wedge \sim q\)
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Table 1.20 also settles a loose end from section 1.1.4. “Neither the library is open nor the catalogue is working” was translated there as \(\sim p \wedge \sim q\), with a remark that \(\sim(p \vee q)\) would do equally well. The second law says the two are equivalent, so both translations are correct.

Fig. 1.2-1 shows the two laws as a single movement, which is how they are best remembered.

Diagram

Fig. 1.2-1 – two-row diagram showing De Morgan’s laws as an inward movement of the negation; top row: on the left the expression ~(p ∧ q) with a bracket drawn around p ∧ q and the ~ outside it, an arrow labelled “negation moves inside” pointing right, and on the right the expression ~p ∨ ~q with the two ~ symbols circled and the connective ∨ circled and labelled “connective flips”; bottom row: the same layout for ~(p ∨ q) becoming ~p ∧ ~q; a caption strip beneath both rows reading “negate each part, and change ∧ to ∨ or ∨ to ∧”

negating the parts but leaving the connective alone What students write:

~(p ∨ q)  =  ~p ∨ ~q

What happens: the two formulae disagree in rows two and three of Table 1.20. Any simplification that begins with this step is wrong from that point onwards, and the error is invisible later, because everything after it is done correctly. The fix: De Morgan’s laws change two things at once — each part is negated and the connective is swapped. A one-second check is to test the row \(p = 1\), \(q = 0\): the true form gives 0, the faulty form gives 1.

1.2.4 The Law of Implication and the Law of the Biconditional

Implication and the biconditional are convenient to write but awkward to work with, because the laws of the previous two subsections say nothing about them. The law of implication and the law of the biconditional remove the awkwardness by expressing both connectives in terms of \(\sim\), \(\wedge\) and \(\vee\). Almost every simplification in this chapter begins by applying them.

the law of implication Statement: \(p \Rightarrow q \equiv \sim p \vee q\) In words: “if \(p\) then \(q\)” says the same thing as “either \(p\) fails or \(q\) holds”. Why it holds: \(p \Rightarrow q\) is false in one row only — \(p\) true, \(q\) false — and \(\sim p \vee q\) is false in exactly that same row, since both of its parts are false there. Table 1.21 sets out all four rows. Used for: removing every \(\Rightarrow\) from a formula, so that the commutative, associative, distributive and De Morgan’s laws can be applied to what remains. Watch out: the negation goes on the antecedent, not on the consequent. \(p \vee \sim q\) is a different formula, and it is in fact equivalent to \(q \Rightarrow p\), the converse.

Table 1.21 – truth table verifying the law of implication \(p \Rightarrow q \equiv \sim p \vee q\)

\(p\) \(q\) \(p \Rightarrow q\) \(\sim p\) \(\sim p \vee q\)
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1

This law also explains, at last, the puzzle from section 1.1.3. There, the formula \(\sim p \vee (p \wedge q)\) turned out to match \(p \Rightarrow q\) row for row. Now the reason is visible: \(p \Rightarrow q\) is \(\sim p \vee q\), and \(\sim p \vee (p \wedge q)\) collapses to the same thing, as the worked example in section 1.2.7 will show.

the law of the biconditional Statement: \((p \Leftrightarrow q) \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)\) In words: “\(p\) if and only if \(q\)” is the two implications, one in each direction, asserted together. Why it holds: the conjunction on the right is true only when neither implication fails, and an implication fails only when its antecedent is true and its consequent false; that leaves exactly the two rows where \(p\) and \(q\) agree, which is where the biconditional is true. Table 1.22 shows this. Used for: replacing a biconditional by implications, which the law of implication then turns into \(\sim\), \(\wedge\) and \(\vee\); and for splitting a proof of “if and only if” into two halves. Watch out: both directions are needed. Keeping only \(p \Rightarrow q\) throws away half the claim, and the result is true in a row where the biconditional is false.

Table 1.22 – truth table verifying the law of the biconditional; compare the third and sixth columns

\(p\) \(q\) \(p \Leftrightarrow q\) \(p \Rightarrow q\) \(q \Rightarrow p\) \((p \Rightarrow q) \wedge (q \Rightarrow p)\)
0 0 1 1 1 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 1 1 1 1

Applying the law of implication to both halves gives a second useful form. Since \(p \Rightarrow q \equiv \sim p \vee q\) and \(q \Rightarrow p \equiv \sim q \vee p\), the biconditional can be written entirely without arrows as \((\sim p \vee q) \wedge (\sim q \vee p)\).

1.2.5 Identity, the Law of Negation, Excluded Middle and Contradiction

Four short laws remain. Each is almost obvious once stated, and each is used constantly.

Identity is the simplest statement in the subject: \(p \equiv p\). A formula is equivalent to itself. It looks too trivial to write down, but it is what permits a symbol to be carried unchanged from one line of a derivation to the next, and every longer proof rests on it silently.

The law of negation says that negating twice returns the original:

\[\sim(\sim p) \equiv p\]

Table 1.2 makes this immediate — negation swaps 0 and 1, so doing it twice restores what you started with. In practice this law is the tidying-up step after De Morgan’s laws, which frequently leave behind a \(\sim(\sim p)\).

The law of excluded middle says that a proposition and its negation cannot both fail:

\[p \vee \sim p \equiv \textbf{true}\]

Whatever \(p\) is, one of \(p\) and \(\sim p\) holds, so the disjunction is true under every interpretation. It is a tautology, and it is the standard way a whole branch of a simplification disappears at once.

The law of contradiction is its mirror image:

\[p \wedge \sim p \equiv \textbf{false}\]

A proposition and its negation cannot both hold, so the conjunction is false under every interpretation. It is a contradiction in the technical sense of section 1.1.6, and it is how an impossible case is detected inside a longer formula.

Q. If \(p \wedge \sim p\) is always false, why would anyone ever write it?

A. Nobody writes it deliberately. It appears in the middle of a simplification, after other laws have rearranged the terms — as it does in the worked example of section 1.2.7 — and spotting it is what allows a whole term to be struck out. Its value lies in recognising it, not in writing it.

1.2.6 Simplification Rules for Conjunction and Disjunction

Once true and false appear inside a formula — and the last two laws guarantee that they will — they need to be absorbed. Four rules do that, and two more deal with a formula meeting itself.

\[p \wedge \textbf{true} \equiv p \qquad\qquad p \vee \textbf{false} \equiv p\] \[p \vee \textbf{true} \equiv \textbf{true} \qquad\qquad p \wedge \textbf{false} \equiv \textbf{false}\]

The upper pair are the harmless cases. Joining a formula to something that always holds by and adds no restriction, so \(p\) survives untouched; joining it to something that never holds by or adds no alternative, so again \(p\) survives.

The lower pair are the destructive cases, and they are the ones that make simplifications collapse dramatically. Once a disjunction contains a part that is always true, the whole disjunction is true and everything else in it is irrelevant. Once a conjunction contains a part that is always false, the whole conjunction is false, however promising the other parts looked.

Two further rules describe a formula joined to itself:

\[p \wedge p \equiv p \qquad\qquad p \vee p \equiv p\]

Asserting the same thing twice adds nothing. In the Boolean notation of section 1.4 this pair is given the name idempotence, and it is proved there again in that setting.

The complete set of equivalence laws is gathered in Table 1.23 for reference. Nothing in it is new; it is the five previous subsections in one place.

Table 1.23 – the equivalence laws of propositional logic

Name Statement
Commutativity \(p \wedge q \equiv q \wedge p\); \(p \vee q \equiv q \vee p\)
Associativity \((p \wedge q) \wedge r \equiv p \wedge (q \wedge r)\); \((p \vee q) \vee r \equiv p \vee (q \vee r)\)
Distributivity \(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)\)
De Morgan’s laws \(\sim(p \wedge q) \equiv \sim p \vee \sim q\); \(\sim(p \vee q) \equiv \sim p \wedge \sim q\)
Law of implication \(p \Rightarrow q \equiv \sim p \vee q\)
Law of the biconditional \((p \Leftrightarrow q) \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)\)
Identity \(p \equiv p\)
Law of negation \(\sim(\sim p) \equiv p\)
Law of excluded middle \(p \vee \sim p \equiv \textbf{true}\)
Law of contradiction \(p \wedge \sim p \equiv \textbf{false}\)
Simplification with true \(p \wedge \textbf{true} \equiv p\); \(p \vee \textbf{true} \equiv \textbf{true}\)
Simplification with false \(p \vee \textbf{false} \equiv p\); \(p \wedge \textbf{false} \equiv \textbf{false}\)
Repetition \(p \wedge p \equiv p\); \(p \vee p \equiv p\)

Each law is stated with single letters, but it applies to whole formulae. De Morgan’s first law works just as well on \(\sim((a \Rightarrow b) \wedge c)\), giving \(\sim(a \Rightarrow b) \vee \sim c\), because \(a \Rightarrow b\) is itself a wff and may stand wherever \(p\) stands. This is what makes so short a list of laws capable of handling formulae of any size.

1.2.7 Simplifying a Well-Formed Formula

There is no single procedure that is guaranteed to find the shortest equivalent formula by algebra alone — that limitation is real, and section 1.6 exists partly because of it. But there is a reliable order of attack that handles most formulae you will meet.

  1. Remove every \(\Leftrightarrow\) using the law of the biconditional.
  2. Remove every \(\Rightarrow\) using the law of implication.
  3. Push every negation inwards with De Morgan’s laws until each \(\sim\) sits on a single variable, tidying with the law of negation as you go.
  4. Rearrange with commutativity, associativity and distributivity so that terms which can cancel stand together.
  5. Strike out what the laws of excluded middle and contradiction allow, then absorb true and false with the simplification rules.

Name the law used at each step as you write it. This is not ceremony; a derivation with the reasons written beside it can be checked line by line, and one without them cannot be checked at all, not even by the person who wrote it.

A first simplification

Simplify \(\sim(\sim p \vee q) \vee (p \wedge q)\).

\[\sim(\sim p \vee q) \vee (p \wedge q)\] \[\equiv (\sim(\sim p) \wedge \sim q) \vee (p \wedge q) \qquad \text{De Morgan's law}\] \[\equiv (p \wedge \sim q) \vee (p \wedge q) \qquad \text{law of negation}\] \[\equiv p \wedge (\sim q \vee q) \qquad \text{distributivity}\] \[\equiv p \wedge \textbf{true} \qquad \text{law of excluded middle}\] \[\equiv p \qquad \text{simplification with true}\]

Five steps have turned a formula with two connectives and two negations into a single letter. Check the result against the meaning: the formula said “it is not the case that (\(p\) fails or \(q\) holds), or else both hold” — and that comes to nothing more than “\(p\) holds”.

The step from line three to line four is the one worth studying. Distributivity is being used backwards, pulling the common factor \(p\) out of the two terms rather than pushing it in. Reading a law from right to left is always permitted, because \(\equiv\) works in both directions, and in simplification the right-to-left reading is usually the useful one.

A second simplification

Simplify \((p \Rightarrow q) \wedge (p \Rightarrow \sim q)\).

Read the formula first. It asserts that \(p\) leads to \(q\) and that the very same \(p\) leads to the denial of \(q\). Something has to give, and the algebra will say exactly what.

\[(p \Rightarrow q) \wedge (p \Rightarrow \sim q)\] \[\equiv (\sim p \vee q) \wedge (\sim p \vee \sim q) \qquad \text{law of implication, twice}\] \[\equiv \sim p \vee (q \wedge \sim q) \qquad \text{distributivity}\] \[\equiv \sim p \vee \textbf{false} \qquad \text{law of contradiction}\] \[\equiv \sim p \qquad \text{simplification with false}\]

The answer is \(\sim p\), and it is worth pausing over. The two premises together do not produce a contradiction; they produce the conclusion that \(p\) must be false. If \(p\) were true you could derive both \(q\) and \(\sim q\), which is impossible, so \(p\) is not true. The algebra reached that conclusion in four lines without any reasoning about what \(p\) and \(q\) mean.

Simplify \(\sim(p \wedge \sim q) \wedge \sim q\), naming the law used at each step. Then build the truth table of the original formula and of your answer, and check that the two final columns agree in all four rows. If they do not, the error will be in whichever step you could not name.

1.2.8 Modus Ponens and the Chain Rule

Everything so far has been about single formulae. Reasoning, though, means starting from statements you accept and arriving at one you did not have before. The statements accepted at the start are called the premises, and the statement arrived at is the conclusion.

The question to be settled is when a conclusion genuinely follows. The test is this: form the conjunction of all the premises, make it the antecedent of an implication whose consequent is the conclusion, and check whether the resulting formula is a tautology. If it is, the conclusion follows in every case, and the argument is sound. If it is not, there is at least one interpretation in which the premises all hold and the conclusion fails — and that single row is enough to reject the argument.

Two patterns of argument are named in this syllabus: modus ponens and the chain rule.

Modus ponens

modus ponens Statement: from the premises \(p\) and \(p \Rightarrow q\), the conclusion \(q\) follows. Equivalently, \((p \wedge (p \Rightarrow q)) \Rightarrow q\) is a tautology. In words: if you accept a conditional and you accept its antecedent, you must accept its consequent. Why it holds: the premises can both be true only in the row where \(p\) is true and \(p \Rightarrow q\) is true, which forces \(q\) to be true; Table 1.24 shows the whole formula taking the value 1 in every row. Used for: the single most common step in any chain of reasoning — discharging a conditional once its condition is known to hold. Watch out: it runs one way only. Accepting \(p \Rightarrow q\) together with \(q\) does not let you conclude \(p\); that would be using the converse, which section 1.1.7 showed is not equivalent.

Table 1.24 – truth table showing that \((p \wedge (p \Rightarrow q)) \Rightarrow q\) is a tautology

\(p\) \(q\) \(p \Rightarrow q\) \(p \wedge (p \Rightarrow q)\) \((p \wedge (p \Rightarrow q)) \Rightarrow q\)
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1

The final column is all 1s, so the conclusion is established. Row three is the one that carries the weight: there \(q\) is false, and the argument survives only because the premises cannot both hold there — \(p \Rightarrow q\) has failed.

The same result can be reached without any table, using the laws of the previous subsections.

\[(p \wedge (p \Rightarrow q)) \Rightarrow q\] \[\equiv (p \wedge (\sim p \vee q)) \Rightarrow q \qquad \text{law of implication}\] \[\equiv ((p \wedge \sim p) \vee (p \wedge q)) \Rightarrow q \qquad \text{distributivity}\] \[\equiv (\textbf{false} \vee (p \wedge q)) \Rightarrow q \qquad \text{law of contradiction}\] \[\equiv (p \wedge q) \Rightarrow q \qquad \text{simplification with false}\] \[\equiv \sim(p \wedge q) \vee q \qquad \text{law of implication}\] \[\equiv (\sim p \vee \sim q) \vee q \qquad \text{De Morgan's law}\] \[\equiv \sim p \vee (\sim q \vee q) \qquad \text{associativity}\] \[\equiv \sim p \vee \textbf{true} \qquad \text{law of excluded middle}\] \[\equiv \textbf{true} \qquad \text{simplification with true}\]

The derivation ends at true, which is precisely what “the formula is a tautology” means.

The chain rule

the chain rule Statement: from the premises \(p \Rightarrow q\) and \(q \Rightarrow r\), the conclusion \(p \Rightarrow r\) follows. Equivalently, \(((p \Rightarrow q) \wedge (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)\) is a tautology. In words: conditionals link end to end, and the middle statement drops out. Why it holds: if \(p\) holds then \(q\) must hold by the first premise, and then \(r\) must hold by the second, so \(p\) cannot hold with \(r\) failing; Table 1.25 confirms this over all eight rows. Used for: joining a series of conditionals into one, which is how a long argument is compressed into a single statement. Watch out: the two premises must share the middle statement in the right positions. \(p \Rightarrow q\) together with \(r \Rightarrow q\) gives no chain at all, because \(q\) is the consequent of both.

Table 1.25 – truth table showing that \(((p \Rightarrow q) \wedge (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)\) is a tautology

\(p\) \(q\) \(r\) \(p \Rightarrow q\) \(q \Rightarrow r\) \((p \Rightarrow q) \wedge (q \Rightarrow r)\) \(p \Rightarrow r\) whole formula
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 1 0 1 0 0 1 1
0 1 1 1 1 1 1 1
1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1

Rows five and seven are the ones that would break the argument if anything could. In both of them the conclusion \(p \Rightarrow r\) is false — and in both, the conjunction of the premises is also false, so the implication as a whole is true. There is no row in which the premises hold and the conclusion fails, which is exactly what soundness requires.

Fig. 1.2-2 shows why the rule is called a chain.

Diagram

Fig. 1.2-2 – three circles in a horizontal row labelled p, q and r; a solid arrow from p to q labelled “premise p ⇒ q”; a solid arrow from q to r labelled “premise q ⇒ r”; a curved dashed arrow drawn beneath, running directly from p to r, labelled “conclusion p ⇒ r”; a note beside the q circle reading “the middle statement drops out of the conclusion”

Choosing between the two methods

Both methods answer the same question, and both are complete — neither can give a wrong verdict if carried out correctly. They differ in cost and in what they reveal.

Table 1.26 – checking an argument by truth table vs by the equivalence laws

Feature Truth table method Algebraic method
What is produced every interpretation, listed a chain of equivalences ending in true, or elsewhere
Effort as variables increase doubles with each variable: 4, 8, 16, 32 rows roughly unchanged; depends on the shape of the formula, not the count
Risk of failure none, if every row is written and checked you may fail to spot the step that works, and be left unsure
What it shows when the argument is unsound the exact row where the premises hold and the conclusion fails a simplified formula that is not true, without naming the offending case
Best suited to few variables; settling a doubtful claim beyond argument many variables; showing why a conclusion follows

The last row is the practical guidance. A table proves; an algebraic derivation explains. When a question asks you to be certain, build the table. When it asks you to show how a conclusion arises, use the laws — and name every one of them.

Test the argument “from the premises \(p \vee q\) and \(\sim p\), conclude \(q\)” by both methods. First build the truth table of \(((p \vee q) \wedge \sim p) \Rightarrow q\) and check whether the final column is all 1s. Then start from that formula and simplify it with the laws of Table 1.23, naming each one, and see whether you reach true.

1.3 Binary Valued Quantities and the Postulates of Boolean Algebra

Everything in the first two sections was written about statements. Statements are convenient for learning the rules, but they are not what the rules are used on. A circuit does not hold an opinion about whether the library is open; it holds a voltage, and the voltage is either present or absent.

This section makes that change of subject. The rules do not change at all — they are the same rules, verified by the same tables — but the notation changes to the one used by engineers since Shannon, and the objects being reasoned about become quantities rather than sentences.

1.3.1 Binary Valued Quantities and Binary Valued Variables

Consider some questions that a machine might have to answer.

  • Is the door of the lift closed?
  • Has the coin been inserted?
  • Is the tank full?

Each has exactly two possible answers. There is no third answer, no partial answer, and no answer that lies between the two. A quantity of this kind is called a binary valued quantity.

NoteDefinition

A binary valued quantity is a quantity that can take exactly one of two possible values, and no other.

The two values may be named in whatever way suits the situation — true and false, yes and no, on and off, closed and open, high and low. Boolean algebra names them 1 and 0, and treats every other pair of names as a description of the same two values.

A binary valued variable, also called simply a binary variable, is a variable that holds such a quantity.

NoteDefinition

A binary valued variable is a variable whose value is a binary valued quantity — that is, a variable that can hold only 0 or 1.

By long convention Boolean variables are written as capital letters: \(A\), \(B\), \(C\), \(X\), \(Y\). Writing \(A = 1\) means the quantity that \(A\) stands for is present, holds, or is true; \(A = 0\) means it is absent, fails, or is false.

The correspondence with section 1.1 is exact and needs stating once, plainly. A propositional variable and a binary valued variable are the same thing under two names: 1 replaces true, 0 replaces false, and every truth table already built remains valid without a single entry being altered.

Q4. Boole’s algebra allows a variable to take only two values. Why does that restriction make it fit an electrical switch so exactly, when ordinary algebra does not?

A. Because a switch has exactly two states and nothing in between — it is closed or it is open, carrying current or not carrying it. An ordinary algebraic variable can take any of infinitely many values, so most of what ordinary algebra can express has no meaning for a switch; there is no state of a switch corresponding to 2.7. A Boolean variable, by contrast, has precisely as many values as a switch has states, so every Boolean expression describes some arrangement of switches and every arrangement of switches is described by some Boolean expression. The restriction that looks like a weakness is exactly what makes the fit perfect.

The restriction to two values is also why Boolean algebra is reliable in a physical device. A circuit does not have to measure a voltage accurately; it only has to decide which of two ranges the voltage falls in. A reading that has drifted a little is still read as the same value, so small errors do not accumulate. An algebra with more values would have demanded accuracy that hardware cannot cheaply provide.

1.3.2 The Operations AND, OR and NOT

Boolean algebra has exactly three operations. Every expression in this chapter, however long, is built from these three and nothing else.

The notation used from here onwards

From this point the older engineering notation is used, and it is the notation of the rest of the chapter:

  • NOT is written as a bar over the quantity: \(\overline{A}\);
  • OR is written with a plus sign: \(A + B\);
  • AND is written as a product, usually with no symbol at all between the letters: \(AB\), or \(A \cdot B\) where a dot makes the expression clearer.

So the propositional formula \(\sim p \vee (q \wedge r)\) becomes the Boolean expression \(\overline{A} + BC\). Table 1.30 later in this subsection sets the two notations side by side.

NOT

The NOT operation, also called complement, reverses the value of a single quantity. It is written \(\overline{A}\) and read “\(A\) bar” or “not \(A\)”.

Table 1.27 – truth table of NOT; the second column holds the complement of the first

\(A\) \(\overline{A}\)
0 1
1 0

NOT is the only operation of the three that takes a single input. Because complementing twice returns the original value, \(\overline{\overline{A}}\) is simply \(A\) — a result that reappears as a named theorem in section 1.4.2.

OR

The OR operation, also called logical addition, gives 1 when at least one of its inputs is 1.

Table 1.28 – truth table of OR; the third column holds \(A + B\)

\(A\) \(B\) \(A + B\)
0 0 0
0 1 1
1 0 1
1 1 1

Written out as separate statements, the four rows say

\[0 + 0 = 0 \qquad 0 + 1 = 1 \qquad 1 + 0 = 1 \qquad 1 + 1 = 1\]

Three of those four look like ordinary arithmetic. The fourth does not, and it is the single most important thing to fix in mind about the plus sign in this chapter.

carrying in a Boolean sum What students write:

1 + 1 = 10

What happens: a carry has been produced where none exists, and every expression containing that step yields a value outside {0, 1}, which is not a Boolean value at all. The fix: the plus sign here is logical addition, not binary arithmetic. It asks “is at least one of these 1?” and the answer to that question is 1, never 10. Binary arithmetic with carries is a separate operation, built later out of these ones.

AND

The AND operation, also called logical product, gives 1 only when all of its inputs are 1.

Table 1.29 – truth table of AND; the third column holds \(A \cdot B\)

\(A\) \(B\) \(A \cdot B\)
0 0 0
0 1 0
1 0 0
1 1 1

Here the resemblance to arithmetic is complete: \(0 \cdot 0 = 0\), \(0 \cdot 1 = 0\), \(1 \cdot 0 = 0\) and \(1 \cdot 1 = 1\) are exactly the products of those numbers. This is why AND is written as a product and why the dot is usually dropped, and it is a small piece of luck that makes Boolean algebra easy to manipulate on paper.

The two notations

Table 1.30 – the same operations in propositional and Boolean notation

Operation Propositional notation Boolean notation Also called
not \(\sim p\) \(\overline{A}\) complement, inversion
and \(p \wedge q\) \(AB\) or \(A \cdot B\) logical product, conjunction
or \(p \vee q\) \(A + B\) logical sum, disjunction
if… then \(p \Rightarrow q\) \(\overline{A} + B\) —
if and only if \(p \Leftrightarrow q\) \(AB + \overline{A}\,\overline{B}\) —

The last two rows are not new operations. They are the law of implication and the law of the biconditional from section 1.2.4, rewritten. Boolean algebra has no separate symbol for implication because it does not need one.

1.3.3 Boolean Expressions and Their Truth Tables

A Boolean expression is any combination of binary valued variables, the constants 0 and 1, and the three operations.

NoteDefinition

A Boolean expression is an expression formed from binary valued variables and the constants 0 and 1, using only the operations AND, OR and NOT.

\(A + B \cdot 1\), \(\overline{A}(B + \overline{C})\) and \(\overline{A + BC}\) are Boolean expressions. \(A + 2B\) is not, because 2 is not a binary value; \(A - B\) is not, because subtraction is not one of the three operations.

Table 1.31 – arithmetic expression vs Boolean expression

Feature Arithmetic expression Boolean expression
Values a variable may hold any number 0 or 1 only
Operations available \(+\), \(-\), \(\times\), \(\div\) and others AND, OR, NOT only
Meaning of \(+\) addition with carry logical addition; \(1 + 1 = 1\)
Meaning of \(\times\) multiplication logical product; matches ordinary multiplication on 0 and 1
How it is checked by substituting sample values; infinitely many remain untested by a truth table listing all \(2^n\) combinations; nothing remains untested

The last row is the same point that answered the third Curiosity Corner question, now stated for expressions rather than formulae. A Boolean expression can be verified completely.

Order of evaluation

Boolean operations follow a fixed precedence, and it matches the one used in section 1.1.4:

\[\text{NOT} \quad,\quad \text{AND} \quad,\quad \text{OR}\]

NOT is applied first, then AND, then OR, unless brackets say otherwise. So \(\overline{A} + BC\) means “complement \(A\), form the product \(BC\), then add the two”, and not anything else. Fig. 1.3-1 marks the order on the expression itself.

Diagram

Fig. 1.3-1 – the expression A̅ + BC written large across the centre; a numbered call-out labelled “1” points to the bar over A with the note “NOT first”; a numbered call-out labelled “2” points to the product BC with the note “AND next”; a numbered call-out labelled “3” points to the + sign with the note “OR last”; beneath, a second line shows the same expression fully bracketed as (A̅) + (B·C) with the caption “the brackets that precedence supplies for you”

A bar that stretches over several symbols, such as the one in \(\overline{A + BC}\), is a bracket in disguise: it says complement the whole of what lies beneath it, so everything under the bar is evaluated first. \(\overline{A + BC}\) and \(\overline{A} + BC\) are quite different expressions, and confusing them is a frequent source of wrong truth tables.

Building the truth table of an expression

The method is the one from section 1.1.3, unchanged: all \(2^n\) rows in standard binary counting order, one new column at a time, each column depending only on columns already written.

Take \(F = A\overline{B} + \overline{A}C\).

Table 1.32 – truth table of \(F = A\overline{B} + \overline{A}C\), with intermediate columns

\(A\) \(B\) \(C\) \(\overline{A}\) \(\overline{B}\) \(A\overline{B}\) \(\overline{A}C\) \(F\)
0 0 0 1 1 0 0 0
0 0 1 1 1 0 1 1
0 1 0 1 0 0 0 0
0 1 1 1 0 0 1 1
1 0 0 0 1 1 0 1
1 0 1 0 1 1 0 1
1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0

Read the fifth row across as a check. There \(A = 1\), so \(\overline{A} = 0\) and the term \(\overline{A}C\) must be 0 whatever \(C\) is; \(B = 0\), so \(\overline{B} = 1\) and \(A\overline{B} = 1\); the sum is \(1 + 0 = 1\).

Notice how much the intermediate columns do. Each of the two product terms has its own column, and each is either plainly 0 or plainly 1 by inspection of two entries. Attempting to fill the \(F\) column directly, without them, is where most errors in this subject are made.

Q. The expression has three variables, but the last two rows of Table 1.32 give the same value of \(F\). Does that mean \(C\) is not really needed?

A. No. Two rows agreeing proves nothing on its own; rows two and four also agree with each other, while rows one and two disagree. \(C\) matters wherever \(A = 0\) — compare rows one and two — so it cannot be dropped from the expression. Whether an expression can be shortened is settled by the methods of sections 1.4 and 1.6, not by glancing at a pair of rows.

1.3.4 The Basic Postulates

Boolean algebra, like any algebra, starts from a small set of statements that are assumed rather than proved. Such a statement is called a postulate, and a statement derived from the postulates is called a theorem.

NoteDefinition

A postulate is a statement that is assumed to be true without proof, and used as a starting point for further reasoning. A theorem is a statement proved to be true using the postulates and previously proved theorems.

Postulates are also called axioms. They are not arbitrary — they are chosen because they describe the system faithfully — but within the system they are the bedrock, and asking for a proof of a postulate is asking the wrong question.

The postulates of Boolean algebra are these.

  1. Every variable takes a value from the set \(\{0, 1\}\), and \(0 \neq 1\).
  2. Three operations exist — AND, OR and NOT — defined exactly by Tables 1.27, 1.28 and 1.29.
  3. Applying any of the three operations to values from \(\{0, 1\}\) gives a result in \(\{0, 1\}\). The algebra never produces a value outside the set it started with.

The third postulate is what the error box in section 1.3.2 was really about. If \(1 + 1\) were 10, the algebra would leak out of its own two-element set at the first step and nothing built on it would be dependable.

Writing out the operations for the constants alone gives the list that is usually quoted as the basic postulates.

Table 1.33 – the basic postulates of Boolean algebra, written out for the constants

OR AND NOT
\(0 + 0 = 0\) \(0 \cdot 0 = 0\) \(\overline{0} = 1\)
\(0 + 1 = 1\) \(0 \cdot 1 = 0\) \(\overline{1} = 0\)
\(1 + 0 = 1\) \(1 \cdot 0 = 0\)
\(1 + 1 = 1\) \(1 \cdot 1 = 1\)

Every entry in Table 1.33 involves constants only. That is what distinguishes a postulate from the theorems of section 1.4: a statement such as \(A + 1 = 1\) contains a variable, so it makes a claim about both possible values of \(A\) at once and has to be established, briefly but genuinely, rather than assumed.

That “briefly but genuinely” deserves a word, because it explains why proofs in this algebra are unusually easy. To prove a statement about one variable, there are two cases to check; about two variables, four. A complete case-by-case check is always available, and it always terminates. In ordinary algebra no such luxury exists.

1.3.5 Compound Boolean Expressions

Three operations are enough to build every Boolean expression, but a few particular combinations arise so often that they are given names of their own. Four are named here. They are expressions, not new operations — each one is written out in terms of AND, OR and NOT — and in the following chapter each will reappear as a component you can buy.

NOR and NAND

NOR is the complement of OR: \(\overline{A + B}\). NAND is the complement of AND: \(\overline{A \cdot B}\). The names are contractions of “not-OR” and “not-AND”, and Fig. 1.3-2 shows how each is formed.

Diagram

Fig. 1.3-2 – two horizontal chains; upper chain: a box labelled “A + B (OR)” followed by an arrow labelled “complement” leading to a box labelled “A + B with a bar over the whole (NOR)”; lower chain: a box labelled “A · B (AND)” followed by an arrow labelled “complement” leading to a box labelled “A · B with a bar over the whole (NAND)”; a caption beneath reading “each is the basic operation with a bar laid over the entire result”

Table 1.34 – truth tables of NOR and NAND, shown beside the operations they complement

\(A\) \(B\) \(A + B\) \(\overline{A + B}\) \(A \cdot B\) \(\overline{A \cdot B}\)
0 0 0 1 0 1
0 1 1 0 0 1
1 0 1 0 0 1
1 1 1 0 1 0

The NOR column is 1 in one row only — the row where both inputs are 0. NAND is 0 in one row only — the row where both inputs are 1. Each is the exact opposite of the operation it is built from, column for column.

De Morgan’s laws, which section 1.4.6 restates in this notation, give each of them a second form: \(\overline{A + B}\) can also be written \(\overline{A} \cdot \overline{B}\), and \(\overline{A \cdot B}\) can also be written \(\overline{A} + \overline{B}\). Both forms describe the same column of Table 1.34, and being able to move between them is what makes these two expressions unexpectedly powerful in the next chapter.

XOR and XNOR

XOR, short for exclusive-OR, is 1 when its two inputs differ:

\[A \oplus B = \overline{A}B + A\overline{B}\]

This is the exclusive or promised in the Side Note of section 1.1.2 — the one that excludes the case where both parts hold. Reading the expression aloud makes the definition clear: either \(A\) fails and \(B\) holds, or \(A\) holds and \(B\) fails.

XNOR is its complement, and is therefore 1 when the two inputs are the same:

\[\overline{A \oplus B} = AB + \overline{A}\,\overline{B}\]

Table 1.35 – truth tables of XOR and XNOR, with the product terms that build them

\(A\) \(B\) \(\overline{A}B\) \(A\overline{B}\) \(\overline{A}B + A\overline{B}\) (XOR) \(AB\) \(\overline{A}\,\overline{B}\) \(AB + \overline{A}\,\overline{B}\) (XNOR)
0 0 0 0 0 0 1 1
0 1 1 0 1 0 0 0
1 0 0 1 1 0 0 0
1 1 0 0 0 1 0 1

Compare the XNOR column with Table 1.6. They are the same four values in the same order, which says something worth keeping: XNOR is the biconditional in Boolean dress. It asks whether two quantities agree, and that is exactly what “if and only if” asks about two statements.

XOR asks the opposite question — do these two differ? — and a circuit that can answer it is the first thing needed to add two binary digits, which is where the next chapter begins.

Build the truth table of \(\overline{A}\,\overline{B} + AB\) and of \(\overline{\overline{A}B + A\overline{B}}\) on paper, each with its intermediate columns, and check that the two final columns agree in all four rows. You will have proved for yourself the claim made above, that the two written forms of XNOR describe the same quantity.

1.4 Basic Theorems of Boolean Algebra

The postulates of section 1.3.4 say what the operations do to the constants 0 and 1. That is a very small stock of knowledge. This section builds on it, and everything proved here is a theorem in the strict sense: a statement established from the postulates, not assumed.

Two methods of proof are available, and both will be used.

The first is perfect induction, which means checking every possible case. A statement about one variable has two cases; a statement about two variables has four. Because the number of cases is always finite and usually tiny, a complete check is genuinely a proof and not a sample. In practice, perfect induction means building the truth table and comparing two columns.

The second is algebraic derivation: starting from one side of the statement and reaching the other by applying postulates and previously proved theorems, naming each one as you go. This is slower to learn, but it scales — a derivation involving four variables is no longer than one involving two, whereas its truth table is four times the size.

Several of the results below have already appeared in section 1.2 in propositional notation. They are not being proved twice for the sake of it. There they were laws about statements, checked with truth tables; here they are theorems about quantities, and the point of the exercise is the algebra — the derivations, the pairing of theorems by duality, and the reductions of section 1.4.8, none of which the earlier section touched.

1.4.1 Duality

Look again at the postulates in Table 1.33 and do something strange to them. In the OR column, replace every 0 by a 1, every 1 by a 0, and every \(+\) by a dot. The first line, \(0 + 0 = 0\), becomes \(1 \cdot 1 = 1\). The second, \(0 + 1 = 1\), becomes \(1 \cdot 0 = 0\). Carry on and you will find you have written out the AND column exactly.

The two halves of the algebra are mirror images of each other. That symmetry is called duality, and it is not an accident of how the tables were arranged; it is a structural fact, and it has a consequence that saves half the work in this whole section. The statement obtained by making the swap is called the dual of the original.

NoteDefinition

The dual of a Boolean statement is obtained by interchanging every \(+\) with a \(\cdot\), every \(\cdot\) with a \(+\), every 0 with a 1 and every 1 with a 0. The variables, and any complements on them, are left exactly as they are.

the principle of duality Statement: if a Boolean statement is true, then its dual is also true. In words: every theorem of Boolean algebra comes with a free companion theorem, obtained by swapping AND with OR and 0 with 1. Why it holds: the postulates themselves come in dual pairs — interchanging the symbols turns the definition of OR into the definition of AND and back again. Any proof built from the postulates can therefore be rewritten symbol for symbol into a proof of the dual statement. Used for: obtaining the second form of every theorem in this section without proving it, and for converting between the sum-of-products and product-of-sums forms of section 1.5. Watch out: duality is not complementation. The dual of an expression is a different expression, generally with a different truth table; the principle says that a true statement stays true, not that an expression keeps its value.

Fig. 1.4-1 shows the two swaps being made on a single statement.

Diagram

Fig. 1.4-1 – a statement and its dual, one above the other; upper line reads “A + A·B = A” with the + sign circled and labelled “swap to ·” and the · circled and labelled “swap to +”; two curved arrows lead downward to the lower line, which reads “A · (A + B) = A”; a note at the side reads “variables A and B, and any bars on them, are left unchanged”; a caption beneath reads “both statements are true; proving one proves the other”

Table 1.36 – Boolean statements and their duals

Statement Dual
\(A + 0 = A\) \(A \cdot 1 = A\)
\(A + 1 = 1\) \(A \cdot 0 = 0\)
\(A + \overline{A} = 1\) \(A \cdot \overline{A} = 0\)
\(A + AB = A\) \(A(A + B) = A\)
\(A(B + C) = AB + AC\) \(A + BC = (A + B)(A + C)\)

The last row is worth a second look, because it explains something left unexplained in section 1.2.2. There it was remarked that the second distributive law has no counterpart in ordinary arithmetic and yet holds exactly in logic. Duality is the reason. Ordinary arithmetic has no such symmetry between \(+\) and \(\times\) — there is nothing that turns addition into multiplication and back — so its distributive law stands alone. Boolean algebra has the symmetry, so its distributive law necessarily comes in a pair.

Duality applies to expressions as well as to whole statements. The dual of \(\overline{A}B + C\) is \((\overline{A} + B)C\): the product became a sum, the sum became a product, and the bar over \(A\) stayed exactly where it was.

complementing an expression when the dual was asked for What students write:

Expression:  A + B·C
"Dual":      A̅ · (B̅ + C̅)

What happens: every variable has been complemented, which is what De Morgan’s theorem does, not what duality does. The answer given is the complement, and it is a different expression from the dual. The fix: for a dual, change only the operations and the constants — swap \(+\) with \(\cdot\) and 0 with 1 — and touch nothing else. The correct dual of \(A + BC\) is \(A(B + C)\), with no new bars anywhere.

1.4.2 Idempotence, Involution and Operations with 0 and 1

The first group of theorems concerns a variable combined with itself, with its own double complement, and with the constants. Every one of them can be proved by perfect induction on a table of two rows, and Table 1.37 proves them all at once.

Table 1.37 – perfect induction proof of idempotence, involution and the operations with 0 and 1; compare each of the last six columns with the first

\(A\) \(\overline{A}\) \(\overline{\overline{A}}\) \(A + A\) \(A \cdot A\) \(A + 0\) \(A \cdot 1\) \(A + 1\) \(A \cdot 0\)
0 1 0 0 0 0 0 1 0
1 0 1 1 1 1 1 1 0

Every claim below is read off this table by comparing two columns.

Idempotence says that combining a quantity with itself changes nothing:

\[A + A = A \qquad\qquad A \cdot A = A\]

Columns four and five of Table 1.37 both reproduce column one. In words: asserting something twice is no stronger than asserting it once, and requiring it twice is no stronger than requiring it once. The two statements are duals of each other, so proving either one would have been enough.

Involution says that complementing twice restores the original:

\[\overline{\overline{A}} = A\]

Column three reproduces column one. Involution is its own dual, since it contains no \(+\), no \(\cdot\), and no constants — there is nothing in it to swap.

The operations with 0 and 1 fall into two pairs. The first pair leaves the variable untouched:

\[A + 0 = A \qquad\qquad A \cdot 1 = A\]

Columns six and seven reproduce column one. Adding 0 offers no new alternative and multiplying by 1 imposes no new requirement, so in each case \(A\) survives.

The second pair destroys the variable altogether:

\[A + 1 = 1 \qquad\qquad A \cdot 0 = 0\]

Column eight is 1 in both rows regardless of \(A\), and column nine is 0 in both rows. Once a sum contains a 1, nothing else in the sum can matter; once a product contains a 0, nothing else in the product can rescue it. These two are the theorems that make long expressions collapse, and you will see them do it repeatedly in section 1.4.8.

1.4.3 Complements

Two theorems describe what happens when a quantity meets its own complement.

\[A + \overline{A} = 1 \qquad\qquad A \cdot \overline{A} = 0\]

Table 1.38 – perfect induction proof of the complement theorems

\(A\) \(\overline{A}\) \(A + \overline{A}\) \(A \cdot \overline{A}\)
0 1 1 0
1 0 1 0

The third column is 1 in both rows and the fourth is 0 in both rows, which is exactly what the two statements claim. Once again they are duals of each other.

These are the Boolean forms of two laws you already know. \(A + \overline{A} = 1\) is the law of excluded middle from section 1.2.5, and \(A \cdot \overline{A} = 0\) is the law of contradiction. The names differ between the two notations because that is how the subject is written in each; the content is identical.

Q. Both theorems seem to say something obvious. Why are they the two most used theorems in the whole section?

A. Because they are the only theorems that make a variable disappear. Every other theorem rearranges an expression or shortens it slightly; these two remove a variable outright, replacing it by a constant, and the constant is then swallowed by \(A + 1 = 1\) or \(A \cdot 0 = 0\). Look at any reduction in section 1.4.8 and you will find that the decisive step is one of these two.

They can also be run backwards, and that is the less obvious use. Reading \(1 = A + \overline{A}\) from right to left lets you introduce a variable into an expression where it was not present, multiplying a term by \((A + \overline{A})\) without changing its value. Section 1.5.2 depends on exactly that manoeuvre.

1.4.4 Commutativity, Associativity and Distributivity

These three appeared in section 1.2.2 as laws about statements. In Boolean notation they read:

Commutativity — the order of the two quantities does not matter:

\[A + B = B + A \qquad\qquad AB = BA\]

Associativity — when the same operation is used twice, the bracketing does not matter:

\[(A + B) + C = A + (B + C) \qquad\qquad (AB)C = A(BC)\]

Distributivity — the two operations spread over each other, in both directions:

\[A(B + C) = AB + AC \qquad\qquad A + BC = (A + B)(A + C)\]

The first distributive law was verified by perfect induction in Table 1.18. The second is its dual, so the principle of duality has already established it. It is worth deriving it algebraically as well, because the derivation is short and it shows the theorems of section 1.4.2 doing real work.

\[(A + B)(A + C)\] \[= A \cdot A + A \cdot C + B \cdot A + B \cdot C \qquad \text{first distributive law, twice}\] \[= A + AC + AB + BC \qquad \text{idempotence, } A \cdot A = A\] \[= A(1 + C + B) + BC \qquad \text{taking } A \text{ common}\] \[= A \cdot 1 + BC \qquad \text{operations with 1, } 1 + C + B = 1\] \[= A + BC \qquad \text{operations with 1}\]

Notice the fourth line. As soon as a 1 appeared inside the bracket, everything else in that bracket became irrelevant, exactly as section 1.4.2 promised.

A useful consequence

One reduction follows directly from the second distributive law and the complement theorems, and it is worth learning as a result in its own right because it appears constantly:

\[A + \overline{A}B = A + B\]

The derivation is three lines.

\[A + \overline{A}B = (A + \overline{A})(A + B) \qquad \text{second distributive law}\] \[= 1 \cdot (A + B) \qquad \text{complements}\] \[= A + B \qquad \text{operations with 1}\]

Table 1.39 confirms it by perfect induction.

Table 1.39 – perfect induction proof of \(A + \overline{A}B = A + B\); compare the fifth and sixth columns

\(A\) \(B\) \(\overline{A}\) \(\overline{A}B\) \(A + \overline{A}B\) \(A + B\)
0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1

Read the result in words and it stops being surprising. “\(A\) holds, or else \(A\) fails and \(B\) holds” covers precisely the cases in which \(A\) holds or \(B\) holds. The complement on \(A\) in the second term is doing no work at all, because the first term has already accounted for every case in which \(A\) is 1.

By duality, the companion result is \(A(\overline{A} + B) = AB\).

1.4.5 Absorption

The next theorem, absorption, removes a whole term from an expression, which is why its name is well chosen.

absorption Statement: \(A + AB = A\) and its dual \(A(A + B) = A\) In words: a term that already contains another term adds nothing to a sum; a factor that already contains another factor imposes nothing extra on a product. Why it holds: \(A + AB = A(1 + B) = A \cdot 1 = A\), using the first distributive law and the operations with 1; Table 1.40 confirms both forms by perfect induction. Used for: deleting redundant terms in a reduction, particularly after a distributive step has multiplied an expression out and produced terms that overlap. Watch out: absorption needs the whole of the smaller term inside the larger one. \(A + \overline{A}B\) is not absorbed, because \(\overline{A}\) is not \(A\); that expression reduces instead to \(A + B\) by the result of section 1.4.4.

Table 1.40 – perfect induction proof of both forms of absorption; compare columns four and six with column one

\(A\) \(B\) \(AB\) \(A + AB\) \(A + B\) \(A(A + B)\)
0 0 0 0 0 0
0 1 0 0 1 0
1 0 0 1 1 1
1 1 1 1 1 1

Fig. 1.4-2 shows why the theorem must hold, in a way that a column of digits does not quite convey.

Diagram

Fig. 1.4-2 – four horizontal strips one below the other, labelled at the left with the input combinations AB = 00, 01, 10, 11; two vertical bands run down the right-hand side, the first headed “rows where AB = 1” and shaded only against the strip 11, the second headed “rows where A = 1” and shaded against the strips 10 and 11; a bracket joins the two bands with the note “every shaded row of the narrow band is already shaded in the wide band, so adding it changes nothing”

The picture is the argument. The rows in which \(AB\) is 1 form a part of the rows in which \(A\) is 1. Adding a term by OR means adding its rows to the collection, and adding rows that are already there leaves the collection unchanged.

Q. Does absorption also work the other way round — does \(AB + A\) reduce to \(A\)?

A. Yes. Commutativity says \(AB + A = A + AB\), and absorption then gives \(A\). The order in which the two terms are written has no effect. What matters is that one term is a product containing the whole of the other.

1.4.6 De Morgan’s Theorem

In Boolean notation, the two laws of section 1.2.3 are together called De Morgan’s theorem.

De Morgan’s theorem Statement: \(\overline{A + B} = \overline{A} \cdot \overline{B}\) and \(\overline{A \cdot B} = \overline{A} + \overline{B}\) In words: the complement of a sum is the product of the complements, and the complement of a product is the sum of the complements. Why it holds: \(A + B\) is 0 only when both \(A\) and \(B\) are 0, which is exactly when \(\overline{A} \cdot \overline{B}\) is 1; Table 1.41 sets out all four rows for both forms. Used for: finding the complement of any expression, however long; breaking a long bar into individual bars; and rewriting an expression so that it uses only one kind of operation, which is what makes the universal gates of the next chapter possible. Watch out: the operation must change as the bar is broken. A bar over a sum becomes a product of bars, never a sum of bars.

Table 1.41 – perfect induction proof of both forms of De Morgan’s theorem; compare columns five and six, and columns seven and eight

\(A\) \(B\) \(\overline{A}\) \(\overline{B}\) \(\overline{A + B}\) \(\overline{A} \cdot \overline{B}\) \(\overline{A \cdot B}\) \(\overline{A} + \overline{B}\)
0 0 1 1 1 1 1 1
0 1 1 0 0 0 1 1
1 0 0 1 0 0 1 1
1 1 0 0 0 0 0 0

The syllabus uses two names for this result, and both are correct. In propositional logic it is called De Morgan’s laws, as in section 1.2.3; in Boolean algebra it is called De Morgan’s theorem. The wording differs because the two settings differ; the content is the same result, and Table 1.41 is Tables 1.19 and 1.20 rewritten in the notation of section 1.3.2.

The theorem extends to any number of variables. Applying it twice gives

\[\overline{A + B + C} = \overline{A} \cdot \overline{B} \cdot \overline{C} \qquad\qquad \overline{A \cdot B \cdot C} = \overline{A} + \overline{B} + \overline{C}\]

and the pattern continues however many terms there are: one long bar becomes a bar on each variable, with every operation under it changed to the other one.

1.4.7 Applications of De Morgan’s Theorem

The commonest use of the theorem is to find the complement of a given expression. The procedure is mechanical.

  1. Place a bar over the whole expression.
  2. Break the longest bar first, changing the operation beneath it from \(+\) to \(\cdot\) or from \(\cdot\) to \(+\).
  3. Repeat on each shorter bar produced, until every bar sits over a single variable.
  4. Tidy up any double bars using involution.
Finding a complement

Find the complement of \(F = AB + \overline{C}\).

\[\overline{F} = \overline{AB + \overline{C}}\] \[= \overline{AB} \cdot \overline{\overline{C}} \qquad \text{De Morgan's theorem, on the outer bar}\] \[= (\overline{A} + \overline{B}) \cdot \overline{\overline{C}} \qquad \text{De Morgan's theorem, on the bar over } AB\] \[= (\overline{A} + \overline{B})C \qquad \text{involution}\]

Check the answer against the meaning. \(F\) is 1 when \(AB\) is 1 or when \(C\) is 0. So \(\overline{F}\) must be 1 when \(AB\) is 0 and \(C\) is 1 — and \((\overline{A} + \overline{B})C\) says precisely that.

A complement with a bracket

Find the complement of \(F = \overline{X}(Y + \overline{Z})\).

\[\overline{F} = \overline{\overline{X}(Y + \overline{Z})}\] \[= \overline{\overline{X}} + \overline{(Y + \overline{Z})} \qquad \text{De Morgan's theorem, on the outer bar}\] \[= X + \overline{(Y + \overline{Z})} \qquad \text{involution}\] \[= X + \overline{Y} \cdot \overline{\overline{Z}} \qquad \text{De Morgan's theorem}\] \[= X + \overline{Y}Z \qquad \text{involution}\]

Notice that the outer operation in the original was AND, so the outer operation in the complement is OR. That flip happens at every level, and checking it is a quick way to catch a mistake: if the topmost operation has not changed, the theorem has not been applied.

complementing the variables and leaving the operations alone What students write:

F  =  A·B + C̅
F̅  =  A̅·B̅ + C

What happens: every variable has been complemented correctly, but the \(+\) and the \(\cdot\) have been left where they were. The result disagrees with the true complement in two rows out of eight, and the error is easy to miss because the expression looks plausible. The fix: each time a bar is broken, the operation beneath it must be swapped. Working from the outermost bar inwards, and writing one line per bar broken, makes it hard to forget.

De Morgan’s theorem has a second use that this chapter can only point at. Because a bar can convert every AND into an OR and every OR into an AND, an expression can be rewritten so that it needs only one kind of operation together with complementation. In the next chapter, where each operation is a physical component, that fact turns into the statement that a single kind of component is enough to build anything.

1.4.8 Reducing Boolean Expressions Algebraically

The theorems are now complete. Table 1.42 collects them, each with its dual, and it is the working list for every reduction in this chapter.

Table 1.42 – the basic theorems of Boolean algebra and their duals

Theorem Form Dual form
Idempotence \(A + A = A\) \(A \cdot A = A\)
Involution \(\overline{\overline{A}} = A\) — (self-dual)
Operations with 0 and 1 \(A + 0 = A\); \(A + 1 = 1\) \(A \cdot 1 = A\); \(A \cdot 0 = 0\)
Complements \(A + \overline{A} = 1\) \(A \cdot \overline{A} = 0\)
Commutativity \(A + B = B + A\) \(AB = BA\)
Associativity \((A + B) + C = A + (B + C)\) \((AB)C = A(BC)\)
Distributivity \(A(B + C) = AB + AC\) \(A + BC = (A + B)(A + C)\)
Absorption \(A + AB = A\) \(A(A + B) = A\)
De Morgan’s theorem \(\overline{A + B} = \overline{A} \cdot \overline{B}\) \(\overline{A \cdot B} = \overline{A} + \overline{B}\)
Consequence of the above \(A + \overline{A}B = A + B\) \(A(\overline{A} + B) = AB\)

A workable order of attack is this. Break every long bar first with De Morgan’s theorem, so that all complements sit on single variables. Then look for terms sharing a common factor and take it out. Then look for a variable standing beside its own complement — that is where a term collapses to a constant. Finally absorb what the constants allow.

As in section 1.2.7, name the theorem used at each step. A derivation whose steps are not named cannot be checked.

A reduction using complements

Simplify \(F = AB + A\overline{B}C + \overline{A}B\).

\[F = AB + A\overline{B}C + \overline{A}B\] \[= (AB + \overline{A}B) + A\overline{B}C \qquad \text{commutativity and associativity}\] \[= B(A + \overline{A}) + A\overline{B}C \qquad \text{distributivity, taking } B \text{ common}\] \[= B \cdot 1 + A\overline{B}C \qquad \text{complements}\] \[= B + \overline{B}(AC) \qquad \text{operations with 1; commutativity}\] \[= B + AC \qquad \text{the consequence } A + \overline{A}B = A + B\]

Three terms have become two, and one variable has disappeared from the expression entirely. The second step is the one that matters: two terms were brought together specifically because they differed only in the complement on \(A\), which is what allowed the complement theorem to strike that variable out.

A reduction using the second distributive law

Simplify \(F = (X + Y)(X + \overline{Y})(\overline{X} + Z)\).

\[F = (X + Y)(X + \overline{Y})(\overline{X} + Z)\] \[= (X + Y\overline{Y})(\overline{X} + Z) \qquad \text{second distributive law, on the first two factors}\] \[= (X + 0)(\overline{X} + Z) \qquad \text{complements}\] \[= X(\overline{X} + Z) \qquad \text{operations with 0}\] \[= X\overline{X} + XZ \qquad \text{first distributive law}\] \[= 0 + XZ \qquad \text{complements}\] \[= XZ \qquad \text{operations with 0}\]

Six lines have reduced three bracketed factors to a single product of two variables. Both distributive laws were needed, in opposite directions — the second law to pull \(X\) out of two brackets, the first to push \(X\) into one.

What algebraic reduction cannot promise

Every step above was justified, and each answer is correct. But notice what has not been claimed: that no shorter form exists.

This is the honest limitation of the method. There is no rule that tells you which theorem to apply next, no way to know that a promising step is not a dead end, and no signal that announces you have arrived at the shortest possible expression. Two students may reduce the same expression correctly and stop at two different forms, each convinced it is finished. With four variables and eight terms, the search becomes genuinely difficult.

That limitation is the reason section 1.6 exists. The Karnaugh map replaces the search with a procedure — you do not have to spot anything, you have only to look at a picture and follow rules — and for expressions of up to four variables it delivers the shortest form reliably.

Simplify \(F = \overline{A}B + \overline{A}BC + \overline{A}B\overline{C}D\) using the theorems of Table 1.42, naming each one. The whole reduction takes two steps and uses a single theorem twice. Then build the truth table of the original expression and of your answer, and check that the two final columns agree in all sixteen rows.

1.5 Sum of Products and Product of Sums

A single Boolean function can be written in an unlimited number of ways. \(A + \overline{A}B\), \(A + B\) and \((A + B)(A + \overline{A})\) all have the same truth table, and section 1.4 was largely about moving between such forms.

That freedom is useful when you are simplifying, and a nuisance when you are comparing. If two people describe the same function and hand you two different expressions, how would you tell that they had described the same thing? And if a function is given to you as a truth table rather than as an expression, where do you even begin?

Both problems are solved by agreeing on standard forms — shapes that any expression can be forced into, so that the same function always produces the same result. Boolean algebra has two such forms, and this section develops both.

1.5.1 Sum of Products Form

A product term is one or more variables, each possibly complemented, combined by AND: \(A\), \(\overline{B}\), \(AB\), \(\overline{A}C\) and \(A\overline{B}\,\overline{C}\) are all product terms. A single variable counts as a product term with one factor.

An expression that is a sum of product terms is said to be in sum of products (SOP) form.

NoteDefinition

An expression is in sum of products (SOP) form if it consists of product terms combined by OR, where each product term is a set of variables or their complements combined by AND, and no complement bar extends over more than a single variable.

The last condition matters. \(\overline{AB} + C\) has a bar stretching over two variables, so it is not in SOP form as it stands, even though it is a sum of two things.

Table 1.43 – expressions, whether each is in SOP form, and why

Expression SOP form? Reason
\(AB + \overline{A}C\) Yes Two product terms, joined by OR.
\(A + B + \overline{C}\) Yes Three product terms, each of one variable.
\(\overline{A}\,\overline{B}C\) Yes A single product term is a sum of one term.
\(A(B + C)\) No A product of a variable and a sum.
\(\overline{A + B} \cdot C\) No A bar extends over two variables.
\(AB + \overline{C + D}\) No The second term has a bar over a sum.
Reducing an expression to SOP form

Any expression can be brought to SOP form by two operations, applied in this order.

  1. Break every bar that extends over more than one variable, using De Morgan’s theorem, until each bar sits on a single variable.
  2. Multiply out every bracket using the first distributive law, and tidy the result with the theorems of Table 1.42.

Take \(F = (A + \overline{B})(B + C)\).

\[F = (A + \overline{B})(B + C)\] \[= AB + AC + \overline{B}B + \overline{B}C \qquad \text{first distributive law}\] \[= AB + AC + 0 + \overline{B}C \qquad \text{complements}\] \[= AB + AC + \overline{B}C \qquad \text{operations with 0}\]

Now one with a bar over a group. Take \(F = \overline{A + \overline{B}C}\).

\[F = \overline{A + \overline{B}C}\] \[= \overline{A} \cdot \overline{\overline{B}C} \qquad \text{De Morgan's theorem}\] \[= \overline{A}(\overline{\overline{B}} + \overline{C}) \qquad \text{De Morgan's theorem}\] \[= \overline{A}(B + \overline{C}) \qquad \text{involution}\] \[= \overline{A}B + \overline{A}\,\overline{C} \qquad \text{first distributive law}\]

The order of the two operations is not optional. Attempting to multiply out before the bars have been broken leaves a bar sitting over a bracket, and nothing useful can be done with it.

1.5.2 Minterms and the Canonical Sum of Products

SOP form is standard in shape but not yet standard in content. \(AB + AC + \overline{B}C\) and \(A + \overline{B}C\) may or may not be the same function; both are in SOP form, and looking at them tells you nothing. To compare functions we need a form in which each function has exactly one representation. That is what a minterm provides.

NoteDefinition

A minterm of \(n\) variables is a product term in which every one of the \(n\) variables appears exactly once, either complemented or uncomplemented.

For three variables \(A\), \(B\) and \(C\), the term \(A\overline{B}C\) is a minterm — all three variables are present, each once. \(AB\) is not a minterm in a three-variable problem, because \(C\) is missing. \(ABB\overline{C}\) is not one either, because \(B\) appears twice.

With \(n\) variables there are exactly \(2^n\) minterms, since each variable can appear in either of two ways and the choices are independent. Three variables give eight.

An expression written as a sum of minterms is called a canonical sum of products, also called a minterm expression. The word canonical means “in the standard form”; it is the guarantee that two people describing the same function will produce identical expressions.

Minterm designation

Each minterm can be labelled with a number instead of written out. The rule is to build a binary pattern from the term, taking the digit 1 for a variable that appears uncomplemented and 0 for one that appears complemented, reading the variables in a fixed order. The decimal value of that pattern becomes the subscript of the letter \(m\), and the result is called the minterm designation.

For variables read in the order \(A\), \(B\), \(C\):

  • \(A\overline{B}C\) gives the pattern 101, which is 5, so the designation is \(m_5\);
  • \(\overline{A}\,\overline{B}\,\overline{C}\) gives 000, which is 0, so the designation is \(m_0\);
  • \(ABC\) gives 111, which is 7, so the designation is \(m_7\).

Table 1.44 – the eight minterms of three variables \(A\), \(B\), \(C\), with their binary patterns and designations

Row \(A\) \(B\) \(C\) Minterm Designation
0 0 0 0 \(\overline{A}\,\overline{B}\,\overline{C}\) \(m_0\)
1 0 0 1 \(\overline{A}\,\overline{B}C\) \(m_1\)
2 0 1 0 \(\overline{A}B\overline{C}\) \(m_2\)
3 0 1 1 \(\overline{A}BC\) \(m_3\)
4 1 0 0 \(A\overline{B}\,\overline{C}\) \(m_4\)
5 1 0 1 \(A\overline{B}C\) \(m_5\)
6 1 1 0 \(AB\overline{C}\) \(m_6\)
7 1 1 1 \(ABC\) \(m_7\)

The first two columns of Table 1.44 are the opening columns of any three-variable truth table, in standard binary counting order. That is not a coincidence, and section 1.5.6 makes use of it.

There is one thing a minterm designation depends on that the symbol does not show: the order of the variables. If the same three variables are read in a different order, \(A\overline{B}\,\overline{C}\) would give the pattern 001 rather than 100, and become \(m_1\) instead of \(m_4\). The order must be stated and then kept.

writing minterm designations without fixing the variable order What students write:

F(A, B, C) = A̅BC̅ + ABC̅
"minterms":  m4 and m6      (written after reading B, A, C by mistake)

What happens: the designation numbers no longer match the rows of the truth table, so every later step — the cardinal form, the conversion to maxterms, the Karnaugh map of section 1.6 — is placed in the wrong cells. The fix: write the variable order down before you start, in the order given in the function’s name, and read every term in that order. \(F(A, B, C)\) means \(A\) first, so \(\overline{A}B\overline{C}\) is \(m_2\) and \(AB\overline{C}\) is \(m_6\).

Converting an expression to canonical SOP form

A product term that is missing a variable can be repaired without changing its value, using the complement theorem read backwards. Since \(X + \overline{X} = 1\) and multiplying by 1 changes nothing, a term missing the variable \(X\) may be multiplied by \((X + \overline{X})\) and then expanded.

Express \(F = A + \overline{B}C\) in canonical SOP form for the three variables \(A\), \(B\), \(C\).

The first term is missing both \(B\) and \(C\):

\[A = A(B + \overline{B})(C + \overline{C}) = (AB + A\overline{B})(C + \overline{C}) = ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\,\overline{C}\]

The second term is missing \(A\):

\[\overline{B}C = (A + \overline{A})\overline{B}C = A\overline{B}C + \overline{A}\,\overline{B}C\]

Adding the two and removing the repeated \(A\overline{B}C\) by idempotence:

\[F = ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\,\overline{C} + \overline{A}\,\overline{B}C\]

In designations, \(F = m_1 + m_4 + m_5 + m_6 + m_7\).

Q. Multiplying by \((B + \overline{B})\) made the expression four times longer. What was gained?

A. A form that can be compared and worked with. Canonical SOP is never the shortest way to write a function — it is close to the longest — but it is the only form in which two descriptions of the same function must look identical. It is also the form the Karnaugh map of section 1.6 requires as input, and the map then produces the shortest form. The expansion is a step on the way, not a destination.

1.5.3 Product of Sums Form

Everything in the last two subsections has a mirror image, and duality guarantees that the mirror image is equally valid.

A sum term is one or more variables, each possibly complemented, combined by OR: \(A\), \(\overline{B}\), \(A + B\) and \(\overline{A} + B + \overline{C}\) are sum terms. An expression that is a product of sum terms is in product of sums (POS) form.

NoteDefinition

An expression is in product of sums (POS) form if it consists of sum terms combined by AND, where each sum term is a set of variables or their complements combined by OR, and no complement bar extends over more than a single variable.

\((A + B)(\overline{A} + C)\) is in POS form. \((A + B)\overline{C}\) is in POS form too, with \(\overline{C}\) counting as a sum term of one variable. \(\overline{A + B} \cdot C\) is not, for the same reason as before — the bar spans two variables.

Reducing an expression to POS form

The procedure mirrors the one in section 1.5.1, but the second distributive law does the work instead of the first.

Take \(F = AB + C\).

\[F = AB + C = (A + C)(B + C) \qquad \text{second distributive law}\]

That single step is worth reading twice, because it is the one that has no arithmetic counterpart and therefore feels wrong the first few times. Check it on a row: with \(A = 1\), \(B = 0\), \(C = 0\), the original gives \(0 + 0 = 0\), and the new form gives \(1 \cdot 0 = 0\).

A second one. Take \(F = \overline{A}\,\overline{B} + C\).

\[F = \overline{A}\,\overline{B} + C = (\overline{A} + C)(\overline{B} + C) \qquad \text{second distributive law}\]

Table 1.45 – sum of products vs product of sums

Feature Sum of products (SOP) Product of sums (POS)
Overall shape terms ANDed, then ORed together terms ORed, then ANDed together
Built from product terms sum terms
Example \(AB + \overline{A}C\) \((A + B)(\overline{A} + C)\)
Obtained by multiplying out with the first distributive law factorising with the second distributive law
Standard version canonical SOP, a sum of minterms canonical POS, a product of maxterms
Read off a truth table from the rows where the function is 1 the rows where the function is 0
The whole expression is 1 when at least one product term is 1 every sum term is 1

The last two rows are the ones to hold on to. SOP describes a function by listing the situations that make it hold; POS describes the same function by listing the conditions that must all be met. Both are complete descriptions, and neither is more correct than the other — but one of them is usually far shorter than the other for a given function, which is why both are worth having.

1.5.4 Maxterms and the Canonical Product of Sums

The mirror image of a minterm is a maxterm.

NoteDefinition

A maxterm of \(n\) variables is a sum term in which every one of the \(n\) variables appears exactly once, either complemented or uncomplemented.

For three variables, \(A + \overline{B} + C\) is a maxterm; \(A + C\) is not, because \(B\) is missing. As with minterms, \(n\) variables give exactly \(2^n\) maxterms.

An expression written as a product of maxterms is a canonical product of sums, also called a maxterm expression.

Maxterm designation

The labelling rule for maxterms reverses the one for minterms. Build the binary pattern by taking 0 for a variable that appears uncomplemented and 1 for one that appears complemented, then use the decimal value as the subscript of a capital \(M\). This is the maxterm designation.

For variables read in the order \(A\), \(B\), \(C\), the maxterm \(A + \overline{B} + C\) gives the pattern 010, which is 2, so its designation is \(M_2\).

Table 1.46 – the eight maxterms of three variables \(A\), \(B\), \(C\), with their binary patterns and designations

Row \(A\) \(B\) \(C\) Maxterm Designation
0 0 0 0 \(A + B + C\) \(M_0\)
1 0 0 1 \(A + B + \overline{C}\) \(M_1\)
2 0 1 0 \(A + \overline{B} + C\) \(M_2\)
3 0 1 1 \(A + \overline{B} + \overline{C}\) \(M_3\)
4 1 0 0 \(\overline{A} + B + C\) \(M_4\)
5 1 0 1 \(\overline{A} + B + \overline{C}\) \(M_5\)
6 1 1 0 \(\overline{A} + \overline{B} + C\) \(M_6\)
7 1 1 1 \(\overline{A} + \overline{B} + \overline{C}\) \(M_7\)

The reversal of the bit convention looks arbitrary until you see what it buys. Compare row 2 of Tables 1.44 and 1.46. The minterm is \(\overline{A}B\overline{C}\) and the maxterm is \(A + \overline{B} + C\) — and by De Morgan’s theorem,

\[\overline{m_2} = \overline{\overline{A}B\overline{C}} = A + \overline{B} + C = M_2\]

The same holds in every row. Each maxterm is the complement of the minterm carrying the same number, and that relationship, \(M_i = \overline{m_i}\), is the whole reason the two conventions are opposite.

Table 1.47 – minterm vs maxterm

Feature Minterm Maxterm
Built by AND OR
Written as \(m_i\) \(M_i\)
Bit convention 1 for a plain variable, 0 for a complemented one 0 for a plain variable, 1 for a complemented one
Value in its own row of the truth table 1, and 0 in every other row 0, and 1 in every other row
Read off from a row where the function is 1 a row where the function is 0
Used to build canonical SOP canonical POS
Relation to the other \(m_i = \overline{M_i}\) \(M_i = \overline{m_i}\)

The fourth row explains the two names. A minterm is 1 in the smallest possible number of rows — exactly one — and a maxterm is 1 in the largest possible number — all but one.

Converting an expression to canonical POS form

A sum term missing a variable is repaired by the dual of the earlier trick. Since \(X\overline{X} = 0\) and adding 0 changes nothing, a sum term missing the variable \(X\) may have \(X\overline{X}\) added to it, and the second distributive law then splits it in two.

Express \(F = (A + \overline{B})(B + C)\) in canonical POS form.

The first term is missing \(C\):

\[A + \overline{B} = A + \overline{B} + C\overline{C} = (A + \overline{B} + C)(A + \overline{B} + \overline{C})\]

The second term is missing \(A\):

\[B + C = B + C + A\overline{A} = (A + B + C)(\overline{A} + B + C)\]

Multiplying the four factors together:

\[F = (A + B + C)(A + \overline{B} + C)(A + \overline{B} + \overline{C})(\overline{A} + B + C)\]

In designations, \(F = M_0 \cdot M_2 \cdot M_3 \cdot M_4\).

This is the same function whose SOP form was found in section 1.5.1 to be \(AB + AC + \overline{B}C\). The two expressions look nothing alike, and the next two subsections give the machinery to see at a glance that they agree.

1.5.5 Cardinal Representation

Once designations are available, a function can be named by a list of numbers and nothing else. This is the cardinal representation.

NoteDefinition

The cardinal representation of a function states the function’s variables in a fixed order, followed by the list of designations of the terms that appear in it: \(\Sigma\) for a sum of minterms, \(\pi\) for a product of maxterms.

The symbol \(\Sigma\) stands for summation and indicates that the listed minterms are to be ORed together; the symbol \(\pi\) stands for product and indicates that the listed maxterms are to be ANDed together.

So the function expanded in section 1.5.2 is written

\[F(A, B, C) = \Sigma(1, 4, 5, 6, 7)\]

and the function expanded in section 1.5.4 is written

\[F(A, B, C) = \pi(0, 2, 3, 4)\]

Two things are compulsory in this notation, and leaving either out makes it meaningless. The variables must be named, in order, because the designations depend on that order. And the symbol must be right: \(\Sigma(1, 4, 5)\) and \(\pi(1, 4, 5)\) describe entirely different functions.

Cardinal form is the most compact description of a Boolean function there is, and it is also the form in which a function is most often handed to you for reduction. Section 1.6 takes cardinal form as its starting point throughout.

1.5.6 Deriving Expressions from a Truth Table

The most useful skill in this section is the one that runs the other way: a function is described in words or given as a table, and an expression has to be produced.

The whole method rests on one observation about minterms. Look again at Table 1.44. The minterm \(m_5 = A\overline{B}C\) takes the value 1 when \(A = 1\), \(B = 0\) and \(C = 1\) — that is, in row 5 — and in every other row at least one of its three factors is 0, so the product is 0. A minterm is a switch that is on in exactly one row of the truth table.

So if you OR together the minterms of precisely those rows where the function is 1, the resulting expression is 1 in exactly those rows and 0 everywhere else. It is the function.

Fig. 1.5-1 shows a minterm being read off a single row.

Diagram

Fig. 1.5-1 – a single highlighted row of a three-variable truth table, showing the entries A = 1, B = 0, C = 1 and F = 1; three downward arrows lead from the three input entries to a line below reading “A · B̅ · C”; the first and third arrows carry the label “entry is 1, so write the variable plain”, the second carries the label “entry is 0, so write the variable complemented”; the assembled term A B̅ C is boxed and labelled “minterm m₅”; a note at the right reads “read only the rows where F = 1”

The dual observation holds for maxterms. The maxterm \(M_2 = A + \overline{B} + C\) is 0 when \(A = 0\), \(B = 1\), \(C = 0\), and 1 in every other row. ANDing together the maxterms of precisely those rows where the function is 0 gives an expression that is 0 in exactly those rows — again, the function itself.

Fig. 1.5-2 sets out the two routes.

Diagram

Fig. 1.5-2 – flow diagram with two branches from a common start; start box labelled “truth table of F”; upper branch of four boxes reading “select the rows where F = 1” → “write one minterm per row: plain variable for 1, complemented for 0” → “combine the minterms with OR” → “canonical SOP, Σ form”; lower branch of four boxes reading “select the rows where F = 0” → “write one maxterm per row: plain variable for 0, complemented for 1” → “combine the maxterms with AND” → “canonical POS, π form”; a two-headed arrow joins the two final boxes, labelled “the same function, described two ways”

A worked example

A school library counter follows this rule. A book is issued when the member’s card is valid, and either the book has not been reserved, or the reservation was made by that same member. Three conditions are involved:

  • \(V = 1\) if the member’s card is valid, 0 otherwise;
  • \(R = 1\) if the book has been reserved, 0 otherwise;
  • \(S = 1\) if the reservation was made by this same member, 0 otherwise;

and the output \(F = 1\) means the book is issued.

Building the table is a matter of applying the rule to each of the eight rows in turn. In every row where \(V = 0\) nothing can be issued, so the first four rows are 0. Row 6 has a valid card and a book reserved by someone else, so it is 0 as well. The other three rows satisfy the rule.

Table 1.48 – truth table of the library issue rule, with the minterm or maxterm contributed by each row

Row \(V\) \(R\) \(S\) \(F\) Term contributed
0 0 0 0 0 \(M_0 = V + R + S\)
1 0 0 1 0 \(M_1 = V + R + \overline{S}\)
2 0 1 0 0 \(M_2 = V + \overline{R} + S\)
3 0 1 1 0 \(M_3 = V + \overline{R} + \overline{S}\)
4 1 0 0 1 \(m_4 = V\overline{R}\,\overline{S}\)
5 1 0 1 1 \(m_5 = V\overline{R}S\)
6 1 1 0 0 \(M_6 = \overline{V} + \overline{R} + S\)
7 1 1 1 1 \(m_7 = VRS\)

Collecting the minterms from the three rows where \(F = 1\) gives the canonical SOP form:

\[F = V\overline{R}\,\overline{S} + V\overline{R}S + VRS \qquad\qquad F(V, R, S) = \Sigma(4, 5, 7)\]

Collecting the maxterms from the five rows where \(F = 0\) gives the canonical POS form:

\[F = (V + R + S)(V + R + \overline{S})(V + \overline{R} + S)(V + \overline{R} + \overline{S})(\overline{V} + \overline{R} + S)\]

\[F(V, R, S) = \pi(0, 1, 2, 3, 6)\]

Both expressions describe the same rule. Here the SOP form is much the shorter, because the function is 1 in only three rows out of eight; had it been 1 in five rows, the POS form would have been the shorter one. This is the practical reason for knowing both.

The SOP form also reduces neatly, which is a useful check that the table was built correctly:

\[F = V\overline{R}\,\overline{S} + V\overline{R}S + VRS\] \[= V\overline{R}(\overline{S} + S) + VRS \qquad \text{distributivity}\] \[= V\overline{R} + VRS \qquad \text{complements; operations with 1}\] \[= V(\overline{R} + RS) \qquad \text{distributivity}\] \[= V(\overline{R} + S) \qquad \text{the consequence } A + \overline{A}B = A + B\]

Read the last line back into English: the card is valid, and either the book is not reserved or the reservation is this member’s. That is the rule the counter was given, recovered from the table.

A hostel mess prints a guest coupon when the resident’s dues are cleared and the guest has been registered, or when the warden has given written permission. Take \(D = 1\) for dues cleared, \(G = 1\) for guest registered and \(W = 1\) for written permission, and build the eight-row truth table. Then write the canonical SOP form and the cardinal \(\Sigma\) representation, and count its minterms. Predict the number of maxterms before you count them.

1.5.7 Converting Between the Two Canonical Forms

Table 1.48 makes the conversion rule obvious once it is pointed out. Every row of the truth table produces exactly one term — a minterm if the function is 1 there, a maxterm if it is 0 — and every row does one or the other. So for a function of \(n\) variables:

\[(\text{number of minterms}) + (\text{number of maxterms}) = 2^n\]

and the two lists of designation numbers, taken together, use up every number from 0 to \(2^n - 1\) exactly once. Each list is therefore completely determined by the other.

To convert, write down the numbers that are missing.

Take \(F(X, Y, Z) = \Sigma(0, 2, 5)\). There are three variables, so the numbers available are 0 to 7. The list uses 0, 2 and 5; the ones left over are 1, 3, 4, 6 and 7. Hence

\[F(X, Y, Z) = \pi(1, 3, 4, 6, 7)\]

Written out, with \(X\), \(Y\), \(Z\) read in that order, the two forms are

\[F = \overline{X}\,\overline{Y}\,\overline{Z} + \overline{X}Y\overline{Z} + X\overline{Y}Z\]

\[F = (X + Y + \overline{Z})(X + \overline{Y} + \overline{Z})(\overline{X} + Y + Z)(\overline{X} + \overline{Y} + Z)(\overline{X} + \overline{Y} + \overline{Z})\]

The conversion in the other direction is the same operation. Given \(F(A, B, C) = \pi(0, 2, 3, 4)\) — the function of section 1.5.4 — the missing numbers are 1, 5, 6 and 7, so \(F(A, B, C) = \Sigma(1, 5, 6, 7)\).

That result settles the loose end left at the end of section 1.5.4. The POS form found there and the SOP form \(AB + AC + \overline{B}C\) found in section 1.5.1 were claimed to be the same function. Expanding the SOP form into minterms confirms it. The term \(AB\) contributes \(ABC\) and \(AB\overline{C}\), that is \(m_7\) and \(m_6\); \(AC\) contributes \(ABC\) and \(A\overline{B}C\), that is \(m_7\) again and \(m_5\); and \(\overline{B}C\) contributes \(A\overline{B}C\) and \(\overline{A}\,\overline{B}C\), that is \(m_5\) again and \(m_1\). Collecting them without repetition gives \(\Sigma(1, 5, 6, 7)\), exactly as predicted.

converting by complementing the terms instead of listing the missing numbers What students write:

F  = Σ(0, 2, 5)
"F" = π(0, 2, 5)          with each minterm complemented in place

What happens: complementing every minterm of \(F\) and multiplying the results gives \(\overline{F}\), not \(F\) written another way. The two are different functions, and they disagree in every row. The fix: to convert between \(\Sigma\) and \(\pi\) for the same function, keep the numbers that are absent and discard the ones that are present. The designation numbers change; the function does not.

Q. If a function is 1 in every row, what are its two cardinal forms?

A. With three variables it is \(\Sigma(0, 1, 2, 3, 4, 5, 6, 7)\), using every minterm. There are no rows where it is 0, so the maxterm list is empty and there is no \(\pi\) form to write out. A product of no factors is taken to be 1, which is exactly right — the function is the constant 1.

1.6 Karnaugh Maps

Section 1.4.8 ended with an admission. Algebraic reduction always gives a correct answer, but it never tells you that you have finished. You apply theorems until nothing further suggests itself, and then you stop — not because the expression is minimal, but because you have run out of ideas.

In 1953 Maurice Karnaugh, working at Bell Telephone Laboratories, published a method that removes the guesswork for expressions of a manageable size. The idea is to arrange the truth table as a grid, in an order chosen so that terms which can be combined always end up next to each other. Simplification then stops being a search and becomes an act of looking: you draw rings around blocks of cells, and read the answer off.

1.6.1 Why Adjacency Simplifies an Expression

Everything in this section rests on one small piece of algebra. Take two minterms that are identical except for a single variable, which appears plain in one and complemented in the other:

\[ABC + AB\overline{C} = AB(C + \overline{C}) = AB \cdot 1 = AB\]

The two three-variable terms have collapsed into one two-variable term, and the variable that differed has vanished. Nothing here is new — it is distributivity followed by the complement theorem — but stated as a rule it is the engine of the whole method.

the combining rule for adjacent terms Statement: if two product terms are identical except that one variable appears plain in one and complemented in the other, their sum equals the common part alone. In symbols, \(XY + X\overline{Y} = X\), where \(X\) stands for everything the two terms share. In words: when two terms differ in exactly one variable, that variable can be struck out and the two terms replaced by one. Why it holds: \(XY + X\overline{Y} = X(Y + \overline{Y}) = X \cdot 1 = X\), by distributivity, the complement theorem and the operations with 1. Used for: every reduction performed by a Karnaugh map; a group of \(2^k\) cells is nothing but this rule applied \(k\) times over. Watch out: the terms must differ in exactly one variable. \(ABC\) and \(A\overline{B}\,\overline{C}\) differ in two, and nothing can be struck out of them.

The rule applies repeatedly. Four minterms in which two variables run through all four of their combinations, while the rest stay fixed, collapse to a term with two fewer variables:

\[ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\,\overline{C} = AB + A\overline{B} = A\]

Eight such minterms would collapse to a term with three fewer variables, and so on. In general a block of \(2^k\) minterms of the right shape reduces to a single term from which \(k\) variables have disappeared.

The problem the map solves

The rule is easy. Finding the terms it applies to is not. In \(\Sigma(0, 1, 2, 3, 5, 7, 8, 10)\) there are eight minterms and twenty-eight pairs to inspect, and a pair that combines may be worth combining with a third and a fourth. Doing this by scanning a list is exactly the guesswork that section 1.4.8 complained about.

A Karnaugh map removes the scanning. It is a grid with one cell for every minterm, laid out so that any two cells sharing an edge differ in exactly one variable. Terms that can be combined are then physically next to each other, and the eye finds them without being told where to look.

NoteDefinition

A Karnaugh map, or K-map, is a grid containing one cell for every possible combination of the variables of a function, arranged so that the combinations labelling any two adjacent cells differ in exactly one variable.

Q5. Simplifying a long expression by applying laws one after another can take a dozen steps, and you can never be sure you have reached the shortest form. Is there a way to see the shortest form instead of deriving it?

A. Yes, for functions of up to four variables, and that is what a Karnaugh map provides. Because the map is arranged so that combinable terms are neighbours, the simplification that algebra has to search for becomes a block of cells that is simply visible. You ring the largest blocks you can find, read one term from each, and add them. There is no sequence of theorems to choose between and no risk of stopping early, because the size of the block you have ringed tells you directly how short the term will be. Beyond four variables the grid can no longer show all the adjacencies on a flat page, and the advantage is lost — which is why section 1.6.8 states the ceiling plainly.

Gray code

For the layout to work, consecutive labels along a row or column must differ in exactly one bit. Ordinary binary counting will not do: 01 is followed by 10, and those differ in both bits.

The order used instead is 00, 01, 11, 10. Check the steps: 00 to 01 changes the second bit; 01 to 11 changes the first; 11 to 10 changes the second. And the last wraps round to the first — 10 to 00 changes only the first bit. An ordering with this property is called a Gray code, and every Karnaugh map in this book is labelled with one.

1.6.2 The Two-Variable Karnaugh Map

With two variables there are four minterms, so the map is a 2 by 2 grid. One variable labels the rows and the other the columns. Fig. 1.6-1 shows the arrangement, with each cell carrying both its minterm and its number.

Diagram

Fig. 1.6-1 – two-variable Karnaugh map drawn as a 2 by 2 grid; the rows are labelled down the left with A̅ then A, and the columns are labelled across the top with B̅ then B; the four cells contain, reading left to right and top to bottom, “A̅B̅ (0)”, “A̅B (1)”, “AB̅ (2)”, “AB (3)”; a small note beside the grid reads “cell number = decimal value of the row bit followed by the column bit”

Reading the cell numbers confirms that the map is the truth table rearranged. Cell 0 sits where \(A = 0\) and \(B = 0\), cell 3 where both are 1, and so on. Table 1.49 lists the correspondence.

Table 1.49 – the four cells of a two-variable map, with the row and column they occupy

Cell \(A\) \(B\) Minterm
0 0 0 \(\overline{A}\,\overline{B}\)
1 0 1 \(\overline{A}B\)
2 1 0 \(A\overline{B}\)
3 1 1 \(AB\)

To use the map, place a 1 in every cell whose minterm appears in the function and leave the rest blank, then look for blocks.

Take \(F(A, B) = \Sigma(0, 1)\). Cells 0 and 1 are the two cells of the top row. They share \(\overline{A}\) and differ in \(B\), so the pair reduces to \(\overline{A}\), and \(F = \overline{A}\).

Take \(F(A, B) = \Sigma(1, 3)\). Cells 1 and 3 form the right-hand column. They share \(B\) and differ in \(A\), so \(F = B\).

The reading rule, which will not change for the rest of the section, is this: a group reduces to the product of exactly those variables that hold the same value throughout the group; any variable that changes within the group drops out.

1.6.3 The Three-Variable Karnaugh Map

Three variables give eight minterms. The map is drawn as two rows and four columns: \(A\) labels the rows, and \(B\) and \(C\) together label the columns, in Gray code order.

Diagram

Fig. 1.6-2 – three-variable Karnaugh map drawn as a grid of 2 rows and 4 columns; the rows are labelled down the left with A̅ then A; the columns are labelled across the top with the pair BC taking the values 00, 01, 11, 10 in that Gray code order, and beneath each heading the product form B̅C̅, B̅C, BC, BC̅; the eight cells carry the numbers, reading left to right, 0, 1, 3, 2 in the upper row and 4, 5, 7, 6 in the lower row; curved arrows join the leftmost and rightmost cells of each row, labelled “these are neighbours too — the map wraps round”

Two features of Fig. 1.6-2 need attention.

The column numbers run 0, 1, 3, 2 and not 0, 1, 2, 3. That is the Gray code doing its work. Cells 1 and 3 sit side by side because their minterms \(\overline{A}\,\overline{B}C\) and \(\overline{A}BC\) differ in \(B\) alone; cells 1 and 2 do not sit side by side because \(\overline{A}\,\overline{B}C\) and \(\overline{A}B\overline{C}\) differ in two variables and cannot be combined.

The map also wraps horizontally. Cell 0 in the leftmost column and cell 2 in the rightmost column are neighbours, because \(\overline{A}\,\overline{B}\,\overline{C}\) and \(\overline{A}B\overline{C}\) differ only in \(B\). The grid is best thought of as a cylinder that has been slit open and flattened, with the two vertical edges really joined.

labelling the columns in ordinary binary order What students write:

columns:  00   01   10   11

What happens: cells that are drawn as neighbours are no longer one variable apart, so blocks that look correct on the page do not correspond to any valid combination, and the term read from them is wrong. The fix: the second and third labels must be 01 and 11. Say the four aloud as “zero-zero, zero-one, one-one, one-zero” and check that each step changes only one digit.

1.6.4 The Four-Variable Karnaugh Map

Four variables give sixteen minterms, and the map is a 4 by 4 grid. \(A\) and \(B\) label the rows in Gray code order and \(C\) and \(D\) label the columns, also in Gray code order.

Diagram

Fig. 1.6-3 – four-variable Karnaugh map drawn as a grid of 4 rows and 4 columns; the rows are labelled down the left with the pair AB taking the values 00, 01, 11, 10 in that Gray code order, with the product forms A̅B̅, A̅B, AB, AB̅ beside them; the columns are labelled across the top with the pair CD taking the values 00, 01, 11, 10 in that Gray code order, with the product forms C̅D̅, C̅D, CD, CD̅ beneath them; the sixteen cells carry the numbers, reading left to right: 0, 1, 3, 2 in the first row; 4, 5, 7, 6 in the second; 12, 13, 15, 14 in the third; 8, 9, 11, 10 in the fourth; curved arrows join the left and right edges of the grid and separately the top and bottom edges, both labelled “opposite edges are adjacent”

Note the row order. The third row is \(AB = 11\) and the fourth is \(AB = 10\), so the numbers run 12, 13, 15, 14 before 8, 9, 11, 10. Writing the rows as 00, 01, 10, 11 is the same mistake as before, in the other direction.

A four-variable map wraps in both directions. The top and bottom rows are neighbours, exactly as the left and right columns are. One consequence is worth noticing now, because it catches many students later: the four corner cells 0, 2, 8 and 10 are all mutually adjacent, and together they form a legitimate block.

This map is where the method stops. The syllabus takes Karnaugh maps up to four variables, and section 1.6.8 explains why that is a sensible place to stop rather than an arbitrary one.

1.6.5 Framing Groups: Pairs, Quads and Octets

Once the 1s have been entered, the work consists of drawing rings around blocks of them. A block drawn on a Karnaugh map is called a group, and not every collection of cells is allowed.

A group must satisfy three conditions.

  1. It must contain only cells holding 1.
  2. Its size must be a power of two — 1, 2, 4 or 8 cells.
  3. It must form a rectangular block on the map, counting the wrap-round adjacencies of sections 1.6.3 and 1.6.4 as real.

Groups have names by size. A group of two cells is a pair, a group of four is a quad, and a group of eight is an octet.

The reason for the power-of-two rule is the combining rule of section 1.6.1. Each doubling of a group’s size is one more application of \(XY + X\overline{Y} = X\), and each application removes exactly one variable. A group of three cells corresponds to no such sequence, and there is no term that describes it.

Table 1.50 – group size and the number of variables in the term it yields

Group Cells Variables removed Term on a three-variable map Term on a four-variable map
single cell 1 0 3 variables 4 variables
pair 2 1 2 variables 3 variables
quad 4 2 1 variable 2 variables
octet 8 3 the constant 1 1 variable

The message of Table 1.50 is short: bigger groups give shorter terms. A quad is always worth more than the two pairs it contains, and an octet more than two quads. This is why the standard advice is to look for the largest groups first.

Diagram

Fig. 1.6-4 – three four-variable Karnaugh maps drawn side by side, each with rows AB labelled 00, 01, 11, 10 and columns CD labelled 00, 01, 11, 10 in Gray code order; the left map is headed “pair” and holds 1s in cells 5 and 7 with a ring around them labelled “A̅BD”; the centre map is headed “quad” and holds 1s in cells 12, 13, 15, 14 with a ring around the whole third row labelled “AB”; the right map is headed “octet” and holds 1s in cells 4, 5, 7, 6, 12, 13, 15, 14 with a ring around the second and third rows together labelled “B”

Read the three panels of Fig. 1.6-4 against the reading rule. In the pair, cells 5 and 7 have \(A = 0\), \(B = 1\) and \(D = 1\) throughout, while \(C\) takes both values, so the term is \(\overline{A}BD\). In the quad, all four cells have \(A = 1\) and \(B = 1\), while \(C\) and \(D\) take every combination, so the term is \(AB\). In the octet, only \(B = 1\) survives, so the term is \(B\).

1.6.5.1 Groups Formed by Rolling the Map

Because opposite edges are adjacent, a group may run off one edge of the map and continue at the other. Such a group is said to be formed by rolling or folding the map, and it is as valid as any group drawn in the middle.

Diagram

Fig. 1.6-5 – two four-variable Karnaugh maps side by side, each with rows AB labelled 00, 01, 11, 10 and columns CD labelled 00, 01, 11, 10 in Gray code order; the left map is headed “a pair across the side edges” and holds 1s in cells 4 and 6, ringed together by two half-rings drawn at the left and right ends of the second row and joined by a dashed line outside the grid, labelled “A̅BD̅”; the right map is headed “a quad in the four corners” and holds 1s in cells 0, 2, 8 and 10, each ringed by a quarter-ring at its corner with dashed lines joining them around the outside of the grid, labelled “B̅D̅”

The four-corner quad in the right-hand panel is the one most often missed. Its cells are 0, 2, 8 and 10, whose binary patterns are 0000, 0010, 1000 and 1010. In all four, \(B = 0\) and \(D = 0\); \(A\) and \(C\) take every combination between them. The term is therefore \(\overline{B}\,\overline{D}\) — a two-variable term obtained from four cells that appear, on the flat page, to be as far apart as possible.

1.6.5.2 Groups Formed by Sharing Cells

A cell may belong to more than one group. Groups are allowed to overlap freely, and doing so is often what makes a larger group possible.

The justification is idempotence. Including a minterm in two groups means it appears twice in the final sum, and \(X + X = X\), so nothing is altered by counting it twice.

Diagram

Fig. 1.6-6 – a three-variable Karnaugh map with rows A̅ and A and columns BC labelled 00, 01, 11, 10 in Gray code order; 1s in cells 1, 3, 5 and 7 of the map, that is in the two middle columns of both rows, and additionally in cell 6; a ring drawn around cells 1, 3, 5, 7 labelled “quad, gives C”; a second ring drawn around cells 7 and 6 labelled “pair, gives AB”; cell 7 lies inside both rings, and an arrow points to it with the note “shared by both groups — permitted, since X + X = X”

1.6.5.3 Redundant Groups

Sharing is permitted, but it has a limit. A group every one of whose cells already lies inside other groups contributes nothing: removing it leaves every 1 still covered, and the term it supplied was surplus. Such a group is called a redundant group, and including it produces an expression that is correct but not minimal.

Diagram

Fig. 1.6-7 – a four-variable Karnaugh map with rows AB labelled 00, 01, 11, 10 and columns CD labelled 00, 01, 11, 10 in Gray code order; 1s in cells 0, 1, 3, 2, 4 and 6; a ring around the whole first row, cells 0, 1, 3, 2, labelled “quad, gives A̅B̅”; a ring around cells 0, 2, 4, 6 spanning the first two rows of the outer columns, drawn with the two halves joined around the side edges, labelled “quad, gives A̅D̅”; a third ring around cells 0 and 2 only, drawn dashed and shaded, labelled “redundant — both its cells are already covered”

The test for redundancy is mechanical. Take the group away; if every 1 on the map still lies inside at least one remaining group, the group was redundant and must be dropped.

Guidelines for grouping

Putting the rules together gives a working procedure.

  1. Look for the largest legal groups first — octets, then quads, then pairs — and remember the wrap-round adjacencies while you look.
  2. Every 1 on the map must end up inside at least one group.
  3. Groups may overlap, and overlapping is often what allows a larger group to be drawn.
  4. Use as few groups as will cover all the 1s.
  5. Check each group at the end and delete any that has become redundant.
  6. A 1 that no larger group can reach is ringed on its own, and contributes a full-length term.

1.6.6 Reducing a Sum of Products Expression

The procedure for an SOP reduction is now complete.

  1. Express the function in canonical form, or as a cardinal \(\Sigma\) list, or as a truth table — any of the three will do.
  2. Draw the map for the right number of variables, with the axes labelled in Gray code order.
  3. Place a 1 in the cell of every minterm present, and leave the others blank.
  4. Frame groups according to the guidelines of section 1.6.5.
  5. Read one product term from each group, keeping the variables that stay constant across it and dropping those that change.
  6. Combine the terms with OR.
A three-variable reduction

Reduce \(F(A, B, C) = \Sigma(1, 3, 5, 6, 7)\).

Diagram

Fig. 1.6-8 – a three-variable Karnaugh map with rows labelled A̅ and A and columns BC labelled 00, 01, 11, 10 in Gray code order, cells numbered 0, 1, 3, 2 in the upper row and 4, 5, 7, 6 in the lower; 1s placed in cells 1, 3, 5, 6 and 7; a ring drawn around the four cells 1, 3, 5, 7, that is the two middle columns of both rows, labelled “quad, gives C”; a second ring drawn around cells 7 and 6, the last two cells of the lower row, labelled “pair, gives AB”

The quad covers cells 1, 3, 5 and 7. Their patterns are 001, 011, 101 and 111; \(C = 1\) throughout, while \(A\) and \(B\) both vary. The term is \(C\).

The pair covers cells 7 and 6, with patterns 111 and 110. Here \(A = 1\) and \(B = 1\) throughout, and \(C\) varies. The term is \(AB\).

Every 1 is now covered — cell 6 by the pair, the rest by the quad — and neither group is redundant, since cell 6 lies only in the pair and cells 1, 3 and 5 only in the quad. Hence

\[F = C + AB\]

Two terms and three literals, from a function that began as five minterms and fifteen literals.

A four-variable reduction

Reduce \(F(A, B, C, D) = \Sigma(0, 1, 2, 3, 5, 7, 8, 10)\).

Diagram

Fig. 1.6-9 – a four-variable Karnaugh map with rows AB labelled 00, 01, 11, 10 and columns CD labelled 00, 01, 11, 10 in Gray code order, cells numbered 0, 1, 3, 2 in the first row, 4, 5, 7, 6 in the second, 12, 13, 15, 14 in the third and 8, 9, 11, 10 in the fourth; 1s placed in cells 0, 1, 3, 2, 5, 7, 8 and 10; a ring drawn around cells 1, 3, 5, 7, that is the two middle columns of the first two rows, labelled “quad, gives A̅D”; a ring drawn around the four corner cells 0, 2, 8 and 10, with dashed lines joining the corners around the outside of the grid, labelled “quad, gives B̅D̅”; a third ring drawn dashed and shaded around the whole first row, cells 0, 1, 3, 2, labelled “quad A̅B̅ — drawn first, then found to be redundant”

Three quads can be drawn on this map, and the interesting part of the example is that only two of them survive.

The first quad covers cells 1, 3, 5 and 7. Their patterns are 0001, 0011, 0101 and 0111: \(A = 0\) and \(D = 1\) throughout, while \(B\) and \(C\) vary. The term is \(\overline{A}D\).

The second is the four-corner quad of cells 0, 2, 8 and 10, which section 1.6.5.1 already showed reduces to \(\overline{B}\,\overline{D}\).

The third is the whole first row, cells 0, 1, 3 and 2, with \(A = 0\) and \(B = 0\) throughout, giving \(\overline{A}\,\overline{B}\). It is a perfectly legal quad, and it is tempting to include it because it is large and easy to see. But apply the test of section 1.6.5.3: cells 0 and 2 are already inside the corner quad, and cells 1 and 3 are already inside the first quad. Every one of its cells is covered elsewhere, so it is redundant and must be dropped.

\[F = \overline{A}D + \overline{B}\,\overline{D}\]

Check the answer against the original list. \(\overline{A}D\) is 1 exactly in cells 1, 3, 5 and 7; \(\overline{B}\,\overline{D}\) is 1 exactly in cells 0, 2, 8 and 10. Together they cover 0, 1, 2, 3, 5, 7, 8 and 10 and nothing else, which is precisely \(\Sigma(0, 1, 2, 3, 5, 7, 8, 10)\).

Q. The redundant quad was legal, and including it would have given \(F = \overline{A}D + \overline{B}\,\overline{D} + \overline{A}\,\overline{B}\). Would that answer have been wrong?

A. It would have been correct but not minimal. The three-term expression has the same truth table as the two-term one, so it describes the same function faithfully. What it is not is the shortest form, and shortness is the entire purpose of the exercise — in the hardware of the next chapter, the extra term is extra components doing nothing. An answer that is right but not reduced has not finished the job.

Reduce \(F(A, B, C) = \Sigma(0, 2, 4, 5, 6)\) using a three-variable map. You should find one quad and one pair. Then check your answer by building the truth table of the expression you obtain and confirming that it holds 1 in exactly the five rows listed and 0 in the other three.

1.6.7 Reducing a Product of Sums Expression

Everything so far has grouped the 1s. To obtain a POS expression, group the 0s instead — and reverse the reading convention.

The reason is straightforward. The cells holding 0 for \(F\) are exactly the cells holding 1 for \(\overline{F}\), so grouping them and reading them in the ordinary way gives an SOP expression for \(\overline{F}\). Complementing that by De Morgan’s theorem turns each product term into a sum term and the sum into a product — which is POS form. Doing the complementation in advance gives a rule you can apply directly:

  • place a 0 in the cell of every maxterm present, and group the 0s exactly as you would group 1s;
  • from each group, keep the variables that stay constant, writing a variable that is constant at 0 as plain and one that is constant at 1 as complemented;
  • join the variables of one group with OR to form a sum term, and join the sum terms with AND.

The bit convention is the maxterm convention of section 1.5.4, and it is reversed from the minterm one for exactly the same reason.

A worked POS reduction

Reduce \(F(A, B, C) = \pi(0, 1, 2, 4)\).

Diagram

Fig. 1.6-10 – a three-variable Karnaugh map with rows labelled A̅ and A and columns BC labelled 00, 01, 11, 10 in Gray code order, cells numbered 0, 1, 3, 2 in the upper row and 4, 5, 7, 6 in the lower; 0s placed in cells 0, 1, 2 and 4, and 1s placed in cells 3, 5, 6 and 7; a ring around cells 0 and 1, the first two cells of the upper row, labelled “pair, gives A + B”; a ring around cells 0 and 2, the first and last cells of the upper row, drawn as two half-rings joined by a dashed line around the side edges, labelled “pair, gives A + C”; a ring around cells 0 and 4, the first cells of the two rows, labelled “pair, gives B + C”

Three pairs of 0s can be drawn, and all three are needed.

Cells 0 and 1 have patterns 000 and 001: \(A = 0\) and \(B = 0\) throughout, and \(C\) varies. Both constants are 0, so both variables are written plain, and the sum term is \(A + B\).

Cells 0 and 2 have patterns 000 and 010: \(A = 0\) and \(C = 0\) throughout, giving \(A + C\).

Cells 0 and 4 have patterns 000 and 100: \(B = 0\) and \(C = 0\) throughout, giving \(B + C\).

None is redundant, because cell 1 lies only in the first group, cell 2 only in the second and cell 4 only in the third. Hence

\[F = (A + B)(A + C)(B + C)\]

This function is worth recognising. It is 1 in cells 3, 5, 6 and 7 — precisely the rows in which at least two of the three inputs are 1 — so it is the majority function, and its POS form says that of every pair of inputs, at least one must be on.

The same function through its 1s

Grouping the 1s of the same map instead gives the SOP form, and comparing the two is instructive. The 1s sit in cells 3, 5, 6 and 7, and three pairs can be drawn: cells 3 and 7 give \(BC\), cells 5 and 7 give \(AC\), cells 6 and 7 give \(AB\). So

\[F = AB + BC + AC\]

Both expressions are minimal, both describe the majority function, and neither is shorter than the other — three terms of two literals each, in both cases. That happens when the 1s and 0s are equally numerous. When they are not, the two forms differ markedly in length, and the map shows which to choose before you have done any work: whichever value appears in fewer cells will generally group into fewer terms.

Table 1.51 – grouping the 1s vs grouping the 0s

Feature Grouping the 1s Grouping the 0s
Cells entered on the map one 1 per minterm, from the \(\Sigma\) list one 0 per maxterm, from the \(\pi\) list
Variable constant at 1 is written plain complemented
Variable constant at 0 is written complemented plain
Variables within one group are joined by AND, forming a product term OR, forming a sum term
Groups are joined by OR AND
Result minimal SOP expression minimal POS expression
Preferable when the function has few 1s the function has few 0s

Note that the rules for forming groups do not change at all between the two columns. Sizes must still be powers of two, blocks must still be rectangular, edges still wrap, overlapping is still allowed and redundant groups must still be dropped. Only the entries grouped and the reading convention differ.

grouping the 0s but reading them like 1s What students write:

group of 0s with A = 0 and B = 0 throughout
term written as:  A̅ · B̅

What happens: a product term has been produced where a sum term was required, and it uses the minterm bit convention instead of the maxterm one. The answer is neither the SOP form nor the POS form of the function. The fix: when grouping 0s, both changes must be made together — plain for a constant 0, complemented for a constant 1, and OR between the variables. The correct term here is \(A + B\).

1.6.8 Limitations of the Karnaugh Map Method

The map is a considerable advance on algebraic reduction, but it is not a universal tool, and its boundaries are worth stating plainly.

It stops at four variables. A five-variable function needs 32 cells, and no flat 32-cell grid can place every pair of one-bit-apart combinations side by side; the map has to be split into two layers with adjacencies running between them, and the visual advantage that justified the method disappears. Beyond that, the number of cells doubles with each new variable and the approach becomes unusable by hand. This is the reason the syllabus sets the ceiling at four, and the reason larger problems are handled by other methods entirely.

It needs the function in canonical or tabular form first. An expression such as \(\overline{A}(B + \overline{C}) + AB\) cannot be plotted until it has been expanded into minterms — work that the map does not do for you, and that uses the algebra of sections 1.4 and 1.5.

It still depends on your eye. The rules say to take the largest groups and to avoid redundancy, but nothing on the page announces a four-corner quad or a group that wraps across two edges. Missing a large group gives an answer that is correct and too long; that is the commonest error in this topic, and it is not one the method prevents.

It gives one minimal form, not all of them. Some functions have two or more equally short expressions, depending on which of several valid groupings is chosen. The map will lead you to one of them; it does not tell you that another exists, and two students may hand in different answers that are both fully minimal.

Table 1.52 – algebraic reduction vs the Karnaugh map

Feature Algebraic reduction Karnaugh map
Input required any expression canonical form, a cardinal list, or a truth table
Number of variables handled any number up to four in practice
How the next step is found by recognising which theorem applies by looking for the largest block
Assurance of reaching the minimum none reliable within four variables, if the grouping rules are followed
Commonest failure stopping too early, with a correct but long answer missing a large or wrapped group, with the same result
What it also gives you a justification, theorem by theorem a picture of which inputs the function depends on

The two methods are not rivals. Algebra brings an expression into a form the map can accept and handles what the map cannot; the map finishes the job for small functions and removes the guesswork. A confident answer usually uses both.

Take the function \(F(A, B, C, D) = \Sigma(0, 4, 8, 12)\) and reduce it with a four-variable map. Then reduce the same function algebraically, starting from its four minterms and using only the theorems of Table 1.42. Compare how many steps each method took, and note where the algebraic route required you to spot something that the map simply showed you.

1.7 Summary

Propositions and connectives
  1. A proposition is a declarative sentence that is either true or false, but not both. Questions, requests and instructions assert nothing, so they have no truth value and are not propositions. A false statement is still a proposition.
  2. A propositional constant is the fixed statement itself; a propositional variable is the symbol that stands in its place and may hold either truth value. A proposition making a single assertion is simple; two or more joined by connectives form a compound proposition.
  3. There are five connectives: \(\sim\) (negation), \(\wedge\) (conjunction), \(\vee\) (disjunction), \(\Rightarrow\) (implication) and \(\Leftrightarrow\) (biconditional). Each is defined completely by its truth table, and nothing about the meaning of the sentences it joins is relevant.
  4. Conjunction is true only when both parts are true. Disjunction is true when at least one part is true, including the case where both are — the \(\vee\) of logic is inclusive.
  5. An implication \(p \Rightarrow q\) is false in exactly one case, when the antecedent \(p\) is true and the consequent \(q\) is false. It is true whenever the antecedent is false, and it claims nothing about cause.
  6. A biconditional is true when its two parts have the same truth value and false when they differ.
Truth tables, well-formed formulae and interpretations
  1. A truth table lists every combination of truth values of the variables. With \(n\) variables there are \(2^n\) rows, all of which must appear, written in standard binary counting order. Columns are added one at a time, each depending only on columns already written.
  2. A well-formed formula (wff) is built by these rules and no others: every propositional variable is a wff; if \(A\) is a wff so is \(\sim A\); if \(A\) and \(B\) are wffs so are \((A \wedge B)\), \((A \vee B)\), \((A \Rightarrow B)\) and \((A \Leftrightarrow B)\); nothing else is a wff.
  3. Brackets are reduced by precedence, from tightest to loosest: \(\sim\), \(\wedge\), \(\vee\), \(\Rightarrow\), \(\Leftrightarrow\).
  4. When a word problem is translated into a wff, but behaves as \(\wedge\), neither… nor gives \(\sim p \wedge \sim q\), and only if reverses the arrow: “\(A\) only if \(B\)” is \(A \Rightarrow B\).
  5. An interpretation assigns a truth value to every variable in a wff; it is one row of the truth table. A wff with \(n\) variables has \(2^n\) interpretations.
Valid, unsatisfiable and satisfiable formulae
  1. A wff is valid, or a tautology, if it is true under every interpretation; unsatisfiable, or a contradiction, if it is false under every interpretation; satisfiable if it is true under at least one interpretation.
  2. Satisfiable is weaker than valid, not an alternative to it: every tautology is also satisfiable. A formula that is satisfiable but not valid is a contingency, and most formulae are contingencies.
  3. Validity is a claim about every row, so it can never be established by checking a few rows. Checking a few rows can only ever disprove it.
Converse, inverse and contrapositive
  1. For the conditional \(p \Rightarrow q\): the converse is \(q \Rightarrow p\), the inverse is \(\sim p \Rightarrow \sim q\), and the contrapositive is \(\sim q \Rightarrow \sim p\).
  2. A conditional and its contrapositive always agree, so either may replace the other. The converse and the inverse also agree with each other, but neither agrees with the original conditional. The truth of a conditional says nothing about the truth of its converse.
Logical equivalence and the equivalence laws
  1. Two wffs are logically equivalent, written \(A \equiv B\), if they take the same truth value under every interpretation. Equivalence is a statement about two formulae, not a connective inside one; \(A \equiv B\) holds exactly when \(A \Leftrightarrow B\) is a tautology.
  2. The equivalence laws are: commutativity of \(\wedge\) and \(\vee\); associativity of \(\wedge\) and \(\vee\); distributivity, \(p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\) and \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\); De Morgan’s laws, \(\sim(p \wedge q) \equiv \sim p \vee \sim q\) and \(\sim(p \vee q) \equiv \sim p \wedge \sim q\); the law of implication, \(p \Rightarrow q \equiv \sim p \vee q\); the law of the biconditional, \((p \Leftrightarrow q) \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)\); identity, \(p \equiv p\); the law of negation, \(\sim(\sim p) \equiv p\); the law of excluded middle, \(p \vee \sim p \equiv \textbf{true}\); and the law of contradiction, \(p \wedge \sim p \equiv \textbf{false}\).
  3. The simplification rules absorb the constants: \(p \wedge \textbf{true} \equiv p\), \(p \vee \textbf{false} \equiv p\), \(p \vee \textbf{true} \equiv \textbf{true}\), \(p \wedge \textbf{false} \equiv \textbf{false}\), \(p \wedge p \equiv p\) and \(p \vee p \equiv p\).
  4. Every law is stated with single letters but applies to whole formulae, since any wff may stand where a letter stands. That is why so short a list handles formulae of any size.
  5. A workable order for simplifying is: remove \(\Leftrightarrow\), then remove \(\Rightarrow\), then push negations inwards with De Morgan’s laws, then rearrange so that terms which can cancel stand together, then strike out with excluded middle or contradiction and absorb the constants. Name the law used at each step, or the derivation cannot be checked.
Drawing conclusions
  1. The statements accepted at the start are the premises and the statement arrived at is the conclusion. An argument is sound exactly when the implication whose antecedent is the conjunction of the premises and whose consequent is the conclusion is a tautology.
  2. Modus ponens: from \(p\) and \(p \Rightarrow q\), conclude \(q\). It runs one way only — accepting \(p \Rightarrow q\) and \(q\) does not permit concluding \(p\).
  3. The chain rule: from \(p \Rightarrow q\) and \(q \Rightarrow r\), conclude \(p \Rightarrow r\). The middle statement drops out of the conclusion.
  4. Both a truth table and an algebraic derivation settle the same question, and neither can give a wrong verdict if carried out correctly. A table proves and shows the exact row that would break an unsound argument; algebra explains why the conclusion follows and does not grow with the number of variables.
Binary quantities and the Boolean operations
  1. A binary valued quantity takes exactly one of two values; a binary valued variable holds such a quantity. Writing 1 for true and 0 for false turns every truth table of propositional logic into a Boolean one, unchanged.
  2. From section 1.3 the notation is \(\overline{A}\) for NOT, \(A + B\) for OR and \(AB\) for AND. Boolean algebra has these three operations and no others.
  3. Logical addition gives \(1 + 1 = 1\); there is no carry. Logical product agrees with ordinary multiplication on 0 and 1.
  4. Precedence is NOT, then AND, then OR. A bar drawn over a group of symbols acts as a bracket: everything beneath it is evaluated before it is complemented, so \(\overline{A + BC}\) and \(\overline{A} + BC\) are different expressions.
  5. A Boolean expression is formed from binary variables and the constants 0 and 1 using only AND, OR and NOT. Unlike an arithmetic expression it can be checked completely, because its truth table is finite.
  6. A postulate is assumed without proof; a theorem is proved from the postulates. The postulates state that variables take values from \(\{0, 1\}\), that the three operations are defined by their tables, and that the operations never produce a value outside \(\{0, 1\}\).
  7. Four compound expressions have names: NOR is \(\overline{A + B}\), NAND is \(\overline{A \cdot B}\), XOR is \(\overline{A}B + A\overline{B}\) and is 1 when the inputs differ, and XNOR is \(AB + \overline{A}\,\overline{B}\) and is 1 when they agree. XNOR is the biconditional written in Boolean notation.
The basic theorems
  1. Proofs use either perfect induction — checking every one of the finitely many cases, which is a genuine proof — or algebraic derivation from the postulates and earlier theorems.
  2. The dual of a statement is obtained by interchanging \(+\) with \(\cdot\) and 0 with 1, leaving variables and their bars unchanged. By the principle of duality, the dual of a true statement is true, so every theorem arrives with a companion. Duality is not complementation, and the dual of an expression generally has a different truth table.
  3. Idempotence: \(A + A = A\) and \(A \cdot A = A\). Involution: \(\overline{\overline{A}} = A\), which is its own dual.
  4. Operations with 0 and 1: \(A + 0 = A\) and \(A \cdot 1 = A\) leave the variable untouched; \(A + 1 = 1\) and \(A \cdot 0 = 0\) destroy it, and these two are what make long expressions collapse.
  5. Complements: \(A + \overline{A} = 1\) and \(A \cdot \overline{A} = 0\). These are the only theorems that remove a variable outright, which is why the decisive step of almost every reduction is one of them. Read backwards, \(A + \overline{A} = 1\) also allows a missing variable to be introduced.
  6. Commutativity, associativity and distributivity hold as in section 1.2, now written \(A + B = B + A\), \(AB = BA\), \((A + B) + C = A + (B + C)\), \((AB)C = A(BC)\), \(A(B + C) = AB + AC\) and \(A + BC = (A + B)(A + C)\). The second distributive law has no arithmetic counterpart, and duality is the reason it exists.
  7. Absorption: \(A + AB = A\) and \(A(A + B) = A\). The smaller term must lie wholly inside the larger; \(A + \overline{A}B\) is not absorbed but reduces instead to \(A + B\).
  8. De Morgan’s theorem: \(\overline{A + B} = \overline{A} \cdot \overline{B}\) and \(\overline{A \cdot B} = \overline{A} + \overline{B}\). It extends to any number of variables, and the operation beneath a bar must change each time the bar is broken.
  9. To complement an expression, bar the whole of it, break the longest bar first while changing the operation beneath it, repeat on each shorter bar, and tidy double bars with involution. If the outermost operation has not changed, the theorem has not been applied.
  10. Algebraic reduction always gives a correct answer but never announces that the answer is the shortest one. That limitation is what the Karnaugh map exists to remove.
Sum of products and product of sums
  1. A product term is variables combined by AND; a sum term is variables combined by OR. An expression is in SOP form if it is product terms joined by OR, and in POS form if it is sum terms joined by AND; in both, no bar may extend over more than one variable.
  2. To reach SOP form, break every long bar with De Morgan’s theorem first, then multiply out with the first distributive law. To reach POS form, factorise with the second distributive law.
  3. A minterm of \(n\) variables is a product term in which every variable appears exactly once; a maxterm is a sum term with the same property. There are \(2^n\) of each. A sum of minterms is a canonical SOP expression; a product of maxterms is a canonical POS expression.
  4. Minterm designation uses 1 for a plain variable and 0 for a complemented one, giving \(m_i\). Maxterm designation reverses this, using 0 for a plain variable and 1 for a complemented one, giving \(M_i\). The conventions are opposite so that \(M_i = \overline{m_i}\) in every row. Both depend on the variable order, which must be stated and kept.
  5. Cardinal representation names the variables in order and then lists the designations: \(\Sigma\) for a sum of minterms, \(\pi\) for a product of maxterms.
  6. A minterm is 1 in exactly one row of the truth table and a maxterm is 0 in exactly one row. So the canonical SOP form is read from the rows where the function is 1, one minterm each, and the canonical POS form from the rows where it is 0, one maxterm each.
  7. Every row yields exactly one term, so the number of minterms and the number of maxterms add to \(2^n\), and the two designation lists together use every number from 0 to \(2^n - 1\) once. Converting between the forms therefore means listing the numbers that are missing, not complementing the terms.
Karnaugh maps
  1. The combining rule is \(XY + X\overline{Y} = X\): two terms differing in exactly one variable collapse into one, and that variable disappears. A block of \(2^k\) such terms removes \(k\) variables.
  2. A Karnaugh map is a grid with one cell per combination of the variables, arranged so that adjacent cells differ in exactly one variable. This is achieved by labelling the axes in Gray code order, 00, 01, 11, 10, in which each step and also the wrap from last to first changes one bit only.
  3. Two variables give a 2 by 2 map, three give 2 by 4 with \(A\) on the rows and \(BC\) on the columns, and four give 4 by 4 with \(AB\) on the rows and \(CD\) on the columns. Opposite edges are adjacent in every case, so on a four-variable map the four corner cells form a single block.
  4. A group must contain only cells of the value being grouped, must be a power of two in size, and must be a rectangular block once wrap-round adjacency is counted. Groups of two, four and eight are called a pair, a quad and an octet. A group of three cells is not permitted, because no sequence of the combining rule produces it.
  5. A group of \(2^k\) cells yields a term with \(k\) fewer variables, so larger groups give shorter terms. A term is read by keeping the variables that stay constant across the group and dropping those that change.
  6. Groups may run off one edge and continue at the other, and they may overlap, since \(X + X = X\). A group all of whose cells lie inside other groups is redundant and must be dropped; keeping it gives an answer that is correct but not minimal.
  7. For a minimal SOP expression, plot the 1s, group them, write a plain variable where the group holds 1 and a complemented one where it holds 0, and join the terms with OR. For a minimal POS expression, plot the 0s, group them by the same rules, write a plain variable where the group holds 0 and a complemented one where it holds 1, join the variables of a group with OR and the groups with AND.
  8. The grouping rules themselves are identical in both cases. Only the entries grouped and the reading convention change.
  9. The map is limited to four variables in practice, needs the function in canonical or tabular form before it can be plotted, still depends on the eye to spot the largest and the wrapped groups, and produces one minimal form where several may exist. Algebra and the map are complementary: algebra prepares an expression and handles what the map cannot, and the map finishes the job for small functions without guesswork.

1.8 Key Terms

  1. absorption — the theorem \(A + AB = A\), and its dual \(A(A + B) = A\); a term already contained in another adds nothing.
  2. antecedent — the part of an implication that comes before the arrow, the “if” part.
  3. associative laws — the laws stating that when the same connective is used twice, the bracketing makes no difference.
  4. biconditional — the connective \(\Leftrightarrow\), read “if and only if”; true when its two parts have the same truth value.
  5. binary valued quantity — a quantity that can take exactly one of two values and no other.
  6. binary valued variable — a variable that holds a binary valued quantity, so that it can hold only 0 or 1.
  7. Boolean expression — an expression formed from binary valued variables and the constants 0 and 1 using only AND, OR and NOT.
  8. canonical — in the standard form; the form in which a given function has exactly one representation.
  9. canonical product of sums — an expression written as a product of maxterms; also called a maxterm expression.
  10. canonical sum of products — an expression written as a sum of minterms; also called a minterm expression.
  11. cardinal representation — a function described by naming its variables in order and then listing the designation numbers of its terms, using \(\Sigma\) for minterms and \(\pi\) for maxterms.
  12. chain rule — the rule that from \(p \Rightarrow q\) and \(q \Rightarrow r\) one may conclude \(p \Rightarrow r\).
  13. commutative laws — the laws stating that the order of the two parts of a conjunction or a disjunction makes no difference.
  14. complement — the NOT operation, written \(\overline{A}\); it reverses the value of a quantity.
  15. compound proposition — a proposition formed by joining two or more simple propositions with connectives.
  16. conclusion — the statement arrived at from the premises of an argument.
  17. conjunction — the connective \(\wedge\), read “and”; true only when both its parts are true.
  18. connective — a word or symbol that joins propositions to form a compound proposition.
  19. consequent — the part of an implication that comes after the arrow, the “then” part.
  20. contingency — a wff that is true under at least one interpretation and false under at least one other.
  21. contradiction — a wff that is false under every interpretation; the same as an unsatisfiable formula.
  22. contrapositive — the conditional \(\sim q \Rightarrow \sim p\) formed from \(p \Rightarrow q\); always equivalent to the original.
  23. converse — the conditional \(q \Rightarrow p\) formed from \(p \Rightarrow q\); not equivalent to the original.
  24. De Morgan’s laws — in propositional logic, \(\sim(p \wedge q) \equiv \sim p \vee \sim q\) and \(\sim(p \vee q) \equiv \sim p \wedge \sim q\).
  25. De Morgan’s theorem — the same result in Boolean notation: \(\overline{A + B} = \overline{A} \cdot \overline{B}\) and \(\overline{A \cdot B} = \overline{A} + \overline{B}\).
  26. disjunction — the connective \(\vee\), read “or”; true when at least one of its parts is true.
  27. distributive laws — the laws by which one connective spreads over the other, in both directions.
  28. dual — the statement obtained by interchanging \(+\) with \(\cdot\) and 0 with 1, leaving variables and their bars unchanged.
  29. duality — the principle that the dual of a true Boolean statement is also true.
  30. Gray code — an ordering of binary patterns, such as 00, 01, 11, 10, in which each step, including the wrap from last to first, changes exactly one bit.
  31. group — a block of cells ringed on a Karnaugh map; its size must be a power of two and its shape rectangular, counting wrap-round adjacency.
  32. idempotence — the theorem \(A + A = A\) and \(A \cdot A = A\); combining a quantity with itself changes nothing.
  33. identity — the law \(p \equiv p\); a formula is equivalent to itself.
  34. implication — the connective \(\Rightarrow\), read “if… then”; false only when the antecedent is true and the consequent false.
  35. inclusive — describing the logical or, which is true when both of its parts hold as well as when only one does.
  36. interpretation — an assignment of a truth value to every variable in a wff; one row of its truth table.
  37. involution — the theorem \(\overline{\overline{A}} = A\); complementing twice restores the original.
  38. Karnaugh map — a grid holding one cell per combination of the variables, arranged so that adjacent cells differ in exactly one variable.
  39. K-map — Karnaugh map.
  40. law of contradiction — the law \(p \wedge \sim p \equiv \textbf{false}\).
  41. law of excluded middle — the law \(p \vee \sim p \equiv \textbf{true}\).
  42. law of implication — the law \(p \Rightarrow q \equiv \sim p \vee q\).
  43. law of negation — the law \(\sim(\sim p) \equiv p\).
  44. law of the biconditional — the law \((p \Leftrightarrow q) \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)\).
  45. logic — the study of the rules of reasoning, treated exactly rather than as a habit of speech.
  46. logical addition — the OR operation, written with a plus sign; note that \(1 + 1 = 1\).
  47. logical product — the AND operation, written as a product.
  48. logically equivalent — describing two wffs that take the same truth value under every interpretation, written \(A \equiv B\).
  49. maxterm — a sum term of \(n\) variables in which every variable appears exactly once, complemented or not.
  50. maxterm designation — the label \(M_i\) obtained by writing 0 for a plain variable and 1 for a complemented one and reading the pattern as a decimal number.
  51. minterm — a product term of \(n\) variables in which every variable appears exactly once, complemented or not.
  52. minterm designation — the label \(m_i\) obtained by writing 1 for a plain variable and 0 for a complemented one and reading the pattern as a decimal number.
  53. modus ponens — the rule that from \(p\) and \(p \Rightarrow q\) one may conclude \(q\).
  54. NAND — the expression \(\overline{A \cdot B}\), the complement of AND.
  55. negation — the connective \(\sim\), read “not”; it reverses the truth value of a proposition.
  56. NOR — the expression \(\overline{A + B}\), the complement of OR.
  57. octet — a group of eight cells on a Karnaugh map.
  58. operations with 0 and 1 — the theorems \(A + 0 = A\), \(A \cdot 1 = A\), \(A + 1 = 1\) and \(A \cdot 0 = 0\).
  59. pair — a group of two cells on a Karnaugh map.
  60. perfect induction — proof by checking every one of the finitely many cases, which for a Boolean statement is a complete proof.
  61. POS — product of sums.
  62. postulate — a statement assumed to be true without proof, used as a starting point for further reasoning.
  63. premise — a statement accepted at the start of an argument, from which the conclusion is drawn.
  64. product of sums (POS) — an expression consisting of sum terms combined by AND, with no bar spanning more than one variable.
  65. product term — one or more variables, each possibly complemented, combined by AND.
  66. proposition — a declarative sentence that is either true or false, but not both.
  67. propositional constant — the fixed statement that a propositional variable stands for.
  68. propositional logic — the logic of whole sentences, concerned only with their truth values and how they combine.
  69. propositional variable — a symbol standing in place of a statement, able to hold either truth value.
  70. quad — a group of four cells on a Karnaugh map.
  71. redundant group — a group every one of whose cells already lies inside other groups, and which must therefore be dropped.
  72. satisfiable — describing a wff that is true under at least one interpretation.
  73. simple proposition — a proposition making a single assertion, containing no connective.
  74. SOP — sum of products.
  75. standard binary counting order — the order in which the rows of a truth table are written, reading the input combinations as binary numbers from 0 upwards.
  76. sum of products (SOP) — an expression consisting of product terms combined by OR, with no bar spanning more than one variable.
  77. sum term — one or more variables, each possibly complemented, combined by OR.
  78. tautology — a wff that is true under every interpretation; the same as a valid formula.
  79. theorem — a statement proved to be true using the postulates and previously proved theorems.
  80. truth table — a table listing every combination of truth values of the variables together with the value the formula takes in each case.
  81. truth value — the value true or false taken by a proposition, written 1 or 0.
  82. unsatisfiable — describing a wff that is false under every interpretation.
  83. valid — describing a wff that is true under every interpretation.
  84. well-formed formula (wff) — an expression built from propositional variables and connectives by the rules of section 1.1.4, and by no others.
  85. wff — well-formed formula.
  86. XNOR — the expression \(AB + \overline{A}\,\overline{B}\), which is 1 when its two inputs are the same.
  87. XOR — the expression \(\overline{A}B + A\overline{B}\), which is 1 when its two inputs differ.

1.9 Points to Ponder

  1. The principle of duality says that every true Boolean statement has a true companion, obtained by swapping the operations and the constants. Half of Table 1.42 was therefore never proved at all — it was simply read off the other half. Does that mean the dual column carries no information? If it does carry information, where did that information come from, given that no work was done to obtain it?

  2. An implication is true whenever its antecedent is false, which is the rule almost every student objects to on first meeting. Suppose the table were changed so that \(0 \Rightarrow 0\) and \(0 \Rightarrow 1\) both came out false instead. Which of the results in this chapter would survive that change, and which would collapse?

  3. Canonical sum of products is close to the longest way of writing a function, and the Karnaugh map produces the shortest. Yet the map cannot be drawn until the function has been put into that longest form first. Why should the shortest route to the shortest expression pass deliberately through the longest one?

  4. Algebraic reduction handles any number of variables but never tells you that you have finished. The Karnaugh map tells you that you have finished but stops at four variables. Is there a reason to expect that no single method could offer both guarantees at once, or is this simply a limitation of the two methods we happen to have?

  5. The biconditional of propositional logic and the XNOR of Boolean algebra turned out to be one operation wearing two names, and the same is true of the law of contradiction and the theorem \(A \cdot \overline{A} = 0\). Since the two vocabularies describe identical rules, would the subject be clearer if one of them were abandoned? What would be lost along with it?

  6. Boole published his algebra of true and false in 1847, and nothing was built that used it for another ninety years. He was not designing for machines, because there were none to design for. What does an episode like this suggest about how a piece of mathematics comes to be useful, and how would you decide, today, which apparently useless ideas are worth keeping?

1.10 Objective Questions

  1. Which of the following sentences is a proposition?
  1. Please switch off the fan.
  2. How many rows has a four-variable truth table?
  3. Every multiple of 6 is a multiple of 4.
  4. Draw the Karnaugh map for this function. [1 mark]
  1. The implication \(p \Rightarrow q\) takes the value 0 only when:
  1. \(p = 0\) and \(q = 0\)
  2. \(p = 0\) and \(q = 1\)
  3. \(p = 1\) and \(q = 0\)
  4. \(p = 1\) and \(q = 1\) [1 mark]
  1. The contrapositive of “If the tank is full, then the pump stops” is:
  1. If the pump stops, then the tank is full.
  2. If the pump does not stop, then the tank is not full.
  3. If the tank is not full, then the pump does not stop.
  4. If the tank is full, then the pump does not stop. [1 mark]
  1. The dual of the statement \(A + AB = A\) is:
  1. \(\overline{A} + \overline{A}\,\overline{B} = \overline{A}\)
  2. \(A(A + B) = A\)
  3. \(A \cdot A \cdot B = A\)
  4. \(A + B = A\) [1 mark]
  1. A function of four variables has six minterms. The number of maxterms it has is:
  1. 4
  2. 6
  3. 10
  4. 16 [1 mark]
  1. A quad framed on a four-variable Karnaugh map yields a term containing:
  1. 1 variable
  2. 2 variables
  3. 3 variables
  4. 4 variables [1 mark]

  1. Fill in the blank: in a three-variable Karnaugh map the four column labels are written in Gray code order as 00, 01, ________ and 10. [1 mark]

  2. State whether the following is true or false: every valid formula is also a satisfiable formula. [1 mark]

  3. State whether the following is true or false: on a Karnaugh map, a cell that already lies inside one group may not be included in a second group. [1 mark]

  4. Match each statement in Column A with the name of the theorem in Column B.

Column A Column B
a. \(A + AB = A\) i. idempotence
b. \(\overline{\overline{A}} = A\) ii. complements
c. \(A + \overline{A} = 1\) iii. absorption
d. \(A + A = A\) iv. involution

[1 mark]

  1. Write the full form of each of the following: (i) SOP (ii) POS (iii) wff (iv) K-map. [1 mark]

  2. Assertion (A): The complement of \(A + B\) is \(\overline{A} \cdot \overline{B}\). Reason (R): De Morgan’s theorem states that the complement of a sum is the product of the complements. Choose the correct option:

  1. Both A and R are true and R is the correct explanation of A.
  2. Both A and R are true but R is not the correct explanation of A.
  3. A is true but R is false.
  4. A is false but R is true. [1 mark]
  1. Assertion (A): Three adjacent cells holding 1 on a Karnaugh map may be ringed as a single group. Reason (R): The number of cells in a group must be a power of two. Choose the correct option:
  1. Both A and R are true and R is the correct explanation of A.
  2. Both A and R are true but R is not the correct explanation of A.
  3. A is true but R is false.
  4. A is false but R is true. [1 mark]
  1. Assertion (A): If a conditional is true, its converse is also true. Reason (R): A conditional and its contrapositive always have the same truth value. Choose the correct option:
  1. Both A and R are true and R is the correct explanation of A.
  2. Both A and R are true but R is not the correct explanation of A.
  3. A is true but R is false.
  4. A is false but R is true. [1 mark]

1.11 Check Your Concepts

  1. Define a proposition. Give one example of a sentence that is not a proposition, and state why it is not. [2 marks]

  2. State the law of excluded middle and the law of contradiction, in symbols. [2 marks]

  3. Define a minterm. Write any one minterm of the three variables \(A\), \(B\) and \(C\), and give its designation. [2 marks]

  4. What is meant by an interpretation of a well-formed formula? How many interpretations has a formula of four variables? [2 marks]

  5. Differentiate between a tautology and a contingency, giving one example of each. [3 marks]

  6. Verify the law of implication, \(p \Rightarrow q \equiv \sim p \vee q\), using a truth table. [3 marks]

  7. Write the converse, the inverse and the contrapositive of the statement “If the pump is switched on, then the tank fills.” [3 marks]

  8. Convert \(F = A + \overline{B}\) into its canonical sum of products form for the two variables \(A\) and \(B\), showing your working. [3 marks]

  9. State De Morgan’s theorem in both its forms, and use it to find the complement of \(\overline{X}Y + Z\). [3 marks]

  10. Simplify \(F = \overline{A}B\overline{C} + \overline{A}BC + AB\overline{C} + ABC\) using the theorems of Boolean algebra, naming the theorem used at each step. [4 marks]

  11. Reduce \(F(A, B, C) = \Sigma(0, 1, 2, 3, 6)\) using a Karnaugh map. Draw the map, mark the groups you have framed, and write the term obtained from each. [4 marks]

  12. Explain, with one worked example of each, the difference between the dual of an expression and the complement of an expression. [4 marks]

  13. A bus depot issues a concession ticket when the passenger produces a valid student card and the journey is within the city, or when the passenger holds a monthly pass, whatever the journey. Take \(S = 1\) if the student card is valid, \(C = 1\) if the journey is within the city and \(M = 1\) if the passenger holds a monthly pass; the output \(F = 1\) means a concession ticket is issued. Draw the truth table, write the canonical SOP expression together with its cardinal \(\Sigma\) representation, and then reduce the expression using a Karnaugh map. [6 marks]

  14. Reduce \(F(A, B, C, D) = \Sigma(0, 1, 4, 5, 10, 11, 14, 15)\) using a Karnaugh map, showing the map, the groups framed and the term read from each. Then expand your reduced expression back into minterms and confirm that it covers exactly the eight given cells and no others. [6 marks]

1.12 Output & Debugging

  1. Copy and complete the truth table below, filling in every entry marked with a dash.
\(p\) \(q\) \(\sim p\) \(p \Rightarrow q\) \(\sim p \vee q\)
0 0 1 – –
0 1 – 1 –
1 0 – – 0
1 1 0 – –

State what the completed table shows about the two expressions in the last two columns. [3 marks]

  1. Evaluate \(F = \overline{A}(B + \overline{C}) + AB\) for each of the following, showing the value of every bracket as you go: (i) \(A = 1\), \(B = 0\), \(C = 1\); (ii) \(A = 0\), \(B = 1\), \(C = 1\); (iii) \(A = 0\), \(B = 0\), \(C = 0\). [3 marks]

  2. The simplification below contains exactly one faulty step.

Step 1:  ~(p ∧ q) ∨ (p ∧ ~q)
Step 2:  (~p ∧ ~q) ∨ (p ∧ ~q)      [De Morgan's law]
Step 3:  ~q ∧ (~p ∨ p)             [distributivity]
Step 4:  ~q ∧ true                 [law of excluded middle]
Step 5:  ~q                        [simplification with true]

Identify the faulty step, state which law has been applied wrongly, write the corrected line, and complete the simplification from that point. [3 marks]

  1. A student plots \(F(A, B, C, D) = \Sigma(0, 1, 2, 3, 4, 5)\) on a four-variable Karnaugh map and frames three groups: the quad of cells 0, 1, 2 and 3; the quad of cells 0, 1, 4 and 5; and the pair of cells 1 and 5. Write the term yielded by each of the three groups, state which group is redundant and why, and give the minimal SOP expression. [4 marks]

  2. A student claims that \(\overline{A}B + A\overline{B} + AB\) simplifies to \(AB\). Build the truth table of the given expression and of \(AB\), state whether the claim is correct, and if it is not, write the minimal expression the student should have reached. [3 marks]