0
$\begingroup$

How to present a three-valued logic function as a polynomial? Having only the truth table. For example:

table

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.

$\endgroup$
5
  • $\begingroup$ i.imgur.com/UYimdoE.png i.imgur//UYimdoE.png table $\endgroup$ Apr 28, 2013 at 20:35
  • $\begingroup$ 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. $\endgroup$
    – Dolma
    Apr 28, 2013 at 20:38
  • 1
    $\begingroup$ 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). $\endgroup$
    – amWhy
    Apr 28, 2013 at 20:42
  • $\begingroup$ 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 $\endgroup$ Apr 28, 2013 at 20:48
  • $\begingroup$ 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. $\endgroup$
    – amWhy
    Apr 28, 2013 at 20:51

2 Answers 2

0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks! Just what I needed. $\endgroup$ Apr 28, 2013 at 21:53
  • $\begingroup$ @user1902193 You're welcome! Glad it helps ;) $\endgroup$
    – Dolma
    Apr 28, 2013 at 22:04
0
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .