3.3 Boolean Logic - A-Level Computer Science

Learning Objectives

By the end of this lesson, you will be able to:

Identify and use the standard symbols for logic gates
Define and understand the functions of logic gates including: NOT, AND, OR, NAND, NOR, XOR (EOR)
Use logic gates to create given logic circuits from: (i) problem statement (ii) logic expression (iii) truth table
Complete a truth table from: (i) problem statement (ii) logic expression (iii) logic circuit
Write a logic expression from: (i) problem statement (ii) logic circuit (iii) truth table
Understand that logic circuits will be limited to a maximum of three inputs and one output
Apply Boolean algebra notation to represent logic expressions
Construct truth tables showing all possible combinations of inputs and outputs

Key Terms

Logic Gate

Simple electronic circuit which processes two states signal according to logical rule

Truth Table

Table showing all possible input combinations and corresponding outputs for a logic gate or circuit

Boolean Algebra

Mathematical system for logical operations using binary values (0 and 1)

Binary Inputs

Input signals that can only be 0 (false/off) or 1 (true/on)

Logic Circuit

Combination of logic gates working together to perform a specific function

NOT Gate

Inverts input signal (0 becomes 1, 1 becomes 0)

AND Gate

Output is 1 only if ALL inputs are 1

OR Gate

Output is 1 if AT LEAST ONE input is 1

NAND Gate

NOT AND - Output is 0 only if ALL inputs are 1

NOR Gate

NOT OR - Output is 1 only if ALL inputs are 0

XOR Gate (EOR)

Exclusive OR - Output is 1 if inputs are DIFFERENT

Logic Expression

Mathematical representation of a logic circuit using Boolean algebra notation

Logic Gates Fundamentals

A logic gate is a simple electronic circuit which processes two states signal according to logical rule. Each gate has one or more inputs and a single output. Logic gates take binary inputs (0 or 1) and produce a binary output.

Real-Life Example: Light Switch System

Think of a room with two light switches:

Switch A = Input A (0 = OFF, 1 = ON)
Switch B = Input B (0 = OFF, 1 = ON)
Light = Output X (0 = OFF, 1 = ON)
If both switches must be ON for light to turn on → AND gate
If either switch turns on the light → OR gate
If switch turns light OFF when flipped ON → NOT gate

Binary Basics

Binary 0

False, OFF, Low voltage, No signal

Binary 1

True, ON, High voltage, Signal present

I/O

Inputs & Outputs

Gates have 1+ inputs, 1 output. NOT has 1 input, others have 2+

Truth Tables

Truth tables are used to show logic gate functions. When constructing a truth table, binary values 1 and 0 are used. Every possible combination, depending on number of inputs, is produced. Number of possible combinations of 1s and 0s is \(2^n\), where \(n =\) number of inputs.

Truth Table Combinations

1 input → \(2^1 = 2\) combinations (0, 1)
2 inputs → \(2^2 = 4\) combinations (00, 01, 10, 11)
3 inputs → \(2^3 = 8\) combinations (000, 001, 010, 011, 100, 101, 110, 111)
For AS Level, we use maximum of 3 inputs and 1 output

Truth Table Builder

Input A	Input B	Input C	Output X

How to read: Each row shows one possible combination of inputs. The output column shows what the logic gate/circuit produces for that combination. For 3 inputs, there are \(2^3 = 8\) rows.

NOT Gate (Inverter)

Function

NOT gate has only one input. Its main function is to invert input signal applied. If applied input is zero then the output becomes one and vice versa.

Logic notation: X = NOT A

Boolean algebra: X = A̅ or X = ¬A

Truth Table

Input A	Output X
0	1
1	0

NOT

Symbol: Triangle with circle at output

AND Gate

Function

Output (X) is true (i.e., 1 or ON) if: INPUT A AND INPUT B are BOTH TRUE (i.e., 1 or ON).

Logic notation: X = A AND B

Boolean algebra: X = A · B or X = A ∧ B

Truth Table

Input A	Input B	Output X
0	0	0
0	1	0
1	0	0
1	1	1

AND

Symbol: D-shaped gate

OR Gate

Function

Output (X) is true (i.e., 1 or ON) if: INPUT A OR INPUT B is TRUE (i.e., 1 or ON).

Logic notation: X = A OR B

Boolean algebra: X = A + B or X = A ∨ B

Truth Table

Input A	Input B	Output X
0	0	0
0	1	1
1	0	1
1	1	1

Symbol: Curved gate

NAND Gate

Function

Output (X) is true (i.e., 1 or ON) if: INPUT A AND INPUT B are NOT BOTH TRUE (i.e., 1 or ON). This is an AND gate followed by a NOT gate.

Logic notation: X = A NAND B

Boolean algebra: X = A · B̅ or X = ¬(A ∧ B)

Truth Table

Input A	Input B	Output X
0	0	1
0	1	1
1	0	1
1	1	0

NAND

Symbol: AND gate with circle at output

NOR Gate

Function

Output (X) is true (i.e., 1 or ON) if: INPUT A OR INPUT B are NOT BOTH TRUE (i.e., 1 or ON). This is an OR gate followed by a NOT gate.

Logic notation: X = A NOR B

Boolean algebra: X = A + B̅ or X = ¬(A ∨ B)

Truth Table

Input A	Input B	Output X
0	0	1
0	1	0
1	0	0
1	1	0

NOR

Symbol: OR gate with circle at output

XOR Gate (EOR - Exclusive OR)

Function

Output, X, is 1 if: (input A is 1 AND input B is 0) OR (input A is 0 AND input B is 1). In other words, output is 1 if inputs are DIFFERENT.

Logic notation: X = A XOR B

Boolean algebra: X = A ⊕ B

Truth Table

Input A	Input B	Output X
0	0	0
0	1	1
1	0	1
1	1	0

XOR

Symbol: OR gate with curved line at input

Boolean Algebra Notation Summary

Operation	Logic Notation	Boolean Algebra	Example
NOT	NOT A	A̅, ¬A	If A=1, then A̅=0
AND	A AND B	A·B, A∧B	1·1=1, 1·0=0
OR	A OR B	A+B, A∨B	1+0=1, 0+0=0

Logic Gates Comparison

Gate	Description	Output is 1 when...	Boolean Expression
NOT	Inverter	Input is 0	X = A̅
AND	All inputs true	ALL inputs are 1	X = A·B
OR	At least one true	AT LEAST ONE input is 1	X = A+B
NAND	NOT AND	NOT all inputs are 1	X = A·B̅
NOR	NOT OR	ALL inputs are 0	X = A+B̅
XOR	Exclusive OR	Inputs are DIFFERENT	X = A⊕B

Activity 1: Gate Identification & Truth Tables

For each scenario below, identify the correct logic gate and complete the truth table:

Scenario 1: Car Security System

The alarm sounds if BOTH the driver's door is open AND the ignition is on.

Gate:

Scenario 2: Room Lighting

The main light turns on if EITHER switch A is on OR switch B is on (or both).

Gate:

Scenario 3: Electronic Lock

The door unlocks only when the two entered keycodes are DIFFERENT.

Gate:

Task 2: Complete this truth table for a NAND gate:

A	B	X (NAND)
0	0
0	1
1	0
1	1

Solution:

Scenario 1: AND gate (both conditions must be true)
Scenario 2: OR gate (either condition can be true)
Scenario 3: XOR gate (inputs must be different)
NAND Truth Table:
- A=0, B=0 → X=1
- A=0, B=1 → X=1
- A=1, B=0 → X=1
- A=1, B=1 → X=0
Remember: NAND gives 0 ONLY when both inputs are 1. All other combinations give 1.

Check Your Understanding: Logic Gates

1. What is a logic gate? [2 marks]

Answer

[1 mark] A logic gate is a simple electronic circuit which processes two states signal according to logical rule
[1 mark] Each gate has one or more inputs and a single output, processing binary inputs (0 or 1) to produce a binary output

2. What is the function of a NOT gate? [2 marks]

Answer

[1 mark] A NOT gate inverts the input signal
[1 mark] If input is 0, output becomes 1; if input is 1, output becomes 0
[Additional] Boolean algebra: X = A̅ or X = NOT A

3. Explain the difference between AND and OR gates. [3 marks]

Answer

[1 mark] AND gate: Output is 1 only if ALL inputs are 1
[1 mark] OR gate: Output is 1 if AT LEAST ONE input is 1
[1 mark] Boolean algebra: AND = A·B, OR = A+B
[Additional] Example: AND = both switches must be ON; OR = either switch can be ON

4. What is a truth table and how many rows does it have for 3 inputs? [3 marks]

Answer

[1 mark] A truth table shows all possible input combinations and corresponding outputs
[1 mark] Number of rows = \(2^n\) where n = number of inputs
[1 mark] For 3 inputs: \(2^3 = 8\) rows
[Additional] Shows every combination from 000 to 111 (binary 0 to 7)

5. What is the difference between NAND and NOR gates? [3 marks]

Answer

[1 mark] NAND: NOT AND - Output is 0 only when ALL inputs are 1
[1 mark] NOR: NOT OR - Output is 1 only when ALL inputs are 0
[1 mark] Boolean: NAND = A·B̅, NOR = A+B̅
[Additional] NAND is AND followed by NOT; NOR is OR followed by NOT

6. When does an XOR gate output 1? [2 marks]

Answer

[1 mark] XOR (Exclusive OR) gate outputs 1 when inputs are DIFFERENT
[1 mark] Specifically: (A=1 AND B=0) OR (A=0 AND B=1)
[Additional] Boolean: X = A⊕B. Outputs 0 when inputs are the same (both 0 or both 1)

Logic Circuits & Applications

When logic gates are combined together to carry out particular function, such as controlling a robot, they form a logic circuit. Output from a logic circuit (network) is checked by producing a truth table. Logic circuits will be limited to a maximum of three inputs and one output for AS Level.

Real-Life Example: Burglar Alarm System

A home security system might use:

Window sensor = Input A (1 = broken)
Door sensor = Input B (1 = opened)
Motion detector = Input C (1 = motion detected)
Alarm = Output X (1 = sound alarm)
Logic: Alarm sounds if (window broken OR door opened) AND motion detected
Circuit: (A OR B) AND C

Circuit Design Process

Problem Statement

Describe what the circuit should do in words

Logic Expression

Write Boolean expression using AND, OR, NOT

Logic Circuit

Draw gates and connections

Truth Table

Test all input combinations

Logic Circuit Builder

Build a circuit: Drag and drop elements to create connections. For AS Level, circuits have max 3 inputs (A, B, C) and 1 output (X).

Example 1: Creating Logic Expressions from Circuits

From the PDF: Write logic expressions of following logic circuits:

Circuit 1: Two Gates Combined

Logic Gate 1: (A AND B)

Logic Gate 2: (B OR C)

Logic Gate 3: XOR joining Gate 1 and Gate 2

Final Expression: (A AND B) XOR (B OR C)

Circuit 2: Complex Combination

Logic Gate 1: (A NAND C)

Logic Gate 2: (B AND C)

Logic Gate 3: (Gate 1) NOR A = ((A NAND C) NOR A)

Final Expression: ((A NAND C) NOR A) OR (B AND C)

Example 2: Truth Table from Logic Statement

From the PDF: Produce a logic circuit and truth table from logic statement: (A XOR C) OR (NOT C NAND B)

A	B	C	Stage 'P' (A XOR C)	Stage 'Q' (NOT C)	Stage 'R' (NOT C NAND B)	Output X (P OR R)
0	0	0	0	1	1	1
0	0	1	1	0	1	1
0	1	0	0	1	0	0
0	1	1	1	0	1	1
1	0	0	1	1	1	1
1	0	1	0	0	1	1
1	1	0	1	1	0	1
1	1	1	0	0	1	1

Explanation: The circuit has intermediate stages 'P', 'Q', 'R' before final output X. Each column is calculated step by step.

Example 3: Logic Expression from Truth Table

Case 1: Simple 2-input

A	B	X
0	0	0
0	1	0
1	0	1
1	1	0

Logic expression: A AND NOT B

How: Output is 1 only when A=1 AND B=0

Case 2: Another 2-input

A	B	X
0	0	0
0	1	1
1	0	0
1	1	1

Logic expression: (NOT A AND B) OR (A AND B)

How: Output is 1 when (A=0 AND B=1) OR (A=1 AND B=1). Simplifies to just B.

Example 4: Logic Expression from 3-input Truth Table

A	B	C	X
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Logic Expression: (NOT A AND B AND C) OR (A AND NOT B AND C) OR (A AND B AND NOT C) OR (A AND B AND C)

Method: For each row where X=1, write the AND combination of inputs (use NOT for 0 inputs). Then OR all these combinations together.

Example 5: Real-World Problem to Logic Circuit

Problem: System used 3 switches A, B, C; Combination of switches determines whether alarm, X, sounds: If switch A or switch B are in the ON position and if switch C is in OFF position then a signal to sound an alarm, X is produced.

Step-by-Step Conversion

If (A = 1 OR B = 1) → First part: A and B joined by OR gate
AND if (C = NOT 1) → Third part: C put through NOT gate
Output X = 1 when both conditions true
Join first part and third part with AND gate

Logic Expression & Circuit

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

Circuit: A and B go to OR gate, C goes to NOT gate, outputs of both go to AND gate.

Example 6: Manufacturing Process Control

Problem: Manufacturing process is controlled by built in logic circuit. A stop signal (X = 1) occurs when: either Volume, V > 1000 litres and Speed, S <= 15 m/s OR Temperature, T <= 750°C and Speed, S > 15 m/s.

INPUTS	BINARY VALUES	CONDITION IN PROCESS
V	1	Volume > 1000 litres
	0	Volume <= 1000 litres
T	1	Temperature > 750°C
	0	Temperature <= 750°C
S	1	Speed > 15 m/s
	0	Speed <= 15 m/s

Logic statement: X = 1 if (V = 1 AND S = NOT 1) OR (T = NOT 1 AND S = 1)

Boolean expression: X = (V AND NOT S) OR (NOT T AND S)

Activity 2: Circuit Design Challenge

Problem 1: System uses three inputs to a logic circuit. Alarm, X, sounds if input A represents ON and input B represents OFF; or if input B represents ON and input C represents OFF. Produce a logic circuit and truth table.

Your Tasks:

Write the logic expression
Draw the logic circuit (describe with text)
Complete the truth table for all 8 combinations

A	B	C
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Logic Expression:

Solution:

Logic Expression: (A AND NOT B) OR (B AND NOT C)
Logic Circuit:
- Input A goes to AND gate
- Input B goes to NOT gate, then to same AND gate → (A AND NOT B)
- Input B also goes to another AND gate
- Input C goes to NOT gate, then to second AND gate → (B AND NOT C)
- Outputs of both AND gates go to OR gate
- OR gate output is X

Truth Table:

A	B	C	X
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Check Your Understanding: Logic Circuits

1. What is a logic circuit? [2 marks]

Answer

[1 mark] A logic circuit is formed when logic gates are combined together to carry out a particular function
[1 mark] Several logic gates combined together form a logic circuit with inputs and outputs
[Additional] Output from a logic circuit is checked by producing a truth table

2. What are the three ways to represent a logic circuit? [3 marks]

Answer

[1 mark] Problem statement (description in words)
[1 mark] Logic expression (Boolean algebra)
[1 mark] Logic circuit diagram (gates and connections)
[Additional] Truth table (all input/output combinations)

3. How do you convert a problem statement to a logic expression? [4 marks]

Answer

[1 mark] Identify inputs and assign binary values (1 = true/ON, 0 = false/OFF)
[1 mark] Break down the problem into logical conditions
[1 mark] Convert "AND" to · (dot), "OR" to + (plus), "NOT" to ¬ or bar
[1 mark] Combine conditions with appropriate operators
[Example] "If A OR B are ON AND C is OFF" → (A + B) · ¬C

4. How do you create a truth table from a logic expression? [3 marks]

Answer

[1 mark] List all possible input combinations (\(2^n\) rows for n inputs)
[1 mark] Calculate intermediate values for each part of expression
[1 mark] Calculate final output column using the logic expression
[Example] For (A AND B) OR C, calculate A·B first, then (A·B)+C

5. What is the maximum number of inputs and outputs for AS Level logic circuits? [2 marks]

Answer

[1 mark] Maximum of three inputs
[1 mark] One output
[Additional] This means truth tables have maximum \(2^3 = 8\) rows

6. How would you write the logic expression for: "Output is 1 if A is 1 and B is 0, or if B is 1 and C is 0"? [3 marks]

Answer

[1 mark] First condition: A is 1 AND B is 0 → A AND NOT B
[1 mark] Second condition: B is 1 AND C is 0 → B AND NOT C
[1 mark] Combined with OR: (A AND NOT B) OR (B AND NOT C)
[Boolean] (A · B̅) + (B · C̅)

Key Takeaways

Logic gates are electronic circuits that process binary inputs (0/1) to produce binary outputs according to logical rules
Basic gates include NOT (inverter), AND (all inputs true), OR (at least one input true)
Combination gates include NAND (NOT AND), NOR (NOT OR), XOR (inputs different)
Truth tables show all possible input combinations and corresponding outputs; for n inputs, there are \(2^n\) rows
Boolean algebra uses notation: AND = · or ∧, OR = + or ∨, NOT = ¬ or bar over variable
Logic circuits combine gates to perform specific functions; AS Level limits to 3 inputs, 1 output
Conversion methods: Problem statement → Logic expression → Logic circuit → Truth table (and vice versa)
Real-world applications include security systems, manufacturing control, electronic devices
NAND and NOR gates are universal gates - any logic function can be built using only NAND or only NOR gates
XOR gate outputs 1 when inputs are different; used in parity checking and addition circuits
When creating truth tables, systematically list all combinations from 00...0 to 11...1
Intermediate values in complex circuits help verify correctness step by step

Question Bank

1. Identify and describe the functions of six types of logic gates. [6 marks]

Marking Scheme & Answer

[1 mark each] NOT: Inverts input (0→1, 1→0). Boolean: X = A̅
[1 mark each] AND: Output 1 only if ALL inputs are 1. Boolean: X = A·B
[1 mark each] OR: Output 1 if AT LEAST ONE input is 1. Boolean: X = A+B
[1 mark each] NAND: NOT AND - Output 0 only if ALL inputs are 1. Boolean: X = A·B̅
[1 mark each] NOR: NOT OR - Output 1 only if ALL inputs are 0. Boolean: X = A+B̅
[1 mark each] XOR: Exclusive OR - Output 1 if inputs are DIFFERENT. Boolean: X = A⊕B

2. Construct a truth table for the expression: (A AND NOT B) OR (NOT A AND B). [5 marks]

Marking Scheme & Answer

A	B	NOT A	NOT B	A AND NOT B	NOT A AND B	Output X
0	0	1	1	0	0	0
0	1	1	0	0	1	1
1	0	0	1	1	0	1
1	1	0	0	0	0	0

Note: This is actually an XOR gate! (A AND NOT B) OR (NOT A AND B) = A XOR B

3. Convert this problem statement to a logic expression: "A warning light turns on if temperature is high AND pressure is low, OR if temperature is high AND vibration is high." [4 marks]

Marking Scheme & Answer

[1 mark] Assign variables: T = temperature high (1 = high, 0 = normal)
[1 mark] P = pressure low (1 = low, 0 = normal)
[1 mark] V = vibration high (1 = high, 0 = normal)
[1 mark] X = warning light (1 = on, 0 = off)
[Expression] First condition: T AND P
[Expression] Second condition: T AND V
[Final] X = (T AND P) OR (T AND V)
[Boolean] X = (T·P) + (T·V) = T·(P + V) [simplified]

4. Draw a logic circuit for the expression: (A NAND B) AND (B OR C). [5 marks]

Marking Scheme & Answer

[1 mark] Inputs A and B go to a NAND gate
[1 mark] Inputs B and C go to an OR gate
[1 mark] Output of NAND gate is (A NAND B)
[1 mark] Output of OR gate is (B OR C)
[1 mark] These two outputs go to an AND gate
[1 mark] Output of AND gate is final output X
[Circuit description] A,B → NAND → AND → X, and B,C → OR → same AND gate

5. Explain how to derive a logic expression from a truth table. [4 marks]

Marking Scheme & Answer

[1 mark] Identify all rows where output is 1
[1 mark] For each such row, create an AND term including all inputs
[1 mark] For inputs that are 0 in that row, use NOT (e.g., if A=0, use NOT A)
[1 mark] Combine all these AND terms with OR operators
[Example] If output=1 when (A=0,B=1,C=1) and (A=1,B=0,C=1): Expression = (NOT A AND B AND C) OR (A AND NOT B AND C)

6. A wind turbine safety system uses three inputs: S (speed), T (temperature), W (wind velocity). Output X = 1 if: S <= 1000 rpm AND T > 80°C, OR S > 1000 rpm AND W > 120 kph, OR T <= 80°C AND W > 120 kph. Write the logic expression. [6 marks]

Marking Scheme & Answer

[1 mark] Convert conditions to binary: S=1 if >1000 rpm, 0 if <=1000 rpm
[1 mark] T=1 if >80°C, 0 if <=80°C
[1 mark] W=1 if >120 kph, 0 if <=120 kph
[1 mark] First condition: NOT S AND T
[1 mark] Second condition: S AND W
[1 mark] Third condition: NOT T AND W
[Final] X = (NOT S AND T) OR (S AND W) OR (NOT T AND W)
[Boolean] X = (S̅·T) + (S·W) + (T̅·W)

7. Complete this truth table for a 3-input circuit and write the logic expression: [7 marks]

Marking Scheme & Answer

A	B	C	X
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Logic Expression:

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

Method: Identify the 4 rows where X=1, create AND term for each, combine with OR.

8. Compare AND, OR, and XOR gates using their truth tables. [6 marks]

Marking Scheme & Answer

AND Gate:

Output 1 only when ALL inputs are 1
A=0,B=0 → X=0
A=0,B=1 → X=0
A=1,B=0 → X=0
A=1,B=1 → X=1
Boolean: X = A·B

OR Gate:

Output 1 when AT LEAST ONE input is 1
A=0,B=0 → X=0
A=0,B=1 → X=1
A=1,B=0 → X=1
A=1,B=1 → X=1
Boolean: X = A+B

XOR Gate:

Output 1 when inputs are DIFFERENT
A=0,B=0 → X=0
A=0,B=1 → X=1
A=1,B=0 → X=1
A=1,B=1 → X=0
Boolean: X = A⊕B

Key difference: AND requires all 1s, OR requires at least one 1, XOR requires different inputs.

9. Explain what NAND and NOR gates are and why they are called "universal gates". [5 marks]

Marking Scheme & Answer

[1 mark] NAND = NOT AND: Output is 0 only when ALL inputs are 1
[1 mark] NOR = NOT OR: Output is 1 only when ALL inputs are 0
[1 mark] Universal gates can be used to create ANY other logic gate
[1 mark] Using only NAND gates, you can make NOT, AND, OR gates
[1 mark] Using only NOR gates, you can also make NOT, AND, OR gates
[Additional] This is important in circuit design - simplifies manufacturing

10. Design a logic circuit for a car seatbelt warning system: Warning light (W) turns on if ignition is on (I=1) AND either driver's seat occupied (D=1) OR passenger's seat occupied (P=1) AND the corresponding seatbelt is not fastened (Bd=0 for driver, Bp=0 for passenger). [8 marks]

Marking Scheme & Answer

[1 mark] Inputs: I (ignition), D (driver seat), P (passenger seat), Bd (driver belt), Bp (passenger belt)
[1 mark] Output: W (warning light)
[1 mark] Driver warning condition: D AND NOT Bd (seat occupied AND belt not fastened)
[1 mark] Passenger warning condition: P AND NOT Bp
[1 mark] Combined seat condition: (D AND NOT Bd) OR (P AND NOT Bp)
[1 mark] Full condition requires ignition on: I AND [(D AND NOT Bd) OR (P AND NOT Bp)]
[2 marks] Logic expression: W = I · [(D · Bd̅) + (P · Bp̅)]
[Circuit description]
- D and NOT Bd go to AND gate → driver warning
- P and NOT Bp go to AND gate → passenger warning
- Outputs of these AND gates go to OR gate → seat warning
- Output of OR gate and I go to final AND gate → W