If a certain function is a functionally complete class, express from it the constants 0,1, negation and conjunction xy using superpositions.

27 Views Asked by At

Example solution (2.4.3) at http://diskra.ru/reshenie_zadach/?lesson=5&id=12

Question

example solution

I don't understand how they are constructing for the function g which is a functionally complete class, and we have to express in the from of the constants 0,1, negation and conjunction xy using superpositions.

Also at the end:

To construct the conjunction, we fix the variable z, giving it the value 1.

We get: g(x,y,1) = 1 + x+y + 1 + x⋅1 + xy⋅1 = xy + y + 1, i.e. we got an expression of the form xy + αx + βy + γ, where α = γ = 0, β = 1.

Consider the function k(x,y) = g(x + β, y + α,1) + αβ + γ =

= g(x + 1,y,1) + 0⋅l + 0= g(g(x,x,x),y,1) =

= g(g(x,x,x),y,g(g(x,g(x,x,x),x),g(x,g(x,x,x),x),g( x,g(x,x,x),x)))

How did they replace x+1 with g(x,x,x) and wrote this whole expression -> g(g(x,x,x),y,g(g(x,g(x,x,x),x),g(x,g(x,x,x),x),g( x,g(x,x,x),x)))?