How to present a three-valued logic function as a polynomial? Having only the truth table. For example:
Perhaps this is due to Zhegalkin polynomial in binary logic. But I do not quite understand how it would look in a multi-valued logic.
How to present a three-valued logic function as a polynomial? Having only the truth table. For example:
Perhaps this is due to Zhegalkin polynomial in binary logic. But I do not quite understand how it would look in a multi-valued logic.
Here's a bivariate polynomial function that fits your points:
$$f(x,y)=\frac{1}{4}\left(-x^2y^2+5x^2y+7xy^2-23xy-4y^2+4x+12y\right)$$
To find it, you just have to see that you have $9$ points to fit, so you need at most $9$ degrees to model these points (actually for multivariate polynomials, I would rather say $9$ coefficients instead). So first write down your polynomial:
$$f(x,y)=a_{22}x^2y^2+a_{21}x^2y+a_{12}xy^2+a_{11}xy+a_{20}x^2+a_{02}y^2+a_{10}x+a_{01}y+a_{00}$$
Here you have your $9$ coefficients to find.
The last $5$ are pretty easy using:
$$\left\{\begin{array}{cc}f(0,0)=0 & \Rightarrow & a_{00}=0 \\ \left\{\begin{array}{cc}f(0,1)=2 \\ f(0,2)=2\end{array}\right. & \Rightarrow & \left\{\begin{array}{cc}a_{01}=3 \\ a_{02}=-1\end{array}\right. \\ \left\{\begin{array}{cc} f(1,0)=1 \\ f(2,0)=2\end{array}\right. & \Rightarrow & \left\{\begin{array}{cc}a_{10}=1 \\ a_{20}=0\end{array}\right. \end{array}\right.$$
And now the other coefficients are found by solving the system:
$$\left\{\begin{array}{cc}f(1,1)=0 \\ f(1,2)=0 \\ f(2,1)=0 \\ f(2,2)=1 \end{array}\right.$$
First of all, consider the three quadratic polynomials $P_2(x) = x(x-1)$, $P_1(x) = x(x-2)$, and $P_0(x) = (x-1)(x-2)$ over $\mathbb{Z}/3\mathbb{Z}$. Each of these is nonzero at precisely one of $(0, 1, 2)$, and can be easily normalized to take on the value $1$ there (how?).
Now, consider the products $P_{ij}(x,y) = P_i(x)P_j(y)$. Each of these is a degree-4 polynomial which is nonzero at only one value $(x,y) = (i,j)$ (why?). Can you see how to use linear combinations of these polynomials over $\mathbb{Z}/3\mathbb{Z}$ to build up functions that take arbitrary values on the nine points? Can you see how to extend the result from here to handle ternary functions with an arbitrary number of arguments?