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: ...
AI0867's user avatar
  • 690
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 ...
A. Bollans's 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 ...
user120366's user avatar
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 ...
Yuval Filmus's user avatar
13 votes
Accepted

Representing binary functions with a finite gate set without exponential blow-up?

No. No matter what representation of functions as circuits/formulas you use, there will exist some functions that require exponential size to represent. This was proven by Shannon in 1949. See ...
D.W.'s user avatar
  • 158k
10 votes

How to construct XOR gate using only 4 NAND gate?

I think you are asking for this proof: ...
Muntasir's user avatar
  • 216
10 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 ...
Andrej Bauer's user avatar
  • 30.4k
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 ...
slebetman's user avatar
  • 679
9 votes
Accepted

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

$u = (a \vee b) \iff (u \vee \bar{a}) \wedge (u \vee \bar{b}) \wedge (\bar{u} \vee a) \wedge (\bar{u} \vee b) =1 $ Unfortunately, the equivalence above does not hold. Let $a=\text{false}$, $b=\text{...
John L.'s user avatar
  • 38.8k
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.
Raphael's user avatar
  • 72.3k
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 ...
Yuval Filmus's user avatar
7 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$ ...
Mario Cervera's user avatar
7 votes
Accepted

Why are there two not operators in lambda calculus?

The lambda-calculus is confluent. All the terms involved are strongly normalizing (these boolean encodings only work on booleans; they could do anything if applied to a lambda-term that doesn't reduce ...
Gilles 'SO- stop being evil''s 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{...
Rick Decker's user avatar
  • 14.8k
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 ...
kkm -still wary of SE promises's user avatar
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 ...
Yuval Filmus's user avatar
6 votes
Accepted

Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

Bitlength and bound needed for two's complement Prove that for $A, B \in \mathbb{Z}$, $A + B$ $= (A\operatorname{\&}B) + (A \mid B)$ $= (A \oplus B) + 2(A\operatorname{\&}B)$ where $\...
John L.'s user avatar
  • 38.8k
5 votes

Do Karnaugh maps yield the simplest solution possible?

Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://web.archive.org/web/20190920201621/...
Alan Wolfe's user avatar
  • 1,348
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 ...
Kyle Jones's user avatar
  • 8,071
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'...
D.W.'s user avatar
  • 158k
5 votes

Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers

This answer isn't rigorous or starting from first principles, but I thought this was elegant so here it is anyway. Given that addition is commutative and associative and bit-shifting all summands left ...
user253751's user avatar
  • 1,739
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 ...
Yuval Filmus's user avatar
4 votes
Accepted

Help me understand the logic behind x - y in binary by boolean?

If $z$ is an $n$-bit number then $!z=2^n-1-z$. So $$ !(!x+y)=2^n-1-(2^n-1-x+y) = x-y. $$
Yuval Filmus's 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 ...
Klaus Draeger's user avatar
4 votes
Accepted

Algorithm for simplifying ANF or polynomials?

The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF ...
D.W.'s user avatar
  • 158k
4 votes

Measuring Complexity of Boolean Satisfiability Problem

I think you have a misconception. SAT by definition accepts formulas in CNF form, and only in CNF form. Moreover, in practice, SAT solvers all use CNF form. (You might find some tools that have a ...
D.W.'s user avatar
  • 158k
4 votes

Relation between Lattice and Boolean Algebra

I would hardly describe a lattice as a generalized form of boolean algebra, since there are many more things that a lattice can describe. A better description would be to say that boolean algebra ...
Joey Eremondi's user avatar
4 votes

How does the following truth table show Y's behaviour?

Giving an example of what Eugene has said, but letting you do your own homework. Let's look at another Truth Table: $ \begin{array}{|c|c|c|c|} \hline a& b & c & \varphi \\ \hline 1 & ...
Aristu's user avatar
  • 1,483
4 votes

Why is A(A+B) = A [Absorption Law]?

I presume you are looking for a way to prove the identity using a calculus. So far you have used distributivity an idempotency. Recall that A = A1 so you get <...
Hendrik Jan's user avatar
  • 30.5k

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