Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
231 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
  • 158k
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
438 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
  • 158k
7 votes
1 answer
6k 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
356 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
0 answers
158 views

Can minimal CNF contain clause longer than initial CNF?

Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$. Can $\Phi_{min}$ contain a clause of size $m > k$? What I ...
rus9384's user avatar
  • 1,600
5 votes
2 answers
1k 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,891
2 votes
1 answer
59 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
2 votes
1 answer
99 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
146 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
  • 158k
1 vote
1 answer
71 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
  • 923
0 votes
1 answer
101 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,600
0 votes
2 answers
152 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