Engineers Garage

  • Electronic Projects & Tutorials
    • Electronic Projects
      • Arduino Projects
      • AVR
      • Raspberry pi
      • ESP8266
      • BeagleBone
      • 8051 Microcontroller
      • ARM
      • PIC Microcontroller
      • STM32
    • Tutorials
      • Audio Electronics
      • Battery Management
      • Brainwave
      • Electric Vehicles
      • EMI/EMC/RFI
      • Hardware Filters
      • IoT tutorials
      • Power Tutorials
      • Python
      • Sensors
      • USB
      • VHDL
    • Circuit Design
    • Project Videos
    • Components
  • Articles
    • Tech Articles
    • Insight
    • Invention Stories
    • How to
    • What Is
  • News
    • Electronic Product News
    • Business News
    • Company/Start-up News
    • DIY Reviews
    • Guest Post
  • Forums
    • EDABoard.com
    • Electro-Tech-Online
    • EG Forum Archive
  • DigiKey Store
    • Cables, Wires
    • Connectors, Interconnect
    • Discrete
    • Electromechanical
    • Embedded Computers
    • Enclosures, Hardware, Office
    • Integrated Circuits (ICs)
    • Isolators
    • LED/Optoelectronics
    • Passive
    • Power, Circuit Protection
    • Programmers
    • RF, Wireless
    • Semiconductors
    • Sensors, Transducers
    • Test Products
    • Tools
  • Learn
    • eBooks/Tech Tips
    • Design Guides
    • Learning Center
    • Tech Toolboxes
    • Webinars & Digital Events
  • Resources
    • Digital Issues
    • EE Training Days
    • LEAP Awards
    • Podcasts
    • Webinars / Digital Events
    • White Papers
    • Engineering Diversity & Inclusion
    • DesignFast
  • Guest Post Guidelines
  • Advertise
  • Subscribe

Boolean Algebra – Boolean Expressions and the Digital Circuits – DE Part 5

By Hai Prasaath K April 21, 2008

In the previous tutorial, various logic gates and their construction was discussed. In the tutorial – Boolean Logic Operations, it was discussed that how by performing logical operations on binary data, arithmetic operations can be executed. In a digital circuit, many logic gates are interconnected along with registers and memory elements to carry out a complex computation task. Any computational problem can be expressed as a boolean function or boolean expression.

A boolean expression takes into account the boolean variables (that can be seen as individual binary data sources) and represent mathematical relationship (in the form of addition and multiplication) between them. The mathematical operations like division and subtraction are executed by multiplication and addition itself. Like, subtraction can be implemented by addition with the complement and division can be implemented by multiplication of divisor by a factor and subtraction.

The boolean functions or expressions follow a set of mathematical rules which are collectively called boolean algebra. The various theorems of boolean algebra are helpful to minimize a boolean function. In order to design an optimized digital circuit (minimum number of logic gates to solve a specific computational problem), a boolean expression must be minimized. So, let us begin with basic theorems and postulates of boolean algebra.

Huntington Postulates –

Boolean Algebra was developed by George Boole in the year 1854. In 1904, E. V. Huntington formulated various postulates that must be satisfied by a boolean algebraic system. These postulates are as follow – 

1) Closure – If a boolean expression involves certain variables that belong a set say S, then set S is closed with respect to a binary operator if for every pair of elements of S, the binary operator specifies rules to obtain a unique element of S. In other words, if a boolean function involves certain boolean variables, then the variables as well as the result of the boolean expression must belong to a common set of elements. Any boolean expression always follow closure with respect to binary addition (+ operator) and binary multiplication (. operator).

2) Identity – A set is said to have an identity element for an operator (like *) if there exists an element say e in the set such that e belongs the set and multiplication of e with any other element result into the same element i.e. if x also belongs to same set, then x*e = e*x = x. In a boolean system, the identity element with respect to binary addition is 0 as for any boolean variable say x, x + 0 = 0 + x = x. Similarly, the identity element with respect to binary multiplication is 1 as for any boolean variable say x, x.1 = 1.x = x.

3) Commutative – Any boolean expression is commutative with respect to binary addition as well as binary multiplication. Like if there are two boolean variables – x and y, then x + y = y + x. Similarly, x.y = y.x.

4) Associative – Any boolean expression is also associative with respect to binary addition as well as binary multiplication. Like if there are three boolean variables – x, y and z, then x + (y + z) = (x + y) + z. Similarly, x.(y.z) = (x.y).z.

5) Distributive – In boolean algebra, binary addition is distributive over binary multiplication and binary multiplication is distributive over binary addition. So, if there are three boolean variables – x, y and z, then x.(y + z) = (x.y) + (x.z). Similarly, x+(y.z) = (x+y). (x+z).

6) Inverse – The boolean algebra does not have additive or multiplicative inverse as there are no subtraction and division operations in boolean algebra. Though, any boolean element say x, has a complement x’ such that x + x’ = 1 and x.x’ = 0.

The associative law is not a Huntington postulate, but it is valid for boolean algebra. It should also be noted that boolean algebra has + operator distributive over . operator. This is different from laws in ordinary algebra. It is also worth noting that boolean algebra has complement but not inverse. The boolean algebra used in digital electronics is a two-valued boolean algebra. It is defined over a set say B which has only two elements – (0, 1). All the above mentioned postulates are valid in the two-valued boolean algebra as follow –

1) Closure – The result of any boolean expression is either 0 or 1. So, it follow closure law with respect to the set (0, 1).

2) Identity – The 0 is identity element with respect to binary addition as for any boolean variable say x, 0 + x = x + 0 = x. If x = 0, then 0 + 0 = 0 + 0 = 0. If x is 1, then 0 + 1 = 1 + 0 = 1. The 1 is identity element with respect to the binary multiplication as for any boolean variable say x, 1.x = x.1 = x. if x = 0, then 1.0 = 0.1 = 0. if x = 1, then 1.1 = 1.1 = 1.

3) Inverse – The complement of 0 is 1 and the complement of 1 is 0. On binary addition, 0 + 1 = 1 and on binary multiplication, 0.1 = 0. For any boolean variable say x, x + x’ = 1 and x.x’ = 0.

Principle of Duality –

Duality is an important property of boolean algebra. According to this property, any boolean expression, deducible by the postulates of boolean algebra (Huntington Postulates along with associative property), remains same if the operator and identity elements are interchanged. So, dual of a boolean expression can be obtained by interchanging AND and OR operators and replacing all 1’s by 0’s and 0’s by 1’s.

Boolean Theorems –

Any boolean expression is deducible by the following theorems – 

Theorem 1 – For any boolean variable x, x + x = x and x.x = x. Suppose, if x = 0, then 0 + 0 = 0 and 0.0 = 0. If x = 1, then 1 + 1 = 1 and 1.1 = 1.

Theorem 2 – For any boolean variable x, x + 1 = 1 and x.0 = 0. Suppose, if x = 0, then 0 + 1 = 1 and 0.0 = 0. If x = 1, then 1 + 1 = 1 and 1.0 = 0.

Theorem 3 (Involution) – For any boolean variable x, (x’)’ = x. Suppose, x = 0, then (0′)’ = 1′ = 0. If x = 1, then (1′)’ = 0′ = 1.

Theorem 4 (associative) – For any boolean variables x, y and z, x + (y + z) = (x + y) + z and x . (y . z) = (x . y) . z.

Theorem 5 (DeMorgan Theorem) – This theorem states duality law for boolean algebra. For any boolean variables x and y, (x + y)’ = x’ . y’ and (x.y)’ = x’ + y’.

Theorem 6 (Absorption) – For any boolean variables x and y, x + (x . y) = x and x . (x + y) = x. This can be proved as follow –

x + (x . y) = (x . 1) + (x . y)

                 = x (1 + y)

                 = x . 1

                 = x

Similarly,

x . (x + y) = (x . x) + (x . y)

                 = x + (x . y)

                 = (x . 1) + (x . y)

                 = x (1 + y)

                 = x . 1

                 = x

Operator Precedence in Boolean Algebra –

The operator precedence in descending order in boolean algebra is as follow – 1) Parenthesis, 2) NOT, 3) AND and 4) OR. Any boolean expression is deduced from left to right and the highest precedence is of parenthesis (). Then NOT, AND and the lastly OR operator.

Boolean Function –   

A boolean function is a boolean algebraic expression consisting of boolean variables (where each variable can have a value 0 or 1), boolean constants (that is 0 and 1) and boolean operators (like AND, OR, NOT). Any boolean function practically represents some computation on binary data. For example, let a boolean function say F be like –

F = x + y.z

Here x, y and z are boolean variables (binary data sources like binary cells from a register) which are related by the AND and OR operators in the above function. All the possible results of a boolean expression can be represented by a truth table. The truth table enlists all the possible combinations of the values of the boolean variables and compare it with the result of the boolean expression. Like for the above stated function, the following is the truth table –

A digital circuit for the above boolean function is nothing other than the interconnection of logic gates (AND, OR, NOT) with binary data sources (represented by boolean variables in the boolean function). The binary multiplication or dot operation between two variables is equivalent to connecting two binary sources as input of AND gate. The binary addition or plus operation between two variables is equivalent to connecting two binary sources as input of OR gate. The complement is equivalent to connecting a binary source to a NOT gate. So, the digital circuit for the above function will be as follow – 

Boolean Function Converted to Logic Circuit

Fig. 1: Boolean Function Converted to Logic Circuit

Complement of a Boolean Function –

The complement of a boolean function is obtained by interchanging all 0’s to 1’s and 1’s to 0’s and interchanging AND and OR operators. In a boolean function, the replacement of all 0’s by 1’s and all 1’s by 0’s is done by replacing the boolean variables by their complements. For example, the complement of the function stated above will be as follow –

If F = x + y.z, then

F’ = x’ . (y’ + z’)

 

Minterm and Maxterm –

A boolean variable can exit in either its normal form (like x) or in its complement form (like x’) in a boolean expression. If AND operation is done between two variables, say x and y, there can be four possible combinations – x.y, x.y’, x’.y and x’.y’. Each of these all possible products are called Minterm or standard product. Similarly, if OR operation is done between two variables, say x and y, then again there are four possible combinations – x + y, x + y’, x’ + y and x’ + y’. Each of these all possible sums are called Maxterm or standard sums.

For two variables, x and y, the following Minterms and Maxterms are possible –

Similarly for three variables say x, y and z, the following Minterms and Maxterms are possible – 

For n variables, there can 2^n Minterms and 2^n Maxterms. An any boolean function can be expressed as sum of Minterms producing 1 for the function in the truth table or Product of Maxterms producing 0 for the function in the truth table provided the truth table for the function is known. For example, there be a function F, with the following truth table –Similarly for three variables say x, y and z, the following Minterms and Maxterms are possible –

From the above truth table, the function F can be expressed as sum of Minterms producing 1 for the function in the truth table as follow – 
F =x’yz + xy‘z’ + xy’z + xyz‘ + xyz = m3 + m4 + m5 + m6 + m7From the above truth table, the function F can be expressed as sum of Minterms producing 1 for the function in the truth table as follow –

Similarly, it can be expressed as product of Maxterms producing 0 for the function in the truth table as follow –

F = (x’ + y’ + z’) . (x’ + y’ + z) . (x’ + y + z’) = M0 . M1 . M2

A function expressed as sum of minterms or product of maxterms is said to be in its canonical form. As for n number of variables, there can be 2^n minterms and 2^n maxterms, the number of functions possible with n number of variables is 2^2n. So, for 2 boolean variables, there can be 4 minterms and 4 maxterms and total number of functions possible with them is 16. So, there can be 16 binary functions (binary operations) possible between two boolean variables or (binary sources).

By expressing a function in the form of Minterms and Maxterms, it can have two level implementation in logic gates. The two-level implementation is always preferred as it produces least amount of delay through the gates when signal propagates from input to output of the digital circuit.

In the next tutorial, learn about all the possible logical operations between two boolean variables. There are additional logical operations other than AND, OR and NOT. All the possible logical operations between two binary sources can be derived with the knowledge of boolean functions and theorems.


Filed Under: Articles

 

Next Article

← Previous Article
Next Article →

Questions related to this article?
👉Ask and discuss on EDAboard.com and Electro-Tech-Online.com forums.



Tell Us What You Think!! Cancel reply

You must be logged in to post a comment.

EE TECH TOOLBOX

“ee
Tech Toolbox: 5G Technology
This Tech Toolbox covers the basics of 5G technology plus a story about how engineers designed and built a prototype DSL router mostly from old cellphone parts. Download this first 5G/wired/wireless communications Tech Toolbox to learn more!

EE Learning Center

EE Learning Center
“engineers
EXPAND YOUR KNOWLEDGE AND STAY CONNECTED
Get the latest info on technologies, tools and strategies for EE professionals.

HAVE A QUESTION?

Have a technical question about an article or other engineering questions? Check out our engineering forums EDABoard.com and Electro-Tech-Online.com where you can get those questions asked and answered by your peers!


RSS EDABOARD.com Discussions

  • Industrial Relay Board Design for Motorcycle Use
  • Sendust vs Ferrite for SMPS
  • connector model question
  • value of feedback resistance in self biased inverter
  • sim7090g

RSS Electro-Tech-Online.com Discussions

  • ac current limiting
  • using a RTC in SF basic
  • It's Amazing What A Buck And A Quarter....
  • Microinverters and storeage batteries?
  • More fun with ws2812 this time XC8 and CLC

Featured – LoRa/LoRaWan Series

  • What is the LoRaWAN network and how does it work?
  • Understanding LoRa architecture: nodes, gateways, and servers
  • Revolutionizing RF: LoRa applications and advantages
  • How to build a LoRa gateway using Raspberry Pi
  • How LoRa enables long-range communication
  • How communication works between two LoRa end-node devices

Recent Articles

  • Infineon launches 3D magnetic sensors with ±50 mT to ±160 mT measurement ranges
  • Nexperia adds 1200 V 20 A silicon carbide Schottky diodes to power portfolio
  • EPC introduces 15 ARMS per phase motor drive in 32 mm diameter form factor
  • Non-contact angle sensors deliver +0.3% linearity across full measurement range
  • TDK introduces RGF board-mount EMI filters for high-current power supply applications

EE ENGINEERING TRAINING DAYS

engineering

Submit a Guest Post

submit a guest post
Engineers Garage
  • Analog IC TIps
  • Connector Tips
  • Battery Power Tips
  • DesignFast
  • EDABoard Forums
  • EE World Online
  • Electro-Tech-Online Forums
  • EV Engineering
  • Microcontroller Tips
  • Power Electronic Tips
  • Sensor Tips
  • Test and Measurement Tips
  • 5G Technology World
  • Subscribe to our newsletter
  • About Us
  • Contact Us
  • Advertise

Copyright © 2025 WTWH Media LLC. All Rights Reserved. The material on this site may not be reproduced, distributed, transmitted, cached or otherwise used, except with the prior written permission of WTWH Media
Privacy Policy

Search Engineers Garage

  • Electronic Projects & Tutorials
    • Electronic Projects
      • Arduino Projects
      • AVR
      • Raspberry pi
      • ESP8266
      • BeagleBone
      • 8051 Microcontroller
      • ARM
      • PIC Microcontroller
      • STM32
    • Tutorials
      • Audio Electronics
      • Battery Management
      • Brainwave
      • Electric Vehicles
      • EMI/EMC/RFI
      • Hardware Filters
      • IoT tutorials
      • Power Tutorials
      • Python
      • Sensors
      • USB
      • VHDL
    • Circuit Design
    • Project Videos
    • Components
  • Articles
    • Tech Articles
    • Insight
    • Invention Stories
    • How to
    • What Is
  • News
    • Electronic Product News
    • Business News
    • Company/Start-up News
    • DIY Reviews
    • Guest Post
  • Forums
    • EDABoard.com
    • Electro-Tech-Online
    • EG Forum Archive
  • DigiKey Store
    • Cables, Wires
    • Connectors, Interconnect
    • Discrete
    • Electromechanical
    • Embedded Computers
    • Enclosures, Hardware, Office
    • Integrated Circuits (ICs)
    • Isolators
    • LED/Optoelectronics
    • Passive
    • Power, Circuit Protection
    • Programmers
    • RF, Wireless
    • Semiconductors
    • Sensors, Transducers
    • Test Products
    • Tools
  • Learn
    • eBooks/Tech Tips
    • Design Guides
    • Learning Center
    • Tech Toolboxes
    • Webinars & Digital Events
  • Resources
    • Digital Issues
    • EE Training Days
    • LEAP Awards
    • Podcasts
    • Webinars / Digital Events
    • White Papers
    • Engineering Diversity & Inclusion
    • DesignFast
  • Guest Post Guidelines
  • Advertise
  • Subscribe