Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
61
questions with no upvoted or accepted answers
9
votes
0
answers
175
views
Boolean formula that agrees with most truth assignments
Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}...
D.W.♦
- 156k
4
votes
0
answers
274
views
Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?
There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
- 339
4
votes
0
answers
33
views
Constructing xor separable boolean upper bound
Problem statement Suppose I have a boolean function $f: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2$ where $\mathbb{F}_2 = \{0,1\}$.
I define two boolean functions $h: \mathbb{F}_2^n \to \...
- 128
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.♦
- 156k
4
votes
0
answers
122
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 ...
- 1,429
3
votes
0
answers
105
views
Circuit complexity of hardest monotone function
Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such
that the minimal size of a monotone circuit that computes $f$ is
$\Omega(2^n / n^2)$. Use the fact that the number of ...
- 163
3
votes
0
answers
40
views
How do I optimize a set of sub-lists which can combine to recreate higher level lists?
I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list ...
3
votes
0
answers
138
views
Boolean function minimization
Does there exist a Boolean function for which no sum-of-products expression that minimizes the number of products also simultaneously minimizes the number of literals (counting repetitions)? ...
- 51
3
votes
0
answers
121
views
Iterating over a union of sets denoted by bitmasks
Consider the set $\mathbb{B}^n$ of all $n$-digit binary numbers. Let us define a bitmask as a tuple $M=(m_0,\ldots,m_{n-1})$, where $m_i\in \{0,1,*\}$.
Such bitmask denotes a set $S \subset \mathbb{B}^...
- 131
3
votes
0
answers
124
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 ...
- 223
2
votes
0
answers
85
views
Prove lower bound on boolean circuit
Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$:
$ A = \begin{...
- 95
2
votes
0
answers
44
views
closure property violated by palindrome language
It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
- 21
2
votes
0
answers
280
views
Examples of relatively complex truth tables/logic gates in real life?
I'm researching truth tables, logical gates, and boolean algebra expressions. I'm trying to find specific real-life examples of logic gates and/or truth tables used in algorithm or circuit design in ...
- 21
2
votes
0
answers
40
views
Simulating Boolean Circuit with RAM
Statement:
Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM).
Could you please supply me with a reference to an ...
- 161
2
votes
0
answers
231
views
Are there quantum algorithm that solve the boolean satisfiability problem in subexponential time?
Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they ...
2
votes
0
answers
49
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 ...
- 221
2
votes
0
answers
59
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 ...
- 2,469
1
vote
0
answers
19
views
Equivalent-symmetric (E-symmetric) variables check for Boolean functions
In [1], it states that checking $f(..., x_i, ..., \bar{x}_j, ...) = f(..., \bar{x}_j, ..., x_i, ...)$ (variables $x_i$ and $x_j$ are E-symmetric) is equivalent to checking $f_{x_ix_j} = f_{\bar{x}_i\...
- 11
1
vote
1
answer
76
views
Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.
Let's say I am doing 5 coin ...
- 11
1
vote
0
answers
75
views
Method for simplifying complex logic tables
Not sure if this is the right StackExchange site, but back in college (20 years ago) I took a Digital Systems Design class where we learned how to reverse engineer a boolean function to meet the ...
- 111
1
vote
0
answers
30
views
Fourier Dimension of Boolean functions
I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero ...
- 123
1
vote
0
answers
30
views
Is there an algorithm for generating non comparable boolean vectors?
First some context:
A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself.
The dynamical behavior of a ...
- 111
1
vote
0
answers
42
views
Efficient bit-level implementation of Boolean polynomials with few variables
A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form
$$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
- 11
1
vote
0
answers
45
views
Intuition for a 2-Monotone Boolean Function
I am currently studying Chapter 8 of Krama and Hammer's textbook on Boolean Functions, and having a hard time understanding what it means for a function to be "k-monotone."
I am currently ...
- 429
1
vote
0
answers
84
views
What is the intuitive logic behind the working of the Variable Entered K-Map (VEM)?
In this site here they have just said how to minimize a function using VEM. But no intuitive logic behind the same has been stated, making it too mechanical. And I am very bad at memorizing things, so ...
- 1,112
1
vote
0
answers
41
views
Computational complexity in Boolean network
An Boolean control networks can be expressed as
\begin{equation}
\label{ControlBN}
\left\{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ {x_{...
- 11
1
vote
0
answers
78
views
Partially defined boolean function
Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
- 11
1
vote
0
answers
19
views
Boolean circuit multigraph
Let us say that our definition of a circuit is the one of a boolean circuit from [Vollmer].
He uses directed acyclic graphs to represent circuits where the computation nodes are labeled with some ...
- 143
1
vote
0
answers
49
views
Logic minimization via 2 inputs NOR gates: Is it monotone w.r.t to adding a minterm?
notation: $x+y:=\mbox{OR}(x,y)$, $\bar x:=\mbox{NOT}(x)$, $xy:=\mbox{AND}(x,y)$, 1:=TRUE, 0:=FALSE.
Let $f$ be a Boolean function of $n$-variables, i.e. $f: \{0,1\}^n \to \{0,1\}$.
minterm:= any ...
- 111
1
vote
0
answers
146
views
Petrick's Méthod With Maxterms
I recently learnt about Quine-McCluskey and Petrick's methods and they are all okay by me using minterms the procedure is as follows :
1- Reduce the prime implicant chart by eliminating the essential ...
- 111
1
vote
0
answers
381
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? ...
- 11
1
vote
0
answers
198
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 ...
- 315
1
vote
0
answers
41
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?
- 493
1
vote
0
answers
111
views
Is such variant of SAT always satisfiable?
Let we have a SAT instance where every clause has length $\ge3$ (when length $2$ is allowed, it can be unsatisfiable) and each pair of literals appear only once.
Non-example: $(x\lor y\lor z)\land(x\...
- 1,429
1
vote
0
answers
66
views
Determining when equal 2CNF has pure literal
Let us assume that we have a 2CNF $\varphi(X,y)$. Then we want to see if there is equal formula where $y$ (or $\overline y$) is pure literal. Can this be done in polynomial time? Are there some ...
- 1,429
1
vote
0
answers
79
views
How does one calculate the block-sensitivity of a function?
I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity".
Can someone kindly ...
- 1,125
1
vote
0
answers
25
views
Real versus Finite field polynomials
Let $f$ be a Boolean function.
Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$.
Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with ...
- 2,881
1
vote
0
answers
108
views
Connection between formula size and time complexity
Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree.
Is there a connection between ...
- 2,881
1
vote
0
answers
61
views
How do I triangularise a netlist?
I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will ...
- 145
1
vote
0
answers
62
views
What is the current state of research on the representation of boolean functions using wavelets
The harmonic representation of boolean functions such as XOR or AND has been studied in different course note lectures that can be found on Google.
http://cs.mcgill.ca/~hatami/comp760-2011/
http://...
- 1,614
1
vote
0
answers
132
views
Simplifying circuits using boolean algebra
I am having a lot of trouble simplifying my circuit using boolean algebra. I am very new to this and any explanation would be greatly appreciated.
I have y'+z+w'x+wx'
I feel like I could use DeMorgan'...
- 11
0
votes
0
answers
16
views
Complexity Class of the Problem: Existence of Unsatisfying Interpretations in Boolean Formulas
What is the complexity class of the problem if there exist two different interpretations that do not satisfy a given Boolean formula? I believe the problem of existence of an interpretation that does ...
- 1
0
votes
0
answers
22
views
SOP Boolean expression of state variable and output of a Moore FSM
Disclaimer: I'm studying for an exam, but I don't have to hand in anything.
I have the state transition diagram of the FSM and its states encoding:
I want to find the sum-of-products (SOP) Boolean ...
- 1
0
votes
0
answers
49
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
0
answers
23
views
Is this language PSPACE complete
Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
- 1
0
votes
0
answers
24
views
Reed-Muller Form
I'm having trouble with the Reed-Muller Form, I'm using this notation to make it easier: + = or, * = and, ^ = xor.
This is the given expression (a + !b) * (b + !c).
a + !b = a + (b ^ 1) = a ^ b ^ 1 ^ ...
- 13
0
votes
0
answers
95
views
Time complexity of negating a CNF formula
Suppose i have a CNF formula. If i negate the CNF formula, then i obtain DNF formula. However, i can't find anywhere on internet that mention the time complexity. What is the time complexity of ...
- 113
0
votes
0
answers
33
views
Is there an efficient way to generate a pseudo-boolean function from a linear constraint?
I would like to define a pseudo-boolean function $f$ such that $f(x) = 0$ for all logically valid combinations of $x\in{0,1}$ and $f(x) > 0$ for all logically invalid combinations of $x\in{0,1}$.
...
- 121
0
votes
0
answers
36
views
graph representation of a Boolean function
I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
- 123
0
votes
0
answers
51
views
Functions expressible in conjunctive normal form, but with XOR replacing OR
What are all the functions $f:\{0,1\}^n\rightarrow\{0,1\}$ that can be expressed as a product of affine Boolean functions? For example, if $x_1,x_2,x_3\in\{0,1\}$ then $x_1x_2x_3\oplus x_2x_3 \oplus ...
