Explore Related Concepts

Boolean Algebra Practice Problems

Introduction to Boolean Algebra:
The theory of Boolean algebra  was given by English Mathematician George Boole in the year 1847. Boolean algebra is apart of mathematics, which is also called as abstract algebra. Boolean algebra are used to analyze the concept of logic circuits or combined circuits. Boolean algebra has  found various form of application are

Rules of Boolean Algebra:
  • A + 0 = A
  • A + 1 = 1
  • A . 0 = 0
  • A . 1  = A
  • A + A = A
  • A + $\overline{A}$ = 1
  • A . A = A
  • A . $\overline{A}$ = 0
  • $\overline{A}$ = A
  • A + AB = A
  • A + $\overline{A}$ B = A + B
  • (A + B) (A + C) = A + BC

Postulates:

      1. Existence of an identity element 0 or 1 with respect to the operator '+'  or '.'
              a) A + 0 =  A
              b) A . 1  = A
 
      2. Commutative property:
              a) X + Y = Y + X
              b) X . Y =  Y . X

      3. Associative property:
              a) X +(Y + Z) = (X + Y) + Z
              b) X. (Y . Z) = (X . Y) . Z

      4. Distributive property
              a) X +(Y . Z) = (X + Y).(X + Z)
              b) X. (Y + Z) = (X . Y) + (X . Z)

      5.  Existence of complement
              a) A + A' = 1
              b) A . A'  = 0


Demorgan's Theorems:

      a)  The complement of a product of variables is equal to the sum of the complements of the variables.

            $\overline{AB}=\overline{A}+\overline{B}$

      b)  The complement of a sum of variables is equal to the product of the complements of the variables.

            $\overline{A+B}=\overline{A}     \overline{B}$


Two Valued Boolean Algebra:
The set of two elements of the variable X(0.1), along with the operators AND  and OR forms a two – valued Boolean algebra. 

AND Operation:

AND Operation

    X         Y          X.Y     
 0  0  0
 0  1   0
 1  0  0 
 1  1  1

OR Operation:

OR Operation

    X         Y          X+Y     
 0  0  0
 0  1  1
 1  0  1
 1  1  1


NOT Operation:

NOT Operation

        X                  X'        
 0 1
 1  0 


Boolean Algebra Practice Problems:

         1.  A + $\overline{AB}$
              we simplify the expression, take the common term
              = A + ($\overline{A}+\overline{B}$)
              = ( A + $\overline{A}$) + $\overline{B}$ commutative and Associative laws
              = 1 + $\overline{B}$            Complement rule 
              = 1 Identity rule

          2.  A + AB
              = A ( 1 + B)
              = A (1)
              = A

          3. XY + X$\overline{Y}$
              = X( Y + $\overline{Y}$)
              =  X (1)
              = X

          4.  XY + X'Z + YZ
              = XY + X'Z + YZ(X + X')
              = XY + X'Z + XYZ + X'YZ
              = XY(1 + Z)+ X'Z(1 + Y)
              = XY + X'Z

          5. $\overline{A}$B + AB + A + A$\overline{B}$
              = $\overline{A}$B + A(B + 1 + $\overline{B}$)
              = $\overline{A}$B + A
              = A + $\overline{A}$B
              = (A+$\overline{A}$)(A+B)
              = A+B


Best Results From Wikipedia Yahoo Answers Youtube


From Wikipedia

Boolean algebra (logic)

Boolean algebra (or Boolean logic) is a logical calculus of truth value s, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition xnbsp;+nbsp; y, and negation minus; x replaced by the respective logical

Canonical form (Boolean algebra)

In Boolean algebra, any Boolean function can be expressed in a canonical formusing the dual concepts of minterms and maxterms. Minterms are called products because they are thelogical AND of a set of variables, and maxterms are called sums because they are the logical OR of a set of variables (further definition appears in the sections headed Minterms and Maxterms below). These concepts are called duals because of their complementary-symmetry relationship as expressed by De Morgan's laws, which state that AND(x,y,z,...) = NOR(x',y',z',...) and OR(x,y,z,...) = NAND(x',y',z',...) (the apostrophe ' is an abbreviation for logical NOT, thus " x' " represents " NOT x ", the Boolean usage " x'y + xy' " represents the logical equation " (NOT(x) AND y) OR (x AND NOT(y)) ").

The dual canonical forms of any Boolean function are a "sum of minterms" and a "product of maxterms." The term "Sum of Products" or "SoP" is widely used for the canonical form that is a disjunction (OR) of minterms. Its De Morgan dual is a "Product of Sums" or "PoS" for the canonical form that is a conjunction (AND) of maxterms. These forms allow for greater analysis into the simplification of these functions, which is of great importance in the minimization or other optimization of digital circuits.

Summary

The usual purpose of doing Boolean algebra is to simplify the design of a digital circuit that performs a function, either to minimize the number of gates, or to minimize the time for the value of the function to settle down after a change in its input(s), or some other practical criterion.

There are sixteen possible functions of two variables, but in digital logic hardware, the simplest gate circuits implement only four of them: conjunction(AND),disjunction(inclusive OR), and the complements of those (NAND and NOR).

Most gate circuits accept more than 2 input variables; for example, the spaceborne Apollo Guidance Computer, which pioneered the application of integrated circuits in the 1960s, was built with only one type of gate, a 3-input NOR, whose output is true only when all 3 inputs are false.

Minterms

For a boolean function of n variables {x_1,\dots,x_n}, a product term in which each of the n variables appears once (in either its complemented or uncomplemented form) is called a minterm. Thus, a minterm is a logical expression of n variables that employs only the complement operator and the conjunction operator.

For example, abc, ab'c and abc' are 3 examples of the 8 minterms for a Boolean function of the three variables a, b and c. The customary reading of the last of those is a AND b AND NOT-c.

There are 2n minterms of n variables, since a variable in the minterm expression can be in either its direct or its complemented form--two choices per n variables.

Indexing minterms

In general, one assigns each minterm an index based on a conventional binary encoding of the complementation pattern of the variables (where the variables in all the minterms are written in the same order, usually alphabetical). This convention assigns the value 1 to the direct form (x_i) and 0 to the complemented form (x'_i). For example, we assign the index 6 to the minterm a b c' (110) and denote that minterm as m_6. Similarly, m_0 of the same three variables is a' b' c' (000), and m_7 is a b c (111).

Functional equivalence

It is apparent that minterm n gives a true value (i.e., 1) for just one combination of the input variables. For example, minterm 5, ab' c, is true only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 1.

If one is given a truth table of a logical function, it is possible to write the function as a "sum of products". This is a special form of disjunctive normal form. For example, if given the truth table for the arithmetic sum bit u of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:

Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can write u as a sum of minterms m_1, m_2, m_4, and m_7. If we wish to verify this: u(ci, x, y) = m_1 + m_2 + m_4 + m_7 = (ci' x' y) + (ci' x y') + (ci x' y') + (ci x y) evaluated for all 8 combinations of the three variables will match the table.

Maxterms

For a boolean function of n variables {x_1,\dots,x_n}, a sum term in which each of the n variables appears once (in either its complemented or uncomplemented form) is called a maxterm. Thus, a maxterm is a logical expression of n variables that employs only the complement operator and the disjunction operator. Maxterms are a dual of the minterm idea (i.e., exhibiting a complementary symmetry in all respects). Instead of using ANDs and complements, we use ORs and complements and proceed similarly.

For example, the following are two of the eight maxterms of three variables:

a+b'+c
a'+b+c

There are again 2n maxterms of n variables, since a variable in the maxterm expression can also be in either its direct or its complemented form--two choices per n variables.

Indexing maxterms

Each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms. The maxterm convention assigns the value 0 to the direct form (x_i) and 1 to the complemented form (x'_i). For example, we assign the index 6 to the maxterm a' + b' + c (110) and denote that maxterm as M6. Similarly M0 of these three variables is a + b + c (000) and M7 is a' + b' + c' (111).

Functional equivalence

It is apparent that maxterm n gives a false value (i.e., 0) for just one combination of the input variables. For example, maxterm 5, a' + b + c', is false only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 0.

If one is given a truth table of a logical function, it is possible to write the function as a "product of sums". This is a special form of conjunctive norm


From Yahoo Answers

Question:I am looking for solved problems under Boolean Algebra... i cannot seem to find any... hELP! I just need at least 10 problems with solutions.. thanks in advance! well this is actually my homework... you know the laws of Boolean Algebra right?? i need problems with solutions using the laws of boolean algebra.. [commutative, distributive etc etc] like... (x+y)(x+z)... then with solution... :)

Answers:See the examples in the site below. They're in Matlab, but they are easy to understand, so that you can repeat the reasoning in any other language. Good luck!

Question:can anybody plz tell me how to completely simplify the following: F = A'B'C + AB'C' + A'B'C' + A'BC' + AB'C i can get till: F = A'B'(C+C') + AB'C' + A'BC' + AB'C = A'B' + AB'C' + A'BC' + AB'C = A'B' + AB'(C+C') + A'BC' = A'B' + AB' + A'BC' = A'(B + BC') + AB' = A'[ B(1 + C') ] + AB' = A'B + AB' is it possible to simplify it further, other than writing A XOR B ?

Answers:Your derivation is not correct. On the very first step, you applied the conversion: A'B'C ==> A'B'(C+C') which is illegal. I suspect you were thinking of the similar expansion: A'B' ==> A'B'(C+C') This is OK because "C" is a "don't care"; however, in the original case, the C *is* specified. However, to prove that your derivation is incorrect, consider the input of 011. A=0 B=1 C=1 Then evaluate the original expression: F = A'B'C + AB'C' + A'B'C' + A'BC' + AB'C F = 101 + 000 + 100 + 110 + 001 F = 0 + 0 + 0 + 0 + 0 F = 0 However, evaluating your expression: F = A'B + AB' F = 11 + 00 F = 1 + 0 F = 1 The generated outputs are not the same, therefore, the expressions are not equal. Instead, the reduction should be as follows. Given: F = A'B'C+AB'C'+A'B'C'+A'BC'+AB'C Rearrange: F = A'B'C'+A'B'C+AB'C'+AB'C + A'BC' Replicate A'B'C': F = A'B'C'+A'B'C+AB'C'+AB'C + A'BC'+A'B'C' Group and reduce: F = (A'B'C'+A'B'C) + (AB'C'+AB'C) + (A'BC'+A'B'C') F = (A'B')+(AB')+(A'C') F = A'B'+AB'+A'C' Group again, and reduce F = (A'B'+AB')+A'C' F = (B')+A'C' F = B'+A'C' This is the minimal sum of products expression.

Question:Can someone simply this for me ( ' means not)? (A+BC')' XOR (A'B + C)

Answers:Given: (A+BC')' XOR (A'B + C) To simplify this, try converting it to AND's and OR's using the transformation a XOR b = (ab') + (a'b) [ (A+BC')' & (A'B + C)' ] + [ (A+BC') & (A'B + C) ] Apply DeMorgan's theorem: [ (A'&(B'+C)) & ((A+B')&C') ] + [ (A+BC') & (A'B + C) ] Distribute terms and multiply: (A'B' + A'C) & (AC' + B'C') + (A+BC') & (A'B + C) A'B'AC' + A'CAC' + A'B'B'C' + A'CB'C' + AA'B + A'BBC' + AC + BC'C Simplify: 0 + 0 + A'B'C' + 0' + 0 + A'BC' + AC + 0 A'B'C' + A'BC' + AC Factor and reduce: A'C' (B' + B) + AC A'C' (1) + AC A'C' + AC However, now recognize that this can be rewritten with XOR: A' XOR C ANSWER: Reduced expression is: A' XOR C As a quick verification, the following program evaluates the three expressions: f1 = original expression f2 = minimized sum-of-products f3 = XOR version for all possible values of a, b, and c. #include int main(int argc, char* argv[]) { printf("a b c ==> f1 f2\n"); for (int a=0; a<2; a++) { for (int b=0; b<2; b++) { for (int c=0; c<2; c++) { /* (A+BC')' XOR (A'B + C) */ int f1 = !(a|(b&(!c))) ^ (((!a)&b) | c); /* A'C' + AC */ int f2 = ((!a)&(!c)) | (a&c); int f3 = (!a) ^ c; printf("%d %d %d ==> %d %d %d\n", a,b,c,f1,f2,f3); } } } } To see the truth tables: $ cc boolean.c $ a.out a b c ==> f1 f2 f3 0 0 0 ==> 1 1 1 0 0 1 ==> 0 0 0 0 1 0 ==> 1 1 1 0 1 1 ==> 0 0 0 1 0 0 ==> 0 0 0 1 0 1 ==> 1 1 1 1 1 0 ==> 0 0 0 1 1 1 ==> 1 1 1

Question:' = vinculum [AB+ (AD)'](A' + AB + C)[(A' + B')' + BC'] Simplify this. I got B as the answer, but I'm not sure. Can someone check for me and show the work please.

Answers:The answer is C because Jimbo Ruqus said so.

From Youtube

Boolean algebra #2: Basic problems :visit www.keleshev.com for structured list of tutorials on Boolean algebra and digital hardware design!

Principles of Boolean Algebra :Principles of Boolean AlgebraAlgebra of logic is a mathematical device used to record, calculat, simplify, and transform logical propositions. Algebra of logic was developed by George Boole and therefore was named Boolean algebra. It started as a speculative science, accessible only to a narrow circle of scientists. That was until Englishman George Boole bet in the nineteenth century he would create a science completely detached from reality and without any practical application. He turned mathematical logic into algebra of propositions. Boolean algebra is the algebra of two values - true and false. For example, the statement "6 is an even number" is true, and the statement "The Neva flows into the Caspian Sea" is false. These 2 elements - true and false - are called constants and they are assigned, respectively, logical 1 and logical 0. In the algebra of logic, propositions can be combined to give new propositions. These new propositions are called functions of the initial propositions of the logical variables A, B, C, each of which can take 0 or 1.Depending on the values of variables and operations, a function can be either 1, or 0. The values of functions are determined by the truth table of this function. A truth table is a table used to establish a correspondence between all possible configurations of logical variables in a logical function and the values of these functions. All possible logical functions of variables can be formed with the help of 3 main operations ...