# Simplifying Boolean Expressions

• Jul 28th 2013, 01:43 AM
jpab29
Simplifying Boolean Expressions
Hello everyone! I apologize for posting often, but math help forum is my only help nowadays. I moved on to other questions of my assignment just to get some progress.

I'd greatly appreciate it if anyone would take a look at my work for me and tell me where I went wrong or if what I've done is right.

Here's the problem:
Attachment 28915

Here are my solutions. I am super confused with the laws and to what extent i can apply them on.

Attachment 28916

Attachment 28917

Thank you so much!
• Jul 28th 2013, 10:48 AM
emakarov
Re: Simplifying Boolean Expressions
I'll write ~x for $\displaystyle \bar{x}$.

a) is correct if you stop at the second last line, which is the simplest expression. Is the last line (y + ~z)(y + ~z)? Then it is incorrect because it does not have x.

In b) you did not change disjunction into conjunction going from line 1 to line 2. Also, x + 1 + ~z = 1, not 0.

In c), you did not copy a + between z and the term in square brackets. Also, what law did you use to go from line 1 to line 2?
• Jul 28th 2013, 09:47 PM
jpab29
Re: Simplifying Boolean Expressions
Quote:

Originally Posted by emakarov
I'll write ~x for $\displaystyle \bar{x}$.

a) is correct if you stop at the second last line, which is the simplest expression. Is the last line (y + ~z)(y + ~z)? Then it is incorrect because it does not have x.

In b) you did not change disjunction into conjunction going from line 1 to line 2. Also, x + 1 + ~z = 1, not 0.

In c), you did not copy a + between z and the term in square brackets. Also, what law did you use to go from line 1 to line 2?

Thank you so much for spotting my errors! I really needed it. Staring at my homework all night does that to me. :)

a) yes i meant the last line to be (y + ~z)(y + ~x) so i changed it now, so my second last line and last line are correct now that I changed it? :)

b) what is disjunction into conjunction? so sorry, can you demonstrate it for me? It seems funny i'm applying laws and I don't know disjunction and conjunction hehe

also, you said x + 1 + ~z =1, in my understanding becomes x(1 + ~z) by absorption law, the 1+~z here is 1 by ? will it always be equal to 1 even if the z is negated or not? like this:
1+~z=1 is the same as 1+z=1?

c. I did some corrections, is this right now? Thanks so much for your help.
Attachment 28918
• Jul 29th 2013, 02:17 AM
emakarov
Re: Simplifying Boolean Expressions
Quote:

Originally Posted by jpab29
a) yes i meant the last line to be (y + ~z)(y + ~x) so i changed it now, so my second last line and last line are correct now that I changed it?

I am not sure on what basis you think that (~z)x + y = (y + ~z)(y + ~x); they are not equal for x = 1 and y = z = 0. Besides, the left-hand side has three connectives while the right-hand side has five. Also, the lhs has thee occurrences of variables while the rhs has four. With respect to these usual measures, the left-hand side is simpler, and since the task was to simplify the expressions, the lhs should be the answer, unless you were told to have the answer is conjunctive normal form.

Quote:

Originally Posted by jpab29
b) what is disjunction into conjunction?

Disjunction is "or" denoted by +, and conjunction is "and" written as juxtaposition. When you apply De Morgan's laws, you change a disjunction into conjunction or vice versa. Thus, $\displaystyle \overline{(\bar{x}+y+z)}=x\bar{y}\bar{z}$.

Quote:

Originally Posted by jpab29
also, you said x + 1 + ~z =1, in my understanding becomes x(1 + ~z) by absorption law, the 1+~z here is 1 by ? will it always be equal to 1 even if the z is negated or not? like this:
1+~z=1 is the same as 1+z=1?

One of the popular laws says that 1 + a = 1 regardless of a, and the dual is that 0x = 0. I believe you used it under the name "dominance law". Thus, x + 1 + ~z = 1 + (x + ~z) = 1.

Quote:

Originally Posted by jpab29
c. I did some corrections, is this right now?

Now the expressions are indeed equal, but there are some minor remarks about the method. I still don't see how to convert wz(xy + wz) into wz(1 + xy) in one step. On the other hand, if you have the same absorption law as Wikipedia (where "and" is denoted by $\displaystyle \land$ and "or" by $\displaystyle \lor$), then wz(xy + wz) = wz directly by the absorption law (and commutativity). Similarly, I don't see how to convert z + wx into (z + w)(z + x) in one step using distributivity. The rhs equals z + zx + wz + wx, and then you need to factor out z and use dominance a couple of times to get z + wx. However, I may not know some laws that you are allowed to use. In any case, z + wx is simpler (w.r.t. the number of both connectives and variable occurrences) then (z + w)(z + x).
• Jul 29th 2013, 02:33 AM
jpab29
Re: Simplifying Boolean Expressions
I am still in the process of understanding conjunctive and disjunctive. I am really poor in using mathematical symbols. I have to read your reply many times. I'll reply to it again soon.

But for how to convert z + wx into (z + w)(z + x) in one step using distributive, i just followed this:

Attachment 28924
• Jul 29th 2013, 03:25 AM
emakarov
Re: Simplifying Boolean Expressions
Quote:

Originally Posted by jpab29
But for how to convert z + wx into (z + w)(z + x) in one step using distributive, i just followed this:

Attachment 28924

I am sorry. Of course, this is distributivity of disjunction ("or") over conjunction ("and"). If in arithmetic $\displaystyle x\times(y+z)=xy+xz$ is distributivity of multiplication over addition, then in Boolean algebra x(y + z) = xy + xz is distributivity of conjunction over disjunction, and x + yz=(x + y)(x + z) is distributivity of disjunction over conjunction. I got too much caught up in the notation, which resembles arithmetic, and in arithmetic the second type of distributivity does not hold.
• Jul 29th 2013, 03:45 AM
jpab29
Re: Simplifying Boolean Expressions
Quote:

Originally Posted by emakarov
I am sorry. Of course, this is distributivity of disjunction ("or") over conjunction ("and"). If in arithmetic $\displaystyle x\times(y+z)=xy+xz$ is distributivity of multiplication over addition, then in Boolean algebra x(y + z) = xy + xz is distributivity of conjunction over disjunction, and x + yz=(x + y)(x + z) is distributivity of disjunction over conjunction. I got too much caught up in the notation, which resembles arithmetic, and in arithmetic the second type of distributivity does not hold.

Haha! It's okay! I am actually learning a lot! But need to digest everythjng one by one. It's almost 5am here, I think I'm going to rest a bit. I'll be back 6 hours after. Thanks so much for your help! I an also working on the other areas of my assignment, and with the forum's help I am making big progress! Thanks so much!
• Jul 30th 2013, 12:10 AM
jpab29
Re: Simplifying Boolean Expressions
As I posted in the other thread, but just in case you didn't see it:

Emakarove, thank you so much for your help. My grades in math are actually dangerously failing, and week 5 (this last week) was my last chance. When I get the results back (hopefully I pass), I will post the answers I had here as help for future students who need.

Thanks again!