Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
14
questions
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.♦
- 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 ...
- 743
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.♦
- 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 ...
- 2,960
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 ...
- 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 ...
- 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.♦
- 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 \...
- 201
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 ...
- 201
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 ...
- 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-...
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.
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 \...
- 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(...
- 1,393