From The Essentials of Computer Organization and Architecture (2nd Edition)

 

pg 155

Using DeMorgan's Law, write an expression for the complement of F if F(w, x, y, z) = xyz'(y'z + x)' + (w'yz + x').

 

Firstly, I expressed the bracketed expression as x'y + x'z'.

Then, I evaluated the left addend to 0.

Left with the right addend, I found that F' = (w'yz + x')' = wx + (yz)'x.

 

The book, in the solutions, complements the entire function first and arrives at x' or y' or z or ((y'z + x)((w + y' + z')x)). Why doesn't my method work?

 

xtheunknown0

F' = (xyz'(y'z + x)' + (w'yz + x'))' = ((xyz')') + ((y'z + x)(w'yz + x')') = (x' + y' + z) + ((y'z + x)(w'yz + x')') = (x' + y' + z) + ((y'z + x)(wx + (yz)'x)) = x' + y' + z + ((y'z + x)((w + y' + z')x))

 

what exactly did you do?

 

(y'z + x)' = (y'z)'x' = ((y')' + z')x' = (y + z')x' = x'y + x'z'

 

xyz'(x'y + x'z') = xy(x'yz' + x'z') = x(x'yz' + x'yz') = xx'yz' + xx'yz' = xx'yz' = 0(yz') = 0 <==== this ????

 

F' = (w + y' + z')x

Edited April 19, 201114 yr by Xittenn

<br />F' = (xyz'(y'z + x)' + (w'yz + x'))' = ((xyz')') + ((y'z + x)(w'yz + x')') = (x' + y' + z) + ((y'z + x)(w'yz + x')') = (x' + y' + z) + ((y'z + x)(wx + (yz)'x)) = x' + y' + z + ((y'z + x)((w + y' + z')x))<br /><br />what exactly did you do?<br /><br />(y'z + x)' = (y'z)'x' = ((y')' + z')x' = (y + z')x' = x'y + x'z'<br /><br />xyz'(x'y + x'z') = xy(x'yz' + x'z') = x(x'yz' + x'yz') = xx'yz' + xx'yz' = xx'yz' = 0(yz') = 0    <====  this ????<br /><br />F' = (w + y' + z')x<br />

<br /><br /><br />

 

xyz'(y'z + x)' = xyz'x'y + xyz'x'z'

= 0 + 0

 

Yes, and I arrived at F' = (w + y' + z')x.

F' = x' + y' + z + ( (y'z + x) * ( (w + y' + z')x ) )

 

= ( ( x' + y' + z ) + ( y'z + x ) ) * ( ( x' + y' + z ) + ( (w + y' + z')x ) )

 

= ( 1 + y' + z + y'z ) * ( ( x' + y' + z ) + ( (w + y' + z')x ) )

 

= ( x' + y' + z ) + ( (w + y' + z')x )

 

= ( ( x' + y' + z ) + ( w + y' + z' ) ) * ( ( x' + y' + z ) + x )

 

= x' + y' + z + w + y' + z'

 

= 1

 

I can't find a direct algebraic manipulation that proves or disproves that (w + y' + z')x == x' + y' + z + ( (y'z + x)( (w + y' + z')x ) ). I believe that any algebraic operation taken that can eliminate a pathway needs to be considered before it is applied. That said if the two solutions are equivalent minus some extra information than the most appropriate answer would have been the one expected without the over simplification. I guess I would say take care to not eliminate a possible solution ... just my thoughts on the matter! I could be way off of course :/

 

(w + y' + z')x != 1 :/

X OR X' = TRUE

 

X AND X' = FALSE

 

You can only use DeMorgan Laws to simplify a boolean equation, but evaluation is only due to input

This x' + y' + z + ((y'z + x)((w + y' + z')x)) should actually be this ( x' + y' + z + (y'z + x) ) * ( (w + y' + z')x ) ... so I have to go over everything again.

 

X OR X' = TRUE

 

X AND X' = FALSE

 

You can only use DeMorgan Laws to simplify a boolean equation, but evaluation is only due to input

 

what?

 

 

 

 

Wait that allegiance makes the two equal and then it is safe to conclude that there is honestly no difference between either solution \o/

 

F' = (xyz'(y'z + x)' + (w'yz + x'))'

 

= (xyz'(y'z + x)')' * (w'yz + x')'

 

= ( (xyz')' + (y'z + x) ) * ( (w'yz)' * x )

 

= ( ( (xy)' + z ) + (y'z + x) ) * ( ( w + (yz)' ) * x )

 

= ( ( (x' + y') + z ) + (y'z + x) ) * ( ( w + ( y' + z') ) * x )

 

= (x' + y' + z + (y'z + x)) * (w + y' + z')x

 

= (1 + y' + z + y'z) * (w + y' + z')x

 

= (w + y' + z')x

 

 

(this is the first time I have done this)

 

 

= (xyz'(y'z + x)')' * (w'yz + x')' <=== I had moved the bracket here to conform to the expected answer :/

Edited April 21, 201114 yr by Xittenn

Wait that allegiance makes the two equal and then it is safe to conclude that there is honestly no difference between either solution \o/

 

F' = (xyz'(y'z + x)' + (w'yz + x'))'

 

= (xyz'(y'z + x)')' * (w'yz + x')'

 

= ( (xyz')' + (y'z + x) ) * ( (w'yz)' * x )

 

= ( ( (xy)' + z ) + (y'z + x) ) * ( ( w + (yz)' ) * x )

 

= ( ( (x' + y') + z ) + (y'z + x) ) * ( ( w + ( y' + z') ) * x )

 

= (x' + y' + z + (y'z + x)) * (w + y' + z')x

 

= (1 + y' + z + y'z) * (w + y' + z')x

1 + y' + z + y'z = y' + z

Why does y' + z = 1?

 

[F'] = (w + y' + z')x

Let me simplify this,

 

You have to apply one rule at a time,

 

F' = (xyz'(y'z + x)' + (w'yz + x'))'

 

= (xyz'(y'z + x)')' (w'yz + x')'

 

= ((xyz')' + (y'z + x)') (w'yz)' x

 

= ((xy)' + z) + ((y'z)' x') ((w'y)' + z') x

 

= ((x' + y' + z + (y + z')) x') ((w + y' + z') x)

 

Note that you have to keep the same structure of the equation when applying rules

 

= ((x' + y'x' + zx' + (y + z')x') (wx + y'x + z'x)

 

= (x'x' + y'x' + zx' + yx' + z'x') (wx + y'x + z'x)

 

= (x' + y' + z + y + z') (w + y' + z') x' x = FALSE = 0

 

Since ( x' x ) = FALSE = 0, simply because, it's a contradiction,

 

This results in,

 

F' = FALSE = 0, F = TRUE = 1

1 + y' + z + y'z = y' + z

Why does y' + z = 1?

 

Because 1 + a = 1 and 1 * a = a ... I never say that y' + z = 1; x' + x = 1 though :/

Edited April 21, 201114 yr by Xittenn

It seem you don't understand what is boolean algebra ...

 

you see every variable X is a logical statement,

 

Example: X = "It is raining", X' = "It is NOT raining"

 

X + X' = ( It is raining ) OR ( It is NOT raining ) = TRUE = 1, is a certainty

 

X X' = ( It is raining ) AND ( It is NOT raining ) = FALSE = 0, is a contradiction

 

1 = 1 + X = 1 OR X, here we don't care about X

 

1 = 1 . X = 1 AND X, here X has to be TRUE, X = 1

 

Relations between variables are defined according to the context,

 

Boolean Algebra is called Prepositional Logic,

 

A higher degree of this is used in AI, First Degree Logic

Because 1 + a = 1 and 1 * a = a ... I never say that y' + z = 1; x' + x = 1 though :/

 

Yeah...I can't remember why I posted that...