Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [boolean-algebra]

The tag has no usage guidance.

178 questions
Filter by
Sorted by
Tagged with
1k views

How do i simplify this SOP expression?

Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer ...
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 ...
558 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 ...
522 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 ...
113 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

27k 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

168k 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 ...
687 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 ...
197 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 ...
562 views

1k 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 ...
149 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?
139 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 ...
178 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 ...
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 ∨ ¬...