Computer Science | Logic

Welcome to the World of Logic!

Hello future Computer Scientist! Don't worry if the word "Logic" sounds intimidating. In Computer Science, logic is simply the rules computers use to make decisions. It’s the absolute foundation of how every circuit, processor, and piece of software works.

Think of logic as the computer's way of saying: "If this condition is true AND that condition is true, then I will run the program."

In this chapter, we will break down these rules using simple components called Logic Gates and visualize them using Truth Tables. By the end, you'll understand the secret language of 1s and 0s!

1. The Basics: Boolean Logic (True or False)

All digital logic is based on the work of mathematician George Boole, which is why we call it Boolean Logic. Computers operate only on two possibilities:

• True (represented by the number 1 or ON)
• False (represented by the number 0 or OFF)

The Concept of Input and Output

Every logic operation takes one or more inputs (0s or 1s) and produces exactly one output (a single 0 or 1).

Analogy: Think of a light switch.

• Input (Switch): ON (1) or OFF (0).
• Output (Light): ON (1) or OFF (0).

Quick Review: Everything is a 1 or a 0. These are the only possible states.

2. Logic Gates – The Building Blocks of Circuits

A Logic Gate is a tiny electronic circuit (made up of transistors) that performs a basic Boolean operation. Every complex function in a computer is built by connecting thousands of these simple gates together.

2.1 The NOT Gate (The Inverter)

The NOT gate is the simplest gate. It only has one input and one output.

• Rule: It inverts or reverses the input. If you put in a 1, you get a 0, and vice versa.
• Key Term: This is often called an Inverter.
• Symbol Tip: The symbol for NOT is a triangle with a small circle (the "bubble") on the output line. The bubble always means "invert" or "NOT."

Analogy: A NOT gate is like saying "No." If the answer is "Yes" (1), the output is "No" (0).

Truth Table for NOT

Input (A)	Output (X)
0	1
1	0

2.2 The AND Gate (The Requirement Gate)

The AND gate requires two or more inputs, but we typically look at two inputs (A and B).

• Rule: The output (X) is 1 (True) only if ALL inputs are 1 (True).
• If even one input is 0, the output is 0.
• Mnemonic: Think of an AND gate as a high standard. It needs A AND B to be perfect (1) to give you a result of 1.

Analogy: To open a high-security vault, you need Key A AND Key B to be inserted simultaneously. If one key is missing (0), the vault stays locked (0).

Truth Table for AND

Input (A)	Input (B)	Output (X)
0	0	0
0	1	0
1	0	0
1	1	1

2.3 The OR Gate (The Flexible Gate)

The OR gate also takes two or more inputs (A and B).

• Rule: The output (X) is 1 (True) if ANY input is 1 (True).
• The output is 0 only if ALL inputs are 0.
• Mnemonic: Think of an OR gate as very flexible. You can bring A OR B (or both!) to succeed.

Analogy: To enter the club, you need a Student ID OR a Passport. If you have either one (1), you get in (1). You only fail (0) if you have neither.

Truth Table for OR

Input (A)	Input (B)	Output (X)
0	0	0
0	1	1
1	0	1
1	1	1

Key Takeaway for Section 2: AND requires all inputs to be 1. OR requires at least one input to be 1. NOT flips the input.

3. Derived Logic Gates

By combining the basic gates (NOT, AND, OR), engineers created more specialized gates that are very common in computer circuits.

3.1 The XOR Gate (Exclusive OR)

XOR stands for Exclusive OR. This gate is used when you want a decision, but not both options.

• Rule: The output (X) is 1 (True) if the inputs are DIFFERENT.
• If the inputs are the same (both 0 or both 1), the output is 0.
• Purpose: XOR is vital in arithmetic circuits (like half-adders) and error checking.

Analogy: At a restaurant, you get Soup OR Salad, but NOT both. If you choose both (1, 1), you break the rule and the output is 0.

Truth Table for XOR

Input (A)	Input (B)	Output (X)
0	0	0
0	1	1
1	0	1
1	1	0

3.2 The NAND Gate (NOT AND)

A NAND gate is simply an AND gate followed immediately by a NOT gate.

• Rule: The output is 1 unless ALL inputs are 1. It is the exact opposite of AND.
• Symbol Tip: It looks like an AND symbol with the small "NOT bubble" on the output.
• Did You Know? NAND is sometimes called a "Universal Gate" because you can build ANY other gate (AND, OR, NOT, XOR) just by combining NAND gates!

3.3 The NOR Gate (NOT OR)

A NOR gate is an OR gate followed immediately by a NOT gate.

• Rule: The output is 1 only when ALL inputs are 0. It is the exact opposite of OR.
• Symbol Tip: It looks like an OR symbol with the small "NOT bubble" on the output.

Truth Tables for NAND and NOR (The Opposites)

Look how they contrast with their parent gates (AND and OR):

Inputs (A, B)	AND	NAND (NOT AND)	OR	NOR (NOT OR)
0, 0	0	1	0	1
0, 1	0	1	1	0
1, 0	0	1	1	0
1, 1	1	0	1	0

Common Mistake to Avoid: Students often mix up XOR and OR. Remember, OR allows (1, 1), but XOR specifically excludes (1, 1).

4. Truth Tables – Mapping Logic

A Truth Table is a mathematical table used to list all possible input combinations and the corresponding output for a given logic circuit or logic gate.

4.1 Calculating the Number of Rows

The number of possible input combinations (and thus the number of rows in your table) depends on the number of inputs (\(n\)).

The calculation is: $$ \text{Number of Rows} = 2^n $$

For example:

• If \(n=1\) input (like NOT), you need \(2^1 = 2\) rows (0 and 1).
• If \(n=2\) inputs (like AND, OR), you need \(2^2 = 4\) rows.
• If \(n=3\) inputs (A, B, C), you need \(2^3 = 8\) rows.

4.2 Step-by-Step: How to Fill the Input Columns

When creating a truth table, it’s crucial to list the inputs systematically so you don't miss any combination.

Example: Creating a 2-Input Table (A and B):

1. Column A: Divide the total rows (4) by 2. Fill the first half (2 rows) with 0s, and the second half (2 rows) with 1s.
   (0, 0, 1, 1)
2. Column B: Divide the previous block (2) by 2. Fill alternating 0s and 1s.
   (0, 1, 0, 1)

This systematic method (counting in binary) ensures you cover every single possibility from 00 up to 11.

4.3 Applying Logic to Complex Circuits

In IGCSE Computer Science, you might be asked to find the output for a circuit that combines several gates.

Step-by-Step Example: Finding the Output (X) for (A AND B) OR C

This circuit has 3 inputs (A, B, C), so we need 8 rows (\(2^3\)). To solve this, we work sequentially (one gate at a time) from left to right.

1. Setup: Create the 8 rows for A, B, C and an intermediate column for the first operation: (A AND B).

   A	B	C	Intermediate (A AND B)	Output X
   0	0	0
   0	0	1
   0	1	0
   0	1	1
   1	0	0
   1	0	1
   1	1	0
   1	1	1

2. Solve the Intermediate Column (A AND B): Fill this column by looking only at A and B. Remember: AND only gives 1 if both A and B are 1.
3. Solve the Final Output X ((A AND B) OR C): Now, treat the "Intermediate" column and input C as the two inputs for the final OR gate. Remember: OR gives 1 if either input is 1.

A	B	C	Intermediate (A AND B)	Output X (Int. OR C)
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

Phew! Don't worry if this seems like a lot of steps. The trick is always to break the complex problem into smaller, individual gate operations. If you master AND, OR, and NOT, you can solve any circuit!

Key Takeaway for Section 4: Truth tables map every input possibility (\(2^n\)) to the final output. Always solve step-by-step using intermediate columns.