# Questions tagged [boolean-algebra]

The tag has no usage guidance.

238 questions
Filter by
Sorted by
Tagged with
345 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 ...
96 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 ...
8k 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?
1k 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 ...
172 views

### how to evaluate a boolen expression

what is an easy but efficient way to evaluate Boolean Expression. I have been searching a lot in google but not really finding a good book or site which has working algorithm. Input string (A=100) ...
353 views

### Is Functional Complete means Turing Complete?

I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates. A Turing machine may halt or not in a particular ...
88 views

651 views

### Question about idempotent and Dominance Laws in Boolean Algebra [closed]

If I have the following statements: For Idempotent: Since X * X = X, would that imply that ~X * ~X = ~X For Dominance: Since X + 1 = 1 would that imply that ~X + 1 = 1
53 views

### Boolean algebra truths with more than one digit

I understand that when you 0 AND 0 it will result in 0 and that 1 AND 1 will result in 1 etc but what I don't understand is if the question was 01 AND 11. How would I work this out?
59 views

### About a universal (functionally complete) function producing a constant

I read in a note the following: Suppose we have a boolean function $f(x,y,z,w)$, if $f(a,a,a,a)=1$ then $f$ can't be functionally complete. Why is that? how does it imply that $f$ can't produce ...
100 views

### Question simplifying boolean expression

This is what I have so far, so I just want to know if I am doing everything right or wrong. I am novice in the topic. I have been given: $(A \oplus B) \land \neg A \lor A$ XOR = $\oplus$ By order ...
210 views

### Help me understand the logic behind x - y in binary by boolean?

x and y are 4 bit signed numbers (2s complement..) x - y can be obtained by: !(!x + y) I know that in 2s complement ...
409 views

### Simplifying Boolean Expression

I am designing a 4-bit comparator with a look ahead unit using a bit slice approach. I have to break the propagation of the Logical expressions for (A<B)i and <...
476 views

### What happens to uninterpreted predicates in Ackermann's reduction?

I know the procedure to apply the Ackermann's reduction to a formula that doesn't involve uninterpreted predicates. But, how do we treat the uninterpreted boolean predicates? Nearly all the examples I ...
268 views

### Which formula corresponds to this K-Map?

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map. $f(w,x,y,z) = \sum(3,7,9,11,13,15) + \Phi(4,5,6)$ We know that both options (a) and (b) are ...
566 views

### What is the XNOR of 3 or more inputs?

We know that for 3 variables (A=0,B=1,C=1), f$_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's. But if we were to do this step by step, f$_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 ...
459 views

445 views

### Number of solutions to linear system of equations over GF(2)

Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option. Is there a ...
182 views

### Converting a digital circuit to two layers of OR and AND gates

The other day someone mentioned to me that you could take an arbitrary digital circuit which mapped N input bits to M output bits, and replace it with a layer of OR gates and a layer of AND gates. I ...
87 views

### How to Apply Binary Transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
6k views

### Is it possible to write an AND gate using XOR gates?

How could I express an AND gate using only XOR gates ?
1k views

### Implementing a Boolean function with NOR gates

Implement f(a, b, c, d) = Σ m(3, 4, 5, 6, 7, 11, 15) as a 2-level gate circuit (a) Using OR gates and NOR gates. (b) Using NOR gates only. I have found that F=ab+d using Karnaugh map. I have also ...
6k views

### Boolean algebraic expression vs Propositional logic expression

There is a lot of similarity between Propositional logic and Boolean algebraic expressions. Similar aspects : 1) Both has variables of two states. 2) Operations of Boolean algebra and ...
58 views

### How does one calculate the block-sensitivity of a function?

I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity". Can someone kindly ...
102 views

### Methods for optimizing short-circuit evaluation for conditions of varying evaluation-cost

I have a bunch of boolean conditions, let's call them A, B, C, D, .... In my code, I need to use these conditions to distinguish between several different possible ...
127 views

### Classical Computation without NOT

Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible ...
88 views

### Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
34 views

### Learning a small disjunction using an input distribution of our choice

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form $$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}.$$ I don't know the values of $i_1,\dots,i_k$, but I ...
129 views

### Learning a small disjunction

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form $$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$ but I don't know the values of $i_1,\dots,i_k$. ...
Suppose that $x = (x_1,\ldots,x_n)$ is a binary vector and $f(x)$ is a boolean function. Furthermore suppose $y = (y_1,\ldots,y_m)$ is a binary vector and that $F(x,y)$ is a binary formula of size $... 7answers 216k views ### How to construct XOR gate using only 4 NAND gate? xor gate, now I need to construct this gate using only 4 nand gate ... 1answer 1k views ### How do you produce a CNF from a circular graph with colouring? If you had a circular graph e.g. A->B->C->D->E->A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node ... 1answer 216 views ### Is there an intuitive proof for the existence of hard functions? I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, For every$n>1$, there exists a function$f:\{0,1\}^n \rightarrow \{0,1\}$that cannot be computed by ... 1answer 580 views ### A logic function that is true iff the first operand is less than the second operand In my computer organization class I have been given a series of problems. One I'm stuck on currently is below: Assume that$X$consists of 4 bits,$x_3 x_2 x_1 x_0$, and$Y$consists of 4 bits,$y_3 ...
I am working on the following problem Find the linear least squares unit weights for the `OR' problem, ie. $v_1^T = (0,0), v_2^T = (1,0), v_3^T = (0,1), v_4^T = (1,1)$ and \$u_1 = 0, u_2 = u_3 = u_4 = ...