Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [boolean]

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

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {$\text{true}, \text{false}$}, {$0,1$} or {$-1,1$}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

65 questions
5
votes
0 answers

Understanding which functions on $\{0,1\}^n$ are non-boolean

I recently came across this paper by Friedgut that shows low sensitivity boolean functions are close to juntas. This was an unintuitive result to me, as I thought I could easily imagine a function on the boolean hypercube that is a linear…
Paul
  • 557
0
votes
0 answers

Sheffer function

I am trying to show that if $f\notin T_0\cup T_1\cup S,$ where $T_0$ and $T_1$ are the sets of zero and one-preserving Boolean functions respectfully and $S$ is the set of all self-dual boolean functions, then $f$ is a Sheffer function (Sheffer…
SAQ
  • 367
0
votes
0 answers

Fourier expansion of a special boolean function

Every bounded Boolean function admits a Fourier expansion in the basis of monomials (Ref: Boolean function analysis, Ryan O'Donnel Course) I was auditing Ryan's course and he said (05:00) that the following function : $$ g(x_1,x_2,x_3,x_4) = …
rivana
  • 11
0
votes
0 answers

How to simplify the function F = AB'C' +A'B'C' + A'BC' + A'B'C

I want to simplify the function F = AB'C' +A'B'C' + A'BC' + A'B'C, but I do not know how to do it, I can only simplify it as B'C' + A'BC' + A'B'C
長衞哲弘
  • 1
0
votes
0 answers

Compute all true bytes from boolean expression without testing each possible byte

Given is a boolean expression $f = f(x_1,x_2,...x_n)$. How do I find all bytes of size $n$ that make $f=1$? I want to do this without having to check for each possible byte of size $n$, see if they result in $f=1$ or $f=0$, and collect the ones that…
Nenunathel
  • 295
0
votes
0 answers

Finding the complement of the boolean expression $(w + x' + y +z')(w' + x + y + z')(w' + x' + y' + z')$

I am given the following boolean expression, and was told to simplify it using De Morgan's Law. $$(w + x' + y +z')(w' + x + y + z')(w' + x' + y' + z')$$ I approached this through the commonly used method of finding the dual, and then taking the…
agni_ka1
  • 1
-2
votes
1 answer

Boolean algebra simplification (DNF)

I am trying to simplify the following expression: $(p \wedge r) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q \wedge r)$ I know that I should get $r \vee (\neg p \wedge q)$ but I am not sure how to explain. Could you please help ? Thanks a lot !
Martin Raynier
  • 9