Logic Gates and Boolean Algebra: Exam Notes

The correct answer is B, OR. Read the table row by row. The output is 0 only when both inputs are 0, and it is 1 in the other three rows, including the row where both inputs are 1. That is exactly the rule of an OR gate, which gives 1 when at least one input is 1 and behaves like two switches wired in parallel. A is wrong because a NOT gate has only one input and so cannot have a table with two input columns at all. C is wrong because an XOR gate responds only to a difference between its inputs, so its last row, with both inputs 1, would give 0 and not 1; this is the one row that separates OR from XOR and the reason the distractor is offered. D is wrong because an AND gate gives 1 only in the last row and 0 in the first three, which is the mirror image of the table shown.

The correct answer is B, NAND and NOR. Each of these gates alone is enough to build every other gate and so every logic circuit: a NAND with its two inputs tied together acts as a NOT, two NANDs in sequence give an AND, and a suitable arrangement of three gives an OR, and the same can be done entirely with NOR gates. That is why chip makers sell packages containing only one gate type. A is wrong because AND and OR cannot produce a complement by themselves; without a NOT they can never invert a signal. C is wrong because XOR and XNOR are themselves derived gates, built from the basic three, and neither can generate the full set on its own. D is wrong because NOT with AND can indeed build everything, but the pair is not given the name universal gates; the term is reserved for the two single gates that suffice by themselves.

The correct answer is B, the sum of the complements. De Morgan's second theorem states that NOT of A AND B equals NOT A OR NOT B. The working rule is to break the bar and change the sign, so a dot under a complement becomes a plus once the complement is distributed over the variables. A is wrong because the product of the complements is the result of the first theorem, which applies to the complement of a sum, not of a product; swapping the two theorems is the standard error in this question. C is wrong because complementing an expression must change it unless the expression is a constant, and the product of A and B is not its own complement. D is wrong because the value depends on the inputs: when A is 1 and B is 1 the expression is 0, so it cannot always be 1. Both theorems together make NAND-only and NOR-only design possible.

The correct answer is C, when the two inputs are different. An exclusive OR gate is a difference detector: it gives 1 for the combinations 0 and 1 or 1 and 0, and gives 0 when the inputs agree. It is sometimes read as either but not both. A is wrong because two inputs of 1 give an output of 0 in an XOR gate; that row is exactly what distinguishes it from an ordinary OR gate, which would give 1. B is wrong because two inputs of 0 also agree, so the output is again 0. D is wrong because an output of 1 for identical inputs describes the XNOR gate, the complement of XOR, which works as an equality detector and is used to compare two binary numbers bit by bit. In a half adder, the XOR gate supplies the sum bit while the AND gate supplies the carry.

The correct answer is D, a variable in its complemented or uncomplemented form. In Boolean algebra a literal is any single appearance of a variable in an expression, whether it appears plain or with a bar over it. The count of literals is used to measure how costly an expression is, because each literal becomes one input line to a gate, so simplification is judged by how many literals it removes. A is wrong because restricting the term to the plain form would leave no name for the complemented appearance, which is equally a literal. C is wrong for the mirror reason: the complemented form is not the only kind. B is wrong because, read as it stands, it suggests a variable taken together with its complement, which describes a pair rather than the single appearance that a literal is. Remember that a term such as A AND NOT B contains two literals and two variables.

The correct answer is B, George Boole, the English mathematician who in the middle of the nineteenth century showed that logical reasoning could be written as an algebra on just two values, true and false. The system was a work of pure mathematics for decades until Claude Shannon showed that it described electrical switching circuits exactly, which opened the way to digital computing. A is wrong because Charles Babbage designed the Difference Engine and the Analytical Engine and is called the father of the computer, but he worked on mechanical calculation, not on logic as algebra. C is wrong because Blaise Pascal built an early mechanical adding machine, the Pascaline, in the seventeenth century. D is wrong because John von Neumann gave the stored-program architecture in which instructions and data share the same memory, a much later contribution. Pair the names carefully: Boole for the algebra, Shannon for its use in circuits, Karnaugh for the simplification map.

The correct answer is C, the XOR gate. Adding two single bits gives a sum that is 1 when exactly one of the bits is 1 and 0 when both are 0 or both are 1, which is precisely the XOR rule; so in a half adder the sum line comes from an XOR gate. A is wrong because the AND gate in a half adder produces the carry, which is 1 only when both bits are 1, and swapping sum with carry is the usual mistake here. B is wrong because an OR gate would wrongly give a sum of 1 when both bits are 1, and in any case the OR gate appears only in the full adder, where it combines the two carry signals. D is wrong because a NOR gate plays no part in the standard half adder at all. Remember the full sentence: half adder equals XOR for sum plus AND for carry, two inputs, no carry in.

The correct answer is C, the NOT gate. It is the only gate that takes a single input, and it simply reverses the logic level it receives, giving 1 for an input of 0 and 0 for an input of 1; because the output is the inverse or complement of the input, the circuit is called an inverter. In Boolean notation it is written with a bar or a prime over the variable, and in a diagram it is a triangle with a small circle at its tip. A is wrong because an AND gate has two or more inputs and does not reverse anything. B is wrong for the same reason. D is wrong because a NAND gate inverts only the result of an AND operation and normally has two inputs, although it is worth remembering that a NAND gate with both of its inputs joined together does behave as an inverter, which is one of the proofs that NAND is a universal gate.

The correct answer is C, eight. Each input can take one of two values, so for three inputs the number of distinct combinations is two multiplied by itself three times, that is two raised to the power three, which is eight. The same rule gives four rows for two inputs, sixteen for four inputs and thirty-two for five. A is wrong because three is simply the number of inputs, not of combinations, and no truth table has as many rows as it has input columns. B is wrong because it comes from multiplying the number of inputs by two, the commonest error on this question; the relationship is a power of two, not a product. D is wrong because nine is three squared, which reverses base and exponent; the base must always be two, since each variable is binary. Checking that the table has the right number of rows is also a quick way to catch a missing combination.

The correct answer is B, 1. This is the complement law for addition, which corresponds to the OR operation. Whatever value A takes, one of A and its complement must be 1, and an OR gate gives 1 whenever any input is 1, so the expression is 1 in both cases. A is wrong because 0 is the answer to the companion law for multiplication, A multiplied by the complement of A, where one factor is always 0 and an AND gate therefore gives 0; the two complement laws are routinely interchanged in papers. C is wrong because A plus A, not A plus its complement, returns A, which is the idempotent law. D is wrong because nothing in Boolean algebra makes a sum collapse to the complement of one of its terms. Keep the pair together in memory: a variable OR its complement is 1, a variable AND its complement is 0.