Discrete Mathematics and Proof

Exclusive or and logic circuits

How can one extra bit reveal that a message was changed on the way, and how can parts that only compute and, or and not end up adding numbers?

You need

Building a truth table for a compound statementDiscrete Mathematics and Proof

Where you are 9 in Logic

Logic, proof and discrete math6

Logic9

▴ 3 above Quantifiers4 Biconditional

Exclusive or and logic circuits

Logical equivalence3 Truth tables3 ▾ Show all 9 (1 more)

Why this exists

And and or gave exclusive or, P \oplus Q, “P or Q but not both”, its table, and the biconditional showed it is \neg(P \leftrightarrow Q): true exactly when the parts differ. It earns a lesson of its own for two reasons.

First, it has an algebra that and and or lack. A statement exclusive-or’ed with itself vanishes, and exclusive or with T is negation. So a long chain of exclusive ors is easy to evaluate: it is true exactly when an odd number of its parts are true. One extra bit sent with a message, a parity bit, uses this to let the receiver notice that a bit was changed on the way.

Second, a connective can be built. A logic gate is a small electronic part whose output is one connective of its inputs. Wired together, gates compute any compound statement, and an XOR gate with an AND gate adds two one-bit numbers.

Definition

Exclusive or. P \oplus Q is true when exactly one of P and Q is true: when P and Q have different truth values. In the usual row order TT, TF, FT, FF its column is F, T, T, F.

Bits and parity. In computing a truth value is a bit: 1 for T and 0 for F. A message is a string of bits b_1 b_2 \ldots b_n. Its even parity bit is

p = b_1 \oplus b_2 \oplus \cdots \oplus b_n,

and the sender transmits the word b_1 b_2 \ldots b_n p. (No brackets are needed in the chain, by the associative law below.)

Gates and circuits. A logic gate has one or two input wires and one output wire, each carrying T or F (in a chip, a high or a low voltage). An AND gate outputs P \land Q, an OR gate P \lor Q, a NOT gate \neg P and an XOR gate P \oplus Q. Figure 1 shows the standard shapes.

Figure 1The four gates. Each one outputs the value of one connective of its inputs.

A circuit is a set of gates joined by wires, the output of one gate feeding an input of another, with no loops: no gate’s output returns, directly or through other gates, to its own input. A wire may branch, marked by a dot; wires that cross without a dot are not connected. The input values fix the value on every wire, so each output carries a compound statement in the inputs. Two circuits are equivalent when their outputs are logically equivalent.

Intuition

Read P \oplus Q as “P, flipped if Q is true”: when Q is F the output is P, and when Q is T it is \neg P. A chain P_1 \oplus P_2 \oplus \cdots \oplus P_n then starts at F and flips once for every true part. An even number of flips lands back on F, an odd number on T.

In bits, \oplus is addition that throws the carry away: 0 \oplus 1 = 1 but 1 \oplus 1 = 0. The carry that 1 + 1 really produces is 1 \land 1, which is why an XOR gate and an AND gate together add two bits.

A circuit is a truth table made physical: each gate computes one column, as in Building a truth table for a compound statement.

Results

Laws of exclusive or. For all statements P, Q, R:

P \oplus Q \equiv Q \oplus P

(P \oplus Q) \oplus R \equiv P \oplus (Q \oplus R)

P \oplus \text{F} \equiv P \qquad P \oplus \text{T} \equiv \neg P \qquad P \oplus P \equiv \text{F}

And distributes over exclusive or:

P \land (Q \oplus R) \equiv (P \land Q) \oplus (P \land R)

Or does not (Example 3).

Parity theorem. P_1 \oplus P_2 \oplus \cdots \oplus P_n is true exactly when an odd number of P_1, \ldots, P_n are true. So a word with an even parity bit has an even number of 1s, and changing any one bit of it makes that number odd.

Every table has a circuit. For each row where a table has T, form the “and” of every input letter, negated where that row has F. The “or” of these terms (or P \land \neg P if the table has no T) has exactly the given column. Only AND, OR and NOT gates are needed; for example

P \oplus Q \equiv (P \land \neg Q) \lor (\neg P \land Q).

Half adder. Two bits A and B add to the two-bit number CS, with sum bit S = A \oplus B and carry bit C = A \land B.

Why it is true

Proof of the laws. “P and Q differ” says the same as “Q and P differ”, so \oplus is commutative. P differs from F exactly when P is T, so P \oplus \text{F} has the value of P; it differs from T exactly when P is F, so P \oplus \text{T} has the value of \neg P. P never differs from itself, so P \oplus P is always F.

For the associative law, split on R. If R is F, the left side is (P \oplus Q) \oplus \text{F}, which is P \oplus Q, and on the right Q \oplus \text{F} is Q, giving P \oplus Q again. If R is T, the left side is \neg(P \oplus Q), and on the right Q \oplus \text{T} is \neg Q, giving P \oplus \neg Q. Now P and \neg Q differ exactly when P and Q agree, so P \oplus \neg Q \equiv \neg(P \oplus Q). The sides agree in both cases. \square

Proof of the parity theorem for three parts. Let k be the number of true parts among P, Q, R. If R is F, then P \oplus Q \oplus R \equiv P \oplus Q, true exactly when k = 1; since k is 0, 1 or 2 here, that is exactly when k is odd. If R is T, then P \oplus Q \oplus R \equiv \neg(P \oplus Q), true exactly when P and Q agree: both F, so k = 1, or both T, so k = 3. Here k is 1, 2 or 3, and again the chain is true exactly when k is odd. \square

The same split handles any length one part at a time. If a chain of n parts is true exactly when an odd number are true, add a part S. If S is F, neither the value nor the count changes. If S is T, the value flips and the count goes up by one, so its oddness flips too. Since one part obeys the rule, every length does. This “one more part” argument is an induction, made formal in Proof by induction.

For the word, the chain of all its bits is (b_1 \oplus \cdots \oplus b_n) \oplus p, which is p \oplus p \equiv \text{F}, so by the parity theorem the word has an even number of 1s. Changing a bit b replaces it by b \oplus \text{T}, which negates the whole chain. \square

Proof that every table has a circuit. A term such as P \land \neg Q \land R is true only on the row where every input matches it, here P T, Q F, R T. The “or” of the terms is true exactly when one of its terms is, which is exactly on the rows where the table has T. \square

Proof of the half adder. Check the four cases.

A	B	A + B	C = A \land B	S = A \oplus B
1	1	2	1	0
1	0	1	0	1
0	1	1	0	1
0	0	0	0	0

In each row 2C + S = A + B. \square

Worked examples

The lesson is taught in two parts. Examples 1 to 3 belong to the first, exclusive or and parity; Examples 4 to 7 to the second, gates and circuits.

Example 1

Simplifying with the laws

Simplify (P \oplus \text{T}) \oplus (P \oplus Q) to a single letter or its negation.

Solution

The associative and commutative laws let a chain of exclusive ors be regrouped and reordered freely, as a sum can. Put the two copies of P together:

\begin{aligned} &(P \oplus \text{T}) \oplus (P \oplus Q) \\ &\equiv (P \oplus P) \oplus (Q \oplus \text{T}) \end{aligned}

P \oplus P \equiv \text{F}, and F changes nothing, so this is Q \oplus \text{T}, the negation of Q. So (P \oplus \text{T}) \oplus (P \oplus Q) \equiv \neg Q.

Check. At P T, Q F: P \oplus \text{T} is F and P \oplus Q is T, so the whole is T, and so is \neg Q.

Example 2

A parity bit catches a changed bit

Yonatan sends Dorottya the message 1011011 with an even parity bit. (a) What word does he send? (b) Dorottya receives 11110111. What does her check show? (c) What if she receives 01110111?

Solution

(a) The message has five 1s, an odd number, so by the parity theorem the chain of its bits is 1. He sends 10110111, which has six 1s.

(b) Dorottya computes the exclusive or of all eight bits. 11110111 has seven 1s, so the chain is 1: no word Yonatan could send looks like this, and a bit has changed. (It was the second.)

(c) 01110111 has six 1s, so the chain is 0 and the word passes. Yet compared with 10110111, the first two bits have both changed. Each change negates the chain, and two negations cancel. A parity bit detects any odd number of changed bits and misses every even number.

Example 3

Which connectives distribute over exclusive or

Show that P \land (Q \oplus R) \equiv (P \land Q) \oplus (P \land R), and that P \lor (Q \oplus R) is not equivalent to (P \lor Q) \oplus (P \lor R).

Solution

Split on P. If P is F, the left side is F, and the right is \text{F} \oplus \text{F}, also F. If P is T, then \text{T} \land X has the value of X, so both sides are Q \oplus R. Every row falls in one case, so the sides are equivalent.

For “or”, one row is enough. Take P T and Q, R both F. The left side is T, since its first part is T. The right side is \text{T} \oplus \text{T}, which is F. (In bits, the first law is a(b + c) = ab + ac with carries dropped.)

Example 4

Reading a circuit

Write the output Y of the circuit in Figure 2 as a statement, find its value when P is T, Q is F and R is T, and list the input rows on which Y is F.

Figure 2The circuit of Example 4.

Solution

Work from the inputs toward the output. The upper gate is an AND fed by P and Q, so its wire carries P \land Q. The lower gate is a NOT on R, carrying \neg R. Both feed an OR:

Y = (P \land Q) \lor \neg R

At P T, Q F, R T, both P \land Q and \neg R are F, so Y is F.

An OR is F only when both inputs are F, so Y is F when R is T and P, Q are not both true: rows (P, Q, R) = (T, F, T), (F, T, T) and (F, F, T). The other five give T.

Example 5

A seat-belt chime from a sentence

A car’s chime sounds when the driver’s belt is not latched, or when the passenger seat is occupied and the passenger’s belt is not latched. With inputs L “the driver’s belt is latched”, S “the passenger seat is occupied” and M “the passenger’s belt is latched”, write the chime C as a statement and build its circuit.

Solution

The sentence translates part by part: “not latched” is \neg L, the second clause is S \land \neg M, and “or” joins them:

C = \neg L \lor (S \land \neg M)

The last connective applied is \lor, so the last gate is an OR. Its inputs are \neg L, a NOT gate on L, and S \land \neg M, an AND gate fed by S and by a NOT gate on M: four gates, Figure 3.

Figure 3The seat-belt chime, C = \neg L \lor (S \land \neg M).

The input S is there for a reason. With the driver latched and an empty passenger seat whose belt hangs loose, C = \text{F} \lor (\text{F} \land \text{T}), which is F: no chime. Put someone in that seat and C = \text{F} \lor (\text{T} \land \text{T}), which is T.

Example 6

A garage door from a table

A garage door controller runs the motor (M) from three inputs: W, the wall button is pressed; R, the remote button is pressed; O, the safety beam is blocked. Its table:

Row	W	R	O	M
1	T	T	T	F
2	T	T	F	T
3	T	F	T	F
4	T	F	F	T
5	F	T	T	F
6	F	T	F	T
7	F	F	T	F
8	F	F	F	F

Build a circuit from the table, then simplify it.

Solution

The table has T on rows 2, 4 and 6. Each gives a term true on that row only, and M is their “or”:

\begin{aligned} M \equiv\; &(W \land R \land \neg O) \\ \lor\; &(W \land \neg R \land \neg O) \\ \lor\; &(\neg W \land R \land \neg O) \end{aligned}

With two-input gates that is 3 NOT, 6 AND and 2 OR gates, 11 in all.

Every term contains \neg O, so the distributive law of \land over \lor factors it out:

\begin{aligned} M \equiv \big[&(W \land R) \lor (W \land \neg R) \\ &\lor (\neg W \land R)\big] \land \neg O \end{aligned}

The first two share W: (W \land R) \lor (W \land \neg R) \equiv W \land (R \lor \neg R), and R \lor \neg R is a Tautologies and contradictions, so this is W. The bracket is now W \lor (\neg W \land R), and the distributive law of \lor over \land turns it into (W \lor \neg W) \land (W \lor R), which is W \lor R. So

M \equiv (W \lor R) \land \neg O,

three gates (Figure 4), and the plain sentence “a button is pressed and the beam is clear”.

Figure 4The garage door controller after simplifying, three gates in place of eleven.

The same answer comes from when the motor stays off, (\neg W \land \neg R) \lor O. Negating it with De Morgan’s laws:

\begin{aligned} \neg[(\neg W \land \neg R) \lor O] &\equiv \neg(\neg W \land \neg R) \land \neg O \\ &\equiv (W \lor R) \land \neg O \end{aligned}

Example 7

Exclusive or from basic gates, and a half adder

(a) Build exclusive or from AND, OR and NOT gates. (b) Build a circuit that adds two one-bit numbers A and B.

Solution

(a) P \oplus Q is T on rows 2 and 3, so the table gives (P \land \neg Q) \lor (\neg P \land Q): two NOT, two AND and one OR, five gates. The reading “at least one, but not both” from And and or: conjunction and disjunction gives (P \lor Q) \land \neg(P \land Q), which needs only four.

(b) In binary, 0 + 0 = 00, 0 + 1 = 01, 1 + 0 = 01 and 1 + 1 = 10. The low bit S is 1 exactly when one of A, B is, so S = A \oplus B; the carry C is 1 only when both are, so C = A \land B. Build S by the four-gate form of (a): it already computes A \land B inside, so a branch from that wire is the carry, and the whole adder is four gates (Figure 5).

Figure 5A half adder from four gates; crossing wires without a dot are not joined. The first AND gate also gives the carry.

Check. For 1 + 1: the OR gives 1 and the first AND gives 1, so C = 1; the NOT gives 0, so S = 1 \land 0 = 0. The output CS = 10 is two in binary.

Boundaries

A chain is not “exactly one”. P \oplus Q \oplus R is true when all three parts are, since three is odd (Exercise 11).
\land distributes over \oplus, but \lor does not (Example 3), and \oplus does not distribute over \land (Exercise 12).
One parity bit detects an odd number of changed bits only, and never says which bit changed.
These circuits have no loops. A loop can hold a value after the inputs change (that is how memory is built), so its output is not a statement in the current inputs.
Gate counts depend on which gates are allowed; every count here uses two-input gates.

Where this goes next

Adding longer numbers needs a full adder, which adds two bits and an incoming carry: its sum bit is a three-part exclusive or and its carry is the “at least two” statement (Exercises 19, 21 and 22). A row of full adders, each passing its carry on, adds numbers of any length. Several parity bits over different parts of a message can say which bit changed, not only that one did.

The same laws return for sets in Set identities: distributive and De Morgan laws. Next comes the universal quantifier.

Exercises

Exercises 1 to 13 go with the first part (Examples 1 to 3), Exercises 14 to 24 with the second (Examples 4 to 7).

Part 1: exclusive or and its laws

Let P be T, Q be F and R be T. Find the truth value of (a) P \oplus Q \oplus R, (b) \neg P \oplus R, (c) (P \oplus R) \lor Q.
Simplify each to a single letter, its negation, T or F: (a) (P \oplus \text{T}) \oplus \text{T}, (b) P \oplus \neg P, (c) (P \oplus Q) \oplus (Q \oplus \text{T}), (d) \neg P \oplus \neg Q.
Use the laws to show \neg P \oplus \neg Q \oplus \neg R \equiv \neg(P \oplus Q \oplus R).
Find a statement X in P and Q with P \oplus X \equiv Q, and show it is the only one up to equivalence.
How many of the 16 rows of the table for P \oplus Q \oplus R \oplus S make it true?
For which integers n from 1 to 10 is (n > 4) \oplus (n \text{ is odd}) true?

Part 1: parity bits

Find the even parity bit of each message: (a) 0110100, (b) 1110111, (c) 0000000.
Dorottya receives these words, each sent with an even parity bit last. Which fail her check? (a) 10010110, (b) 01110011, (c) 11111111.
A word sent with even parity arrives as 1\,1\,0\,?\,1\,0\,0\,0, one bit unreadable and the rest correct. What is the missing bit?
An odd parity bit makes the number of 1s in the word odd. Write it as a statement in b_1, \ldots, b_7, and find it for the message 1010000.

Part 1: reasoning

Write a statement using \oplus, \land and \neg that is true exactly when exactly one of P, Q, R is true, and say why P \oplus Q \oplus R alone is not it.
Show that P \oplus (Q \land R) is not equivalent to (P \oplus Q) \land (P \oplus R).
Explain why one parity bit can show that a word has an error but never which bit is wrong.

Part 2: reading circuits

Write the output Y of the circuit in Figure 6 as a statement. On how many of the 8 input rows is Y true?

Figure 6The circuit of Exercise 14.

P and Q feed an OR gate; its output and R feed an AND gate, whose output goes through a NOT gate. Write the output, find it at P F, Q T, R T, and list the rows where it is F.

Part 2: building circuits

Describe a circuit for (P \lor \neg Q) \land R and count its gates.
The garage controller gets a lock switch K: the motor runs when a button is pressed, the beam is clear and the lock is off. Write M, then use De Morgan’s laws to build it from four two-input gates.
A circuit with inputs P, Q has output column T, T, F, T in the order TT, TF, FT, FF. Write the statement the table method gives, then find one with two gates.
The majority statement is true when at least two of P, Q, R are true. Find a circuit for it with four two-input gates.

Part 2: simplifying and adding

Simplify the circuit for \neg(\neg P \lor \neg Q) \lor (P \land R), counting gates before and after.
Three bits a, b, c are added, giving a two-bit number. Show that its low bit is a \oplus b \oplus c and its high bit is the majority statement of Exercise 19.
A half adder adds a and b, giving carry c_1 and sum s_1; a second half adder adds s_1 and c, giving c_2 and s_2. Show that s_2 and c_1 \lor c_2 are the low and high bits of Exercise 21.

Part 2: reasoning

A circuit has only AND and OR gates. Show that its output is F when every input is F, and conclude that no such circuit computes \neg P.
Show that every statement in P and Q can be computed with NOT and AND gates alone.

Answers

(a) F: two parts are true, an even number. (b) T: \neg P is F and R is T. (c) F: P \oplus R is F since both are T, and Q is F.
(a) P: it is P \oplus (\text{T} \oplus \text{T}), and \text{T} \oplus \text{T} \equiv \text{F}. (b) T: P and \neg P always differ. (c) \neg P: regroup to P \oplus (Q \oplus Q) \oplus \text{T}, which is P \oplus \text{T}. (d) P \oplus Q: it is (P \oplus \text{T}) \oplus (Q \oplus \text{T}), and the two T’s cancel.
Write each \neg X as X \oplus \text{T} and regroup: (P \oplus Q \oplus R) \oplus (\text{T} \oplus \text{T}) \oplus \text{T}. The pair \text{T} \oplus \text{T} is F and drops out, leaving (P \oplus Q \oplus R) \oplus \text{T}.
X \equiv P \oplus Q, since P \oplus (P \oplus Q) \equiv (P \oplus P) \oplus Q, which is \text{F} \oplus Q \equiv Q. If P \oplus X \equiv Q, then P \oplus (P \oplus X) \equiv P \oplus Q, and the left side is X by the same steps.
8: one true part on 4 rows, three true parts on 4 rows.
n = 1, 3, 6, 8, 10: the parts differ for odd n \le 4 and even n > 4.
(a) 1, three 1s. (b) 0, six 1s. (c) 0: zero 1s is an even count.
Only (b), with five 1s. (a) has four and (c) eight, so both pass.
1. The seven readable bits hold three 1s, and the total must be even.
b_1 \oplus \cdots \oplus b_7 \oplus \text{T}, that is, \neg(b_1 \oplus \cdots \oplus b_7). 1010000 has two 1s, so its odd parity bit is 1.
(P \oplus Q \oplus R) \land \neg(P \land Q \land R). The chain is true when one or three parts are, and the second part rules out three. The chain alone is wrong when all three are true.
Take P T, Q T, R F. The left side is \text{T} \oplus \text{F}, which is T; the right is \text{F} \land \text{T}, which is F.
Changing any single bit turns the chain from F to T, whichever bit it is. The check has only two outcomes, so a change in bit 1 and a change in bit 5 look the same to it.
Y = (P \oplus Q) \land \neg R, true on 2 rows: (T, F, F) and (F, T, F).
\neg((P \lor Q) \land R). At F, T, T, (P \lor Q) \land R is T, so the output is F. It is F exactly when R and P \lor Q are T: rows (T, T, T), (T, F, T) and (F, T, T).
Three gates: a NOT on Q, an OR fed by P and that NOT, and an AND fed by the OR and R.
M = (W \lor R) \land \neg O \land \neg K, five gates. Since \neg O \land \neg K \equiv \neg(O \lor K), M \equiv (W \lor R) \land \neg(O \lor K): two OR, one NOT, one AND.
(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q). The output is F only where \neg P \land Q is T, so it is \neg(\neg P \land Q) \equiv P \lor \neg Q: a NOT and an OR.
At least two are true exactly when some pair is: (P \land Q) \lor (P \land R) \lor (Q \land R). The first two terms are P \land (Q \lor R) by the distributive law, giving (P \land (Q \lor R)) \lor (Q \land R): two OR, two AND.
Before, six gates: three NOT, two OR, one AND. De Morgan gives \neg(\neg P \lor \neg Q) \equiv P \land Q, and (P \land Q) \lor (P \land R) is P \land (Q \lor R): two gates.
The sum is 0 to 3. Its low bit is 1 exactly when the sum is odd, that is, when an odd number of a, b, c are 1: a \oplus b \oplus c by the parity theorem. Its high bit is 1 exactly when the sum is at least 2, that is, when at least two are 1.
s_2 = (a \oplus b) \oplus c, the low bit. The carry c_1 \lor c_2 is (a \land b) \lor ((a \oplus b) \land c): if a, b are both 1 it is 1; if exactly one is, it equals c; if neither, it is 0. Each case is “at least two of a, b, c are 1”.
A gate whose inputs are all F outputs F, since \text{F} \land \text{F} and \text{F} \lor \text{F} are F. Working outward from the inputs, every wire carries F, the output included. \neg P is T when P is F, so no such circuit computes it.
The table method gives a circuit of AND, OR and NOT gates for any table. Replace each OR by A \lor B \equiv \neg(\neg A \land \neg B), De Morgan’s law: three NOT gates and one AND.