Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am completely new to Boolean algebra, and I've tried to simplify this expression. All I did is tried to follow my lecturers methods, but I don't think it's right, and I have no idea how to do it.

¬a∧¬b∧¬c ∨ a∧¬b∧c ∨ a∧b∧¬c ∨ a∧b∧c

First, I picked out the "¬b"-s from the first two expressions, based on the distributive law:

¬b (¬a∧¬c ∨ a∧c) ∨ a∧b∧¬c ∨ a∧b∧c

Next, I picked up the "a"-s from the last two expressions based on the distributive law:

¬b (¬a∧¬c ∨ a∧c) ∨ a (b∧¬c ∨ b∧c)

Then, I thought I could cancel out "(¬a∧¬c ∨ a∧c)" completely, since they are opposite of each other (hope I'm right):

¬b ∨ a (b∧¬c ∨ b∧c)

Then again, I applied the distributive law to "pick out" the "b"-s:

¬b ∨ a (b (¬c∧c))

Next, I cancelled out "(¬c∧c)":

¬b ∨ a∧b

Then, applying negative absorption, I have removed "¬b", leading to:

a∧b

I am pretty sure I can't simplify this to a single AND gate, it is impossible for the truth tables to be the same, but I don't have a clue about the whole thing. Where did I misunderstand the applied rules, and what is the correct solution? (The work is really urgent and I appreciate your help very much. After this I won't even learn Boolean algebra - I am trying to be a sysadmin, not a hardware engineer :) )

share|improve this question
    
One issue that makes your proof hard to follows is the fact that $x\vee y \wedge z$ is ambiguous. You can mean $x\vee (y\wedge z)$ or $(x\vee y)\wedge z$. –  Hayden Nov 28 '13 at 1:36
    
Sorry about that... the expression I was trying to simplify is: (¬a∧¬b∧¬c) ∨ (a∧¬b∧c) ∨ (a∧b∧¬c) ∨ (a∧b∧c) Then I picked out "¬b" from the first 2 parts: ¬b (¬a∧¬c ∨ a∧c) ∨ (a∧b∧¬c) ∨ (a∧b∧c) Then I picked out "a" from the last 2 parts: ¬b (¬a∧¬c ∨ a∧c) ∨ a (b∧¬c ∨ b∧c) And I'm stuck here (my next step is wrong according to the first answer). –  user111982 Nov 28 '13 at 1:47
add comment

3 Answers 3

After third step, you cannot cancel (¬a∧¬c ∨ a∧c). You can cancel ¬(a∧c) ∨ a∧c but this is not the case. Remember also to respect the operators order: $$a ∧ b ∨ c$$ means $$( a ∧ b ) ∨ c$$

p.s. in my opinion, evereone(engineer, sys admins, lawers ...) must learn boolean algebra :) .

share|improve this answer
    
I see, thanks. Well, I'd like to understand it better too :D Can I simplify it further after the first two steps, or do I need a different start in the first place? (and what would be the best exactly?) I'll post my next attempt in a bit –  user111982 Nov 28 '13 at 1:53
    
Here's my next try... I have removed the "¬a∧¬c" and the "¬c" according to negative absorption: ¬b (a∧c) ∨ a (b ∨ b∧c) Am I correct or why not - and can I simplify it further? –  user111982 Nov 28 '13 at 2:13
    
A goog resource for compuiting boolean expression. Here you can find the solution for your particular problem. wolframalpha.com/input/… –  Redjan Shabani Nov 28 '13 at 2:17
add comment

I'm afraid that you cannot simplify $a\wedge c\vee\neg a\wedge\neg c$ as $1.$ Let's consider an expression of the form $$(d\wedge e)\vee(\neg d\wedge\neg e).$$ By distributivity, we have $$\bigl((d\wedge e)\vee\neg d\bigr)\wedge\bigl((d\wedge e)\vee\neg e\bigr),$$ and applying distributivity again gives us $$\bigl((d\vee\neg d)\wedge (e\vee\neg d)\bigr)\wedge\bigl((d\vee\neg e)\wedge (e\vee\neg e)\bigr),$$ which we can simplify to $$(e\vee\neg d)\wedge(d\vee\neg e).$$ That really isn't much simpler, so it isn't necessarily worth the effort.

You can simplify $a\wedge b\wedge\neg c\vee a\wedge b\wedge c$ as $a\wedge b,$ though, just as you did. Here's a bit of a slick trick (called idempotence) you can use: $p\vee p$ is the same as $p.$ What we can do, then, is note that the following are equivalent (parentheses inserted for a bit more clarity): $$(¬a∧¬b∧¬c) ∨ (a∧¬b∧c) ∨ (a∧b∧¬c) ∨ (a∧b∧c)\\(¬a∧¬b∧¬c) ∨ (a∧¬b∧c) ∨ (a∧b∧¬c) ∨ (a∧b∧c) ∨ (a∧b∧c)\\(¬a∧¬b∧¬c) ∨ (a∧¬b∧c) ∨ (a∧b∧c) ∨ (a∧b∧¬c) ∨ (a∧b∧c)\\(¬a∧¬b∧¬c) ∨ (a∧¬b∧c) ∨ (a∧b∧c) ∨ \bigl(a∧b∧(¬c∨c)\bigr)\\(¬a∧¬b∧¬c) ∨ (a∧¬b∧c) ∨ (a∧b∧c) ∨ (a∧b)\\(¬a∧¬b∧¬c) ∨ \bigl(a∧(¬b ∨ b)∧c\bigr) ∨ (a∧b)\\(¬a∧¬b∧¬c) ∨ (a∧c) ∨ (a∧b)\\(¬a∧¬b∧¬c) ∨ \bigl(a∧(c ∨ b)\bigr)\\(¬a∧¬b∧¬c) ∨ \bigl(a∧(b ∨ c)\bigr)\\\bigl(a∧(b ∨ c)\bigr) ∨ (¬a∧¬b∧¬c)$$

All of that just used idempotence, inverse, distributivity, identity, and commutativity properties. This is pretty much as simple as it gets. At this point, we could use DeMorgan's laws to write $\neg b\wedge\neg c$ as $\neg(b\vee c).$ So, our expression becomes $$\bigl(a∧(b ∨ c)\bigr) ∨ \bigl(¬a∧¬(b\vee c)\bigr)$$ But this is just another expression of the form $(d\wedge e)\vee(\neg d\wedge\neg e),$ and as we saw above, there isn't much we can do with that if $d$ and $e$ are logically independent (as I assume that $a,b\vee c$ ought to be).

share|improve this answer
add comment

Thanks Cameron Buie.

Let's consider an expression of the form (d∧e)∨(¬d∧¬e).

By distributivity, we have

((d∧e)∨¬d)∧((d∧e)∨¬e),

and applying distributivity again gives us

((d∨¬d)∧(e∨¬d))∧((d∨¬e)∧(e∨¬e)),

which we can simplify to

(e∨¬d)∧(d∨¬e).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.