2.2 The parity model

The simple model with which we begin is concerned with integers and whether they are odd or even; we shall call it the parity model. There are various technical terms associated with it:

• •

  the universe;
  

• •

  variables;
  

• •

  the parity values;
  

• •

  the parity switcher;
  

• •

  the parity table;
  

• •

  the operations;
  

• •

  expressions;
  

• •

  equivalence of expressions.

The universe for the model is the set $\mathbb{Z}$ of integers. The variables, denoted by letters $x,\,y,\,z$ and so on, can stand for any elements of the universe. For example, $x$ might represent the integer $3$, while $y$ stands for $-14$.

There are two parity values $D$ (for ‘‘odd’’) and $E$ (for ‘‘even’’) which any variable can take, depending on which element of the universe it represents. Thus if $x$ represents $3$, then the parity value of $x$ is $D$ (because the number $3$ is odd), and if $y$ represents $-14$, then the parity value of $y$ is $E$ (because $-14$ is even). (Note: using $O$ for ‘‘odd’’ might cause confusion, so we prefer $D$.)

The parity switcher $\sim$ (called ‘‘twiddles’’) is an operation on the variables, defined by setting the integer represented by $x$ to be $1$ minus the integer represented by $x$. For example, if $x$ represents $3$, then $\sim\!x$ represents $1-3=-2$, and if $y$ represents $-14$, then $\sim\!y$ represents $1-(-14)=15$. We observe that the parity value of a variable $x$ is always the opposite of that of $\sim\!x$; we summarize this observation in the following parity table.

Moreover, we note that $\sim\!(\sim\!x)=x$ because $1-(1-x)=1-1+x=x$.

There are two operations $+$ (‘‘plus’’) and $\times$ (‘‘times’’) which we can use to create expressions from the variables. Thus for variables $x$ and $y$, we can form $x+y$ and $x\times y$. For example, if $x$ and $y$ represent $3$ and $-14$, respectively, then $x+y$ represents $3+(-14)=-11,$ while $x\times y$ represents $3\times(-14)=-42$. The expressions obtained in this way also have parity values; they are completely determined by the parity values of the variables concerned as shown in the following parity tables.

Note that each table has $2^{2}=4$ rows to allow for all possible combinations of the parity values of the two variables $x$ and $y$.

The operations $\sim$, $+$ and $\times$ can be applied to expressions (as well as variables), enabling us to construct more complex expressions. When an expression involves more than a single operation, we use brackets to clarify its structure, and we work from the inside of the brackets outwards. For example, in the expression $\bigl((x+y)\times z\bigr)+y$, we first create $x+y$, we then multiply this by $z$, and finally we add $y$.

We can form parity tables for complicated expressions by building them up column by column. For example, the expression $\bigl((x+y)\times(x+z)\bigr)+(y\times z)$ has the following table.

Note that this table has $2^{3}=8$ rows to allow for all possible combinations of the parity values of the three variables $x$, $y$ and $z$.

In some cases we may find that two different expressions have the same parity table. For example, $x\times\bigl(\sim\!(y+z)\bigr)$ has the same parity table as $\bigl((x+y)\times(x+z)\bigr)+(y\times z)$ because the right-hand column of the following table is the same as that of the table above.

This means that, whatever elements of the universe are represented by $x$, $y$ and $z$, the two expressions will have the same parity, that is, both will be odd or both will be even. We call such expressions equivalent.