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:
...
- 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 ...
- 351
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
...
- 231
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 ...
- 279k
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.♦
- 166k
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 ...
- 31.2k
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 ...
- 699
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{...
- 39.1k
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 ...
- 279k
8
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 ...
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 ...
- 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 ...
- 279k
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 $\...
- 39.1k
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 ...
- 8,149
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.♦
- 166k
5
votes
Accepted
All 16 Boolean Logic Gates
What do you mean by real? You can define as many logic gates as you want and build them. However, in a boolean logic with 2 inputs, there are 16 different combination of outputs. On the other hand, it ...
- 499
4
votes
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?
Linearity for boolean functions means exactly linearity over a vector space.
Consider the field $\mathbb{F}_2$, i.e., the field with two elements $\{0,1\}$. Here the "addition" is addition modulo 2, ...
D.W.♦
- 166k
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 ...
- 30.1k
4
votes
Why is A(A+B) = A [Absorption Law]?
Here is a proof:
$$
A \stackrel{(1)}= A \cdot 1
\stackrel{(2)}= A \cdot (1+B)
\stackrel{(3)}= A \cdot 1 + A \cdot B
\stackrel{(4)}= A + A \cdot B
\stackrel{(5)}= A \cdot A + A \cdot B
\stackrel{(6)}= ...
- 41
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 <...
- 31.1k
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 & ...
- 1,493
4
votes
Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula
Most satisfiability algorithms do actually find an assignment for the variables to satisfy the equation, but in your case (a conjunction of single variables) this is not necessary.
When the entire ...
- 13.9k
4
votes
Accepted
Understanding kQBF: changing order of quantification?
$\exists x\forall y \hspace{1mm}\varphi$ is not equivalent to $\forall y \exists x \hspace{1mm} \varphi$.
Consider for example the formula "for all $x$ there exists $y$ such that $y=x^2$". When ...
- 13.6k
4
votes
Accepted
Emulating equal operator using multiplication
Suppose that $f,g$ were functions satisfying $f(A) g(A) = 1$ and $f(A) g(B) = 0$ if $A \neq B$. Take any $A \neq B$. Then $f(A) g(B) = 0$, and so either $f(A) = 0$ or $g(B) = 0$. If $f(A) = 0$ then $f(...
- 279k
4
votes
Accepted
Is any sudoku solver an SAT solver?
Your program is not a SAT solver. A SAT solver takes as input a SAT formula and outputs whether it is satisfiable or not. Your program doesn't take as input a SAT formula, so it isn't a SAT solver....
D.W.♦
- 166k
4
votes
Accepted
Is every X3SAT instance with no cycles satisfiable?
The graph below is a positive answer without words.
Here is the detailed proof.
Definitions
Let $X$ be an instance of X3SAT.
$X$ is linear if any two clause shares at most one variable.
$X$ is ...
- 39.1k
4
votes
Why is Boolean satisfiability such a rare case?
The sets of satisfiable and unsatisfiable formulas are the same size: both are countably infinite. However, that doesn't imply that there's any particular relationship between the number of ...
- 82.2k
4
votes
Is is possible to determine if a given number is xor combination of some numbers?
Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the ...
- 279k
Only top scored, non community-wiki answers of a minimum length are eligible