Binary decision diagram for a six-figure Boolean function

Question

Let $p$ be the six-figure Boolean function with the following definition:

$p(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=\begin{cases} true & \text{if } x_{0}=x_{5} \text{ and } x_{1}=x_{4} \text{ and } x_{2}=x_{3}, \\ false & \text{else.} \end{cases}$

This function obviously yields $true$ iff $x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}$ is a palindrome. Provide a BDD for $p$ relative to a variable ordering of your choice.

My problems begin when I try to define an appropriate variable ordering, so I am only able to guess it: $x_{0}=x_{5} < x_{1}=x_{4} < x_{2}=x_{3}$. I'm actually pretty lost with this exercise and any help is much appreciated (sorry for not being able to provide a better own approach).

Answer 1

So finally this should be the correct solution:

The variable ordering is $x_{0} < x_{5} < x_{1} < x_{4} < x_{2} < x_{3}$. The BDD is:

Answer 2

The wikipedia article has a fairly good example in the "Variable Ordering" section. By carefully picking the order we evaluate the variables in, we can come to (at least some) decisions sooner.

In your case, if we know that for example $x_{0} = true$ and $x_{5}=false$, we can immediately answer $false$, regardless of the values of the other variables. You should be able to extend this to a full BDD of reasonably small size.

Answer 3

Can you show us what you've tried so far? The problem says you can choose any variable ordering you want, so I'm a bit puzzled why you are trying to choose an "appropriate" variable ordering or guess a variable ordering. I suggest you choose any variable ordering you want (anything, really, it doesn't matter what you choose, just pick one), and then try to build the BDD. Why don't you try that, and then show us what you got? At that point we might be able to help you better.

P.S. When we say a variable ordering, we mean an ordering: a list of the variables in some order. An example of a variable ordering would be $x_0,x_5,x_1,x_4,x_2,x_3$. (I'm not sure what's going on with $x_0=x_5$; that's not a valid part of a variable ordering.)