Simple Boolean Algebra - bah

[Kantalope]

After googling til I am crazy and getting blown off by the professor...I needs helps.

Assignment: simplify boolean functions.

I won't give the exact one until the bottom because what I am looking for and what I can't find, is the strategy for solving these things. I have the techniques. The rules for boolean algebra are all over the place. But randomly giving it the DeMorgan treatment or factoring or whatever seems counter-productive. What I want to know, and what I have been unable to locate, is a way to figure out what rule to apply and when.

And while there may not be any dumb questions, there is a spectrum....I hope this problem is not too close to the margin.

So here is the equation: (x’y’+z)’ + z + xy + wz
help

[jemidiah]

I'm first trying DeMorgan's since it looks like it's applicable and it gets rid of the odd-man-out term that involves a '.

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

Well that doesn't seem helpful. We want to get something or other to cancel so we have to combine this term with the others. I'm gonna keep going in this direction since it might allow us to combine/cancel later terms.

(x+y)z' = xz'+yz' giving in all xz' + yz' + z + xy + wz

Continuing blindly, try to combine two of these terms to form one. I googled a list of boolean algebra rules (http://scitec.uwichill.edu.bb/cmp/online/P10F/rulesof.htm) probably like the one you have. Three rules involve multiple variables on that page so I look at them and see if any apply to get rid of a term.

I'm gonna try combining xz' + z with the A + A'B = A + B rule. Set A=z, B=x and reorder the terms to apply it.

xz' + z = z + x giving in all yz' + z + x + xy + wz

This didn't get rid of terms but we can apply this rule again--which seems promising. Maybe it'll lead somewhere.

yz' + z = z + y giving in all x + y + z + xy + wz

Well this is a bit sad. I can't see anything more to be done but there might be a rule that applies. On that page, A + AB = A which looks very promising since it gets rid of terms. Set A=x, B=y in one case and A=z, B=w in another to get these:

x+xy = x
z+zw = z
...in all y + x + z

Reordered prettily, (x'y'+z)' + z + xy + wz = x+y+z. I think that's as far as we can go--why? Because if I was making this problem I would start with some nice expression and apply some rules in reverse to get to something obscure.


I've documented my actual steps in solving this problem. Luckily I didn't go through a pointless step, but sometimes you will. In general I tried...

1. Get things in a form where terms might combine. This told me to work on the (x'y'+z)' term until it was factored down to monomials.
2. Apply whatever rules apply with the aim of reducing multiple terms down to fewer terms. Note that sometimes you'll have to apply rules that don't reduce the number of terms or maybe even increase the number of terms as intermediate steps--so try to lookahead in your mind to see if your rule might produce results later.
3. Imagine what you might do if you had made the problem.

There's no real algorithm for applying these, it's all intuition and brute force. [That's not to say in a technical sense that simplifying boolean algebra can't be done algorithmically--I'm sure a "minimum expression" is computable through something very brute-force.]

[Kantalope]

I think you found the problem my "intuiter" that I'm using for intuition isn't very effective. I go round and round and round never knowing if I'm getting anywhere really or not.

[jemidiah]

I wanted to mention that I didn't know the answer when I started writing that post, and I didn't delete anything. What I wrote was basically my thought process in attempting to solve it. Maybe you can glean something from that--or maybe you can study extra hard on the rest of your material and just hope for the best on this type of question on your exams :).

[Kantalope]

That did help. Thanks a ton. Now if I can convince the prof. that the midterm should have an infinite time allowance, I think I am all set....fingers crossed for epiphany.

k