# Questions tagged [boolean-algebra]

The tag has no usage guidance.

24 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
119 views

109 views

### Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? ...
42 views

### Maximal combinations in a Boolean algebra

Consider a finite set $X$ and the boolean algebra $\mathcal{P}(X)$ of the subsets of $X$. While I focus on $\mathcal{P}(X)$ in this question, the problem could be expressed more generally in any ...
50 views

### substituting expressions

I have a set of expressions $E_1 .. E_n$ over boolean variables and I'm looking for an assignment to the variables so that all expressions are satisfied. Normally this would be NP-complete, but I ...
97 views

### Methods for optimizing short-circuit evaluation for conditions of varying evaluation-cost

I have a bunch of boolean conditions, let's call them A, B, C, D, .... In my code, I need to use these conditions to distinguish between several different possible ...
51 views

### How do I get the NAND gate configuration for full adder from the logic table?

I'm self-studying, but I've gotten stuck already. If I'm given the logic table for a full-adder or any two-output table, how do I figure out the NAND-gate configuration, preferably methodically? ...
49 views

### Can I use the Quine-McCluskey to simplify a CNF which is not a product of maxterms?

As I understand it the Quine-McCluskey method allows you to start with a set of maxterms (or minterms), and combine them pairwise in a systematic way into a smaller set of clauses with a smaller set ...
36 views

### About sign-rank of Boolean functions

Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?