Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
273
questions
0
votes
1
answer
99
views
Prove that $\neg 0 = 1$
Starting from this definition https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$?
Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ¬...
CommunityBot
- 1
8
votes
1
answer
2k
views
Which CNF boolean formulas blow up exponentially at conversion to DNF?
If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa).
But what is an example of such a formula (and is there a ...
CommunityBot
- 1
1
vote
1
answer
563
views
Parity function
How is the parity function defined in standard way if inputs are in $\{-1,+1\}$ instead of $\{0,1\}$. For $\{0,1\}$, parity is $x_1\oplus x_2\oplus\cdots\oplus x_{n-1}\oplus x_n$. I am looking for how ...
- 2,881
1
vote
1
answer
93
views
How do you represent basic arithmetic using boolean function? [closed]
Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers?
...
- 2,881
1
vote
0
answers
108
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 ...
- 2,881
5
votes
2
answers
1k
views
Sensitivity and Block sensitivity
May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity.
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.
Let ...
- 72k
1
vote
1
answer
99
views
Function with minimum sensitivity
Let sensitivity be defined as in Sensitivity and Block sensitivity
Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$?
Is ...
CommunityBot
- 1
1
vote
0
answers
61
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 ...
- 145
1
vote
1
answer
51
views
Comparing coefficients of boolean functions
Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
- 275k
2
votes
1
answer
312
views
Can the Euclidean distance function be computed using only XOR's
The Eulidean distance function $d$ of $x$ and $y$ is given by:
$
d(x,y)=\sqrt{x^2-y^2}
$
Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. ...
D.W.♦
- 156k
1
vote
0
answers
62
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://...
- 1,614
2
votes
2
answers
326
views
Is my simplified explaination of the XOR swap correct?
The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows:
a = a ^ b
b = a ^ b
a = a ^ b
Now, I was ...
CommunityBot
- 1
2
votes
2
answers
151
views
What is the state of the art in efficient boolean function operations?
How do you most efficiently combine boolean functions with a large number of variables using AND, OR, and NOT? The most up-to-date work that I can find on this subject is about 20 years old (...
- 11k
1
vote
1
answer
48
views
Reducing a system of two boolean algebra assertions to a single one
Given a system of two Boolean Algebra equalities
a = b.
c = d.
one can exhibit a single equation
F(a,b,c,d) = 0.
which is ...
- 475
11
votes
2
answers
4k
views
Are Boolean functions Turing complete
A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$.
The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left ...
- 11k
1
vote
0
answers
132
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'...
- 11
5
votes
1
answer
220
views
Finding a graph-theoretic representation of expressions in Boole's algebra
I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but ...
- 136
0
votes
1
answer
1k
views
Odd Parity Function [closed]
I am trying to define a Odd Parity Function that takes three 1 bit inputs and will output a 1 if the 3 bits are odd as a Boolean function.
...
- 111
9
votes
0
answers
175
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\}...
D.W.♦
- 156k
4
votes
1
answer
455
views
Issue understanding the reduction of SAT to 3-SAT in poly time
Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-...
- 81.4k
2
votes
1
answer
399
views
Recognizing Horn clauses
I am currently studying model theory and I am trying to decide if a clause is a Horn Clause. I know that a Horn Clause is a clause with at most one positive literal, but there are some clauses that it ...
D.W.♦
- 156k
1
vote
0
answers
129
views
Popcount Orders and Lexicographic Orders [closed]
A popcount order of a two bit vector {1,1}=3 can be given by:
{{1, 1}, {1, 0, 1}, {1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 1, 0, 0}, {1,
0, 0, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 1, 0, 0}}
and as a ...
- 275k
1
vote
1
answer
403
views
Laws to simplify a boolean formula
$$ (\neg A \wedge \neg C) \vee (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$
can simplify down to
$$ (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$
...
CommunityBot
- 1