How to implement NAND in XOR basis and is it possible?

Question

Electronics

The task was set to "Implement a logical element AND-NOT in the basis of Exclusive OR-NOT".
Advise, please, good resources or literature on this subject.

Answer 1

Are you sure the problem is solvable? The logical element "AND-NOT" implements a function called "Sheffer stroke":
https://en.wikipedia.org/wiki/Sheffer_stroke
It is remarkable in that it forms a complete system of functions. That is, you can express any function as a superposition of such functions, or, speaking in circuitry language, you can build from such elements, by combining them, a circuit that implements any logical function.
You want to implement a NAND gate in an XOR basis. This function has the following truth table:
https://en.wikipedia.org/wiki/XNOR_gate
Since the function belongs to Post's functional class T_1, which preserves the constant 1 (this follows from the fact that on a single set it takes the value of one), then the system of functions from the "Exclusive OR-NOT" function alone will not be complete according to Post's theorem (1) .
Let's assume that it is possible to complete the task, and there is a way to express the "AND-NOT" function in the basis of "XOR-NOT". Then, due to the completeness of the "AND-NOT" function, it follows that it is possible to express all functions in the "Exclusive OR-NOT" basis, but this is impossible, which we proved earlier using Post's theorem (1). We have come to a contradiction, therefore, the task is impossible to complete.
The only thing is, check the XNOR truth table to see if it matches your element's truth table. The rest of the calculations, I think
PS If you are interested in questions related to the Post theorem and the functional completeness of systems of logical functions, then I know what to advise you. Send me an email - I'll send it.

Answer 2

In the OR-NOT basis, you can build any logical operation, so it forms the basis for the space of Boolean functions of two variables (you can even read on Wiki, the article " Pierce's Arrow ").
And I can’t advise literature, because. studied it from notes. But if you need an algorithm of actions, then it is as follows:
1. We build a truth table for the function (we have - AND-NOT).
2. We build SDNF or SKNF, depending on what form we need to get (in this case, SKNF).
3. If necessary, we minimize the function (Vitch diagrams, Carnot maps, Quine's method).
4. From what happened, we find how the function will look like in the required basis (you have Pierce's algebra) by adding a double negation over the resulting function and expanding it according to de Morgan's rules until the form contains only operations " OR NO".
5. The resulting function can already be built on logical elements.