Boolean Algebra Exercises v1-07-with answers PDF

Preview

Summary

Boolean Algebra ExercisesTry these exercises. They get progressively harder. The answers and working out areprovided at the end of this document. Don’t look at the answers till you have attempted thequestions. It may help if you go through the laws of Boolean Algebra which are set out onpages 3 to 5...

Description

V1 – 07

Boolean Algebra Exercises Try these exercises. They get progressively harder. The answers and working out are provided at the end of this document. Don’t look at the answers till you have attempted the questions. It may help if you go through the laws of Boolean Algebra which are set out on pages 3 to 5. (1) a + 0 = ……….. (2) .0 = ……….. (3) a + a  = ……….. (4) a + a = ……….. (5) a + ab = ……….. (6) a + b = ……….. (7) a( + b) = ……….. (8) ab + b = ……….. (9) ( +  )( + b) = ……….. (10) a(a + b + c + d) = ………..

(11) Look at the expression X.Y.Z + ( X. Y. Z). Does its’ value change with different values of X, Y and Z? ……….. (12) Can you simplify the expression X ( YZ + XY) ? ………..………..……….. (13) Using De Morgan’s Law can you write an expression for the inverse of X ( Y + Z) ? This is the equation X( Y + Z) ? ………..………..………..……….. (14) Show that ( X + Y) ( X + Y) ( X + Z) = XZ ………..………..………..……….. (15) Prove that XYZ + XZ = Z(X+ Y) ………..………..………..……….. (16) Prove that ( X + Y) (X +  Y) is always false ………..………..………..……….. The next 3 problems are from UTSOnline – Web Systems (17) Prove not((x or y) and z) = (not(x) and not (y)) or not(z) It may help to restate the problem as:  +  )Z = (    ) +  prove (

V1 – 07 (18) (not(x) or y) and not(z) = not(x or z) or (y and not(z)) It may help to restate the problem as:  ) Prove (  + Y ) = ( +  ) + ( Y (19) not(not(x) and not(y)) = x or y It may help to restate the problem as:  ) = X +Y Prove (  

V1 – 07

The Laws of Boolean Algebra Law Inverse law

And form

Or form

 = 0 (  ) Note: this expression is the same as .  In many cases the . is left out. The AND operation is only true when both inputs are true. When a Boolean value and its inverse are both inputs into an AND operation, then one of the inputs must be false. Therefore the output is always false.

Idempotent Law. This is similar to the Inverse Law except that a Boolean variable is both inputs into an AND or OR operation. Although the number of inputs is two, effectively the number of inputs is cut down to one since the two inputs will be identical.

 +  = 1 ( ) The OR operation is true when one or both inputs are true. When a Boolean value and its inverse are both inputs into an OR operation, then one of the inputs must be true. Therefore the output is always true.

 = 

+  = 

The AND operation is only 1 (true) when both inputs are 1 (true). When a Boolean variable is made to be both inputs into an AND operation, if the variable is 1 (true) then the output is 1 (true). If the variable is 0 (false) then the output is 0 (false). In other words the output value is the same as the input value.

The OR operation is 1 (true) when at least one inputs is 1 (true). When a Boolean variable is made to be both inputs into an OR operation, if the variable is 1 (true) then the output is 1 (true). If the variable’s value is 0 (false) then the output is 0 (false). In other words the output value is the same as the input value

V1 – 07

Law Identity Law

Null (or Dominance) Law

Commutative Law

Associative Law

And form

Or form 1 = 

+ 0 = 

The AND operation is only true when both inputs are true. When a Boolean value and a value of 1 (or true) is an input into an and operation, then the value of the output is the value of the other input.

The OR operation is true when one or both inputs are true. When a Boolean value of zero (or false) and a Boolean variable are the inputs into an OR operation, then the output will be determined by the value of the Boolean variable.

0  = 0(  )

 + 1 = 1 ( )

The AND operation is only true when both inputs are true. When a Boolean value of 0 (or false) is one of the inputs then the output is always false.

The OR operation is true when one or both inputs are true. When a Boolean value of one (true) and a Boolean variable are the inputs into an OR operation, then at least one of the inputs is true, so the output must be true. The actual value of the variable is irrelevant.

AB = BA

A+B=B+A

The order of the operation is not important – A AND B is identical to B AND A

The order of the operation is not important – A OR B is identical to B OR A

(A B)C = A(BC)

(A + B ) + C = A + (B + C)

If we have three or more inputs to an AND operation we can AND any two of them and then AND the result of that operation with the remaining inputs.

Distributive Law

If we have three or more inputs to an OR operation we can OR any two of them and then OR the result of that operation with the remaining inputs.

A ( B + C ) = AB + AC

A + BC = (A + B)(A+C)

A AND B OR C is the same as A AND B OR A AND C

A OR B AND C is the same as A OR B AND A OR C

V1 – 07

Law Absorption Law

De Morgan’s Law

And form A ( A + B) = A

A + AB = A

If we expand this expression we get the expression AA + AB. It can be seen that if A is true then AA is true. If AA is true, then the complete expression is true.

If we factorise this expression we get the expression A (1 + B). This means we have two inputs to an AND operation. It can be seen that one input, the expression (1 + B) is always true whatever the value of B. Therefore, the value of the expression becomes whatever the value of A is.

  ) . = ( + 

  +  =   .  

NOT A AND NOT B is the same as NOT ( A OR B) Double Complement Law

Or form

NOT A OR NOT B is the same as NOT ( A AND B)  = A

This law simply says that the inverse of the inverse of something is the thing itself.

V1 – 07 (1) a + 0 = a Can be established by simple reasoning or by using a simple OR truth table with one side always 0 or by using the identity law. (2) .0 = 0 Can be established by simple reasoning or by using a simple AND truth table with one input always 0, hence the output will always be 0. Alternatively cite the Null or dominance law. =1 (3) a + a Can be established by simple reasoning or by using a simple OR truth table. One input will always be 1. Hence the output will always be 1. Alternatively cite the Inverse law. (4) a + a = a Can be established by simple reasoning or by using a simple OR truth table. Both inputs will be 1 or both inputs will be 0. Hence the output will always be the same as the input. Alternatively cite the idempotent law (5) a + ab = a

If we factorise this expression we get the expression a (1 + b). This means we have two inputs to an AND operation. It can be seen that one input, the expression (1 + b) is always true whatever the value of b (Null or Dominance law). Therefore, the value of the expression becomes whatever the value of a is. If a is true the whole expression is true. If a is false then the whole expression becomes false. Alternatively cite the Absorption law (6) a + b = a + b We can use the Distributive Law. That is: A + BC = AB + BC Let A = a, b = B and C =  Then the expression a + b becomes A + CB which is ( A + C )(A + B) (Distributive Law) substituting back a, b and  the expression becomes ( a + ) ( a + b ) but ( a + ) = 1 (Inverse Law) So the expression becomes: (1)(a + b) which is: (a + b)

V1 – 07 (7) a( + b) = ab The expression expands to a + ab but ais always false and can be ignored. The expression becomes ab. (8) ab + b = b The expression can be factorised into b( a +  ). The second term ( a +  ) is always true so the expression becomes whatever the value of b is. (9) ( +  )( + b) =  The expression in brackets can be expanded out to become:  + b + a + b The first term becomes , the last term becomes 0, so the expression becomes  +  b + a Factorising the  out the expression becomes (1 + b +  ). The term (1+ b +  ) is 1, so the expression becomes 1, which is . (10) a(a + b + c + d) = a Expanding the expression it becomes: aa + ab +ac +ad The aa can be replaced with a, so the expression becomes: a + ab + ac + ad which can be refactored as: a(1+b+c+d) the term ( 1 + b + c + d ) can be replaced by 1, so the expression becomes a(1) which is a.

(11) Look at the expression X.Y.Z + ( X. Y. Z). Does its’ value change with different values of X, Y and Z? A: No. The expression is always true. The term X.Y.Z can be replaced by the t erm A. The expr ession t hen becomes A + , which is 1 which is t rue.

(12) Can you simplify the expression X ( YZ + XY) ? Yes, it’s XYZ

V1 – 07

Expanding the expression X ( YZ + XY) , it becomes XYZ + XXY, but t he second t er m cont ains XX which is false, so we can dr op the second term. The expr ession becomes XYZ

(13) Using De Morgan’s Law can you write an expression for the inverse of X ( Y + Z) ? The inverse is X(Y + Z) (14) Show that ( X + Y) ( X + Y) ( X + Z) = XZ Expanding t he fir st two br acket s we get: ( XX + XY +  + Y) (X + Z) but XX can be r eplaced by X, Y is alw ays false, so it can be ignor ed. The expr ession becomes ( X + X Y + ) ( X + Z) . The term in the first set of brackets bracket can be

factorised so it becomes ( X + X (Y + ) ), but ( Y + ) is always true, so the first term becomes ( X + X (1)) which is X. So the whole expression becomes X (X + Z) . Expanding this it becomes XX + XZ. But the first term, X is alw ays false, so it can be ignor ed. The expr ession then becomes XZ.

(15) Prove that XYZ + XZ = Z(X+ Y) Take the RHS Z(X+ Y) and expand it . Z(X+ Y) = ZX + ZY Take the ZY term and multiply it by ( X + X) (t his t erm is equal to 1 so it does not change the value of the equation. The expr ession becomes: ZX + ZY( X + X). Expanding the br ackets, it becomes: ZX + ZYX + ZY This expr ession can be factor ised int o ZX( 1 + ZY) + ZY The t erm ( 1 + ZY ) can be r eplaced by 1, t he expr ession becomes: ZX + ZY w hich is XYZ + XZ

(16) Prove that ( X + Y) (X +  Y) is always false This can be proven by applying de Morgan’s law to both expressions in brackets.

V1 – 07

  ). The second term becomes ( ) which can be simplified to The first term becomes (  XY which can be arranged to X Y  . Since X is (XY). The whole expression becomes  always false and Y is also always false, the whole expression is always false. The next 3 problems are from UTSOnline – Web Systems (17) Prove not((x or y) and z) = (not(x) and not (y)) or not(z) It may help to restate the problem as:     ) +  prove  (  +   )  = ( Let A = X+Y, then LHS becomes  (de Morgan’s law). Substituting ( X + Y ) back for A we   + , which can be transformed to  + get: ( + LHS =  ) +  

 )  can be transformed into    (de Morgan’s law) (  +  but     ) +   which is the value of the RHS. so the LHS becomes (  (18) (not(x) or y) and not(z) = not(x or z) or (y and not(z)) It may help to restate the problem as: )  +  ) + ( Y Prove (  + Y ) = ( Take the RHS  ( +  ) can be transformed to   (de Morgan’s law)  So the RHS becomes   + Y  so that the expression becomes This can be factorised by taking out the   + Y ) which is the value of the LHS ( (19) not(not(x) and not(y)) = x or y It may help to restate the problem as:  ) = X +Y Prove (    ) component can be transformed to ( Take the LHS. The (    + ) using de Morgan’s law. (  + ) ) . Notice that there are two negations at the top of the expression. These The LHS is now ( cancel each other out (Double Complement law), so the expression becomes ( X + Y ) which is the RHS.

V1 – 07...