# Questions tagged [boolean-algebra]

The tag has no usage guidance.

188 questions
Filter by
Sorted by
Tagged with
155 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 ...
135 views

### When is a 1-in-3 SAT clause satisfied?

How does exactly 1 in 3 sat work given the variables Xi, Xy, Xz if one of the variables in the formula are negative. We know that the results are if they are all positive given that: R(Xi, Xy, Xz) = ...
22 views

### Emulating equal operator using multiplication

I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use ...
44 views

### Boolean expression to a truth table

How do I fill a truth table from the following expression? I can't decide whether it is SOP or POS. Y=(A+B)C+AB+(A+C)C+(`AB)
87 views

### If it's Possible to Create the If-Statement from Simpler Primitives

This question is about how to create an if statement (one of the control-flow statements) from scratch. An if-statement is typically a built-in construct in ...
70 views

### Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?

When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?
46 views

### When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables?

When you use resolution variable elimination to preprocess/simplify a formula in cnf form the resulting formula is equisatisfiable. What I wonder about is if I can use this technique to remove ...
1k views

28 views

### Taking mod $2$ with LTF gates

Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates? I do not mean that the ...
197 views

### Are there quantum algorithm that solve the boolean satisfiability problem in subexponential time?

Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they ...
60 views

### Simplyfing a particular boolean expression

I'm having a lot of trouble with two problems the first is: ...
239 views

### Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
40 views

### Determine whether a variable has positive influence in Boolean function

Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$. Given a ...
73 views

131 views

### Boolean Logic Equation

How can I prove this. what is the way? im up to the second last line. and i dont actually know how can x * (1 + y) then the y just disappears into x * 1. ...
140 views

### Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable). Output: unsatisfiable formula. Restrictions: Every clause contains exactly 3 variables. Every clause differs ...
908 views