AND, OR, NOT, and creating turing complete programming languages

Question

Suppose I have an arbitrary computing language, and the following holds:

Let all constants be finite, and assume we are computing in binary.

• An arbitrary number of inputs, A, and outputs, B, can be created, which can be called at any time, to any function.

• An arbitrary number of functions can be made, which each take $ F_A $ inputs and $ F_B $ outputs specific to the function, using addition mod 2 as a fundamental operation. $ F_A $ and $ F_B $ can be called from anywhere for each function. Additionally, every function can be called anywhere.

• An arbitrary number of programs can be made, which can contain $ P_F $ functions for computing, and an arbitrary number of its own inputs, $ P_A $, and outputs, $ P_B $ . Each of the $ P_F $ functions follow the free "rules" above.

• Variables, Functions, and Programs are called in sequence by the Master Set, M, which has separate variables, functions, and programs used to order operations.

• Recursion is possible in the sense that one can create programs that call themselves, loop eachother, etc.

What requirements are necessary to make such a language, and assuming the variables above were infinite, is it turing complete?

But the $ real $ $ heart $ of it:

I know:

Using OR and NOT as functions, one can create the AND function.

Using AND and NOT as functions, one can create the OR function.

Is it possible to create NOT with OR and AND? Please give an example. Any kind of logic notation is fine.

I'm under the assumption that if one can sequentially and recursively do the following, abstractly and to infinity, one has created a Turing Machine.

Sorry for being so winded, just trying to be clear. Oh and this has an application in basic computing in the game Minecraft :P

Answer 1

I am taking your question to be about boolean algebras. No combination of $\land$ and $\lor$ in the language of boolean algebras can be equivalent to $\lnot$. This is because $x \land x = x \lor x = x$. So any expression constructed from a variable $x$ using $\land$ and $\lor$ will evaluate to $x$. More generally, any function involving any number of variables that is expressible using just $\land$ and $\lor$ will be monotonic (i.e., it will respect the ordering on the boolean algebra), but $\lnot$ is not monotonic.