Logic Gates and Logic Circuits

💬 4.01 Boolean logic and problem statements

Suppose someone asks whether Colombo is further north than Singapore. If you know a little geography, you answer yes or no. You could just as well say the statement is TRUE or FALSE: in logic, those are the only two possible values.

Real decisions usually depend on more than one proposition:

• I will take an umbrella if it is raining or the forecast says rain.
• The air-conditioning should run during working hours and when the temperature is above 25 °C.

Each of these is a problem statement: an informal description of an outcome. The words or and and are doing logical work, joining two propositions.

🧪 Spot the proposition

A logic proposition has to be something that is definitely TRUE or definitely FALSE at a given moment. Questions, commands and opinions are not propositions. Check yourself:

⚙️ 4.02 Boolean operators

The words that join propositions become Boolean operators, named after the mathematician George Boole. Three of them do all the work:

Using them, the two problem statements from 4.01 can be written more formally:

Take_umbrella = TRUE IF (raining = TRUE) OR (rain_forecast = TRUE)

Aircon_on = TRUE IF (working_hours = TRUE) AND (temperature > 25)

Any logic expression at all can be written with only AND, OR and NOT. Even so, three more operators are useful:

🛒 Worked Example 4.01 Problem statement → expression

A shopkeeper has new stock delivered at the end of every month. A delivery is also made early in two situations: when the stock of an item falls to its re-order level, or when a regular customer places an order for a large amount.

Step 1: name the propositions.

Step 2: join them. Any one of three things triggers a delivery, so they are joined with OR. The third one needs both C and D, so it is bracketed with AND:

X = A OR B OR (C AND D)

✏️ Task 4.01

📊 4.03 Truth tables

A truth table lists every possible combination of input values and the output each one produces. In a truth table, 1 stands for TRUE and 0 for FALSE. Here is the table for A AND B:

Table 4.01 · the truth table for A AND B

Only the last row has both inputs TRUE, so it is the only row with an output of 1.

✏️ Task 4.02

🔌 4.04 Logic circuits and logic gates

Inside a computer, a logic proposition is a signal that is either on (1) or off (0). A logic circuit combines these signals using components called logic gates, each one acting like a Boolean operator.

Every gate has its own symbol. The shape tells you which gate it is; the inputs come in on the left and the output leaves on the right. Here is the AND gate:

Figure 4.01 (redrawn) · the symbol for an AND gate

A gate can be built with more than two inputs, but in this course every gate has at most two.

🔣 All six gates Figure 4.02

• The NOT gate has only one input. Its output is the opposite of that input.
• A NAND gate gives the same result as an AND gate followed by a NOT gate. The small circle (bubble) on its output means "invert".
• A NOR gate gives the same result as an OR gate followed by a NOT gate.
• XOR is the OR shape with an extra curved line at the back.

✏️ Task 4.03 and Extension Question 4.01

❓ Question 4.01

🏦 Worked Example 4.02 Statement → expression → circuit

A bank offers a special interest rate. To get it, a customer must have banked there for at least two years. They must also meet at least two of these three conditions: they are married, they are aged 25 or over, and at least one of their parents banks there.

Step 1: the propositions.

Step 2: the expression. "Two of B, C and D" means B AND C, or B AND D, or C AND D. A is needed as well:

X = A AND (((B AND C) OR (B AND D)) OR (C AND D))

The extra brackets are there because each gate has only two inputs, so the three ORs have to be done one pair at a time.

Step 3: the circuit. Each AND or OR in the expression becomes one gate, so the circuit needs four AND gates and two OR gates.

Here it is live. P, Q and R are the three AND pairs; S and T are the two OR gates.

🔍 Worked Example 4.03 Circuit → truth table

Find the truth table for this circuit:

Step 1: set up the table. Three inputs give eight rows. Leave a workspace between the inputs and the output for the values partway through the circuit:

Table 4.02 · the empty table with its workspace

Step 2: label the intermediate points. Each gate output gets a letter:

• M = A AND B
• N = NOT B
• P = NOT M
• Q = N AND C
• X = P AND Q

Step 3: fill in the columns from left to right. Each workspace column only needs columns already filled in. Toggle the inputs to watch the values flow, then compare with the finished table:

X is 1 only for inputs 001 and 101.

🔁 Truth table → logic expression

To write an expression from a truth table, use only the rows where the output is 1:

1. For each of those rows, AND the inputs together, putting NOT in front of any input that is 0.
2. OR all of those terms together.

Table 4.04 · a truth table to turn into an expression

Rows 001, 011 and 100 give 1, so:

X = (NOT A AND NOT B AND C) OR (NOT A AND B AND C) OR (A AND NOT B AND NOT C)

This is correct but long. Chapter 19 shows how to simplify expressions like this one.

🔌 Logic circuit → logic expression

There are two ways to do this:

• Build the truth table for the circuit (as in the Circuit → truth table tab), then use the rows with output 1 as above.
• Or work backwards from the output, writing each gate as an operator with its two inputs in brackets. For Figure 4.05 this gives X = NOT (A AND B) AND (NOT B AND C).

✏️ Task 4.04

📌 Summary

• A logic scenario can be described by a problem statement or by a logic expression.
• A logic expression is made of logic propositions joined by Boolean operators.
• A logic circuit is built from logic gates, and each gate works like one Boolean operator.
• The outcome of a logic expression or logic circuit can be set out as a truth table.
• A logic expression can be built from a truth table by using the rows that give an output of 1.

🪞 Reflection Point

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my own mark-scheme-style answers, not official mark schemes. Where the answer is a circuit, it is live: toggle the inputs to check it.