Laws of Boolean Algebra

As well as the logic symbols “0” and “1” being used to represent a digital input or output, we can also use them as constants for a permanently “Open” or “Closed” circuit or contact respectively.

A set of rules or Laws of Boolean Algebra expressions have been invented to help reduce the number of logic gates needed to perform a particular logic operation resulting in a list of functions or theorems known commonly as the Laws of Boolean Algebra.

Boolean Algebra is the mathematics we use to analyse digital gates and circuits. We can use these “Laws of Boolean” to both reduce and simplify a complex Boolean expression in an attempt to reduce the number of logic gates required. Boolean Algebra is therefore a system of mathematics based on logic that has its own set of rules or laws which are used to define and reduce Boolean expressions.

The variables used in Boolean Algebra only have one of two possible values, a logic “0” and a logic “1” but an expression can have an infinite number of variables all labelled individually to represent inputs to the expression, For example, variables A, B, C etc, giving us a logical expression of A + B = C, but each variable can ONLY be a 0 or a 1.

Examples of these individual laws of Boolean, rules and theorems for Boolean Algebra are given in the following table.

Truth Tables for the Laws of Boolean

Boolean Expression	Description	Boolean Algebra Law or Rule
A + 1 = 1	A in parallel with closed = “CLOSED”	Annulment
A + 0 = A	A in parallel with open = “A”	Identity
A . 1 = A	A in series with closed = “A”	Identity
A . 0 = 0	A in series with open = “OPEN”	Annulment
A + A = A	A in parallel with A = “A”	Idempotent
A . A = A	A in series with A = “A”	Idempotent
NOT A = A	NOT NOT A (double negative) = “A”	Double Negation
A + A = 1	A in parallel with NOT A = “CLOSED”	Complement
A . A = 0	A in series with NOT A = “OPEN”	Complement
A+B = B+A	A in parallel with B = B in parallel with A	Commutative
A.B = B.A	A in series with B = B in series with A	Commutative
A+B = A.B	invert and replace OR with AND	de Morgan’s Theorem
A.B = A+B	invert and replace AND with OR	de Morgan’s Theorem

The basic Laws of Boolean Algebra that relate to the Commutative Law allowing a change in position for addition and multiplication, the Associative Law allowing the removal of brackets for addition and multiplication, as well as the Distributive Law allowing the factoring of an expression, are the same as in ordinary algebra.

Each of the Boolean Laws above are given with just a single or two variables, but the number of variables defined by a single law is not limited to this as there can be an infinite number of variables as inputs too the expression. These Boolean laws detailed above can be used to prove any given Boolean expression as well as for simplifying complicated digital circuits.

A brief description of the various Laws of Boolean are given below with A representing a variable input.

Description of the Laws of Boolean Algebra

• Annulment Law – A term AND´ed with a “0” equals 0 or OR´ed with a “1” will equal 1
•  
  • A . 0 = 0    A variable AND’ed with 0 is always equal to 0
  • A + 1 = 1    A variable OR’ed with 1 is always equal to 1
•  
• Identity Law – A term OR´ed with a “0” or AND´ed with a “1” will always equal that term
•  
  • A + 0 = A   A variable OR’ed with 0 is always equal to the variable
  • A . 1 = A    A variable AND’ed with 1 is always equal to the variable
•  
• Idempotent Law – An input that is AND´ed or OR´ed with itself is equal to that input
•  
  • A + A = A    A variable OR’ed with itself is always equal to the variable
  • A . A = A    A variable AND’ed with itself is always equal to the variable
•  
• Complement Law – A term AND´ed with its complement equals “0” and a term OR´ed with its complement equals “1”
•  
  • A . A = 0    A variable AND’ed with its complement is always equal to 0
  • A + A = 1    A variable OR’ed with its complement is always equal to 1
•  
• Commutative Law – The order of application of two separate terms is not important
•  
  • A . B = B . A    The order in which two variables are AND’ed makes no difference
  • A + B = B + A    The order in which two variables are OR’ed makes no difference
•  
• Double Negation Law – A term that is inverted twice is equal to the original term
•  
  • A = A     A double complement of a variable is always equal to the variable
•  
• de Morgan´s Theorem – There are two “de Morgan´s” rules or theorems,
•  
• (1) Two separate terms NOR´ed together is the same as the two terms inverted (Complement) and AND´ed for example:  A+B = A . B
•  
• (2) Two separate terms NAND´ed together is the same as the two terms inverted (Complement) and OR´ed for example:  A.B = A + B

 

Other algebraic Laws of Boolean not detailed above include:

• Boolean Postulates – While not Boolean Laws in their own right, these are a set of Mathematical Laws which can be used in the simplification of Boolean Expressions.
•  
  • 0 . 0 = 0    A 0 AND’ed with itself is always equal to 0
  • 1 . 1 = 1    A 1 AND’ed with itself is always equal to 1
  • 1 . 0 = 0    A 1 AND’ed with a 0 is equal to 0
  • 0 + 0 = 0    A 0 OR’ed with itself is always equal to 0
  • 1 + 1 = 1    A 1 OR’ed with itself is always equal to 1
  • 1 + 0 = 1    A 1 OR’ed with a 0 is equal to 1
  • 1 = 0    The Inverse (Complement) of a 1 is always equal to 0
  • 0 = 1    The Inverse (Complement) of a 0 is always equal to 1
•  
• Distributive Law – This law permits the multiplying or factoring out of an expression.
•  
  • A(B + C) = A.B + A.C    (OR Distributive Law)
  • A + (B.C) = (A + B).(A + C)    (AND Distributive Law)
•  
• Absorptive Law – This law enables a reduction in a complicated expression to a simpler one by absorbing like terms.
•  
  • A + (A.B) = (A.1) + (A.B) = A(1 + B) = A  (OR Absorption Law)
  • A(A + B) = (A + 0).(A + B) = A + (0.B) = A  (AND Absorption Law)
•  
• Associative Law – This law allows the removal of brackets from an expression and regrouping of the variables.
•  
  • A + (B + C) = (A + B) + C = A + B + C    (OR Associate Law)
  • A(B.C) = (A.B)C = A . B . C    (AND Associate Law)

Boolean Algebra Functions

Using the information above, simple 2-input AND, OR and NOT Gates can be represented by 16 possible functions as shown in the following table.

Function	Description	Expression
1.	NULL	0
2.	IDENTITY	1
3.	Input A	A
4.	Input B	B
5.	NOT A	A
6.	NOT B	B
7.	A AND B (AND)	A . B
8.	A AND NOT B	A . B
9.	NOT A AND B	A . B
10.	NOT AND (NAND)	A . B
11.	A OR B (OR)	A + B
12.	A OR NOT B	A + B
13.	NOT A OR B	A + B
14.	NOT OR (NOR)	A + B
15.	Exclusive-OR	A . B + A . B
16.	Exclusive-NOR	A . B + A . B

Laws of Boolean Algebra Example No1

Using the above laws, simplify the following expression:  (A + B)(A + C)

Q =	(A + B).(A + C)
	A.A + A.C + A.B + B.C	– Distributive law
	A + A.C + A.B + B.C	– Idempotent AND law (A.A = A)
	A(1 + C) + A.B + B.C	– Distributive law
	A.1 + A.B + B.C	– Identity OR law (1 + C = 1)
	A(1 + B) + B.C	– Distributive law
	A.1 + B.C	– Identity OR law (1 + B = 1)
Q =	A + (B.C)	– Identity AND law (A.1 = A)

 

Then the expression:  (A + B)(A + C) can be simplified to A + (B.C) as in the Distributive law.

Code Conversion

There are many methods or techniques which can be used to convert code from one format to another. We'll demonstrate here the following

• Binary to BCD Conversion
• BCD to Binary Conversion
• BCD to Excess-3
• Excess-3 to BCD

Binary to BCD Conversion

Steps

• Step 1 -- Convert the binary number to decimal.

• Step 2 -- Convert decimal number to BCD.

Example − convert (11101)₂ to BCD.

Step 1 − Convert to Decimal

Binary Number − 11101₂

Calculating Decimal Equivalent −

Step	Binary Number	Decimal Number
Step 1	111012	((1 × 24) + (1 × 23) + (1 × 22) + (0 × 21) + (1 × 20))10
Step 2	111012	(16 + 8 + 4 + 0 + 1)10
Step 3	111012	2910

Binary Number − 11101₂ = Decimal Number − 29₁₀

Step 2 − Convert to BCD

Decimal Number − 29₁₀

Calculating BCD Equivalent. Convert each digit into groups of four binary digits equivalent.

Step	Decimal Number	Conversion
Step 1	2910	00102 10012
Step 2	2910	00101001BCD

Result

(11101)2 =  (00101001)BCD

BCD to Binary Conversion

Steps

• Step 1 -- Convert the BCD number to decimal.

• Step 2 -- Convert decimal to binary.

Example − convert (00101001)_BCD to Binary.

Step 1 - Convert to BCD

BCD Number − (00101001)_BCD

Calculating Decimal Equivalent. Convert each four digit into a group and get decimal equivalent for each group.

Step	BCD Number	Conversion
Step 1	(00101001)BCD	00102 10012
Step 2	(00101001)BCD	210 910
Step 3	(00101001)BCD	2910

BCD Number − (00101001)_BCD = Decimal Number − 29₁₀

Step 2 - Convert to Binary

Used long division method for decimal to binary conversion.

Decimal Number − 29₁₀

Calculating Binary Equivalent −

Step	Operation	Result	Remainder
Step 1	29 / 2	14	1
Step 2	14 / 2	7	0
Step 3	7 / 2	3	1
Step 4	3 / 2	1	1
Step 5	1 / 2	0	1

As mentioned in Steps 2 and 4, the remainders have to be arranged in the reverse order so that the first remainder becomes the least significant digit (LSD) and the last remainder becomes the most significant digit (MSD).

Decimal Number − 29₁₀ = Binary Number − 11101₂

Result

(00101001)BCD = (11101)2

BCD to Excess-3

Steps

• Step 1 -- Convert BCD to decimal.

• Step 2 -- Add (3)₁₀ to this decimal number.

• Step 3 -- Convert into binary to get excess-3 code.

Example − convert (0110)_BCD to Excess-3.

Step 1 − Convert to decimal

(0110)_BCD = 6₁₀

Step 2 − Add 3 to decimal

(6)₁₀ + (3)₁₀ = (9)₁₀

Step 3 − Convert to Excess-3

(9)₁₀ = (1001)₂

Result

(0110)BCD = (1001)XS-3

Excess-3 to BCD Conversion

Steps

• Step 1 -- Subtract (0011)₂ from each 4 bit of excess-3 digit to obtain the corresponding BCD code.

Example − convert (10011010)_XS-3 to BCD.

Given XS-3 number  = 1 0 0 1 1 0 1 0 
Subtract (0011)2   = 1 0 0 1 0 1 1 1
                    --------------------
               BCD = 0 1 1 0   0 1 1 1

Computer architecture

In computer engineering, computer architecture is a set of rules and methods that describe the functionality, organization, and implementation of computer systems. Some definitions of architecture define it as describing the capabilities and programming model of a computer but not a particular implementation.

Von Neumann Architecture

Von Neumann architecture was first published by John von Neumann in 1945.

His computer architecture design consists of a Control Unit, Arithmetic and Logic Unit (ALU), Memory Unit, Registers and Inputs/Outputs.

Von Neumann architecture is based on the stored-program computer concept, where instruction data and program data are stored in the same memory.  This design is still used in most computers produced today.

Central Processing Unit (CPU)

The Central Processing Unit (CPU) is the electronic circuit responsible for executing the instructions of a computer program.

It is sometimes referred to as the microprocessor or processor.

 

 

The CPU contains the ALU, CU and a variety of registers.

Registers

Registers are high speed storage areas in the CPU.  All data must be stored in a register before it can be processed.

MAR	Memory Address Register	Holds the memory location of data that needs to be accessed
MDR	Memory Data Register	Holds data that is being transferred to or from memory
AC	Accumulator	Where intermediate arithmetic and logic results are stored
PC	Program Counter	Contains the address of the next instruction to be executed
CIR	Current Instruction register	Contains the current instruction during processing

Arithmetic and Logic Unit (ALU)

The ALU allows arithmetic (add, subtract etc) and logic (AND, OR, NOT etc) operations to be carried out.

Control Unit (CU)

The control unit controls the operation of the computer’s ALU, memory and input/output devices, telling them how to respond to the program instructions it has just read and interpreted from the memory unit.

The control unit also provides the timing and control signals required by other computer components.

Buses

Buses are the means by which data is transmitted from one part of a computer to another, connecting all major internal components to the CPU and memory.

A standard CPU system bus is comprised of a control bus,data bus and address bus. 

Address Bus	Carries the addresses of data (but not the data) between the processor and memory
Data Bus	Carries data between the processor, the memory unit and the input/output devices
Control Bus	Carries control signals/commands from the CPU (and status signals from other devices) in order to control and coordinate all the activities within the computer

Memory Unit

The memory unit consists of RAM, sometimes referred to as primary or main memory.  Unlike a hard drive (secondary memory), this memory is fast and also directly accessible by the CPU.

RAM is split into partitions.  Each partition consists of an address and its contents (both in binary form).

The address will uniquely identify every location in the memory.

Loading data from permanent memory (hard drive), into the faster and directly accessible temporary memory (RAM), allows the CPU to operate much quicker.