How can I solve a boolean algebra problem without using a Karnaugh table?

[Truthlover]

I don't know if it's ok to put this thread here. I have to say that's the first time i use boolean algebra and I'm not sure id i used the good theorem proprely. Sorry for the bad english. Thanks everyone.

Homework Statement

Solve this equation without using the Karnaugh table

Homework Equations

a'b'cd'+a'b'cd+a'bc'd+a'bcd+ab'cd+abc'd

The Attempt at a Solution

a'b'cd'+a'b'cd+a'bc'd+a'bcd+ab'cd+abc'd=

1+a'b'cd+a'bc'd+a'bcd+ab'cd=

1+b'cd*(a'+a)+a'bc'd+a'bcd=

1+b'cd*1+a'bc'd+a'bcd=

1+b'cd+a'bc'd+a'bcd=

1+b'cd+a'bd*1=

1+b'cd+a'bd

 

[wsalem]

The first step is incorrect (where did that 1 come from!), but suppose this step was correct, in particular
$$F = 1 + \overline{a} \overline{b} c d + \overline{a} b \overline{c} d + \overline{a} b c d + a \overline{b} c d$$

Let $$F = 1 + X$$ where $$X = \overline{a} \overline{b} c d + \overline{a} b \overline{c} d + \overline{a} b c d + a \overline{b} c d$$.

Apply theorem $$1 + X = 1$$ to conclude immediately that $$F = 1$$.

But, it is impossible for the original function to be reduced to $$F = 1 + X= 1$$ because your function is in canonical form (each term is a minterm containing all 4 variables), and you have only 6 min-terms. Since for a function to equal logic 1, its canonical form should contain all min-terms, i.e $$2^4$$ in case of a 4 variable function. This is equivalent to having all cells in the Karnaugh map equals 1.

You need to start over, and apply similar technique as you did correctly in your second, third and fourth steps. In particular apply commutative axiom (if needed) $$ABC = ACB$$, distributive axiom $$A (B + C) = AB + AC$$, theorem $$\overline{X} + X = 1$$, then theorem $$X 1 = X$$.

Keep in mind an important "trick", when you group two terms $$\overline{a} \overline{b} c \overline{d} + \overline{a} \overline{b} c d$$ to produce a simplified term, see if you still need anyone of the two to make further simplifications in the remaining terms of your function. This is due to theorem $$X + X Y = X$$. It is equivalent to using a cell more than one time to simplify adjacent cells in a Karnaugh map.

 

[Truthlover]

The one in the first resolution came from a'b'cd'+abc'd. Is it ok?

 

[wsalem]

No, please reread my previous reply, you just can't get a logic 1 no matter what!.

I can see where your confusion is,
The theorem $$X + \overline{X} = 1$$ is best read as
The sum of an expression and its complement is always 1

Now let us take $$X = \overline{a} \overline{b} c \overline{d}$$, it's complement $$\overline{X} \neq a b \overline{c} d$$, rather its complement is obtained by applying De Morgan theorem,

$$\overline{X} = \overline{\overline{a} \overline{b} c \overline{d}} = a + b + \overline{c} + d$$

Here's an easy way to remember this, with complements you "flip" not only the variables, but also the operators. The ANDs becomes ORs and ORs becomes ANDs.

To restate De Morgan Theorem(s)

$$\overline{A + B} = \overline{A} \cdot \overline{B}$$

$$\overline{A \cdot B} = \overline{A} + \overline{B}$$

Here's a very important thing to notice. $$\overline{a} \overline{b} c \overline{d}$$ is $$\overline{a} \cdot \overline{b} \cdot c \cdot \overline{d}$$, there's an AND between the variables that was omitted. It is very common among students to forget that, especially when applying De Morgan Theorem(s).Also, when you are unsure, just do a truth table. You would have known that $$a b \overline{c} d$$ is not the complement of $$\overline{a} \overline{b} c \overline{d}$$.

In case you are unsure how, derive the truth table for $$X = \overline{a} \overline{b} c \overline{d}$$.

Let a new column, labeled $$\overline{X}$$, consist of all values of $$X$$ where 1s are flipped to 0s and 0s are flipped to 1s, that is the complement of $$X$$

Now you suspect $$a b \overline{c} d$$ is the complement of $$X$$, derive its truth table, and compare to $$\overline{X}$$. You should find that they're quite different.

 

[Truthlover]

Thanks now I understand the problem i will post the solution as soon as I get it.

 

[Truthlover]

hello, sorry for the long time but i have got some problems to take care of before so here is the solution i have foun with your hints.

a'b'cd'+a'b'cd+a'bc'd+a'bcd+ab'cd+abc'd

a(bdc'+cdb')+b(cda'+da'c')+c(da'b'+a'b'd')

ad(bc'+b'c)+b(da'(c+c'))+c(a'b'(d+d'))

ad(b$$\oplus$$c)+bda'+ca'b'

ad(b$$\oplus$$c)+a'(bd+b'c)

 

[wsalem]

a'b'cd'+a'b'cd+a'bc'd+a'bcd+ab'cd+abc'd
=a'b'c(d'+d)+a'bd(c'+c)+ab'cd+abc'd
=a'b'c + a'bd + ab'cd + abc'd

Here we have a'bd, so we may introduce a'bc'd to get rid of the a in abc'd (reread my first reply), similary we have a'b'c, so introduce a'b'cd to get rid of the a in ab'cd
= a'b'c + a'bd + ab'cd + abc'd + a'bc'd + a'b'cd
= a'b'c + a'bd + (a + a')bc'd + (a + a')b'cd
= a'b'c + a'bd + bc'd + b'cd

This is the optimized sum of products expression, you should stop at this point.

There's no need for the xor, unless you were told to use it! Similarly do not (by default) group a'b'c + a'bd to get a'(b'c + bd), it may appear simpler but it is unwanted sometimes as it introduces an additional level.
For example, in a'b'c + a'bd, you have the OR coming from the general expression and you use only two ANDs, whereas the "simplified" a'.(b'.c + b.d) uses three ANDs and an additional OR!