Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
15 views

influence of neighourhood points

Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we ...
2 votes
0 answers
49 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 ...
0 votes
2 answers
35 views

Boolean Logic when one component switches from 0 to 1

I recently was constructing boolean logic for all sorts of examples from Morris Mano's "Digital Logic and Circuit Design". I noticed that it is possible to construct a boolean logic wrt the ...
0 votes
1 answer
46 views

Is there a notation for boolean algebra complexity?

To represent complexity of an algorithm, Computer Scientist is used to using big-O notation. How about complexity of boolean algebra? Boolean algebra is commonly used in digital circuit design with ...
2 votes
1 answer
1k views

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable. 3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
0 votes
0 answers
57 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 ...
  • 103
1 vote
2 answers
104 views

Combinational logic check if bits is prime

I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not. For example given input fixed 8-bit that will produce 1-bit output. 00000101 will ...
0 votes
0 answers
18 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 ...
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 ...
  • 11
1 vote
1 answer
46 views

How many different boolean functions exist up to permutation of its $n$ variables

i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
1 vote
1 answer
26 views

Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?

I want to know what will change if we keep on using {0,1} for our Fourier analysis of boolean functions? What are the things, which can not be performed with {0,1} and can be done with {+1, -1}?
  • 11
1 vote
0 answers
20 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 ...
1 vote
2 answers
174 views

Clarification regarding linear boolean functions!

I am a little confused when it comes to linear boolean functions. According to this post: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to ...
  • 13
1 vote
1 answer
20 views

How to come up with combination a short-circuit evaluation table?

(a || b) || (c && d)) Given the above, how do I derive the table below: a b c d output T - - - TRUE F T - - TRUE F F T T TRUE F F T F FALSE F F F - FALSE I'm told that this is short ...
  • 11
1 vote
1 answer
42 views

Influence of a variable in composition of Boolean functions

Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$? To me it ...
2 votes
1 answer
60 views

Is $f(X)f^d(X) = 0$ for a Boolean function $f$?

I'm currently trying to understand a step in the proof for in the Crama and Hammer book on Boolean Functions. The proof is Proposition 4.12, which claims that the self-dualization of Boolean $f$ is ...
  • 419
1 vote
1 answer
45 views

Is [F(a, b, c) = a' + b] functionally or logically complete?

I'm having a problem determining whether [F(a, b, c) = a' + b] is functionally(logically) complete or not. I would really appreciate it if you could help me. P.S: I can't have 1 or 0 as input.
0 votes
1 answer
35 views

Can element occur in a CNF formula?

For example, is $(X \vee 1)$ a valid formula in conjunctive normal form (CNF)? If yes, then I would have to consider such formulas when trying to prove a statement about all CNF formulas.
  • 103
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 ...
2 votes
1 answer
20 views

sum of Boolean characters larger degree

I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then $$ \frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1 $$ if and ...
0 votes
0 answers
31 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
30 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 ...
3 votes
1 answer
51 views

Stalmarck's method: x ≡ x → z, does z have to be true?

I have been researching Ståmarck's method 1. In the paper cited here, some rules are given. Rules are made of triplets (x, y, z) such that: y $\to$ z $\equiv$ x where x, y and z are booleans which ...
  • 53
1 vote
1 answer
24 views

Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?

I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean ...
-1 votes
1 answer
28 views

Can anyone solve this? Is the answer 4 or 7. I'm confused

I'm trying to solve this but I'm confused with different answers. I'm getting 4 but the answer written is 7. Please guide me.
1 vote
0 answers
33 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
0 votes
1 answer
73 views

What boolean algebra simplification is applied in this Shannon's expansion?

Found this question about Shannon's expansion. While I am trying to follow its logic, found one super convenience simplification used. Can we do this in general while dealing with boolean algebra? or ...
  • 123
0 votes
1 answer
55 views

Boolean formula for graph 3COL

For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be ...
  • 115
2 votes
3 answers
647 views

Why is SAT based on the CNF?

I have been reading up on Boolean logic and, specifically, the Boolean satisfiability problem. I have seen several people mention that the expression must be converted to conjunctive normal form (CNF) ...
1 vote
1 answer
103 views

Sorting by boolean algebra (hardware) instead of algorithm (software)

Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11] Maybe that case seems complicated,...
0 votes
0 answers
45 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 ...
-1 votes
1 answer
416 views

Four Queens Problem to a Conjunctive Normal Form

Given a chessboard with 4 rows and 4 columns (4x4) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Assign a Boolean variable to each cell of the board as below (1, 2, 3, etc. are variable names) If a ...
  • 1
4 votes
2 answers
67 views

Compact representation for quantified boolean formula

I got black-box (too big to analyze) boolean formula f(...) with 3 sets of input arguments: $x_1... x_i, y_1... y_j, z_1... z_k$. And I want to find such values for x-arguments that for every y-...
2 votes
1 answer
154 views

What are the limits of Boolean Algebra?

Any decision problem algorithm can be represented as a boolean expression. The rules of boolean algebra (De Morgan's law, distributivity, etc.) can be used to manipulate and simplify that expression, ...
1 vote
1 answer
33 views

Definition and use of a Boolean equation system

According to google, a system of boolean equations is defined as follows Essentially, a Boolean equation system is an ordered sequence of fixed point equations over Boolean variables, with associated ...
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 ...
-2 votes
1 answer
63 views

Simplify $X'(X+Y) + (Y+X.X) ( X + Y') + Z + X.Z$

I wanna know if $X'(X+Y)$ means $X'.X+Y.X'$? Does it have an AND gate after $X'$? Notation: $X'$ : NOT $X$ $X + Y$: $X$ OR $Y$ (OR gate) $X.Y$ : $X$ AND $Y$ (AND gate) New to boolean, can't seem ...
1 vote
2 answers
71 views

Simplifying the boolean expression xy + (!x)z + yz with boolean algebra?

So using K-maps I was able to simplify xy + (!x)z + yz to xy + (!x)z, and I double-checked that the truth tables are the same. I'm having trouble understanding how I would have used boolean algebra to ...
  • 147
1 vote
1 answer
44 views

How to perform AND on binary "recursive repeating sequences"?

Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
  • 71
-1 votes
1 answer
89 views

Prove x . y' . z' is y' . z'

Please, how can I prove that x . y' . z' simplifies to y' . z'? I have tried without success. Below is the context of my question; I am taking a course on Coursera
  • 109
2 votes
0 answers
75 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{...
1 vote
1 answer
152 views

How to find the reverse of a binary string with simple binary operators?

I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome? So my approach is to feed the input to a circuit that reverses the input, ie if ...
  • 11
2 votes
1 answer
31 views

What can be said about the Fourier expansion of compositions of Boolean functions, if anything?

Let $\chi_S: \mathbb{F}_2^n \to \{\pm 1\}, x \mapsto (-1)^{\sum_{i \in S}x_i}$ for every $S \subseteq [n]$ denote the parity functions from $\mathbb{F}_2^n$ to $\{\pm 1\}$. Then, of course, every $f: \...
1 vote
0 answers
18 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 ...
  • 419
3 votes
1 answer
72 views

What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
  • 41
1 vote
0 answers
50 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 ...
2 votes
0 answers
37 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
1 vote
1 answer
31 views

Functions with small support have small circuits

I have been trying to understand the use of circuit models for boolean functions, and came across this question, that I am trying to struggle to understand: Show that if a function $f\colon \{0,1\}^n→\...
0 votes
1 answer
49 views

Simplify Boolean expression

The following Boolean expression is simplified into its minimal number of literals: $$x'y' + yz +x'yz' \implies x'+yz.$$ How do you logically conclude this using the Boolean Laws?
0 votes
2 answers
77 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 ...

1
2 3 4 5 6