Chapter 2

Number System & Logic Gates

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 1

Outlines
 Section I:

 Number System

 Conversion

 Arithmetic Operations

 Complements

 Coding systems

 Section II:

 Logic gates

 Boolean Algebra

 Combinational Circuits

 Decoder & Encoder , Multiplexers

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 2
 Logic Gates
 Logic gates are the fundamental building blocks of all digital logic circuits.

 A gate is an electronic circuit that produces an output signal that is a simple Boolean operation on
its input signals.

 A logical operations on one or more binary inputs to produce a single binary output.

 We can group gates in to three:

 Basic gates: AND, OR, NOT

 Universal gates: NAND and NOR (can build any logic circuit)

 Special purpose gates : XOR and XNOR (parity checking, comparison).

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 3

 Cont’d…
 Each logic gates can be represented in three standard ways:

 Boolean Expression (Algebraic form):

 Each output signal is expressed as a Boolean function of its input signals.

 Truth Table (Tabular form):

 For each of the 2 power n possible combinations of input signals, the binary value of each of
the m output signals is listed.

 Logic Diagram (Symbolic circuit form)

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 4

 Basic Gates: AND Gate
 The same as the multiplication symbol of ordinary arithmetic

 AND Gate implements the AND function.

 1 if input A and B are both equal to 1 ,otherwise the output is 0.

 Boolean Expression: AB = C (Sometimes AB = C)

x x•y
y
Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 5

 Basic Gates: OR Gate
 The same as the addition symbol of ordinary arithmetic

 AND Gate implements the OR function.

 1 if input A or B or both equal to 1 , otherwise the output is 0.

 Boolean Expression: A+B = C

x x+y
y
Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 6

 Basic Gates: NOT Gate(Inverter)
 Inverts the logic sense of a binary signal.

 It produces the NOT or complement function.

 Output is the complement of input

 Logic expression: x = x

x x

Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 7

 Universal Gates(compound)
 They can be used to construct any other logic gate or logic circuit.

 The NAND gate and the NOR gate are called universal gates.

Why Are Universal Gates "Universal"?

A. Ability to Perform All Logic Operations: can be combined in various configurations to

perform the basic logic operations.

B. Flexibility in Circuit Design: Instead of requiring a variety of different gates a designer can use
just NAND gates or just NOR gates to build a circuit.

C. Simplified Implementation in Hardware: using only one type of gate can reduce the
complexity of the design and save space on a chip.

Click here to learn how to implement universal gates?

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 8
 Universal Gates: NAND Gate(not-AND)
 Complement of AND gate

 Output is the complement of AND function

 Boolean expression: Z = (A.B)= A+B

x y NAND
0 0 1
x x•y 0 1 1
y
1 0 1
1 1 0
Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 9

 Universal Gates: NOR Gate(not-OR)
 Complement of OR gate

 Output is the complement of OR function

 Boolean expression: Z = (A+B)= A.B

x x+y
y

Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 10

 XOR Gate(Exclusive-OR)
 Output is 1 when inputs are different

 Boolean expression: Z=A⊕B=A′B+AB′

x xÅ y
y xy+xy

Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 11

 XNOR Gate(Exclusive-OR)
 Output is 1 when inputs are same

 Boolean expression: Z=(A⊕B)′=AB+A′B′

x xÅ y xy+xy
y x y

Logic Diagram
Truth Table

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 12

Summary of Logic Gates

Gate Boolean Expression Truth Table Logic Diagram

AND Y = A·B Shows 1 when A and B = 1 “D” shape

OR Y=A+B Shows 1 when A or B = 1 Curved

NOT Y = A′ Inverts input Triangle + bubble

NAND Y = (A·B)′ Opposite of AND AND + bubble

NOR Y = (A+B)′ Opposite of OR OR + bubble

XOR Y = A ⊕B 1 when inputs differ XOR symbol

XNOR Y = (A⊕B)′ 1 when inputs same XOR + bubble

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 13

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 14
 Boolean Algebra
 Boolean Algebra is a branch of algebra that deals with binary variables (0 and 1) and logical
operations.
 Binary Variables: Only two values 0 (LOW / FALSE) and 1 (HIGH / TRUE)

 Basic Operations: AND, OR, NOT

 Boolean Algebra forms the foundation of all combinational and sequential logic circuits.

 A Boolean expression is a combination of Boolean variables and Boolean operators.

 A Boolean function has one or more input variables and produces a result that is based on these
input values. The result can have a value of 0 or 1.

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 15

 Cont’d…
• The purpose of Boolean algebra is to facilitate the analysis and design of digital circuits.

• It provides a convenient tool to:

 Express in algebraic form a truth table relationship between binary variables.

 Express in algebraic form the input-output relationship of logic diagrams.

 Find simpler circuits for the same function.

• The relationship between a function and its binary variables can be represented in a truth table.

• we need a list of the 2n combinations of the n binary variables.

• Example: If you have 3 inputs, each input can independently be 0 or 1, giving 2×2×2=8
combinations: (000),(001),(010),(011),(100),(101),(110),(111)

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 16

 Cont’d…
• Example: equation F= x + y ’ z.

 How do we know which operator to apply first?

 The rules of precedence for Boolean operators give NOT top priority, followed by AND, and
then OR.

 For function F, we would negate y first, then perform the AND of y’ and z, and lastly OR this
result with x.

x F
y
z

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 17

 Laws of Boolean Algebra Laws
• Laws 1 - 4 cover fundamental algebra properties, Law 5 – 6 address inversion and complement
• Law 7 deals with special cases of combining variables with 0 or 1
• Law 9 – 10 commonly used for simplifying Boolean expressions and minimizing logic gates

No. Law Name Expression (AND) Expression (OR)

1 Identity Law A·1 =A A+0=A
2 Commutative Law A·B=B·A A+B=B+A
3 Associative Law A · (B · C) = (A · B) · C A + (B + C) = (A + B) + C
4 Idempotent Law A·A=A A+A=A
5 Double Negative Law (A′)′ = A (A′)′ = A
6 Complementary Law A · A′ = 0 A + A′ = 1
7 Null Law A·0 =0 A+1=1
8 De Morgan’s Law (A · B)′ = A′ + B′ (A + B)′ = A′ · B′

9 Distributive Law A · (B + C) = (A · B) + (A · C) A + (B · C) = (A + B) · (A + C)

10 Absorption Law A · (A + B) = A A + (A · B) = A

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 18

 Boolean Analysis of Logic Circuits
Boolean Expression for a Logic Circuit

 To derive the Boolean expression for a given logic circuit, begin at the leftmost inputs and work
toward the final output, writing the expression for each gate.

 For example: for logic circuit given below determine the Boolean expression.

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 19

 Simplification using Boolean Algebra
 A simplified Boolean expression uses the fewest gates possible to implement a given expression.

 Example: Using Boolean algebra techniques, simplify this expression: AB + A (B + C) + B (B + C)

Solution:

 Step 1: Apply the distributive law to the second and third terms in the expression, as follows: AB + AB +
AC + BB + BC

 Step 2: Apply Idempotent law (BB = B) to the fourth term. AB + AB + AC + B + BC

 Step 3: Apply Idempotent law (AB + AB = AB) to the first two terms. AB + AC + B + BC

 Step 4: Apply Absorption law (B + BC = B) to the last two terms. AB + AC + B

 Step 5: Absorption law (AB + B = B) to the first and third terms.

 = B+AC at this point the expression is simplified as much as possible.

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 20

Cont’d……
(a) Original Boolean expression and Logic Diagram
(b) Simplified Boolean expression and Logic Diagram

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 21

Simplification using Boolean Algebra

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 22

Simplification using Boolean Algebra

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 23

 Combinational Circuit
 A combinational circuit is a type of digital circuit in which the output depends only on the present input
values.

 Which used to build circuits that contain basic Boolean operators, inputs, and outputs.

Example:
 Adders (Half Adder, Full Adder)

 Multiplexers (MUX), Demultiplexers (DEMUX)

 Encoders, Decoders

• Block diagram

• Input Variables → Represent binary values (0 or 1)

• Logic Circuit → Built using logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR)

• Output Variables → Determined from input combinations

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 24
Characteristics of Combinational Circuit

Feature Description

Memory No memory element present

Output Depends only on present inputs

Time Dependency Output changes immediately when input changes

Implementation Uses logic gates and Boolean algebra

Truth table → Boolean expression → Logic gate

Design Method
implementation

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 25

 Advantage and Limitations of Combinational Circuit
 Advantages of Combinational Circuits

 Fast operation (no clock required)

 Simple design

 Easy to analyze using Boolean algebra

 Less complex than sequential circuits

 Limitations

 No memory (cannot store previous states)

 Sensitive to input changes

 Not suitable for time-dependent operations (e.g., counters, registers)

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 26

Types of Common Combinational Circuit

Circuit Type Function

Half adder Performs addition of 2 single-bit numbers.

Full adder Performs addition of 3 bits (including carry).

Multiplexer (MUX) Selects one input from many and routes it to output.

Demultiplexer
Distributes single input to multiple outputs.
(DEMUX)

Encoder Converts 2ⁿ inputs into n-bit binary code.

Decoder Converts n-bit binary input into 2ⁿ unique outputs.

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 27

 Combinational Circuit: Half adder
 Half adder is a combinational circuit that is used to add two 1-bit inputs to generate two outputs
sum and carry Truth Table A B Sum (XOR) Carry (AND)
0 0 0 0
 Inputs: A, B 0 1 1 0
1 0 1 0
• Outputs:
1 1 0 1
• Sum (S) = A ⊕ B (XOR gate)

• Carry (C) = A · B (AND gate)

• To implement half adder,

• we require one XOR gate and one AND gate.

Logic Diagram

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 28

 Combinational Circuit: Full adder
 Half adder is a combinational circuit that is used to add three 1-bit inputs to generate two outputs
sum and carry

 Inputs: A, B, Cin (Carry in)

• Outputs:

• Sum (S) = A ⊕ B ⊕ Cin

• Carry (Cout) = A·B + B·Cin + A·Cin

• They are used in the ALUs (Arithmetic Logic Units),Binary Additions, Address decoding,
Counters and Registers, Data Encryption and Decryption and Digital Signal Processing.

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 29

 Combinational Circuit: Full adder
 Half adder Truth table

A B Cin Sum Cout

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1
06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 30
 Combinational Circuit: Multiplexer
 MUX, is a combination logic circuit that is designed to accept multiple input signals and transfer
only one of them through the output line.

 For N input lines, log2(N) selection lines are required, or equivalently, for 2n input lines, n

selection lines are needed.

 The multiplexer is also called data selector as it selects one from several

 The multiplexer acts like an electronic switch that selects one from different

• Types of Mux

• 2x1 Mux

• 4x1 Mux

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 31

 Combinational Circuit: Multiplexer
 The 2×1 multiplexer is basic two input multiplexer which has two data input lines designated as

I0 and I1, one data select line denoted by S and one output line denoted by Y.

 The output of the 2x1 Mux will depend on the selection line S0,

 When S0 is 0(low), the I0​is selected

 when S0 is 1(High), I1 is selected

 Logical expression: Y=S0​.I0​+ S0​.I1

Block Diagram

 Source ​

Select Line (S) Output (Y)

0 I0
1 I1

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 32

 Combinational Circuit: Multiplexer
 The 4×1 Multiplexer has four data inputs I3, I2, I1 & I0, two selection lines s1 & s0 and one output

Y. Truth Table
Selection Lines Output
• When S1S0=00, the input I0 is selected. S1 S0 Y
0 0 I0
• When S1S0=01, the input I1 is selected.
0 1 I1

• When S1S0=10, the input I2 is selected. 1 0 I2

1 1 I3
• When S1S0=11, the input I3 is selected.

 Y = S1′S0′I0 + S1S0′I1 + S1S0′I2 + S1S0I3

Block Diagram

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 33

 Combinational Circuit: Multiplexer
 Circuit diagram for 4x1 MUX: We can implement Y = S1′S0′I0 + S1S0′I1 + S1S0′I2 + S1S0I3 using

Inverters, AND gates & OR gate.

 Source

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 34

 Combinational Circuit: Encoder
 An encoder is a digital circuit that converts a set of binary inputs into a unique binary code that
represents the position of the input.

 Encoders are widely used in digital systems to convert parallel inputs into serial codes(Code
conversion).

• Function: Converts 2ⁿ inputs into n-bit binary output.

• Only one input line should be active at a time.

• Example: 8-to-3 Encoder (Octal to binary encoder)

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 35

Combinational Circuit: Encoder

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 36

 Combinational Circuit: Encoder
 Truth Table for 8 to 3 encoder

INPUTS OUTPUTS
Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 A2 A1 A0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 37

 Reading Assignment
 Demultiplexers (DEMUX)

 Decoders

 Sequential Digital Circuits

 Types of Flip-flops

06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 38

 Thank You!!!
?
06/05/2026 Prepared by Muluken Zemed (MSc.) | 2025 39