Question 49

Tree Expression Decomposition:
Let the eight leaves from left to right be denoted $x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8 \in \{0, 1\}$.

• Left Subtree:

  • Left child is + with leaves $x_1, x_2 \implies (x_1 + x_2)$.
  • Right child is − with leaves $x_3, x_4 \implies (x_3 - x_4)$.
  • Root of left subtree is −:
    $$L = (x_1 + x_2) - (x_3 - x_4) = x_1 + x_2 - x_3 + x_4.$$

• Right Subtree:

  • Left child is − with leaves $x_5, x_6 \implies (x_5 - x_6)$.
  • Right child is + with leaves $x_7, x_8 \implies (x_7 + x_8)$.
  • Root of right subtree is +:
    $$R = (x_5 - x_6) + (x_7 + x_8) = x_5 - x_6 + x_7 + x_8.$$

Overall Root Expression:
The root operator is +:

Maximizing the Expression:

• The coefficients of the 8 variables are:
  $$+1, +1, -1, +1, +1, -1, +1, +1.$$
• There are 6 variables with coefficient $+1$ ($x_1, x_2, x_4, x_5, x_7, x_8$) and 2 variables with coefficient $-1$ ($x_3, x_6$).
• To maximize $E$, assign value $1$ to every variable with coefficient $+1$, and assign value $0$ to every variable with coefficient $-1$:
  $$E_{\max} = 1 + 1 - 0 + 1 + 1 - 0 + 1 + 1 = 6.$$