Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Minimal Boolean Formulas (2011)

research.swtch.com

Post reply on HN
Print view View original

11–20 of 21 posts

Re: Minimal Boolean Formulas (2011)

#11

Post by dse1982 »

WorldMaker wrote: post #9
dse1982 wrote: post #7

Earlier quoted context omitted.

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

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…

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.

Re: Minimal Boolean Formulas (2011)

#12

Post by o11c »

dooglius wrote: post #10

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.

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.

Re: Minimal Boolean Formulas (2011)

#14

Post by _kb »

cluckindan wrote: post #5

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.

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

Re: Minimal Boolean Formulas (2011)

#16

Post by wasabi991011 »

WorldMaker wrote: post #9
dse1982 wrote: post #7

Earlier quoted context omitted.

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

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…

Do you really need to introduce category theory for that?

Seems like overkill, abstract algebra seems sufficient to categorize both boolean logic and integer operations as having the common structure of a ring.

Re: Minimal Boolean Formulas (2011)

#17

Post by WorldMaker »

wasabi991011 wrote: post #16
WorldMaker wrote: post #9

Earlier quoted context omitted.

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…

Do you really need to introduce category theory for that? Seems like overkill, abstract algebra seems sufficient to categorize both boolean logic and integer operations as having the common structure of a ring.

Of course you don't "need" to introduce category theory for that, which is why I saved it for fun at the end. I just think it is neat. It's also one of those bridges to "category theory is simpler than it sounds", which is also why I disagree with it being "overkill" in general in part because that keeps category theory in the "too complex for real needs" box, which I think is the wrong box. Which, case in point:

> […] abstract algebra seems sufficient to categorize both boolean logic and integer operations as having the common structure of a ring.

I don't think Ring Theory is any easier than Category Theory to learn/teach, I rather think that Category Theory is a subset of some of best parts of abstract algebra, especially Group Theory, boiled down to the sufficient parts to describe (among other things) practical function composition tools for computing.

Re: Minimal Boolean Formulas (2011)

#18

Post by yorwba »

WorldMaker wrote: post #9
dse1982 wrote: post #7

Earlier quoted context omitted.

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

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…

> digital representation of booleans implies that integer multiplication still applies

Yes. Multiplication of unsigned 1-bit integers is the same function as boolean AND.

Re: Minimal Boolean Formulas (2011)

#19

Post by AlotOfReading »

WorldMaker wrote: post #9
dse1982 wrote: post #7

Earlier quoted context omitted.

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

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…

I would normally interpret "Boolean multiplication" as multiplication over GF(2), where + would be XOR. This notation is fairly common when discussing things like cryptography or CRCs.
Post reply on HN