Pseudo-Boolean function: Difference between revisions

Revision as of 09:32, 8 July 2023

Revision as of 09:46, 8 July 2023

Line 5:

==Representations==

Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Citecite journal |titlelast1=Hammer |first1=P.L. |last2=Rosenberg |first2=I. |last3=Rudeanu |first3=S.|date=1963 |title=On the determination of the minima of pseudo-Boolean functions|last1 = Hammer|first1 language=ro P.L.|date = 1963|journal = Studii și cercetări matematice|last2 = Rosenberg|first2 = I.|last3 = Rudeanu|first3 = S.|issue =14 14|pages = 359–364|language = ro|issn = 0039-4068}}</ref><ref>{{Citecite book |titlelast1=Hammer |first1=Peter L. |last2=Rudeanu |first2=Sergiu |year=1968 |title=Boolean Methods in Operations Research and Related Areas|last1 = Hammer|first1 = Peter L.|publisher = Springer|year = 1968|isbn = 978-3-642-85825-3|last2 = Rudeanu|first2 = Sergiu}}</ref>

:<math>f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i<j}a_{ij}x_ix_j + \sum_{i<j<k}a_{ijk}x_ix_jx_k + \ldots</math>