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.

Filter by
Sorted by
Tagged with
1
vote
2answers
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 ...
3
votes
4answers
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$ ...
3
votes
2answers
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. ...
0
votes
0answers
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 ...
0
votes
2answers
558 views

How to prove the following xor equation?

In a test paper, a question is given as : ...
1
vote
3answers
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 ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
56 views

Counterexample for equality in Quantified Boolean Formula

I'm looking for a counterexample for the following (false) equality. It should exist. $n$ is an odd integer. $f(x_1, x_2 .. x_n)$ is a boolean expression in 3 CNF form with boolean variables x. $A =...
0
votes
1answer
543 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
49 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
93 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
107 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
360 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
387 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
232 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
277 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
365 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
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)
-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
254 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
122 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
77 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
922 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
44 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
98 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
87 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
90 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
84 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 $...
15
votes
7answers
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 ...
1
vote
1answer
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 ...
6
votes
1answer
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 ...
-2
votes
1answer
562 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
170 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
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 ...
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
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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?
3
votes
1answer
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 ...
1
vote
1answer
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"[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
92 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 ∨ ¬...
6
votes
1answer
738 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 ...