Boolean Algebra

Boolean Algebra Operations

The three basic algebraic operations in the order of their precedence are as follows:

1. Negation (NOT operation): The negation of two variables is represented by the given Venn diagram. Here, the region except for the negated variable is included in the result. It is also represented by the ‘ or ¬ symbol.
   
   
                    Source: Link
   
    
2. Conjunction (AND operation): A conjunction of two variables is represented by the given Venn diagram. Here, the common region between both the variables represents the conjunction between A and B. (A ∧ B) It is also represented by dot(.) or ∧ symbol.
   
   
                   Source: Link
   
    
3. Disjunction (OR operation): The given Venn diagram represents a disjunction of two variables. Here, the entire region covered by A and B represents the disjunction. (A ∨ B) It is also represented by + or ∨ symbol.
   
   
                  Source: Link
   
    

Boolean Algebra Truth Table

The table used to represent the Boolean expression is commonly known as Truth Table. A logic gate truth table represents every possible input combination to the gate with the resultant output depending upon the combination of these inputs. The number of rows in a Truth Table is equal to 2ⁿ, where n equals the number of literals in the given function.

Consider the Truth Table given below:

Boolean Functions

A Boolean function is formed with binary variables, operators (AND, OR, and NOT), and parenthesis. The value of a Boolean function can either be 0 or 1. A Boolean function can be represented in a truth table or an algebraic expression.

Representation as an Algebraic Expression

Consider the given expression:

Y = X + (W)’ ^ Z

Here, variable Y is a function of X, W, and Z that can also be written as Y= f(X, W, Z).

The RHS of the equation is known as expression, and the variables X, W, and Z are known as the literals of the expression. A Boolean function can have more than one algebraic expression.

Representation as a Truth Table

Consider the given expression:

Y = X + (W)’ ^ Z

Truth Table for the given expression will look like this:

Laws in Boolean Algebra

The basic laws of Boolean algebra are as follows:

1. Commutative Law: This law states that changing the order of operands in a Boolean equation doesn’t affect the output of the equation.
   Example:  A + B = B + A
    
2. Associative Law: This law states that the output of the Boolean equation does not depend on the order of the logical operands.
   Example: (A*B)*C = A*(B*C)
    
3. Distributive Law: Every Boolean expression satisfies the following condition:
   (A + B) *C = A*C + B*C
    
4. AND Law: This law uses the AND operation.
   A .0 = 0  (Annulment)
   A . 1 = A (Identity)
   A. A = A (Idempotent)
   A. A’ = 0 (Complement)
    
5. OR Law: This law uses the OR operation.
   A + 0 = A (Identity)
   A + 1 = 1 (Annulment)
   A + A = A (Idempotent)
   A + A’ = 1 (Complement)
    
6. Inversion Law: This law states that the double inversion of the variable results in the original variable. i.e., A = (A’)’. 
    
7. Absorption Law: Every Boolean expression satisfies the following condition:
   A . (A + B) = A
   A + AB = A

Theorems in Boolean Algebra

The most important theorem used in Boolean Algebra is known as De Morgan’s Law/ Theorem depending on the concept of duality. Duality states the interchanging of operators such as AND to OR and vice-versa, or the variables 0 to 1 and 1 to 0.

The two theorems given by De Morgan's are as follows:

1. De Morgan's First Law:  This law states that the negation of a conjunction is the disjunction of the negation, which implies that the complement of the variable’s product is equal to the sum of their complements.
   ( A . B)’ = A’ + B’ 
   
   We can verify the above expression by the given truth table:
   
   
   
    
2. De Morgan’s Second Law: This law states that the negation of a disjunction is the conjunction of the negation, which implies that the complement of the variable’s sum is equal to the product of their complements.
   ( A + B )’ = A’. B’ 
   
   We can verify the above expression by the given truth table:
   
   
    

Boolean Logic Diagram

Let’s try to understand the concept of a logic diagram through some examples. Consider the following examples:

Example: Given a Boolean expression Y = A + B’C

The logic diagram for the Boolean expression can be represented as:

The given Boolean expression is converted into a logic diagram consisting of AND, OR, inverter gates with the help of the truth table. The inverter at B generated B’. Similarly, there is an AND gate attached for the expression B’C, and at last, the OR gate is used to combine the complete expression A + B’C.

The truth table for the given expression will look like this:

Also see,  what is middleware

Frequently Asked Questions

1. What is a snooping protocol?
   A snooping protocol is also known as the bus-snooping protocol. It is used to maintain the cache coherency in symmetric multiprocessing environments. All caches on the bus snoop are monitored to determine if they have a copy of the requested data on the bus. In a multiprocessing environment, several copies of a file can be read without facing the problem of coherence. However, a processor should have access to the bus to write.
    
2. What is the easiest way to determine the cache location to store the memory blocks?
   Direct mapping is one of the easiest ways to define the cache locations to store memory blocks. It maps each block of the main memory into one possible cache line. The cache in a direct-mapped structure is organized into several sets, a single line per set. Based on the memory block's address, it can only use a single cache line. The cache can also be framed as a column matrix.
    
3. What do you understand by the term wait-state?
   A wait-state is when a computer processor experiences a delay while accessing a device or an external memory. We try to minimize or eliminate wait-states as they are considered wasteful in a processor's performance. These include pipelines, caches, instruction prefetch, branch prediction, and simultaneous multithreading. These techniques can't eliminate wait-states, but they can significantly minimize the problem when implemented simultaneously.

Key Takeaways

This blog discussed Boolean Algebra, its complement, functions, laws, along with the truth table and logic expressions. Boolean Algebra is very useful when dealing with complex expressions. Such expressions can be simplified using Boolean logic diagrams and truth tables. 

If you are a beginner and are interested in learning other fields related to computer subjects such as web development, or competitive programming, you can follow our guided path to get a good grip on such concepts.