As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [boolean-algebra]

The tag has no usage guidance.

269 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
1 vote
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$...
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 ...
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.
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 ...
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 ...
28 views

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 ...
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 ...
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) ...
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