Content

Functions for Boolean Algebras

Let's make it harder to make it simpler! It turns out that here is another and easier way to produce a switching circuit once you have the circuits's table. This comes about from knowing the function that will do the job for you. This function is a polynomial on the possible switches and their complements and polynomials are relatively simple to handle. As they say, now read on.

Your used to dealing with functions of real numbers, things like $f(x) = 3x + 5$ and $f(x) = x^2 - 5x - 1$, where there is only one variable $x$. But you can also have functions of two variables: $f(x, y) = x + xy - 2y$ and $f(x, y) = x^2 + y^2$. Functions with two variables work in more or less the same way as do functions of one variable. If you want to know the value of the function at particular values of $x$ and$ y$ you just substitute them in the formula for $f(x, y)$.

Questions

  1. Find the values of the following functions when $x = 1$ and $y = -1$.
    1. $\hspace{10px}f(x, y) = x + xy - 2y;$
    2. $\hspace{6px}f(x, y) = x^2 + y^2;$
    3. $f(x, y) = e^xe^y.$
  2. But sometimes we can reduce functions of two variables to functions of one variable. What happens to the two variable functions in Q36 if $ y = 3x$?

But functions are not confined to being associated with real numbers. They work with whatever class of variables you choose. We now choose to work with variables from Boolean algebras. (Why are you not surprised?) But in some ways Boolean algebras make the algebra simpler! Like the functions of real numbers there is a point in introducing functions of Boolean algebras. We'll get to this in the next section.

Let's have a look at a couple of functions on the simplest Boolean algebra there is - the one consisting only of 0 and 1. We'll see what the functions looks like by drawing up a table of values.

Example

Let $f(x, y) = x + (x + y)$. The table we get from this is

$x$ $y$ $f(x,y)$
0 0 0
1 0 1
0 1 1
1 1 1

The result is not surprising because we can simplify the function to $f(x, y) = x + y$.

Example

Let $f(x, y) = x + xy$. The table we get from this is

$x$ $y$ $f(x,y)$
0 0 0
1 0 1
0 1 0
1 1 1

Again this is not surprising as $x + xy = x$.

Questions

  1. Produce a table that shows the values of the following functions for the smallest Boolean algebra. Check these values by simplifying the expression if possible.
    1. $\hspace{10px}f(x, y) = x + y + 1;$
    2. $\hspace{6px}f(x, y) = (x + 1)(y' + 0);$
    3. $f(x, y) = xy;$
    4. $f(x, y) = (xy')(xy)';$
    5. $\hspace{3px}f(x, y) = x + x'y(x + y)$;
  2. But there is no reason to be restricted to two variables. Produce a table that shows the values of the following functions of three variables for the smallest Boolean algebra.
    3. \[f(x, y, z) = (x + y)(y + z)(z + x);\] \[f(x, y, z) = x + x'y + y'z.\]

Questions

  1. Show that any non-identity function of one variable on any Boolean algebra can be written in the form $f(x) = \alpha x + \beta x'$. What can be said about $\alpha$ and $\beta$?
  2. Show that any non-identity function of two variables on any Boolean algebra can be written in the form $f(x, y) = \alpha xy + \beta x'y + \gamma xy' + \delta x'y'$. What can be said about $\alpha, \beta, \gamma$ and $\delta$?
    What is the corresponding situation for a polynomial function of three variables?

The form of a two variable non-identity function for switches $x$ and $y$ can be written as \[f(x, y) = f(1, 1)xy + f(0, 1)x'y + f(1, 0)xy' + f(0, 0)x'y'\] and we know the values of the constants by the answer to Q41. This form is called the disjunctive normal form. It can be used more readily to produce switching circuits than the circuit we used in the Switches Again section. We know from the table of the situation what the values of $f(0, 0), f(1, 0), f(0, 1) $and $f(1, 1)$ are and so we can substitute these in the disjunctive normal form to get the function we need so that we can immediately draw up the switching system for a particular problem. But you will get a simpler circuit if you use the various methods from Boolean algebra to simplify the polynomial you have.

Questions

    1. Devise a switching circuit for two people, where a light goes on if and only if they both vote for a proposal.
    2. Devise a switching circuit for three people, where a light goes on if and only if there is a majority in favour of the proposal.
    3. Able, Baker and their children Charlie and Delta need a voting system too. However, Able and Baker are prepared to accept a majority vote but decide that if they both vote for a proposal or they both vote against it, their opinion should prevail. Devise a switching circuit for this situation.
  2. Design the switching circuit for the Light in the Passage using a disjunctive normal form approach.
  3. Three passages meet and there is a strong light at this junction that lights up all the passages. Each passage has a switch at the end away from the light. A switching circuit is needed that will only go on when an odd number of switches is on. Design this circuit.

Next page - Content - A Reasoning Retreat