# How to present a three-valued logic function as a polynomial?

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.

-
i.imgur.com/UYimdoE.png i.imgur//UYimdoE.png table – user1902193 Apr 28 '13 at 20:35
Hint: You might want to look at bivariate polynomials ;) And since you want to fit 9 values, you might need to go up to a degree 9 polynomial. – Dolma Apr 28 '13 at 20:38
Please include the question statement into the post itself (not just in the title). Also it will help us help you if you provide more context for the problem, as well as your thoughts about it, and what you've tried. (And it will help keep your post from being closed and/or downvoted). – amWhy Apr 28 '13 at 20:42
amWhy, sorry but I really do not know what to add. 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 – user1902193 Apr 28 '13 at 20:48
Even inserting what you just wrote (no need for apologies) would improve the question. I haven't downvoted your post; but some users are rather strict about what constitutes a good question. – amWhy Apr 28 '13 at 20:51

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.$$

-
Thanks! Just what I needed. – user1902193 Apr 28 '13 at 21:53
@user1902193 You're welcome! Glad it helps ;) – Dolma Apr 28 '13 at 22:04

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?

-