Corrected exercises: Boolean and mathematical logic (201-N11)

$\lnot q$ inverts the column of $q$, then apply AND, which equals 1 only when both columns equal 1. Rows in the order $(p,q)=(1,1),(1,0),(0,1),(0,0)$: $\lnot q$ is $0,1,0,1$ and $p\land\lnot q$ is $0,1,0,0$. The expression is therefore true only on the row $p=1$, $q=0$. That is exactly the row where $p\Rightarrow q$ is false, and it is no coincidence: $p\land\lnot q$ is the negation of $p\Rightarrow q$.

A single row: $p=1$ and $q=0$. An implication is false only when the premise is true and the conclusion is false. In the example, the promise “if the file exists, then the read succeeds” is broken only when the file really does exist and the read fails anyway. If the file does not exist, the promise is never tested, and we declare it kept: the last two rows equal 1. This is the point students resist the longest, because the “if” of everyday language carries an idea of cause that the logical $\Rightarrow$ does not have.

$p\oplus q$ equals 1 when the two values differ: $0,1,1,0$ on the four rows. $p\Leftrightarrow q$ equals 1 when they are equal, that is $1,0,0,1$, so its negation is $0,1,1,0$. The two columns are identical: $p\oplus q$ and $\lnot(p\Leftrightarrow q)$ are the same Boolean function. Two expressions are equivalent exactly when their tables agree row by row, and this is the only proof of equivalence that requires no trick.

With $n$ propositions, each proposition takes 2 values independently of the others: the table has $2^{n}$ rows, so $2^{5}=32$ rows for five propositions. To count the functions of two variables, notice that a function is entirely determined by the column of outputs it produces, that is 4 cells to fill with 0 or 1: there are $2^{4}=16$ Boolean functions of two variables. They all have a name: AND, OR, XOR, NAND, NOR, the implication, the two constants, and so on. Classic pitfall: answering 4 by confusing the number of rows with the number of functions.

$A + AB = A(1+B) = A \cdot 1 = A$, because $1+B=1$: an OR with 1 always equals 1. This is the absorption law. How to read it: if $A$ alone already makes the expression true, adding a more demanding case ($A$ AND $B$) adds nothing. Pitfall: writing $A+AB = A+B$ by “simplifying” as in ordinary algebra.

Expand: $(A+B)(A+\overline{B}) = AA + A\overline{B} + BA + B\overline{B}$. Now $AA=A$ (idempotence) and $B\overline{B}=0$ (a variable and its negation are never true together), so what remains is $A + A\overline{B} + AB = A(1+\overline{B}+B) = A$. You can also apply directly the distributive law of OR over AND: $(A+B)(A+\overline{B}) = A + B\overline{B} = A+0 = A$. This second distributive law, $X+YZ = (X+Y)(X+Z)$, has no counterpart with real numbers: it is the one people forget.

De Morgan gives $\overline{AB} = \overline{A}+\overline{B}$, so $\overline{AB}+\overline{A} = \overline{A}+\overline{B}+\overline{A} = \overline{A}+\overline{B}$ by idempotence, which is again $\overline{AB}$. The expression was already $\overline{AB}$ from the start: the term $\overline{A}$ was absorbed.

De Morgan on the first factor: $\overline{\overline{A}+\overline{B}} = \overline{\overline{A}} \cdot \overline{\overline{B}} = AB$. The expression becomes $AB(A+B) = ABA + ABB = AB + AB = AB$. Result: $AB$. The long bar is lifted in one go and changes the connective; the short bar over each letter stays.

$A \oplus A = 0$: two identical values give 0. $A \oplus \overline{A} = 1$: they always differ. $A \oplus 0 = A$: XOR with 0 lets the value through. These three identities are the basis of XOR encryption and of swapping two variables without a temporary variable.

Table of $(A+B)(A+\overline{B})$ on the rows $(A,B)=(1,1),(1,0),(0,1),(0,0)$: $A+B$ is $1,1,1,0$; $A+\overline{B}$ is $1,1,0,1$; their product is $1,1,0,0$. That is exactly the column of $A$. The table confirms the simplification, and it is the only check that cannot be argued with.

Contrapositive: $s \Rightarrow \lnot c$, that is “if the program contains a syntax error, then it does not compile”. The contrapositive swaps AND negates both sides. It always has the same truth value as the original implication: the two have the same table. That is what justifies proof by contrapositive.

Converse: $\lnot s \Rightarrow c$, that is “if the program contains no syntax error, then it compiles”. It is false: a syntactically correct program can fail to compile because of a type error, a missing library or a file that cannot be found. That is a counterexample, and one is enough. The converse has no reason to share the truth value of the implication: confusing the two is the most frequent reasoning error of the course.

To negate an implication is to assert the premise and negate the conclusion: $\lnot P = c \land s$, that is “the program compiles AND it contains a syntax error”. The negation of an implication is never an implication, and certainly not $c \Rightarrow s$. The landmark: a promise is refuted only by exhibiting the case where it is broken.

Table on the rows $(p,q)=(1,1),(1,0),(0,1),(0,0)$. $p \Rightarrow q$ is $1,0,1,1$. For $\lnot p \lor q$: $\lnot p$ is $0,0,1,1$, so $\lnot p \lor q$ is $1,0,1,1$. The two columns agree on all four rows, so the expressions are equivalent. This identity is how all of logic enters circuits: an implication is wired with one NOT and one OR.

$\lnot(p \Rightarrow q) = \lnot(\lnot p \lor q) = p \land \lnot q$ by De Morgan. We recover the answer to question c) by calculation, which confirms it.

Example: in a loop over an empty array, the statement “for every iteration performed, the counter increases” is vacuously true, since no iteration is performed. A unit test run on an empty array therefore always passes if its condition is about the elements: it proves nothing. That is why a specification of the form “if the array contains a duplicate, then the function returns true” must be tested on a case where the premise is actually true.

$\forall i \in \{0,\dots,n-1\},\ T[i] > 0$. We quantify over the indices, not over the values: this is the form that translates directly into a loop.

Negation swaps the quantifier and negates the property: $\exists i \in \{0,\dots,n-1\},\ T[i] \le 0$, that is “there is at least one element of $T$ that is negative or zero”. In words, the negation of “all” is not “none” but “at least one is not”. Confusing the two is the costliest error of the chapter, because it goes unnoticed when you reread.

“$T$ contains at least one duplicate” is written $\exists i,\ \exists j,\ (i \neq j) \land (T[i]=T[j])$. Its negation is $\forall i,\ \forall j,\ (i \neq j) \Rightarrow (T[i] \neq T[j])$: all the elements are pairwise distinct. Notice that the negation of an $\exists$ followed by an AND gives a $\forall$ followed by an implication, not by an AND.

The first is true: for each $x$, choose $y=-x$, and this choice is allowed to depend on $x$ since $y$ is quantified after it. The second is false: it would require a single $y$ that cancels every $x$ at once, but $y$ would work for $x=-y$ and fail for $x=-y+1$. The comparison shows that the order of the quantifiers is not decoration: $\forall\exists$ and $\exists\forall$ are two different statements, and one can be true while the other is false.

It is true. On an empty array there is no index $i$, so no opportunity to find a counterexample: the statement is vacuously true. A function that scans the array and returns true if no violation was found therefore does return true on the empty array, which is the correct behaviour and not a bug.

To verify the statement, you must go all the way: $n$ comparisons in the worst case, and exactly $n$ when the statement is true. To refute it, a single counterexample is enough, so 1 comparison at best, and $n$ at worst if the only offending element is the last one. This asymmetry is that of $\forall$: expensive to confirm, sometimes immediate to disprove. For an $\exists$, it is the other way around.

The rows where $f=1$ are $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ and $(1,1,1)$. Each row gives a product: $\overline{A}BC$, $A\overline{B}C$, $AB\overline{C}$ and $ABC$. Hence $f = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$. The rule: a variable that equals 1 on the row enters as it is, a variable that equals 0 enters complemented. Each product equals 1 on its own row and on that row alone, so the sum equals 1 on exactly the four rows we want.

Each product of three variables requires 2 two-input AND gates, so 8 AND gates, plus 3 NOT gates (one per complemented variable, here $\overline{A}$, $\overline{B}$, $\overline{C}$), plus 3 OR gates to join the 4 terms. Total: 14 gates. It is precisely this cost that motivates simplification.

Expand the proposed form. $AB$ equals 1 on the rows $(1,1,0)$ and $(1,1,1)$; $BC$ equals 1 on $(0,1,1)$ and $(1,1,1)$; $AC$ equals 1 on $(1,0,1)$ and $(1,1,1)$. The union of these rows is $\{(0,1,1),(1,0,1),(1,1,0),(1,1,1)\}$, exactly the set of rows where $f=1$, and no other row is reached. The tables agree, so $f = AB+BC+AC$. Algebraically: $ABC$ is covered by all three terms and can be duplicated by idempotence, which lets you merge $\overline{A}BC + ABC = BC$, $A\overline{B}C+ABC = AC$ and $AB\overline{C}+ABC = AB$. We go from 14 gates to 5.

$f$ equals 1 exactly when at least two of the three variables equal 1: it is the majority function. It is used for majority voting in redundant systems (triple modular redundancy), where the failure of one sensor out of three is tolerated.

$\overline{f}$ equals 1 on the four remaining rows: $(0,0,0)$, $(0,0,1)$, $(0,1,0)$ and $(1,0,0)$. Hence $\overline{f} = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C}$, which does have 4 terms. The 8 rows are split between $f$ and $\overline{f}$ with nothing left over: a free check to do every time.

The row $AB=01$ means $A=0$ and $B=1$; the column $CD=11$ means $C=1$ and $D=1$. The number is $8(0)+4(1)+2(1)+1 = 7$, which is indeed in the list. This check is worth doing on two or three cells before grouping anything: a badly filled map produces an impeccable simplification of the wrong function.

Test the column $CD=11$, which is all 1s. Its four numbers are $3$ (row 00), $7$ (row 01), $15$ (row 11) and $11$ (row 10). But $3$ and $11$ are not in the list $\{0,2,5,7,8,10,13,15\}$. The faulty cells are therefore those of rows $AB=00$ and $AB=10$ in column $CD=11$: they equal 0. After correcting them, the map becomes: row $00$: $1,0,0,1$; row $01$: $0,1,1,0$; row $11$: $0,1,1,0$; row $10$: $1,0,0,1$. There are then 8 cells holding 1, matching the 8 minterms announced. This count is the check not to skip.

First group: the four corners of the map, cells $(AB,CD) = (00,00), (00,10), (10,00), (10,10)$, that is the numbers $0, 2, 8, 10$. Since opposite edges are adjacent, these four corners do form a rectangle of 4. Over this group $A$ changes and $C$ changes, but $B=0$ and $D=0$ throughout: it gives $\overline{B}\,\overline{D}$. Second group: the central block of rows $01$ and $11$ over columns $01$ and $11$, that is the numbers $5, 7, 13, 15$. $A$ changes, $C$ changes, but $B=1$ and $D=1$: it gives $BD$. All 8 cells are covered, so $f = \overline{B}\,\overline{D} + BD$. The variables $A$ and $C$ have disappeared: the function does not depend on them.

$f$ equals 1 exactly when $B$ and $D$ have the same value: it is the exclusive NOR (XNOR), $f = \overline{B \oplus D}$, called an equality comparator. It is the building block of a binary word comparator: test equality bit by bit, then join the results with ANDs.

Canonical form: 8 minterms of 4 variables, so 24 two-input AND gates, 7 OR gates and 4 NOT gates, about 35 gates. Simplified form: 2 NOT gates, 2 AND gates, 1 OR gate, so 5 gates, or a single XNOR gate if the library offers one. The ratio is roughly 7 to 1, and it is paid for in silicon area, power consumption and propagation delay.

$A$ and $B$ both enter the XOR gate at the top and the AND gate at the bottom. So $S = A \oplus B$ and $C = AB$. The dots on the wires mark junctions: the same signal feeds two gates, which is allowed and costs nothing more than a trace.

Rows $(A,B) = (0,0), (0,1), (1,0), (1,1)$. $S$ is $0, 1, 1, 0$ and $C$ is $0, 0, 0, 1$. Reading $C$ as the most significant bit and $S$ as the least significant bit, the pair $(C,S)$ is $00, 01, 01, 10$ in binary, that is $0, 1, 1, 2$ in decimal: exactly $A+B$. The circuit adds. The case $1+1$ is what justifies the carry: the sum is 2, which does not fit in one bit.

$S = A \oplus B \oplus C_{\text{in}}$: the sum equals 1 when an odd number of inputs equal 1. $C_{\text{out}} = AB + C_{\text{in}}(A \oplus B)$: there is a carry either because $A$ and $B$ both equal 1, or because exactly one of them equals 1 and the carry-in is added to it. Numerical check: for every combination, $2C_{\text{out}} + S = A+B+C_{\text{in}}$, which equals 0, 1, 2 or 3. This block is wired $n$ times in a chain to add two $n$-bit words.

NOT: $\overline{A} = A \uparrow A$, a single NAND, with both inputs tied together. AND: $AB = \overline{\overline{AB}} = (A \uparrow B) \uparrow (A \uparrow B)$, so 2 NAND gates. OR: by De Morgan, $A+B = \overline{\overline{A} \cdot \overline{B}} = \overline{A} \uparrow \overline{B} = (A \uparrow A) \uparrow (B \uparrow B)$, so 3 NAND gates. Since every circuit can be described with NOT, AND and OR, every circuit can be described with NAND gates alone: the gate is called universal. The NOR gate is universal too.

Because a plant that etches a single transistor pattern etches it better, tests it with a single test bench and reuses the same library cell everywhere. In CMOS technology, the NAND is also the cheapest gate: 4 transistors, against 6 for an AND, which is just a NAND followed by an inverter. A circuit built entirely of NAND gates is therefore often smaller than the same circuit written with ANDs and ORs, even if it has more gates on the schematic.

FALSE. An implication and its converse are two independent statements. “If $x=2$ then $x^{2}=4$” is true, but its converse “if $x^{2}=4$ then $x=2$” is false for $x=-2$. Correct statement: an implication always has the same truth value as its CONTRAPOSITIVE, never necessarily as its converse.

FALSE. This is De Morgan's law applied wrongly: lifting the bar also changes the connective. Counterexample with $A=1$, $B=0$: $\overline{AB} = \overline{0} = 1$, whereas $\overline{A} \cdot \overline{B} = 0 \cdot 1 = 0$. Correct statement: $\overline{AB} = \overline{A} + \overline{B}$, and symmetrically $\overline{A+B} = \overline{A} \cdot \overline{B}$.

FALSE. Each proposition doubles the number of rows: there are $2^{n}$ of them, so $2^{4} = 16$ for four propositions. Eight rows correspond to three propositions. Correct statement: a table with $n$ propositions has $2^{n}$ rows, and the number of Boolean functions of $n$ variables is $2^{2^{n}}$.

FALSE. OR distributes over AND by duplicating the term: counterexample with $A=1$, $B=0$, $C=0$: on the left $1 + 0 = 1$, on the right $(1+0) \cdot 0 = 0$. Correct statement: $A + BC = (A+B)(A+C)$.

FALSE. Logical OR is inclusive: $1+1 = 1$. It is true as soon as at least one input equals 1, including when both equal 1. Correct statement: the connective that equals 0 when both inputs equal 1 is the exclusive OR, written $A \oplus B$, and it satisfies $A \oplus B = A\overline{B} + \overline{A}B$.

The specification translates term by term: $A = BCH + BCD$. Each “AND” becomes a product, and “also” becomes an OR.

$BCH + BCD = BC(H+D)$ by factoring, that is the distributive law of AND over OR read from right to left. Business reading: you need the badge AND the code, plus at least one of the two time justifications. This form states the specification better than the first, because it separates identification from time authorization.

Before: each product of three variables requires 2 AND gates, so 4 AND gates, plus 1 OR gate: 5 gates. After: 1 OR gate for $H+D$, then 2 AND gates for $B \cdot C \cdot (H+D)$: 3 gates. We save 2 gates out of 5, and above all one level of logic, hence delay.

$A$ equals 1 when $B=1$, $C=1$ and $H+D=1$. With $B$ and $C$ fixed, the 4 combinations of $(H,D)$ remain, 3 of which satisfy $H+D=1$: $(1,0)$, $(0,1)$ and $(1,1)$. So 3 combinations out of 16 open the door. The proportion is a useful check: a security system that opened on half of the combinations would be suspect by design.

$\overline{A} = \overline{BC(H+D)} = \overline{BC} + \overline{H+D} = \overline{B} + \overline{C} + \overline{H}\,\overline{D}$, by De Morgan applied twice. Three causes of refusal, and they are clearly distinct: invalid badge, or wrong code, or outside business hours AND without a dispensation. Notice that the third cause is a product, not a sum: being outside business hours is not enough to refuse if a dispensation exists.