Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [boolean-algebra]

The tag has no usage guidance.

0
votes
1answer
466 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
0
votes
2answers
45 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?
2
votes
1answer
49 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 ...
-1
votes
1answer
92 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 ...
2
votes
1answer
93 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 ...
1
vote
1answer
330 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 <...
4
votes
1answer
368 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 ...
-1
votes
2answers
226 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 ...
4
votes
1answer
247 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 ...
2
votes
1answer
342 views

Result of ANDing & ORing functions expressed as CDNF & CCNF

I came across following fact: If we AND two functions expressed as CDNF (Canonical Disjunctive Normal Form), then the result contains sum of commont minterms. For example consider two functions $...
2
votes
1answer
25k views

Two's complement Using ONLY Logic Gates

How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)? (This question was redirected to CS from Stack Overflow)
-1
votes
2answers
1k views

How to simplify boolean expression? [closed]

I am having trouble simplifying logical expressions to a much simpler form, can someone provide me some insight on how to approach the problem? Let's assume i have the following expression: $ABCD + A\...
4
votes
1answer
214 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 ...
2
votes
2answers
110 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 ...
1
vote
1answer
70 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 ...
20
votes
2answers
5k 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
1answer
910 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 ...
3
votes
2answers
4k 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 ...
1
vote
0answers
32 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 ...
2
votes
0answers
95 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 ...
3
votes
2answers
118 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 ...
2
votes
1answer
86 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: ...
3
votes
1answer
31 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 ...
2
votes
1answer
73 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$. ...
0
votes
1answer
82 views

Computing a boolean function with a small formula

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 $...
14
votes
7answers
152k 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 ...
1
vote
1answer
607 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 ...
6
votes
1answer
193 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 ...
-2
votes
1answer
553 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, $...
1
vote
1answer
165 views

Creating a single layer perceptron for the OR problem

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 = ...
0
votes
1answer
911 views

Brackets in distributive law?

The (second) distributive law in boolean algebra is defined as $A + (B C) = (A + B) (A + C)$ But wouldn't it be correct to define it that way: $(A + (B C)\, ) = (A + B) (A + C)$ Because if you ...
1
vote
0answers
24 views

Real versus Finite field polynomials

Let $f$ be a Boolean function. Let $g$ be the minimum degree real polynomial that represents $f$ with degree $d$. Let $g_{p}$ be the minimum degree $\Bbb F_p$ polynomial that represents $f$ with ...
-1
votes
1answer
140 views

A Combinational circuit Problem

A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, …, 9 by 1001. A Combinational circuit is to be designed which takes these 4 bits as input and ...
0
votes
1answer
107 views

4-bit input, 5-bit output, logical right shift by 2, which is the correct set of 5 output bits?

Suppose I have the following inputs: 1110 1111 If I perform a logical right shift by 2 on each, are the 5-bit outputs these: 00111 00111 or these: 01110 01111 If it's neither, then I'd ...
0
votes
1answer
121 views

Example of a boolean function

Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?
3
votes
1answer
132 views

Couting Self dual functions

The Dual of a Boolean function $F(x_1, x_2, ..., x_n)$, written as $F^D$ is the same expression as that of $F$ with $+$ and $.$ swapped. $F$ is said to be self dual if $$F=F^D$$ How can we count ...
1
vote
1answer
170 views

Lower bound on approximation degree in Nisan-Szegedy

In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It ...
1
vote
1answer
66 views

consider a base 16 adder how to modify the adder so that it can perform a base 8 addition?

Consider a base 16 adder. How can I modify the adder so that it can perform a base 8 addition? I expect this question will appear in my exam tomorrow; if anyone can give me a hint or a solution, I'd ...
0
votes
1answer
91 views

Prove that $\neg 0 = 1$

Starting from this definition https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$? Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ¬...
5
votes
1answer
666 views

Which CNF boolean formulas blow up exponentially at conversion to DNF?

If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa). But what is an example of such a formula (and is there a ...
1
vote
1answer
340 views

Parity function

How is the parity function defined in standard way if inputs are in $\{-1,+1\}$ instead of $\{0,1\}$. For $\{0,1\}$, parity is $x_1\oplus x_2\oplus\cdots\oplus x_{n-1}\oplus x_n$. I am looking for how ...
1
vote
1answer
76 views

How do you represent basic arithmetic using boolean function? [closed]

Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers? ...
1
vote
0answers
98 views

Connection between formula size and time complexity

Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree. Is there a connection between ...
1
vote
1answer
46 views

Function with minimum sensitivity

Let sensitivity be defined as in Sensitivity and Block sensitivity Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$? Is ...
5
votes
2answers
318 views

Sensitivity and Block sensitivity

May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity. Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function. Let ...
2
votes
2answers
461 views

Karnaugh map simplification

I'm working through an example that looks like a fairly simple Karnaugh map and simplification, but I feel stupid that I can't seem to understand the correct answer. This is the map: My groupings: ...
1
vote
0answers
50 views

How do I triangularise a netlist?

I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will ...
1
vote
1answer
34 views

Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
1
vote
2answers
361 views

Do Karnaugh maps yield the simplest solution possible?

I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example: Truth table (inputs are A B C; output is F): ...
0
votes
1answer
93 views

Unique boolean functions with one input

I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique". I thought about writing down the truth table for a NOT, ...