As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
214 views

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

Is there a simple example of a monotone 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 ...
D.W.'s user avatar
  • 152k
8 votes
1 answer
2k views

Which CNF boolean formulas blow up exponentially at conversion to DNF?

If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa). But what is an example of such a formula (and is there a ...
lukas.coenig's user avatar
0 votes
2 answers
387 views

Is 2QBF in P^NP?

2QBF is the following problem: given a CNF formula $\psi$ on $2n$ variables, determine the truth value of $$\forall x \in \{0,1\}^n . \exists y \in \{0,1\}^n . \psi(x,y).$$ Question: Is 2QBF in $P^{...
D.W.'s user avatar
  • 152k
7 votes
1 answer
5k views

What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in ...
Charlie Parker's user avatar
6 votes
1 answer
313 views

Why are there two not operators in lambda calculus?

From Wikipedia: $\mathrm{true} = \lambda a. \lambda b. a$ $\mathrm{false} = \lambda a. \lambda b. b$ Because true and false choose the first or second parameter they may be combined to provide logic ...
HappyFace's user avatar
  • 191
5 votes
2 answers
999 views

Sensitivity and Block sensitivity

May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity. Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function. Let ...
Turbo's user avatar
  • 2,862
2 votes
1 answer
141 views

Learning a small disjunction

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form $$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$ but I don't know the values of $i_1,\dots,i_k$. ...
D.W.'s user avatar
  • 152k
2 votes
1 answer
93 views

Conjunctive normal form to simple elementary algebra

I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra. An example: $$\phi=\left(x_1 \vee x_2 \right) \wedge \...
Ben Crossley's user avatar
2 votes
1 answer
57 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
Ben Crossley's user avatar
1 vote
1 answer
59 views

Relationship between circuit size and formula size in Sipser text

The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can ...
ShyPerson's user avatar
  • 911
1 vote
3 answers
2k views

How many 3-SAT expressions with up to N variables are satisfiable?

TL;DR There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
Tomas Reimers's user avatar
0 votes
2 answers
56 views

Two's complement using logic gates

How can a 4-bit two's complement operation be implemented using boolean NOR gate? I search lots of 4-bit two's complement videos and articals, but most of them are using XOR gate.
Colin Newmann's user avatar
0 votes
0 answers
28 views

Is this a valid method to merge clauses in CNF formulas?

Assume $$C_1 = (x_1 \lor x_2 \lor \lnot x_3)\hspace{0.2cm} C_2 = (x_4 \lor x_5 \lor x_3) \hspace{0.2cm} C_3 = (x_3 \lor x_5 \lor x_6)$$ Let $$ \phi_1 = C_1 \land C_2 \land C_3$$ and $$ \phi_2 = (x_1 \...
C Marius's user avatar
  • 185
0 votes
1 answer
89 views

Understanding kQBF: changing order of quantification?

2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(...
rus9384's user avatar
  • 1,393