# Questions tagged [boolean-algebra]

The tag has no usage guidance.

231 questions
Filter by
Sorted by
Tagged with
5k views

29 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 ...
215 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 ...
61 views

### Simplyfing a particular boolean expression

I'm having a lot of trouble with two problems the first is: ...
338 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 ...
49 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 ...
85 views

146 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. ...
214 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 ...
1k views

929 views

### How to simplify sum of products boolean expression?

I started with this sum of products: abc’d’ + abc’d + ab’cd’ + a’b’cd’ + a’bc’d + a’bcd + ab’c’d + a’b’c’d I have been able to simplify to this: ...
104 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). ...
324 views

### Random forests on monotone training set yields a monotone classifier?

Suppose I train a random forests classifier on a monotone training set. Is the resulting classifier guaranteed to be a monotone function? Suppose I apply the ID3 algorithm (the greedy algorithm) to ...
94 views

### Boolean Algebra: Operation Linkage Laws

Im studying some properties of Boolean Algebra and found the Operation Linkage Laws. Im not able to understand how this laws are possible, and the remark on the proof is not really clear for me. Can ...
7k views

### Why is A(A+B) = A [Absorption Law]?

Could you proof it to me that A(A+B) = A? AA + BA [AA = A] A + AB Then what?
963 views

### Extracting Boolean Function using Machine Learning

How can machine learning help extract a Boolean relationship in a given binary input-output data set? Let us assume that the given data set is exhaustive - ie. it cover all possible input ...
131 views

### How does the following truth table show Y's behaviour? [closed]

a b c Y 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 ...