2
$\begingroup$

By hand, I computed $f(x,y) = x \oplus xy = (0, 0, 1, 0)$ since, in ascending (lexicographical) order,

$f(0,0) = 0 \\ f(0,1) = 0 \\f(1,0) = 1 \\ f(1,1) = 0$

However, using the following code on sagemath

R.<x,y> = BooleanPolynomialRing(2)
B = BooleanFunction( x+x*y)
B.truth_table(format='int')

The answer is (0, 1, 0, 0). I tried with other Boolean functions of two variables and I'm getting different answers from what I calculate by hand. Another example is $f(x,y) = x$. By hand, the answer is $f = (0,0,1,1)$ but using sage, it is $(0, 1, 0, 1)$. Is it that the order in which the bits are calculated is incorrect?

A few details for context

I'm specifically interested in the convention regarding Boolean functions. For example, there are tasks that ask to find the ANF of a boolean function given in the $f = (b_1,b_2, \ldots , b_n)$ where $b_i$ is either $0$ or $1$. In the textbooks I have checked, it is often assumed that these values are in ascending order. In this answer, for instance, the truth table was calculated in ascending order

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The truth table

\begin{array}{|c|c|c|} \hline x & y & xy & x \oplus xy \\ \hline 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline \end{array}

and you can use Boolean formulas

f = propcalc.formula("x ^x&y")
f.truthtable()

outputs

x      y      value
False  False  False  
False  True   False  
True   False  True   
True   True   False
Improve this answer
$\endgroup$
6
  • $\begingroup$ But what if I have, say, a function in a larger ring? What is the convention for ordering the bits? And if I'm given a boolean function in truth table form (i.e something like $f = (0101)$), doesn't that mean the entries are listed in ascending order? $\endgroup$
    – E.Nole
    Commented Dec 17, 2020 at 21:52
  • $\begingroup$ @E.Nole The convention has to be specified, presumably in the software documentation. There really is no issue with the computation itself, right? $\endgroup$
    – kodlu
    Commented Dec 17, 2020 at 22:00
  • $\begingroup$ Although, I've given the answer, actually, there is ask.sageMath for your questions. This is rather a usage of sagemath. There is no convention, lex, inv_lex, grad, etc are possible examples. $\endgroup$
    – kelalaka
    Commented Dec 17, 2020 at 22:01
  • 1
    $\begingroup$ It is a matter of taste on the truth table, some uses to start false, some - like me - used to start 1 since I've seen logic. So, from the docs, you should see the order like here and you can specify it according to yo your need. $\endgroup$
    – kelalaka
    Commented Dec 17, 2020 at 22:34
  • 1
    $\begingroup$ Also, note that; in commutative algebra, the order affects the result. $\endgroup$
    – kelalaka
    Commented Dec 17, 2020 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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