Minimal Boolean Formulas (2011)

[OscarCunningham]

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....

[AaronFriel]

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

[Sharlin]

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.

[dooglius]

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]

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.

[lilyball]

The example parity function for 3 variables appears to be flipped. Instead of being true if the number of true inputs is odd, it's true if the number of true inputs is even.

[fallat]

How is Russ so f'ing cracked. The brain on this human. 99.9% of us will never touch his intelligence.

[senderista]

(From 2011)

[cluckindan]

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.

[_kb]

From what I’ve had exposure to conjunction, disjunction, and negation symbols are common if you’re discussing logic [1].

Boolean algebra then use product, sum, and complement [2].

Both can express the same thing. In this case `*` is easier to type than `·`.

[1]: https://simple.industries/notes/propositions.html

[2]: https://simple.industries/notes/boolean-algebra.html

[dse1982]

Isn't the AND operation often represented using multiplication notation (dot or star) because it is basically a boolean multiplication?

[bee_rider]

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.