What is Boolean Algebra?

2017-11-15 17:45:53 zhengxiaowei 98

Boolean algebra is the mathematical language of digital logic circuits, which are simply circuits built out of the three gates (operations) introduced above. It provides techniques for describing, analysing and designing their operation. Using the above descriptions of the operation of the three basic gates, and their Boolean descriptions, Y=A, Y=A+B, the additional rules and laws of Boolean logic which are needed will now be introduced.

1. Single-variable theorems

As the heading suggests, this section details those rules which describe the operation of logic gates when only one variable is present. Note that these laws, given in Table 1.3, provide exactly the same information as the truth tables.


The OR operator gives exactly the same result and these laws give the output in rows 1 and 4 (see Table 1.2) of the truth tables.

Inverse elements

The law of inverse elements describes the effect of operating on a variable, Ay with its complement, A. For the AND gate this gives Y^A  A=0y since A and A must have complementary values and therefore 1^=0.

For the OR gate + = since either >4 or A must be 1. This law describes the operations in rows 2 and 3 of the truth tables.

Involution law

This describes the effect of operating on a variable twice with the NOT operator (i.e. passing a signal through two NOT gates). The effect of this is to return the variable to its original state. So Y=A=A.

Note that the truth tables could be derived from the above three laws as the give exactly the same information. It will become apparent that there is always more than one way of representing the information in a distal circuit, and that you must be able to choose the most suitable representation for any given situation, and also convert readily between them.

Properties of identity elements

The above laws give all of the information held in the truth tables. However another way of expressing this information is as the properties of identity elements. These just give the output of the AND and OR gates when a variable, is operated on by a constant (an identity element). (So for a two-input gate one of the inputs is held at either 0 or 1.) Obviously these laws, shown in Table 1.3, can also be used to completely determine the truth tables.

Note that Equation 1.6 in Table 1.3 states that ANE’ing any variable (or Boolean expression) with 0 gives 0, whilst Equation 1.9 means that OR’ing any variable (or Boolean expression) with 1 gives 1. However AND’ing with 1 (Equation 1.7) or OR’ing with 0 (Equation 1.8) gives the Boolean value of the variable or expression used in the operation.

Example 1.5_                     —                       

What is the result of the operations {X' 0) and {{X- Y)+1)




Example 1.6.

What is the result of the operations (K-1) and (X*Y +0)?


The outputs will be whatever the digital values of Y and (X' Y) are, since anything AND’d with 1 or OR’d with 0 is unchanged.

2. Multivariable theorems

These rules describe the operations of Boolean algebra when more than one variable is present. This includes defining the equivalence of certain groups of operations (i.e. groups of gates forming a circuit). All of the multivariable theorems described below are given in Table 1.4.

Commutative laws

These simply slate that it does not matter which way two variables are AND'd or OR*d together. So

Y=A'B=B'A and Y=A+B=B+A

This is the same as saying it does not matter which inputs of a two<input gate the two variables are connected to.

Associative laws

These show how operations can be associated with each other (grouped to together). Essentially if three or more variables are to be ANO^d or OR'd together it not matter in which order it is done. This is relevant if three variables are ^ operated upon and only gates with two inputs are available.          Example 1.7

If only two input OR gates are available draw the circuit to implement the Boolean expression Y-A+B+C. 


The circuit is shown in Fig. 1.4. Note that because of the associative law it do^ not matter which two of the three variables are OR’d together first.

Fig. 1.4 implementation of Y=A+B+C using two-input OR gates as discussed in Example 1.7 Distributive laws

The rules given by the commutative and associative laws are intuitive. However, the remaining multivariable theorems require more thought and are less obvious. The distributive laws (Equations l. 14 and 1.15) show how to expand out Boolean expressions and are important because it is upon them that the factorisation, and hence simplification, of such expressions are based.

TAG:  Fundamentals Boolean Algebra