0

Redundancy At Work

Redundant Variables

Let's say we have function with two instances of one variable, $(\textbf{A}^n,X,X)_{\alpha'}$. Now clearly, if we assign a value to $X$, it will assign values to the penultimate and last variables of $\alpha'$. Thus, this redundant variable function really acts like a function with only one instance of that variable.

$$(\textbf{A}^n,X,X)_{\alpha'}=(\textbf{A}^n,X)_\alpha$$

Let's further examine the consequences of assigning values to $X$. As described above, when a value is assigned to $X$ the penultimate and final variable will receive that value. $$(\textbf{A}^n,0,0)_{\alpha'}\text{ and }(\textbf{A}^n,1,1)_{\alpha'}$$ We can see here, that the final variables can't have different values. That is, $(\textbf{A}^n,0,1)_{\alpha'}$ and $(\textbf{A}^n,1,0)_{\alpha'}$ won't happen. The $2^n$ parses with similar condition values won't be used, and therefore can be anything.

This is where redundant variables becomes useful. If we had some function, $(\textbf{A}^n,X)_\alpha$, and we added a redundant variable, $(\textbf{A},X,X)_{\alpha'}$, we'd be free to assign whatever values we wanted to the $2^n$ parses where the last two variables were different. Such a free form function creation, without deviating logically from $\alpha$ means we'll be able to manipulate expressions that don't meet the criteria of an algebraic operation (more on that later).

Next >