# Questions tagged [boolean-algebra]

The tag has no usage guidance.

177 questions
Filter by
Sorted by
Tagged with
1k views

### Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$

I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow. I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ ...
2k views

### Measuring Complexity of Boolean Satisfiability Problem

How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. ...
37 views

### How storage affect if we use tertiary language? [duplicate]

as we uses binary language in all the computer systems around us which consist of 0s and 1s (Off and On) bits. Let assume that someone is developing a computer system based on tertiary system -1, 0, 1 ...
540 views

### How to prove the following xor equation?

In a test paper, a question is given as : ...
3k views

### Sum of 3 integers with full adder

1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image ...
513 views

### Algorithm for simplifying ANF or polynomials?

I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates. For instance: $B_{out} = B_1 B_2 \oplus B_1 B_3$ I was wondering, are there any ...
88 views

### How do I simplify this boolean expression?

I have constructed truth tables to prove that: $ABC + ABC'+ AB'C +A'BC = AB+AC+BC$ How do I prove it by simplifying the expression? I know that I can simplify: $ABC + ABC' = AB(C+C')=AB$. However I ...
111 views

### Boolean expression logic law confusion

I've been trying to attempt a particular question that I need to translate truth table into boolean expression but I'm completely stuck on one point now. First, I worked it out by using Sums of ...
56 views

26k 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)
1k views

162k 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 ...
638 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 ...
196 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 ...
556 views

981 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 ...
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 ...
146 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 ...
114 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 ...
123 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?
137 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 ...
176 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" Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It ...
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 ...
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 ∨ ¬...
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 ...