2022 Developer Survey is open! Take survey.
77 votes
Accepted

Why do logic gates behave the way they do?

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here: ...
user avatar
  • 690
36 votes

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

You cant. Since $XOR$ is associative, i.e. $(x_1\oplus x_2)\oplus x_3=x_1\oplus(x_2\oplus x_3)$, you can only implement functions of the form $x_{i_1}\oplus...\oplus x_{i_k}$ where $x_{i_j}\in\{x_1,...
user avatar
  • 13.2k
25 votes

Why do logic gates behave the way they do?

It's easiest to think of $1$ representing a true statement and $0$ representing a false statement. The logic gates then act as truth functions. Say you put two statements, $p,q$, together to form a ...
user avatar
23 votes

Why do logic gates behave the way they do?

I think the questioner has it backwards. If we have a logical function such that ...
user avatar
19 votes

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

Hmmm. It can't be done with boolean algebra that's for sure, but I could wire one up physically. The trick is wiring one of the inputs to a power lead of an XOR gate. ...
user avatar
  • 382
17 votes

How to construct XOR gate using only 4 NAND gate?

From that formula? It can be done. But it's easier to start with this one: (using a different notation here) a ^ b = ~(a & b) & (a | b) Ok, now what? ...
user avatar
  • 1,813
17 votes
Accepted

Boolean absorption

Here is one way to prove the first identity: $$ A \land (A \lor C) = (A \lor 0) \land (A \lor C) = A \lor (0 \land C) = A \lor 0 = A. $$ The second identity has a similar proof. Alternatively, you ...
user avatar
9 votes
Accepted

Is there an intuitive proof for the existence of hard functions?

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent ...
user avatar
9 votes

How to construct XOR gate using only 4 NAND gate?

I think you are asking for this proof: ...
user avatar
  • 206
9 votes
Accepted

Boolean algebraic expression vs Propositional logic expression

They are not the same, but I don't blame you for thinking that they are. The reason why it doesn't seem clear that they are the same is that you've only seen one example of each. So let's step back, ...
user avatar
  • 18.8k
9 votes
Accepted

Absorption Law Proof by Algebra

First of all, this is a math question. I think you are confused on how brackets are used. They indicate precedence of operations, and can be used anywhere, even in places where such indication is not ...
user avatar
  • 28.1k
9 votes

Why do logic gates behave the way they do?

The why of it actually comes from the development of logic, which is a philosophical study of what is true and what is not true. Logic was originally a study of human language with the assumption that ...
user avatar
  • 589
8 votes

Are Boolean functions Turing complete

Informally, a (programming) language is Turing complete if every computable function has a representation. A general computable function accepts an input of arbitrary size. Boolean functions, on the ...
user avatar
8 votes

Which law is this expression X+ X’.Y=X+Y

One way of looking at this is as a consequence of distributivity, where $P+QR\equiv (P+Q)(P+R)$. Then you'll have $$\begin{align} X+(X'Y) &\equiv (X+X')(X+Y)&\text{distributivity}\\ &\...
user avatar
  • 14.5k
8 votes
Accepted

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

Note that $\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$; you can "multiply out". Add in $\qquad (A \lor \lnot A) \land B \equiv B$ and you are done.
user avatar
  • 70.8k
8 votes
Accepted

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

There are two ways to define a universal operator: when constants are allowed, and when they are not allowed. If constants are allowed, then one can define a universal operator which doesn't satisfy ...
user avatar
7 votes
Accepted

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

The classical example is $$(x_1 \lor y_1) \land (x_2 \lor y_2) \land \cdots \land (x_n \lor y_n)$$ which blows up to $2^n$ terms when converted to a DNF. Most functions have CNF and DNF complexity ...
user avatar
6 votes

How to construct XOR gate using only 4 NAND gate?

Since you already have the diagram answer, easily awailable from wikipedia by typing you question title in Google, as a .png diagram identical to yours, it should be easy for you to find the formula ...
user avatar
  • 19.1k
6 votes
Accepted

Measuring Complexity of Boolean Satisfiability Problem

The boolean satisfiability problem (SAT) involves finding a satisfying truth assignment for a set of clauses $C$ over the boolean variables $V=\{v_1, v_2, ..., v_n\}$ so that each clause in $C$ ...
user avatar
6 votes

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

I'll write your expression as $A\lor(\neg A\land B)$. Then $$\begin{align} A\lor B &= A\lor((A\lor\neg A)\land B) &\text{identity}\\ &=A\lor (A\land B)\lor(\neg A\land B) &\text{...
user avatar
  • 14.5k
6 votes

Boolean absorption

Here's one way of thinking how these identities "work". Of the first one, when A is false, A and anything is false; when A is true, A or C is true, and the whole thing is true too; therefore being ...
user avatar
  • 161
6 votes

Why is SAT based on the CNF?

Conjunctive normal form first appears, in this context, in Davis and Putnam's A computing procedure for quantification theory, in which they describe a primitive form of the DPLL algorithm (which ...
user avatar
5 votes
Accepted

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

No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it ...
user avatar
  • 140k
5 votes

Are Boolean functions Turing complete

strictly speaking as YF has answered, finite circuits cannot be Turing complete. however its worth mentioning a lead in response to this question (and maybe what youre looking for) a closely related ...
user avatar
  • 10.8k
5 votes
Accepted

Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?

There is a preprocessing method called vivification$^1$ that can be used to detect subsumed clauses. It relies on unit propagation to work. To vivify a clause, make a partial variable assignment ...
user avatar
  • 7,833
5 votes

Why is Boolean satisfiability such a rare case?

Your trick doesn't really work. There are several issues. First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$. But that doesn'...
user avatar
  • 140k
4 votes
Accepted

Sensitivity and Block sensitivity

2 does not hold as stated. All you know is that if you flip the all bits in a given block $B_i$, the output flips. Without additional conditions, I don't think you're guaranteed anything about ...
user avatar
  • 1,944
4 votes
Accepted

Classical Computation without NOT

You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can ...
user avatar
4 votes
Accepted

What is the XNOR of 3 or more inputs?

There is no standard definition for the XNOR of more than two inputs (indeed, nor is there a standard definition for less than two inputs). Since XNOR is associative, one possible definition is $$ A_1 ...
user avatar
4 votes
Accepted

What happens to uninterpreted predicates in Ackermann's reduction?

Essentially, you can treat uninterpreted predicates as boolean-valued functions (adding a new boolean sort if necessary) and replace them with boolean variables as you would other functions. For the ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible