Minimal Boolean Formulas (2011)
research.swtch.com
Minimal Boolean Formulas (2011)
1–10 of 21 posts
Re: Minimal Boolean Formulas (2011)
#2(From 2011)
Re: Minimal Boolean Formulas (2011)
#3We 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....
Re: Minimal Boolean Formulas (2011)
#4The 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.
Re: Minimal Boolean Formulas (2011)
#5Using 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.
Re: Minimal Boolean Formulas (2011)
#6Using 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.
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.
Re: Minimal Boolean Formulas (2011)
#7Using 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.
Isn't the AND operation often represented using multiplication notation (dot or star) because it is basically a boolean multiplication?
Re: Minimal Boolean Formulas (2011)
#8Surprised not to see Karnaugh maps mentioned here, as a tool for humans to intuitively find these simplifications.
Re: Minimal Boolean Formulas (2011)
#9Using 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.
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 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.
Re: Minimal Boolean Formulas (2011)
#10Could 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.