Questions tagged [boolean]

For questions related to Boolean function (whose arguments and result assume values from a two-element set).

77 questions
Filter by
Sorted by
Tagged with
20 views

Notational change for linearity condition in analysis of Boolean functions

On Wikipedia, it clearly states that a Boolean function $f: \{-1, 1\}^n \rightarrow \{-1,1\}$ is linear iff it satisfies $f(xy)=f(x)f(y)$ where $xy = (x_1 y_1, \dots, x_n y_n)$. However, on another ...
18 views

How Do I simplify This Boolean Expression? [duplicate]

Expression: $$XY' + Y'Z' + X'Z'.$$ I think it has something to do with the consensus formula, but I can't actually figure out how to approach this problem.
24 views

Inverse of a boolean lower unitriangular matrix

Is the inverse of a boolean lower unitriangular matrix identical to the matrix itself? The matrix entries are considered to be in GF(2), i.e. bool.
• 532
35 views

1 vote
76 views

Boolean Simplification - Confused

I am doing some mathematics, and I am currently stuck on something. I do not understand this part at all, how can one approach this? No variable is used here. Problem: Simplify the following Boolean ...
• 269
76 views

Convert list of Boolean functions into logic circuit

Assume that I have a list of variables $x_1,...,x_n$ and a list of Boolean functions $f_1(x_1,...,x_n),...,f_m(x_1,...,x_n)$ What I would like to do is create a circuit gate graph $G=(V,E)$ which ...
• 343
1 vote
61 views

Is boolean formula or circuit more powerful description than blackbox?

Assume we are given boolean formula or circuit (I don't know if answer for this scenarios is different, and I am interested in both). Can we in polynomial time say anything about corresponding ...
• 15.9k
1 vote
This is exercise 1.5 from Analysis of Boolean Functions by Ryan O'Donnell. Suppose $f: \{-1, 1\}^n \to \{-1, 1\}$. We want to show that at most one Fourier coefficient has magnitude exceeding $1/2$. ...