Boolean Algebra and

Logic Gates

Aziz Qaroush
Basic Definitions
 Boolean Algebra defined with a set of elements, a set of
operators and a number of axioms (‫ )البديهيات‬or postulates
(‫)المسلمات‬.
 A set if a collection of objects having a common property

Elements
x is an element of set S

y is not an element of set S

* Binary operator and
result c of operation on
a and b is an element of
set S
Basic Definitions
1. Closure: A set S is closed with respect to a binary operator
if, for every pair of elements of S, the binary operator
specifies a rule for obtaining a unique element of S.
2. Associative law: (x*y)*z=x*(y*z) for all z, y, z ЄS.
3. Commutative law: x*y=y*x
4. Identity Element: e*x=x*e=x
5. Inverse: A set S having the identity element e with respect to
binary operator * is said to have an inverse whenever, for
every xЄS, there exists an element y such that x*y=e
6. Distributive law: If * and . are binary operators on S, * is said
to be distributive over . whenever x*(y.z)=(x*y).(x*z)
Axiomatic Definition of Boolean Algebra
Boolean algebra is an algebraic structure defined by a set of
elements, B, together with binary operators (+) and (.)
1. (a) The structure is closed with respect to +
(b) The structure is closed with respect to .
2. (a) The element 0 is an identity element with respect to +
(b) The element 1 is an identity element with respect to .
3. (a) The structure is commutative with respect to +
(b) The structure is commutative with respect to .
4. (a) The operator . is distributive over +
(b) The operator + is distributive over .
5. For every element xЄB, there exists an element x’ЄB called the
complement of x such that
(a) x+x’=1 and
(b) x.x’=0
6. There exist at least two elements x, yЄB such that x≠y
Two-valued Boolean Algebra

Defined on a set of two elements

x y x.y x y x+y x x’
0 0 0 0 0 0
0 1
0 1 0 0 1 1
1 0 0 1 0 1 1 0
1 1 1 1 1 1
Two-valued Boolean Algebra

x y z y+z x.(y+z) x.y x.z (x.y)+(x.z)

0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
Duality Principle
 The dual of a Boolean expression can be obtained by:
 Interchanging AND (·) and OR (+) operators
 Interchanging 0's and 1's

 Example: the dual of 𝑥(𝑦 + 𝑧′) is 𝑥 + 𝑦𝑧′

 The complement operator does not change

 The properties of Boolean algebra appear in dual pairs

 If a property is proven to be true then its dual is also true

Property Dual Property

Identity 𝑥+0=𝑥 𝑥·1=𝑥
Complement 𝑥 + 𝑥′ = 1 𝑥 · 𝑥′ = 0
Distributive 𝑥 (𝑦 + 𝑧) = 𝑥𝑦 + 𝑥𝑧 𝑥 + 𝑦𝑧 = (𝑥 + 𝑦)(𝑥 + 𝑧)
Basic Theorems
Theorem 1(a)

but

thus

Distributing + over . gives in general

Theorem 1(b)

It can be proved by duality of Theorem 1(a)

Theorem 2(a)
Theorem 2(b)

By duality of Theorem 2(a)

Theorem 3

and

Both equations define the complement

The complement of is and is also

Since the complement is unique

Theorem 6(a) Absorption
Theorem 6(b) Absorption

By duality of Theorem 6(a)

Theorem 6(a) Absorption

Proof by truth table

x y xy x+xy
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1
DeMorgan's Theorem
 (𝑥 + 𝑦)′ = 𝑥′ 𝑦′ Can be verified
 (𝑥 𝑦)′ = 𝑥′ + 𝑦′ Using a Truth Table

x y x' y' x+y (x+y)' x'y' x y (x y)' x'+ y'

0 0 1 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0 1 1
1 0 0 1 1 0 0 0 1 1
1 1 0 0 1 0 0 1 0 0
Identical Identical

 Generalized DeMorgan's Theorem:

 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 ′ = 𝑥1′ ∙ 𝑥2′ ∙ ⋯ ∙ 𝑥𝑛′
 𝑥1 ∙ 𝑥2 ∙ ⋯ ∙ 𝑥𝑛 ′
= 𝑥1′ + 𝑥2′ + ⋯ + 𝑥𝑛′
Boolean Functions
 Boolean functions are described by expressions that consist of:
 Boolean variables, such as: 𝑥, 𝑦, etc.
 Boolean constants: 0 and 1
 Boolean operators: AND (·), OR (+), NOT (')
 Parentheses, which can be nested
 Example: 𝑓 = 𝑥 𝑦 + 𝑤 ′ 𝑧
 The dot operator is implicit and need not be written
 Operator precedence: to avoid ambiguity in expressions
 Expressions within parentheses should be evaluated first
 The NOT (') operator should be evaluated second
 The AND (·) operator should be evaluated third
 The OR (+) operator should be evaluated last
Truth Table
 A truth table can represent a Boolean function
 List all possible combinations of 0's and 1's assigned to variables
 If n variables then 2n rows
Boolean functions
Transform the algebraic equation of F1 to a circuit
diagram using logic gates

FIGURE 2.1 Gate implementation of F1 = x + y’z

Boolean functions
Transform the algebraic equation of F2 to a circuit
diagram using logic gates
Algebraic manipulation (‫)معالجة‬
Literal: A single variable within a term that may be
complemented or not.

Use Boolean Algebra to simplify Boolean functions to produce

simpler circuits (minimum number of literals)

Example 1

Example 2

Example 3

Example 5

By duality of Consensus Theorem

Consensus Theorem
 Prove that: 𝑥𝑦 + 𝑥′𝑧 + 𝑦𝑧 = 𝑥𝑦 + 𝑥′𝑧 (consensus theorem)
 Proof: 𝑥𝑦 + 𝑥 ′ 𝑧 + 𝑦𝑧
= 𝑥𝑦 + 𝑥′𝑧 + 1 · 𝑦𝑧 𝑦𝑧 = 1 · 𝑦𝑧
= 𝑥𝑦 + 𝑥′𝑧 + (𝑥 + 𝑥′)𝑦𝑧 1 = (𝑥 + 𝑥′)
= 𝑥𝑦 + 𝑥′𝑧 + 𝑥𝑦𝑧 + 𝑥′𝑦𝑧 Distributive · over +
= 𝑥𝑦 + 𝑥𝑦𝑧 + 𝑥′𝑧 + 𝑥′𝑦𝑧 Associative commutative +
= 𝑥𝑦 · 1 + 𝑥𝑦𝑧 + 𝑥′𝑧 · 1 + 𝑥′𝑧𝑦 𝑥𝑦 = 𝑥𝑦 · 1, 𝑥 ′ 𝑦𝑧 = 𝑥 ′ 𝑧𝑦
= 𝑥𝑦(1 + 𝑧) + 𝑥′𝑧(1 + 𝑦) Distributive · over +
= 𝑥𝑦 · 1 + 𝑥′𝑧 · 1 1 + 𝑧 = 1, 1 + 𝑦 = 1
= 𝑥𝑦 + 𝑥′𝑧 𝑥𝑦 · 1 = 𝑥𝑦, 𝑥′𝑧 · 1 = 𝑥′𝑧
Boolean functions
Compare the two implementations

FIGURE 2.2 Implementation of Boolean function F2 with gates

Complementing Boolean Functions
 What is the complement of 𝑓 = 𝑥′𝑦𝑧′ + 𝑥𝑦′𝑧′ ?

 Use DeMorgan's Theorem:

 Complement each variable and constant

 Interchange AND and OR operators

 So, what is the complement of 𝑓 = 𝑥 ′ 𝑦𝑧 ′ + 𝑥𝑦 ′ 𝑧 ′ ?

Answer: 𝑓′ = (𝑥 + 𝑦 ′ + 𝑧)(𝑥 ′ + 𝑦 + 𝑧)

 Example 2: Complement 𝑔 = (𝑎′ + 𝑏𝑐)𝑑′ + 𝑒

 Answer: 𝑔′ = (𝑎(𝑏′ + 𝑐′) + 𝑑)𝑒′

Complement of a function
Find the complement of the following functions

= 𝒙′ + 𝒚𝒛′ + 𝒚′ 𝒛
Complement of a function
Find the complement of the following functions by taking
their duals and complementing each literal

The dual
Complement each literal

The dual

Complement each literal

Simplification Example
Simplification Example
Canonical Forms
 Minterms and Maxterms

 Sum-of-Minterm (SOM) Canonical Form

 Product-of-Maxterm (POM) Canonical Form

 Representation of Complements of Functions

 Conversions between Representations

Combinational Circuit
 A combinational circuit is a block of logic gates having:

𝑛 inputs: 𝑥1, 𝑥2, … , 𝑥𝑛

𝑚 outputs: 𝑓1, 𝑓2, … , 𝑓𝑚

 Each output is a function of the input variables

 Each output is determined from present combination of inputs

 Combination circuit performs operation specified by logic gates

Combinational
𝑛 inputs 𝑚 outputs



Circuit
Example of a Simple Combinational Circuit
𝑥
𝑦 𝑓

 The above circuit has:

 Three inputs: 𝑥, 𝑦, and 𝑧
 Two outputs: 𝑓 and 𝑔

 What are the logic expressions of 𝑓 and 𝑔 ?

 Answer: 𝑓 = 𝑥𝑦 + 𝑧′
𝑔 = 𝑥𝑦 + 𝑦𝑧
From Truth Tables to Gate Implementation
 Given the truth table of a Boolean function 𝑓, how do we
implement the truth table using logic gates?

Truth Table
x y z f
0 0 0 0
What is the logic expression of 𝑓?
0 0 1 0
0 1 0 1
0 1 1 1 What is the gate implementation of 𝑓?
1 0 0 0
1 0 1 1 To answer these questions, we need
1 1 0 0
to define Minterms and Maxterms
1 1 1 1
Minterms and Maxterms
 Minterms are AND terms with every variable present in either
true or complement form
 Maxterms are OR terms with every variable present in either
true or complement form
Minterms and Maxterms for 2 variables 𝑥 and 𝑦
x y index Minterm Maxterm
0 0 0 𝑚0 = 𝑥′𝑦′ 𝑀0 = 𝑥 + 𝑦
0 1 1 𝑚1 = 𝑥′𝑦 𝑀1 = 𝑥 + 𝑦′
1 0 2 𝑚2 = 𝑥𝑦′ 𝑀2 = 𝑥′ + 𝑦
1 1 3 𝑚3 = 𝑥𝑦 𝑀3 = 𝑥′ + 𝑦′

 For n variables, there are 2n Minterms and Maxterms

Minterms and Maxterms for 3 Variables
x y z index Minterm Maxterm
0 0 0 0 𝑚0 = 𝑥 ′ 𝑦 ′ 𝑧′ 𝑀0 = 𝑥 + 𝑦 + 𝑧
0 0 1 1 𝑚1 = 𝑥 ′ 𝑦 ′ 𝑧 𝑀1 = 𝑥 + 𝑦 + 𝑧′
0 1 0 2 𝑚2 = 𝑥′𝑦𝑧′ 𝑀2 = 𝑥 + 𝑦′ + 𝑧
0 1 1 3 𝑚3 = 𝑥′𝑦𝑧 𝑀3 = 𝑥 + 𝑦 ′ + 𝑧′
1 0 0 4 𝑚4 = 𝑥𝑦 ′ 𝑧′ 𝑀4 = 𝑥′ + 𝑦 + 𝑧
1 0 1 5 𝑚5 = 𝑥𝑦 ′ 𝑧 𝑀5 = 𝑥′ + 𝑦 + 𝑧′
1 1 0 6 𝑚6 = 𝑥𝑦𝑧′ 𝑀6 = 𝑥′ + 𝑦′ + 𝑧
1 1 1 7 𝑚7 = 𝑥𝑦𝑧 𝑀7 = 𝑥′ + 𝑦 ′ + 𝑧′

Maxterm 𝑀𝑖 is the complement of Minterm 𝑚𝑖

𝑀𝑖 = 𝑚𝑖′ and 𝑚𝑖 = 𝑀𝑖′
Purpose of the Index
 Minterms and Maxterms are designated with an index

 The index for the Minterm or Maxterm, expressed as a

binary number, is used to determine whether the variable
is shown in the true or complemented form

 For Minterms:
 ‘1’ means the variable is Not Complemented

 ‘0’ means the variable is Complemented

 For Maxterms:
 ‘0’ means the variable is Not Complemented

 ‘1’ means the variable is Complemented

Sum-Of-Minterms (SOM) Canonical Form
Truth Table
x y z f Minterm
Sum of Minterm entries
0 0 0 0
that evaluate to ‘1’
0 0 1 0
0 1 0 1 𝑚2 = 𝑥′𝑦𝑧′
Focus on the ‘1’ entries
0 1 1 1 𝑚3 = 𝑥′𝑦𝑧
1 0 0 0
𝑓 = 𝑚2 + 𝑚3 + 𝑚5 + 𝑚7
1 0 1 1 𝑚5 = 𝑥𝑦′𝑧
1 1 0 0
𝑓 = ෍ 2, 3, 5, 7
1 1 1 1 𝑚7 = 𝑥𝑦𝑧

𝑓 = 𝑥 ′ 𝑦𝑧 ′ + 𝑥 ′ 𝑦𝑧 + 𝑥𝑦 ′ 𝑧 + 𝑥𝑦𝑧
Examples of Sum-Of-Minterms

 𝑓 𝑎, 𝑏, 𝑐, 𝑑 = σ(2, 3, 6, 10, 11)

 𝑓 𝑎, 𝑏, 𝑐, 𝑑 = 𝑚2 + 𝑚3 + 𝑚6 + 𝑚10 + 𝑚11

 𝑓 𝑎, 𝑏, 𝑐, 𝑑 = 𝑎′ 𝑏 ′ 𝑐𝑑′ + 𝑎′ 𝑏 ′ 𝑐𝑑 + 𝑎′𝑏𝑐𝑑′ + 𝑎𝑏′𝑐𝑑′ + 𝑎𝑏′𝑐𝑑

 𝑔 𝑎, 𝑏, 𝑐, 𝑑 = σ(0, 1, 12, 15)

 𝑔 𝑎, 𝑏, 𝑐, 𝑑 = 𝑚0 + 𝑚1 + 𝑚12 + 𝑚15

 𝑔 𝑎, 𝑏, 𝑐, 𝑑 = 𝑎′ 𝑏 ′ 𝑐′𝑑′ + 𝑎′ 𝑏 ′ 𝑐′𝑑 + 𝑎𝑏𝑐′𝑑′ + 𝑎𝑏𝑐𝑑

Product-Of-Maxterms (POM) Canonical Form
Truth Table
x y z f Maxterm
Product of Maxterm entries
0 0 0 0 𝑀0 = 𝑥 + 𝑦 + 𝑧
that evaluate to ‘0’
0 0 1 0 𝑀1 = 𝑥 + 𝑦 + 𝑧′
0 1 0 1
Focus on the ‘0’ entries
0 1 1 1
1 0 0 0 𝑀4 = 𝑥′ + 𝑦 + 𝑧
𝑓 = 𝑀0 · 𝑀1 · 𝑀4 · 𝑀6
1 0 1 1
1 1 0 0 𝑀6 = 𝑥′ + 𝑦′ + 𝑧
𝑓 = ෑ 0, 1, 4, 6
1 1 1 1

𝑓 = (𝑥 + 𝑦 + 𝑧)(𝑥 + 𝑦 + 𝑧 ′ )(𝑥 ′ + 𝑦 + 𝑧)(𝑥 ′ + 𝑦 ′ + 𝑧)

Examples of Product-Of-Maxterms
 𝑓 𝑎, 𝑏, 𝑐, 𝑑 = ς(1, 3, 11)

 𝑓(𝑎, 𝑏, 𝑐, 𝑑) = 𝑀1 ∙ 𝑀3 ∙ 𝑀11

 𝑓(𝑎, 𝑏, 𝑐, 𝑑) = 𝑎 + 𝑏 + 𝑐 + 𝑑′ 𝑎 + 𝑏 + 𝑐 ′ + 𝑑′ (𝑎′ + 𝑏 + 𝑐 ′ + 𝑑 ′ )

 𝑔 𝑎, 𝑏, 𝑐, 𝑑 = ς(0, 5, 13)

 𝑔(𝑎, 𝑏, 𝑐, 𝑑) = 𝑀0 ∙ 𝑀5 ∙ 𝑀13

 𝑓(𝑎, 𝑏, 𝑐, 𝑑) = 𝑎 + 𝑏 + 𝑐 + 𝑑 𝑎 + 𝑏 ′ + 𝑐 + 𝑑 ′ (𝑎′ + 𝑏′ + 𝑐 + 𝑑′ )
Conversions between Canonical Forms
 The same Boolean function 𝑓 can be expressed in two ways:
 Sum-of-Minterms 𝑓 = 𝑚0 + 𝑚2 + 𝑚3 + 𝑚5 + 𝑚7 = σ(0, 2, 3, 5, 7)
 Product-of-Maxterms 𝑓 = 𝑀1 ∙ 𝑀4 ∙ 𝑀6 = ς(1, 4, 6)

Truth Table
x y z f Minterms Maxterms
0 0 0 1 𝑚0 = 𝑥 ′ 𝑦′𝑧′
0 0 1 0 𝑀1 = 𝑥 + 𝑦 + 𝑧′ To convert from one canonical
0 1 0 1 𝑚2 = 𝑥 ′ 𝑦𝑧′ form to another, interchange
0 1 1 1 𝑚3 = 𝑥 ′ 𝑦𝑧
the symbols  and  and list
1 0 0 0 𝑀4 = 𝑥′ + 𝑦 + 𝑧
those numbers missing from
1 0 1 1 𝑚5 = 𝑥𝑦′𝑧
1 1 0 0 𝑀6 = 𝑥′ + 𝑦′ + 𝑧 the original form.
1 1 1 1 𝑚7 = 𝑥𝑦𝑧
Function Complement
Truth Table Given a Boolean function 𝑓

x y z f f' 𝑓(𝑥, 𝑦, 𝑧) = ෍ 0, 2, 3, 5, 7 = ෑ(1, 4, 6)

0 0 0 1 0
0 0 1 0 1 Then, the complement 𝑓′ of function 𝑓
0 1 0 1 0
𝑓′(𝑥, 𝑦, 𝑧) = ෑ 0, 2, 3, 5, 7 = ෍(1, 4, 6)
0 1 1 1 0
1 0 0 0 1
The complement of a function expressed by a
1 0 1 1 0
Sum of Minterms is the Product of Maxterms
1 1 0 0 1
with the same indices. Interchange the symbols
1 1 1 1 0
 and , but keep the same list of indices.
Algebraic Conversion to Sum-of-Minterms
 Expand all terms first to explicitly list all minterms
 AND any term missing a variable v with (v + v)
 Example 1: f = x + x y (2 variables)
f = x (y + y) + x y
f=xy+xy+xy
f = m3 + m2 + m0 = ∑(0, 2, 3)
 Example 2: g = a + b c (3 variables)
g = a (b + b)(c + c) + (a + a) b c
g=abc+abc+abc+abc+abc+abc
g=abc+abc+abc+abc+abc
g = m1 + m4 + m5 + m6 + m7 = ∑ (1, 4, 5, 6, 7)
Algebraic Conversion to Product-of-Maxterms
 Expand all terms first to explicitly list all maxterms
 OR any term missing a variable v with v · v
 Example 1: f = x + x y (2 variables)
Apply 2nd distributive law:
f = (x + x) (x + y) = 1 · (x + y) = (x + y) = M1
 Example 2: g = a c + b c + a b (3 variables)
g = (a c + b c + a) (a c + b c + b) (distributive)
g = (c + b c + a) (a c + c + b) (x + x y = x + y)
g = (c + b + a) (a + c + b) (x + x y = x + y)
g = (a + b + c) (a + b + c) = M5 . M2 = ∏ (2, 5)
Summary of Minterms and Maxterms
 There are 2n Minterms and Maxterms for Boolean functions with
n variables, indexed from 0 to 2n – 1

 Minterms correspond to the 1-entries of the function

 Maxterms correspond to the 0-entries of the function

 Any Boolean function can be expressed as a Sum-of-Minterms

and as a Product-of-Maxterms

 For a Boolean function, given the list of Minterm indices one can
determine the list of Maxterms indices (and vice versa)

 The complement of a Sum-of-Minterms is a Product-of-Maxterms

with the same indices (and vice versa)
Sum-of-Products and Products-of-Sums
 Canonical forms contain a larger number of literals
 Because the Minterms (and Maxterms) must contain, by definition, all
the variables either complemented or not

 Another way to express Boolean functions is in standard form

 Two standard forms: Sum-of-Products and Product-of -Sums
 Sum of Products (SOP)
 Boolean expression is the ORing (sum) of AND terms (products)
 Examples: 𝑓1 = 𝑥𝑦′ + 𝑥𝑧 𝑓2 = 𝑦 + 𝑥𝑦′𝑧

 Products of Sums (POS)

 Boolean expression is the ANDing (product) of OR terms (sums)
 Examples: 𝑓3 = (𝑥 + 𝑧)(𝑥′ + 𝑦′) 𝑓4 = 𝑥(𝑥′ + 𝑦′ + 𝑧)
Standard Forms
47

 Sum of Products (SOP)

AB(C  C )
 AB(1)
F  ABC  ABC  ABC  ABC
 AB
AC ( B  B)
 AC
BC ( A  A)
 BC
F  BC ( A  A)  AB(C  C )  AC ( B  B)

F  BC  AB  AC
Standard Forms
48

 Product of Sums (POS)

AB(C  C )

F  ABC  ABC  ABC  ABC

BC ( A  A)

AC ( B  B )
F  AC ( B  B)  AB(C  C )  BC ( A  A)

F  AC  AB  BC
F  ( A  C )( A  B)( B  C )
Two-Level Gate Implementation
𝑓1 = 𝑥𝑦′ + 𝑥𝑧 𝑓2 = 𝑦 + 𝑥𝑦′𝑧
𝑥 𝑦
𝑦′
𝑓1 𝑓2
𝑥
𝑥 𝑦′
𝑧 AND-OR 𝑧 3-input AND gate
implementations

𝑓3 = (𝑥 + 𝑧)(𝑥 ′ + 𝑦 ′ ) 𝑓4 = 𝑥(𝑥 ′ + 𝑦 ′ + 𝑧)
𝑥 𝑥
𝑧
𝑓3 𝑓4
𝑥′
𝑥′ 𝑦′
𝑦′ OR-AND 𝑧 3-input OR gate
implementations
Two-Level vs. Three-Level Implementation
 ℎ = 𝑎𝑏 + 𝑐𝑑 + 𝑐𝑒 (6 literals) is a sum-of-products
 ℎ may also be written as: ℎ = 𝑎𝑏 + 𝑐(𝑑 + 𝑒) (5 literals)
 However, ℎ = 𝑎𝑏 + 𝑐(𝑑 + 𝑒) is a non-standard form
 ℎ = 𝑎𝑏 + 𝑐(𝑑 + 𝑒) is not a sum-of-products nor a product-of-sums

2-level implementation 3-level implementation

ℎ = 𝑎𝑏 + 𝑐𝑑 + 𝑐𝑒 ℎ = 𝑎𝑏 + 𝑐(𝑑 + 𝑒)
𝑎
𝑏 𝑎
𝑏
𝑐
𝑑 ℎ 𝑐 ℎ
𝑑
𝑐 𝑒
𝑒 3-input OR gate
Additional Logic Gates and Symbols
 Why?
 Low cost implementation
 Useful in implementing Boolean functions

 Factors to be weighed in considering the construction of other

types of logic gates are
 The feasibility and economy of producing the gate with physical
components,
 The possibility of extending the gate to more than two inputs,
 The basic properties of the binary operator, such as commutativity and
associativity,
 The ability of the gate to implement Boolean functions alone or in
conjunction with other gates.
Additional Logic Gates and Symbols

𝑥 𝑥
𝑥·𝑦 𝑥+𝑦 𝑥 𝑥′
𝑦 𝑦
AND gate OR gate NOT gate (inverter)

𝑥 ′ 𝑥
𝑥·𝑦 (𝑥 + 𝑦)′ 𝑥 𝑥
𝑦 𝑦
NAND gate NOR gate Buffer
𝑐
𝑥 𝑥
𝑥⊕𝑦 (𝑥 ⊕ 𝑦)′ 𝑥 𝑓
𝑦 𝑦
XOR gate XNOR gate 3-state gate
NAND Gate
 The NAND gate has the following symbol and truth table
 NAND represents NOT AND
 The small bubble circle represents the invert function

𝑥 x y NAND
𝑥·𝑦 ′ = 𝑥′ + 𝑦′
𝑦 0 0 1
NAND gate 𝑥 0 1 1
𝑥′ + 𝑦′
𝑦 1 0 1
Another symbol for NAND 1 1 0

 NAND gate is implemented efficiently in CMOS technology

 In terms of chip area and speed
NOR Gate
 The NOR gate has the following symbol and truth table
 NOR represents NOT OR
 The small bubble circle represents the invert function

𝑥 x y NOR
𝑥+𝑦 ′ = 𝑥′ · 𝑦′
𝑦 0 0 1
NOR gate 𝑥 0 1 0
𝑥′ · 𝑦′
𝑦 1 0 0
Another symbol for NOR 1 1 0

 NOR gate is implemented efficiently in CMOS technology

 In terms of chip area and speed
Non-Associative NAND / NOR Operations
 Unlike AND, NAND operation is NOT associative

(𝑥 NAND 𝑦) NAND 𝑧 ≠ 𝑥 NAND (𝑦 NAND 𝑧)

(𝑥 NAND 𝑦) NAND 𝑧 = ((𝑥𝑦)′𝑧)′ = ((𝑥′ + 𝑦′)𝑧)′ = 𝑥𝑦 + 𝑧′

𝑥 NAND (𝑦 NAND 𝑧) = (𝑥(𝑦𝑧)′)′ = (𝑥(𝑦′ + 𝑧′))′ = 𝑥′ + 𝑦𝑧

 Unlike OR, NOR operation is NOT associative

(𝑥 NOR 𝑦) NOR 𝑧 ≠ 𝑥 NOR (𝑦 NOR 𝑧)

′ ′
(𝑥 NOR 𝑦) NOR 𝑧 = 𝑥+𝑦 ′+𝑧 = 𝑥′𝑦′ + 𝑧 = (𝑥 + 𝑦)𝑧′

′ ′ ′
𝑥 NOR (𝑦 NOR 𝑧) = 𝑥 + 𝑦 + 𝑧 = 𝑥 + 𝑦′𝑧′ = 𝑥′(𝑦 + 𝑧)
Extension to multiple inputs
Demonstrating the nonassociativity of the NOR operator: x  y  z  x  y z


Multiple-Input NAND / NOR Gates
NAND/NOR gates can have multiple inputs, similar to AND/OR gates

𝑥 𝑤
𝑥 𝑦 ′ 𝑥 𝑤·𝑥·𝑦·𝑧 ′
𝑥·𝑦 ′ 𝑥·𝑦·𝑧 𝑦
𝑦 𝑧 𝑧
2-input NAND gate 3-input NAND gate 4-input NAND gate

𝑥 𝑤
𝑥 𝑦 ′ 𝑥 𝑤+𝑥+𝑦+𝑧 ′
𝑥+𝑦 ′ 𝑥+𝑦+𝑧 𝑦
𝑦 𝑧 𝑧
2-input NOR gate 3-input NOR gate 4-input NOR gate

Note: a 3-input NAND is a single gate, NOT a combination of two 2-input gates.
The same can be said about other multiple-input NAND/NOR gates.
Extension to multiple inputs
Multiple‐input and cascaded NOR and NAND gates
Exclusive OR / Exclusive NOR
 Exclusive OR (XOR) is an important Boolean operation used
extensively in logic circuits

 Exclusive NOR (XNOR) is the complement of XOR

x y XOR x y XNOR
0 0 0 0 0 1
0 1 1 0 1 0 XNOR is also known
1 0 1 1 0 0 as equivalence
1 1 0 1 1 1
𝑥 𝑥
𝑥⨁𝑦 (𝑥 ⨁ 𝑦)′
𝑦 𝑦
XOR gate XNOR gate
XOR / XNOR Functions
 The XOR function is: 𝑥 ⨁ 𝑦 = 𝑥𝑦′ + 𝑥′𝑦
 The XNOR function is: (𝑥 ⨁ 𝑦)′ = 𝑥𝑦 + 𝑥′𝑦′
 XOR and XNOR gates are complex
 Can be implemented as a true gate, or by
 Interconnecting other gate types

 XOR and XNOR gates do not exist for more than two inputs
 For 3 inputs, use two XOR gates
 The cost of a 3-input XOR gate is greater than the cost of two XOR gates

 Uses for XOR and XNOR gates include:

 Adders, subtractors, multipliers, counters, incrementers, decrementers
 Parity generators and checkers
Extension to multiple inputs
Three‐input exclusive‐OR gate
Positive and Negative Logic
 Choosing the high‐level H to represent logic 1 defines a
positive logic system
 Choosing the low‐level L to represent logic 1 defines a
negative logic system.
 It is up to the user to decide on a positive or negative logic
polarity.

Signal assignment and logic polarity

Positive and Negative Logic
 The conversion from positive
logic to negative logic and vice
versa is essentially an operation
that changes 1’s to 0’s and 0’s to
1’s in both the inputs and the
output of a gate.
 Since this operation produces
the dual of a function, the
change of all terminals from one
polarity to the other results in
taking the dual of the function.