Skip to main content

Questions tagged [boolean]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
Saksham Sethi's user avatar
-1 votes
0 answers
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.
Mosaddeq Hussain's user avatar
0 votes
1 answer
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.
Daniel S.'s user avatar
  • 532
0 votes
0 answers
35 views

Prove: Let α be a proposition containing only Boolean connectives ∧,∨. Then any assignment satisfying α must also satisfy f(α)

The question: Let f be a mapping that takes as input a Boolean proposition (no quantifiers) and outputs the same proposition but with all ∧ symbols replaced by ∨. For example: $$ f(x_1 ∧ (x_2 → ¬x_5) =...
User33975329257439645's user avatar
3 votes
1 answer
64 views

Proof-Theoretic Advantages to Using Only NANDs in Infinitary Logics

This question comes out of a question on Philosophy Stack Exchange, and a particular difference of opinion in regards to the initial question stated in 'Is there any major benefit to using NAND in ...
J D's user avatar
  • 145
3 votes
1 answer
90 views

Finite Commutative ring with 100 elements where $x^2=x$?

Does there exist a finite Commutative ring with 100 elements where $x^2=x$ for every $x\in R$? I know finite Boolean rings has the property this property but they have cardinality $2^n$, for some $n$. ...
Learner's user avatar
  • 369
2 votes
3 answers
246 views

Given the output frequencies create a truth table with minimal boolean function

I have a black box with eight inputs and three outputs and I would like to write minimized boolean functions for them. I know how to simplify the boolean expressions given a truth table, but I don't ...
Andrea Marenco's user avatar
0 votes
0 answers
33 views

A generalized algorithm to convert a formula in algebraic normal form to an equivalent formula that minimizes the number of bitwise operations

In this question, “bitwise operation” means any operation from the set {XOR, AND, OR}. The NOT operation is not included because ...
lyrically wicked's user avatar
-1 votes
1 answer
63 views

Maximum subgroup within a set [closed]

Suppose we have a set $S\subseteq \{ 0,1 \}^{2n}$ satisfying $|S|\geq 2^n$ (promised $ 0^n\in S$), then what is the largest $S'\subseteq S$ such that $S'$ is a group? There is a lot of literature on ...
Vaas's user avatar
  • 413
0 votes
0 answers
59 views

Group actions on functions induced by group actions on their domain

In Exercise 1.30 of Ryan O'Donnell's Analysis of Boolean Functions is written Permutations $\pi \in S_n$ act on strings $x \in \{-1,1\}^n$ in the natural way: $(x^{\pi})_i=x_{\pi(i)}$. They also act ...
Simon's user avatar
  • 2,175
0 votes
0 answers
18 views

Convex distance on the Boolean cube

The convex distance (or Talagrand distance) can be defined as $\sup_{\alpha}\inf_y d_\alpha(A,x)$, where $d_\alpha$ is the weighted Hamming distance, that is $d_\alpha(x,y)=\sum_{x_i\neq y_i}\alpha_i$,...
xyz's user avatar
  • 1,000
0 votes
0 answers
12 views

Disjunctive normal form of the negation of a disjunctive normal form.

Let $\mathsf{B}$ be a Boolean algebra with carrier set $B$ and Boolean operations $\vee,\wedge,(-)'$ and constants $0,1$. Let $a,b,c,d\in B$. Let us consider the Boolean function $p_{a,b,c,d}\colon B^...
Amaru's user avatar
  • 97
5 votes
1 answer
199 views

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 ...
Paul's user avatar
  • 557
0 votes
0 answers
18 views

Guess the number in the box - which complexity class does this belong in?

I'm trying to improve my understanding of complexity classes by reading the complexity zoo here, https://complexityzoo.net/Complexity_Zoo, and a number of other resources. I'm having an argument with ...
3mar's user avatar
  • 1
1 vote
2 answers
85 views

Simplifying the Boolean expression $x'y + x(x+y')$

Expression: $$x'y + x(x+y')$$ My attempt: $x'y + x(x+y')$ $x'y + xx + xy' \quad \textit{After applying second Distributive law.}$ $x'y + x + xy' \quad \textit{After applying second Idempotent law.}$ $...
Alix Blaine's user avatar
0 votes
1 answer
40 views

Trying to simplify the following boolean expression but suck and new to this

Expression: $[x + (yz)](x' + z)$ My attempt: $[x + (yz)](x' + z)$ $(x + y)(x + z)(x' + z) \quad \textit{Distributive law}$ The answer is supposed to be: $(x + y) \times z$ N.B. I am still new to ...
Alix Blaine's user avatar
1 vote
2 answers
180 views

How to simplify the boolean expression $(x\times y)'+(y\times z)$?

Expression: $$(x\times y)'+(y\times z)$$ My attempt: $(xy)' + (yz)$ $(x'+y') + (yz) \quad \textit{After applying de Morgan's Axiom}$ $x' + (y' + yz) \quad \textit{After applying 1st Distributive ...
Alix Blaine's user avatar
0 votes
1 answer
68 views

Where did I go wrong trying to simplify this down to $(x \times y)$ boolean expression?

Simplify: $[(x \times y') + x']' $ My attempt: $((x \times y') + x')' $ $(x \times y')' \times x''$ $(x'+ y'') \times x''$ $(x' + y'') \times x$ $(x' + y) \times x$ $(x'+ y)(x' + x)$ $x(x' + y) + x'(...
Alix Blaine's user avatar
1 vote
2 answers
86 views

Trying to simplify the following boolean expression [closed]

Simplify: $y \times [x + (x' \times y)]$ My attempt: $y \times [(x + x') \times (x + y)] \quad \textit{First Distributive Axiom} $ $y \times [1 \times (x + y)] \quad \textit{First Inverse Axiom} $ ...
Alix Blaine's user avatar
2 votes
0 answers
52 views

Find the minimum number of conjuncts in the DNF of function $g$

The Boolean function $g$ of the variables $x_1 , . . . , x_5 , y_1 , . . . , y_5$ , is given by the formula: $$ \bigwedge_{i=1}^{5} (x_i \ \vee \ y_i) $$ Mission: find the dnf($g$). (the minimum ...
Jacobs Monarch's user avatar
1 vote
1 answer
53 views

I've found the minimal AND-OR expression for a function, but I can't find the minimal OR-AND function

I am given a function $f(W,X,Y,Z)$ that only outputs $1$ if exactly three inputs are $1$. The AND-OR function is easy enough to find: $$ W'X\,YZ + WX'YZ + WX\,Y'Z + WX\,YZ' $$ I think that function is ...
Daniel's user avatar
  • 71
0 votes
0 answers
22 views

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 ...
SAQ's user avatar
  • 385
0 votes
0 answers
34 views

Boolean logic calculation for dependent variables

Given the following problem: Which statements are equivalent: ...
DCR's user avatar
  • 109
0 votes
0 answers
24 views

Boolean conclusions within ezyme biochemistry example

In Brown's book "Boolean reasoning: the logic of Boolean equations.", Chapter 5.7 Selection deduction, he does an example using 'a modification of one given by Ledley', which uses Blake ...
sheppa28's user avatar
  • 929
0 votes
1 answer
59 views

Does finding feasible solution to set cover problem is as hard as SAT problem?

I have a weird feeling that finding a single feasible solution to the set cover problem is as hard as SAT problem. I think that this might be wrong but I am not sure why. To illustrate my thinking, ...
Tuong Nguyen Minh's user avatar
0 votes
0 answers
19 views

Is it possible to approximate the cardinal of boolean functions inside a ball?

Let $\mathcal{X}$ be an input space equiped with a distribution $\mathcal{D}_{\mathcal{X}}$. We denote $\mathcal{F}$ the set of boolean functions defined on $\mathcal{X}$. Fix $\epsilon >0$ and $h$ ...
rivana's user avatar
  • 1
0 votes
0 answers
20 views

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 ...
rivana's user avatar
  • 1
0 votes
1 answer
50 views

Can $p_2$ be recovered from $p_1$ and $p_1 \land p_2$ using boolean operations?

Consider the propositional logic formulas $p_1$ and $p_1 \land p_2$, where $p_1$ and $p_2$ are propositional atoms. Can $p_2$ be recovered from $p_1$ and $p_1 \land p_2$ using boolean operations? That ...
user107952's user avatar
  • 21.4k
0 votes
0 answers
27 views

If a certain function is a functionally complete class, express from it the constants 0,1, negation and conjunction xy using superpositions.

Example solution (2.4.3) at http://diskra.ru/reshenie_zadach/?lesson=5&id=12 Question example solution I don't understand how they are constructing for the function g which is a functionally ...
Neil 's user avatar
  • 33
1 vote
1 answer
28 views

Finding a Proposition to Satisfy Given Logical Statements

I'm facing a logical inference problem and seeking guidance to find a proposition p3 that satisfies certain logical conditions. Given propositions: p1 = p or r p2 = q => !p p3=? Given conclusions: ...
brodar's user avatar
  • 157
0 votes
1 answer
61 views

How does this fit in with the definition of finite boolean functions?

My lecture defined that a boolean function is a function f: ${\{0,1\}}^{V} → \{0,1\}$ with $V$ being the set of variables. Moreover a boolean function f: ${\{0,1\}}^{V} → \{0,1\}$ is finite if set of ...
StudentSeekingHelp's user avatar
1 vote
1 answer
71 views

Show that $xz +x'y + zy = xz + x'y$ (Boolean Algebra)

My best guess is that somehow $$xz + x'y = zy$$ I know that $$A + A'B = A + B$$ but can that be applied here since there is an extra variable? Is there a relevant rule I'm missing? Question 25 from ...
addledo's user avatar
  • 21
0 votes
0 answers
19 views

Have I simplifed $ \bar AB + ABC\bar D + AB\bar CD + AB(C \oplus D) + CD(A \oplus B) $ correctly?

Please verify my simplified boolean expression and let me know if it is correct, or if we can further simplify? Simplifying Equation I have further simplified it: Further Simplification
tabish's user avatar
  • 1
1 vote
0 answers
32 views

How to find values that generate a particular boolean expression

On question 1 of our homework we are asked to find which values of the boolean variables equate to the resulting boolean expression. I tried finding resources on how to complete this but I came up ...
Yeonari's user avatar
  • 11
0 votes
0 answers
82 views

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
長衞哲弘's user avatar
2 votes
1 answer
113 views

Is it possible to form a committee of insane inhabitants in Smullyan's logic puzzle?

My question is about Puzzle 11 in Chapter 3 of R. Smullyan's The Lady or the Tiger. Here is the context and problem: "Inspector Craig of Scotland Yard was called over to France to investigate ...
msb15's user avatar
  • 138
-1 votes
1 answer
36 views

Reconstruct a Boolean function from its partial derivatives [closed]

If I have a Boolean function is there a way for me to reconstruct given it’s partial derivative? What if I have the second order derivatives? This is for discrete functions. I am struggling to find ...
snickers_stickers's user avatar
0 votes
0 answers
15 views

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 ...
Nenunathel's user avatar
1 vote
2 answers
82 views

Prove that the set {$\rightarrow, \oplus$} is functionally complete by using that it is {$+, \neg$}

The set {$+, \neg$} is functionally complete, because every boolean function can be represented as only combination of Disjunctions ($+$) and Negations ($\neg$). Prove that the set {$\rightarrow, \...
wengen's user avatar
  • 1,135
-3 votes
1 answer
80 views

Can truth tables be different for equal expressions? [closed]

I have a equation (A'B + B'C)C'. If I simplify this down to A'B C' the truth tables are not the same. What am I doing wrong?
Mark Filenko's user avatar
0 votes
0 answers
21 views

A questions about using basic rules to simplify complicated boolean algebra:

When I was in the digital logic class at school, the teacher taught me basic Boolean algebra rules and some common simplification methods and then assigned some homework, but when I went to prove it ...
Lesen Liu's user avatar
0 votes
0 answers
51 views

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 ...
agni_ka1's user avatar
1 vote
1 answer
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 ...
Alix Blaine's user avatar
3 votes
0 answers
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 ...
Shore's user avatar
  • 343
1 vote
1 answer
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 ...
mihaild's user avatar
  • 15.9k
1 vote
0 answers
191 views

Magnitude of the Fourier coefficient of a boolean function

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$. ...
deltaepsilonnn's user avatar
1 vote
1 answer
95 views

How to solve for the required Boolean function when the partial Walsh spectrum is known

Boolean function denotes the map from $\mathbb{F}_2^n$ to $\mathbb{F}_2$. All the $n$-variable Boolean function consist the set $\mathfrak{B}_{n}$. Any elements $\alpha=(\alpha_0,\alpha_1,...,\alpha_{...
SnabbyHu's user avatar
0 votes
0 answers
27 views

Given set of number $\{{a_1}, ..., {a_n}\}$, how to know whether $b$ can be obtained by performing $XOR$ operation between number in the set?

For example, given the set {0011, 1001, 0110, 1110}, the number 1011 can be obtained by performing xor between number in the set 0011 xor 0110 xor 1110 = 0101 xor 1110 = 1011 Another example, given ...
LLL's user avatar
  • 113
1 vote
0 answers
91 views

Applications of Boolean Differential Calculus

I've recently read about a subject field called "Boolean differential calculus", which discusses changes of Boolean variables and functions. This subject defines the derivative of a Boolean ...
CauchyChaos's user avatar
1 vote
0 answers
56 views

Specifying sets of binary strings by inclusion and exclusion filters

Consider the set $S^n$ of binary strings of length $n$, i.e. $S^n = \{0,1\}^n$, and the set $F^n$ of filters of length $n$ which have some unspecified entries $x$, i.e $F^n = \{0,1,x\}^n$. For $f \in ...
Hans-Peter Stricker's user avatar