OSDev.org

hiya,

in my computing class, we are learning about de morgan's law. what i was wondering is if there was an easier way of showing that 2 boolean equations are equal?

atm, we use the long method of writing out the schematic then making truth tables, but is there an faster way around this?

if there is, could you please explain using the equation in the attached picture.

I am not sure about either your wording or your notation. (Slash above means NOT, I know that. Point means OR, plus means AND?)

So, you are looking for an easier way to prove DeMorgan's law than truth tables? AFAIK, there is none. You could go through association and distribution laws, but that's even more involved than truth tables (and not as instructive). But you'll never have to prove DeMorgan's law again; it's one of the building blocks of Boolean logic. (Like you don't have to prove that 1+1=2.)

So I am not quite sure if that answers your question?

Solar wrote:I am not sure about either your wording or your notation. (Slash above means NOT, I know that. Point means OR, plus means AND?)

Actually I think you're wrong,point means AND,plus means OR.
about de morgan's law take a look.

I know DeMorgan, studied it myself. It's the notation, and why one would want to "optimize" a mathematical proof that you'll never do again in your lifetime.

(In class, ee used the "correct" notation of v for "or", ^ for "and". I've seen the point-and-plus notation for the first time in this thread.)

Solar wrote:I know DeMorgan, studied it myself. It's the notation, and why one would want to "optimize" a mathematical proof that you'll never do again in your lifetime.

(In class, ee used the "correct" notation of v for "or", ^ for "and". I've seen the point-and-plus notation for the first time in this thread.)

Point-and-plus notation is used to create a canonical form boolean equation/statement, and is heavily used in cryptography and in hardware (used a lot in karnaugh maps).

The v/^ form is used more in the theoretical/mathematical classes, at least at our university.

Solar wrote:I am not sure about either your wording or your notation. (Slash above means NOT, I know that. Point means OR, plus means AND?)

No, the other way round. The dots mean AND and the plus means OR. Usually you use * for AND, because it fits the precedence over +, like AND has a higher precedence than OR.

Solar wrote:So, you are looking for an easier way to prove DeMorgan's law than truth tables? AFAIK, there is none. You could go through association and distribution laws, but that's even more involved than truth tables (and not as instructive). But you'll never have to prove DeMorgan's law again; it's one of the building blocks of Boolean logic. (Like you don't have to prove that 1+1=2.)

Well, prooving it mathematically/by logic is another way than prooving it by truth tables. The "truth tables way" uses the "complete enumeration", that is practical if you have only two variables (a, b) with two possible values (0, 1 / false, true) each. But remember, the Boolean Algebra that we use is the smallest possible. If you have more possible values then complete enumeration isn't practical.

The way of using the axioms and some well-known calculation rules (derived from the axioms) is the most generic one. The "truth table way" is easier because you don't have to think, just calculate, and finally compare the results.

For time consumption - well, the "truth table way" works well for low variable count (let's say 1 to 4 variables). For more variables it will get very annoying and your concentration will decrease so it's likely you make an error (just writing a single wrong value (0 instead of 1, or vice versa) is very bad). For the "maths/logic way" it depends mainly on the length of the formulas, the complexity of the terms, the bracketing (depth of bracketing) and your practice. If you have much practice you'll see very quickly with which terms you can do what and can use some tricks (like '+ (A * not(A))' or something).

I, personally, found that the algebraic way is the better for me. But that is a personal taste.

xDDunce wrote: if there is, could you please explain using the equation in the attached picture.
[Picture: DeMorgans law]

[anecdote]
At my university there was an exam on which they asked "Can DeMorgan be proved mathematically? Yes/No". The right answer was "Yes". Then, a year later the same question in the same exam. The suggested solution had "No" as the right answer. So, now, what's right?
[/anecdote]

I think you can proove it. If I have time, later this afternoon, I'll look for my algebraic proof of DeMorgan that I wrote down some time. If I find it, I'll post it here.

--TS

Hyperdrive wrote:I think you can proove it. If I have time, later this afternoon, I'll look for my algebraic proof of DeMorgan that I wrote down some time. If I find it, I'll post it here.

Okay, too late. Wikipedia has it. And it looks pretty the same as my solution IIRC.

--TS

hiya,

This notation is adapted for easier understanding in the course i'm doing (so it isn't exactly the generic way of writing it, but it is an easier way for non-mathematical students - half my class took the course thinking it was just advanced ICT which demonstrates alot. lol).

my question is not "how can i prove it works?" because, of course, i don't want to go and re-invent the wheel. but rather "is there an easier way of simplifying this equation, than drawing a schematic and writing a truth table for the circuit?"

i can convert the equation into the mathematical equivalent, if you think it may be easier?

thanks in advance,
James.

xDDunce wrote:my question is not "how can i prove it works?" because, of course, i don't want to go and re-invent the wheel. but rather "is there an easier way of simplifying this equation, than drawing a schematic and writing a truth table for the circuit?"

Ah, you ask for simplfying... Like you have a really biiig formula and you want to "minimize" it, so that it comes down to some very simple terms? Am I right?

Then you can try Karnaugh maps, which is only really practical up to 4 variables. You can also try the Quine-McCluskey algorithm, which IMO is very very cool (but IIRC NP-complete, which is sad and bad). There are more methods for minimization (like the tabular method), you maybe want google "minimization".

--TS

Hi,

De - Morgan's Law
(a) (a + b) ' = a’. b'
(b) ( a . b )' = a ' + b '

{ Easy way to remember : replace all variables by their complements , replace 'or' by 'and' and 'and' by 'or' }
So you know that (x')' = x

So treating expression as (( a . b' + a' .b)')' = ( ( a' + b) . ( a + b') )' (Applying De Morgan law) . All this is very elementary; you shall do your home work well. At least you should take an effort from your side. Proving, solving usually requires
(a) Algebraic Simplification
(b) The method of prime implicates
(c) K- Maps (only till 5 variables ,after that it gets very complex)

Proof of De- Morgan
we know that x . x ' = 0
so if ( a '. b' ) is a complement of ( a + b ) then ( a ' . b ' ) . ( a + b ) should be zero
which is zero using distributive laws . I really do not want to spoon feed you here .The second law also can be proved similarly.

Regards
Shrek

thanks shrek, that was exactly what i was looking for but i had JUST managed to work it out before i saw your post.

took me bout 6 hours to work it out. but i got there

thanks for the help guys, you just helped me earn an easter egg

Glad that you did find it yourself .

Regards
Shrek