3
$\begingroup$

There are obvious analogs (pardon the pun) between Boolean algebra and algebra. They have similar laws, operators and properties. I can't figure out why Karnaugh Maps and sum of products, which are used to derive a Boolean function from a truth table, doesn't have an equivalent in algebra. Perhaps it does, but I haven't seen it.

My only explanation is that if it were possible, you could theoretically find a function for any arbitrary series of numbers (0, 2, 4, 6, 8 f(n)=2n). Thus, you could solve a ton of very difficult problems. I'm not necessarily looking for a formal proof but an explanation.

Right now, I am having fleeting ideas that it has something to do with infinite outputs and inputs, something to do with place values, or true or false equivalents in algebra. There's something here that's difficult to put my finger on.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Why can't you do what in algebra? A Karnaugh map is a well-organized table of all output values for a Boolean function. Surely you don't want a complete list of output values for a function $f\colon\mathbb{Z}\to\mathbb{Z}$, do you? $\endgroup$
    – JeffE
    Jul 1 '12 at 7:55
  • 1
    $\begingroup$ @JeffE: That said, you can do it over finite domains, e.g. $\mathbb{Z}/p$. I remember describing operations with complete tables in such cases. I am not sure how to exploit the "well-organised" aspect in those cases to get a compact representation of the function, though; is that what the question is about? $\endgroup$
    – Raphael ♦
    Jul 1 '12 at 9:45
  • $\begingroup$ @JeffE: Forgive me for my naive question as I am not a mathematician. The reason is a fleeting thought in my head and it's very hard to articulate. "Do what" means using karnaugh maps in standard algebra. $\endgroup$
    – user148298
    Jul 1 '12 at 18:36
  • 5
    $\begingroup$ @user148298: As with everything in mathematics, the devil in the details. What precisely do you mean by the phrase "use Karnaugh maps in standard algebra"? As it stands, you're essentially asking why you can't use something like a Philips screwdriver to make brownies. The knee-jerk answer is "because the two things have nothing to do with each other", but that's not entirely fair; maybe you have some half-baked idea in mind. (Answer: You can use the screwdriver to stir the batter, and later to test whether the brownies are done.) $\endgroup$
    – JeffE
    Jul 1 '12 at 20:15
  • $\begingroup$ @JeffE: Just refined my question. Raphael gave me some clues. When I say Karnaugh maps, I should be a bit more general, but I don't have the terminology for it. Essentially, the entire process of using truth tables and the sum of products (or Karnaugh maps) to derive a function from a set of inputs and outputs. Essentially, I am asking is there an analog to this in algebra since the rest of Boolean logic is fairly similar. To say they have nothing to do with each other, is like saying that the similarities are purely coincidental. $\endgroup$
    – user148298
    Jul 1 '12 at 20:25
4
$\begingroup$

There are two possible ways to define a non-boolean algebra.

  1. Stick with $\mathbb{F}_2 = \{0,1\}$ but choose base operations other than $\{\land, \lor, \lnot\}$.
  2. Change the base set entirely.

For the whole concept of simplification to word similarly to boolean algebra, we need two binary operations with associativity, commutativity and distributivity. Fields are the natural choice and, I think, the only one. Commutative rings might work but I suspect you get into trouble composing functions in a regular way if you don't have multiplicative inverse elements.

Infinite fields do not make sense here -- you can not draw an infinite table. So finite fields remain, of which there is exactly one per size (up to isomorphy).

So let us, for example, consider $\mathbb{Z}/5$ (the smallest field over $\mathbb{Z}$ with more than two elements and interesting inverses). Now try and formulate a function in a way that looks like a boolean function provided by Karnaugh maps, that is in additive (disjunctive) or multiplicative (conjunctive) normal form. We get to the core question:

What is the complement of a given element in a non-binary algebra?

The simple logic "if it's not one it's the other" does not work here. Note that the boolean complement does not correspond to the additive nor the multiplicative inverse, so there no hope there. So let's try and define a "complement"; say $\overline{a} = a + 1$ (which contains the boolean complement as special case). We note with unease that this new complement is not symmetric. I expect symmetry to be of essence; reading off from the Karnaugh map seems to rely on it.

So there is no way to get there with an odd number of elements; let's pick one with an even number (so we can pair elements for a complement relation). Now things become messy and I'll stop. After all, Wikipedia says that (emphasis mine)

the solution can be found by eliminating extra variables within groups using the axioms of boolean algebra

which characterise boolean algebra. Therefore -- provided that all axioms are needed for Karnaugh maps to work -- the concept does not work for non-boolean algebras.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.