Questions tagged [boolean-algebra]
The boolean-algebra tag has no usage guidance.
269
questions
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 ...
CommunityBot
- 1
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$...
- 8,797
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 ...
- 7,894
-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.
- 129
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 ...
- 8,797
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
20
votes
3
answers
6k
views
Is it possible to write an AND gate using XOR gates?
How could I express an AND gate using only XOR gates ?
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
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 ...
CommunityBot
- 1
0
votes
2
answers
84
views
is duality principle in boolean algebra is true for every expression
Let say A = 1 and B = 1
and then A+B = 1
now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0
but this is not 0, because 1.1 = 1, so please anyone clear my ...
CommunityBot
- 1
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:
- 8,797
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.
- 8,797
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
1
vote
2
answers
155
views
For a logic gate to be universal, must it necessarily be able to perform duplication?
It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to ...
- 101
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 ...
- 20.2k
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)....
- 38.2k
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,...
CommunityBot
- 1
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 ...
- 27.4k
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
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 ...
- 274k
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}?
- 274k
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 ...
- 8,797
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 ...
- 274k
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 ...
- 882
1
vote
2
answers
5k
views
How do i simplify this SOP expression?
Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer ...
- 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-...
- 22.4k
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.
- 26.4k
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 ...
- 274k
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}$.
...
D.W.♦
- 152k
1
vote
2
answers
136
views
Why can't we reduce register automata to symbolic automata?
When considering automata, they are normally considered over finite alphabets. The following are two types of automata that can handle words over infinite alphabets (definitions included for clarity).
...
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 ...
- 78
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 ...
D.W.♦
- 152k
0
votes
1
answer
143
views
What does it mean to "show algebraically" in propositional logic?
The biconditional operator $\iff$ of Propositional Logic can be defined by the identity
$p \iff q \equiv (\lnot p \lor q) \land (\lnot q \lor p) \quad (1.1)$
Use the identity $(1.1)$ and identities ...
CommunityBot
- 1
-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.
- 319
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\} .$...
- 7,325
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
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 ...
- 3,060
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) ...
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
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 ...
- 251
2
votes
2
answers
553
views
Is any sudoku solver an SAT solver?
I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning ...
- 151