Questions tagged [boolean-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
21
votes
2answers
6k views

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

How could I express an AND gate using only XOR gates ?
20
votes
7answers
203k 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 ...
17
votes
11answers
5k views

Why do logic gates behave the way they do?

I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do. Why for example: ...
10
votes
2answers
2k views

Are Boolean functions Turing complete

A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$. The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left ...
7
votes
0answers
127 views

Boolean formula that agrees with most truth assignments

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}...
6
votes
1answer
206 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 ...
6
votes
1answer
1k 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 ...
6
votes
1answer
58 views

Small world theorem for set constraints

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
6
votes
1answer
4k views

What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in ...
5
votes
2answers
1k views

Boolean absorption

A and ( A or C ) = A And A or A and C = A How do these identities work? Using the rule A and ( B or C ) = A and B or A and C For the first identity, I get A and A or A and C = A or A ...
5
votes
3answers
5k 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 ...
5
votes
2answers
867 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 ...
5
votes
2answers
2k views

Converting truth table to algebraic normal form

Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)? I have seen that Sage has one implementation (official ...
5
votes
1answer
202 views

Finding a graph-theoretic representation of expressions in Boole's algebra

I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but ...
4
votes
1answer
125 views

A universal operator necessarily generates $\neg x$ for input $x,…,x$

I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more. I saw a claim in a slideshow from a basic computer architecture course ...
4
votes
1answer
375 views

Issue understanding the reduction of SAT to 3-SAT in poly time

Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-...
4
votes
3answers
3k 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. ...
4
votes
1answer
113 views

Why are there two not operators in lambda calculus?

From Wikipedia: $\mathrm{true} = \lambda a. \lambda b. a$ $\mathrm{false} = \lambda a. \lambda b. b$ Because true and false choose the first or second parameter they may be combined to provide logic ...
4
votes
1answer
467 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 ...
4
votes
1answer
509 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 ...
4
votes
1answer
409 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 ...
4
votes
1answer
86 views

Common parse tree for several formulas

I have a large (~1k) number of boolean formulas like: f1(x) = p1 AND p2 f2(x) = (p1 AND p2) OR p3 f3(x) = p4 OR !p5 The argument x is a set, and the predicates (...
4
votes
2answers
2k views

Simplest combination of logic gates to produce a given set of outputs

Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the ...
4
votes
0answers
202 views

Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?

There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
4
votes
0answers
26 views

Constructing xor separable boolean upper bound

Problem statement Suppose I have a boolean function $f: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2$ where $\mathbb{F}_2 = \{0,1\}$. I define two boolean functions $h: \mathbb{F}_2^n \to \...
4
votes
0answers
44 views

Why do Karnaugh maps work?

The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, ...
4
votes
0answers
102 views

Can minimal CNF contain clause longer than initial CNF?

Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$. Can $\Phi_{min}$ contain a clause of size $m > k$? What ...
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
125 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 ...
3
votes
2answers
174 views

Is every X3SAT instance with no cycles satisfiable?

Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
3
votes
1answer
120 views

Is is possible to determine if a given number is xor combination of some numbers?

I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
3
votes
1answer
95 views

Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula

I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption ...
3
votes
1answer
621 views

Relation between Lattice and Boolean Algebra

In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). ...
3
votes
1answer
4k views

Boolean Algebra : Using identities, prove x(x + y) = x

Example: Prove the ABSORPTION LAW: $$ x(x + y) = x $$ $ Solution: \\ x(x + y) \\ = (x + 0)(x + y) \;\;\;\;\; Identity \;Law \\ = x + (0 · y) \;\;\;\;\;\;\;\;\;\;\; Distributive \;Law \\ = x + y · 0 ...
3
votes
1answer
284 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 ...
3
votes
1answer
70 views

Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
3
votes
1answer
310 views

Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
3
votes
1answer
55 views

What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
3
votes
1answer
95 views

Programmatically checking equivalence of statements

So as part of a theorem-prover/checker, I'm using Prolog to try to determine the equivalence of statements that have been parsed into tree form, e.g. $x=2$ is represented as ...
3
votes
1answer
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 ...
3
votes
1answer
146 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 ...
3
votes
1answer
801 views

Karnaugh map with don't care: increasing the number of groups instead of simplifying

AB 00 01 11 10 00 | x | 1 | 0 | 1 | CD 01 | 0 | 1 | x | 0 | 11 | 1 | x | x | 0 | 10 | x | 0 | 0 | x | The answer to the ...
3
votes
0answers
35 views

How do I optimize a set of sub-lists which can combine to recreate higher level lists?

I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list ...
3
votes
0answers
131 views

Boolean function minimization

Does there exist a Boolean function for which no sum-of-products expression that minimizes the number of products also simultaneously minimizes the number of literals (counting repetitions)? ...
3
votes
0answers
72 views

Iterating over a union of sets denoted by bitmasks

Consider the set $\mathbb{B}^n$ of all $n$-digit binary numbers. Let us define a bitmask as a tuple $M=(m_0,\ldots,m_{n-1})$, where $m_i\in \{0,1,*\}$. Such bitmask denotes a set $S \subset \mathbb{B}^...
3
votes
0answers
166 views

Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? ...
2
votes
3answers
22k views

Absorption Law Proof by Algebra

I'm struggling to understand the absorption law proof and I hope maybe you could help me out. The absorption law states that: $X + XY = X$ Which is equivalent to $(X \cdot 1) + (XY) = X$ No problem ...
2
votes
2answers
246 views

Is my simplified explaination of the XOR swap correct?

The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows: a = a ^ b b = a ^ b a = a ^ b Now, I was ...
2
votes
3answers
139 views

Is $A\odot B\odot C = A\oplus B\oplus C$?

(The notations used: $\oplus$ is XOR operator $\odot$ is XNOR operator) I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. ...
2
votes
1answer
208 views

Can the Euclidean distance function be computed using only XOR's

The Eulidean distance function $d$ of $x$ and $y$ is given by: $ d(x,y)=\sqrt{x^2-y^2} $ Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. ...

1
2 3 4 5