[HN Gopher] Minimal Boolean Formulas
___________________________________________________________________
Minimal Boolean Formulas
Author : mcyc
Score : 71 points
Date : 2025-06-20 13:53 UTC (3 days ago)
(HTM) web link (research.swtch.com)
(TXT) w3m dump (research.swtch.com)
| senderista wrote:
| (From 2011)
| OscarCunningham wrote:
| We also know the optimal circuits if you want to compute two
| boolean functions from four variables at the same time:
| https://cp4space.hatsya.com/2020/06/30/4-input-2-output-bool....
| Sharlin wrote:
| The standard Floyd-Warshall is fairly easily parallelizable. I
| wonder how fast you could solve this problem with today's GPUs,
| and whether a(6) might be attainable in some reasonable time.
| cluckindan wrote:
| Using the * operator for AND is very non-standard. Unicode
| provides ! for negation, [?] for conjunction and [?] for
| disjunction. These are commonly used in CS literature, along with
| bar(s) over variables or expressions to denote negation, which
| are definitely a mixed bag for readability.
| bee_rider wrote:
| It is not so uncommon to see it represented by a dot. I guess a
| star is like a dot, but doesn't require finding any weird keys.
| It isn't ideal but it is obvious enough what they mean.
| dse1982 wrote:
| Isn't the AND operation often represented using multiplication
| notation (dot or star) because it is basically a boolean
| multiplication?
| WorldMaker wrote:
| It's not so much that it is "boolean multiplication" (because
| how do you define that, also because digital representation
| of booleans implies that integer multiplication still
| applies) so much as AND follows similar Laws as
| multiplication, in particular AND is _distributive_ across OR
| in a similar way multiplication is distributive over
| addition. [Example: a * (b + c) <=> a * b + a * c] Because
| it follows similar rules, it helps with some forms of
| intuition of patterns when writing them with the familiar
| operators.
|
| It's somewhat common in set notations to use * and + for set
| union and set intersection for very similar reasons. Some
| programming languages even use that in their type language (a
| union of two types is A * B and an intersection is A + B).
|
| Interestingly, this is why Category Theory in part exists to
| describe the similarities between operators in mathematics
| such as how * and [?] contrast/are similar. Category Theory
| gets a bad rap for being the origin of monads and fun phrases
| like "monads are a monoid in the category of endofunctors",
| but it also answers a few fun questions like why are * and
| [?] so similar? (They are similar functions that operate in
| different "categories".) Admittedly that's a very rough, lay
| gloss on it, but it's still an interesting perspective on
| what people talk about when they talk about Category Theory.
| dse1982 wrote:
| Thx for your thorough explanation! I don't know much about
| these things, just thought about similarities in the
| algebraic properties, especially with regards to the zero-
| element: 0*1=0.
| AaronFriel wrote:
| Surprised not to see Karnaugh maps mentioned here, as a tool for
| humans to intuitively find these simplifications.
|
| https://en.m.wikipedia.org/wiki/Karnaugh_map
| dooglius wrote:
| Could one do this directly with transistors or standard cells?
| Seems very useful for ASICs, particularly structured ASICs which
| are mapped from FPGA lookup tables of size 4-6.
| o11c wrote:
| This isn't quite as useful in practice as it seems, since NOT
| isn't always free, you almost always _can_ eliminate common
| subexpressions, and gates with more than two inputs are often
| cheaper than doing everything with two-input gates.
___________________________________________________________________
(page generated 2025-06-23 23:00 UTC)