# Tag Info

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: ...

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.
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 ...
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$ ...
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 ...

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 ...
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 ...

### 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 ...