Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
    
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
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.