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 universal sets of gates that do not utilise the NOT transformation. Thanks!

EDIT: to clarify, you can perform any set of operations you want, but if there is some sequence that you apply these operations in that is equivalent to a NOT operation then they are forbidden. For example, in quantum computing you can take the square root of a not operation, but as applying two of these gives a not operation then this would not be allowed

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 also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful.

It is more meaningful to ask what happens if all gates are monotone, that is, they satisfy $g(x_1,\ldots,x_n) \leq g(y_1,\ldots,y_n)$ whenever $x_i \leq y_i$ (here $\text{FALSE}\leq\text{TRUE}$). Such circuits are known as monotone circuits, and they can only compute monotone functions. One natural complete basis is $\{\text{AND},\text{OR}\}$. You can show that this basis is complete using DNFs.

StackExchange Computer Science Q#44493, answer score: 4