Questions tagged [boolean-algebra]

The tag has no usage guidance.

57 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
157 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\}...
user avatar
  • 143k
4 votes
0 answers
243 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 ...
user avatar
4 votes
0 answers
31 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 \...
user avatar
  • 128
4 votes
0 answers
202 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 ...
user avatar
  • 143k
4 votes
0 answers
111 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 ...
user avatar
  • 1,393
3 votes
0 answers
71 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 ...
user avatar
  • 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 ...
user avatar
3 votes
0 answers
135 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)? ...
user avatar
  • 51
3 votes
0 answers
100 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}^...
user avatar
2 votes
0 answers
72 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{...
user avatar
2 votes
0 answers
35 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 ...
user avatar
  • 21
2 votes
0 answers
30 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 ...
user avatar
  • 151
2 votes
0 answers
227 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 ...
user avatar
2 votes
0 answers
48 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 ...
user avatar
2 votes
0 answers
58 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 ...
user avatar
2 votes
0 answers
104 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 ...
user avatar
  • 213
1 vote
0 answers
19 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 ...
user avatar
1 vote
0 answers
29 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 ...
user avatar
1 vote
0 answers
32 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\} .$...
user avatar
  • 11
1 vote
0 answers
17 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 ...
user avatar
  • 419
1 vote
0 answers
41 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 ...
user avatar
1 vote
0 answers
27 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_{...
user avatar
  • 11
1 vote
0 answers
56 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 ...
user avatar
1 vote
0 answers
144 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 ...
user avatar
1 vote
0 answers
17 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 ...
user avatar
1 vote
0 answers
40 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 ...
user avatar
  • 111
1 vote
0 answers
97 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 ...
user avatar
1 vote
0 answers
360 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? ...
user avatar
  • 11
1 vote
0 answers
145 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 ...
user avatar
1 vote
0 answers
39 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?
user avatar
1 vote
0 answers
96 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\...
user avatar
  • 1,393
1 vote
0 answers
65 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 ...
user avatar
  • 1,393
1 vote
0 answers
71 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 ...
user avatar
  • 1,085
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 ...
user avatar
  • 2,824
1 vote
0 answers
107 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 ...
user avatar
  • 2,824
1 vote
0 answers
58 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 ...
user avatar
  • 145
1 vote
0 answers
55 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://...
user avatar
  • 1,574
1 vote
0 answers
130 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'...
user avatar
0 votes
0 answers
47 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 ...
user avatar
  • 103
0 votes
0 answers
14 views

Bitcoin Mining Adder optimised with hardcoded constant

I've been reviewing Intel's paper Bonanza Mine: an Ultra-Low-Voltage Energy-Efficient Bitcoin Mining ASIC where they claim to have a completion adder optimised with a hardcoded constant that is unique ...
user avatar
0 votes
0 answers
9 views

Why do we talk of Affine Subspaces in terms of their codimension more than their dimension?

We know that the dimension of an affine subspace $U=H+a, (a \in V)$ equals the dimension of subspace $H$ of vector space $V$. But whenever I read about affine subspaces, I find it mentioned with its ...
user avatar
  • 11
0 votes
0 answers
29 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}$. ...
user avatar
  • 121
0 votes
0 answers
26 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 ...
user avatar
0 votes
0 answers
39 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 ...
user avatar
0 votes
0 answers
24 views

Doubt regarding the physical folding of a two dimensional K-map

While grouping terms in a k-map, if we pair terms on the first row with the ones on the last, it can be interpreted as the folding the 2-D map in the form of a cylinder, along the horizontal axis. ...
user avatar
0 votes
0 answers
14 views

Minimization of an expression through K-map, in which there are more chances of errors and with Quine-McCluskey Method there are less chance of errors

Minimization of any expression of 4 variables through K-map, in which there are more chances of errors (like error in grouping) and the same expression with Quine-McCluskey Method there are less ...
user avatar
0 votes
2 answers
70 views

is duality principle in boolean algebra is true for every expression

Let say A = 1 and B = 1 and then A+B = 1 now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0 but this is not 0, because 1.1 = 1, so please anyone clear my ...
user avatar
0 votes
0 answers
152 views

Karnaugh Map: does maximal overlap always produce simplest boolean expression?

Suppose I have a 4x4 Karnaugh map with a few cells that are don't cares, and there are two ways of producing 3 groups of 4 cells. One of these ways overlaps groupings more that the other. Is one way ...
user avatar
  • 11
0 votes
0 answers
48 views

Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
user avatar
0 votes
0 answers
59 views

How can I parse a boolean expression to group it based on the conjunction?

I have to design an algorithm to parse an array of terms and conjunctions into a grouped boolean expression. I never studied computer science and don't usually need this for web development, but today ...
user avatar