Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
269
questions
1
vote
1
answer
38
views
Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.
If you know $A$ is $1$, you have one bit of information.
If you know $A\land B$ is $1$, you have two bits of information.
If you know $A\land B$...
- 13
0
votes
1
answer
41
views
Why is conjunctive normal form (CNF) "better" for SAT than disjunctive normal form (DNF)?
When hand-manipulating algebra DNF (sum of products) is easier than
CNF (product of sums). Possibly because factoring is more difficult
than expanding. So why is it the opposite for computational ...
- 1,084
-3
votes
2
answers
52
views
!(ab)*(!a+b)(!b+b)=!a Boolean Algebra
How can I prove that !(ab)(!a+b)(!b+b)=!a* in boolean algebra? This is an exercise from a past paper of my teacher but I can't really find the way to the answer. I would appreciate some help.
0
votes
1
answer
17
views
How to solve boolean SAT with equality constraints
Say I have boolean formula in form of a CNF(x1,x2,...) with $x_i$ being boolean variables.
Testing the satisfiability of the CNF is the SAT problem, i.e. determine ...
- 161
5
votes
5
answers
947
views
Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\&} B)$ where $\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is ...
- 161
0
votes
0
answers
28
views
Is this a valid method to merge clauses in CNF formulas?
Assume $$C_1 = (x_1 \lor x_2 \lor \lnot x_3)\hspace{0.2cm} C_2 = (x_4 \lor x_5 \lor x_3) \hspace{0.2cm} C_3 = (x_3 \lor x_5 \lor x_6)$$ Let
$$ \phi_1 = C_1 \land C_2 \land C_3$$ and
$$ \phi_2 = (x_1 \...
- 185
0
votes
0
answers
20
views
Is this language PSPACE complete
Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
- 1
1
vote
1
answer
57
views
Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.
Let's say I am doing 5 coin ...
- 11
0
votes
1
answer
24
views
7 segment decoder Combinational Logic Circuits using Logic Gates
How can a 7 segment decoder operation be implemented using boolean NOR gate ONLY?
Question:
Here's my truth table and k-map:
Normal circuit diagram:
0
votes
2
answers
56
views
Two's complement using logic gates
How can a 4-bit two's complement operation be implemented using boolean NOR gate?
I search lots of 4-bit two's complement videos and articals, but most of them are using XOR gate.
0
votes
0
answers
16
views
Reed-Muller Form
I'm having trouble with the Reed-Muller Form, I'm using this notation to make it easier: + = or, * = and, ^ = xor.
This is the given expression (a + !b) * (b + !c).
a + !b = a + (b ^ 1) = a ^ b ^ 1 ^ ...
- 13
0
votes
1
answer
20
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 ...
1
vote
0
answers
55
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 ...
- 111
0
votes
2
answers
44
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 ...
- 1
0
votes
1
answer
49
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
79
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 ...
- 113
1
vote
2
answers
118
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
23
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 ...
1
vote
1
answer
53
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 ...
- 13
1
vote
1
answer
27
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
24
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 ...
- 123
1
vote
2
answers
195
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
48
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 ...
- 123
2
votes
1
answer
63
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 ...
- 429
1
vote
1
answer
48
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.
- 13
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.
- 113
1
vote
0
answers
30
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 ...
- 111
2
votes
1
answer
23
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 ...
- 21
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
33
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 ...
- 123
3
votes
1
answer
60
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
40
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 ...
- 11
-1
votes
1
answer
29
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.
- 11
1
vote
0
answers
35
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
136
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 ...
- 237
0
votes
1
answer
72
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
846
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) ...
- 133
1
vote
1
answer
117
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
48
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
532
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
71
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-...
- 113
2
votes
1
answer
231
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, ...
- 23
1
vote
1
answer
43
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 ...
- 2,450
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
91
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
49
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
91
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