Return to MODULE PAGE
McCulloch-Pitts Neurons: Intermediate Level (page 7)
Michael Marsalli: Author
Logic Functions
Let I^2 = { (1,1), (1,0), (0,1), (0,0) }. If we think of the pair of inputs x1 and x2 as an ordered pair (x1, x2), then I^2 is the set of all possible inputs for a two input MCP neuron. We can then think of an MCP neuron as a type of function from I^2 to the set {0,1}. In other words, an MCP neuron assigns 1 or 0 to each ordered pair made from the set {0,1}. For example, the MCP neuron in Table 1 above is essentially the function F from I^2 to {0,1} where F((1,1))= 1, F((0,0)) = 1, F((0,1)) = 0, and F((0,0)) = 0. This function is summarized in the table below.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A function from I^2 to {0,1} is called a logic function. Every two input MCP neuron is thus a logic function. Logic functions are closely connected to truth tables, which you may have seen in a logic course. Consider the following table for a logic function called OR.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Note that the value of OR is 1 if either x1 = 1 or x2 = 1, or both are 1. Otherwise OR is 0. Consider the MCP neuron with w1 = 0.5, w2 = 0.5, and T = 0.5. If we use A for the output of this neuron, then we would have the following table.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thus this particular MCP neuron is the same as the OR function.
Exercise. Construct a table as above for the MCP neuron with w1= 0.5, w2= 0.5, and T= 0.2. |
Exercise. Construct a table as above for the MCP neuron with w1= 0.5, w2= 0.3, and T= 0.5. |
Another logic function is the AND function, which gives an output of 1 only when both x1 = 1 and x2 = 1. Here's the table for the AND function.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We saw above that the OR function can be obtained from a two input MCP neuron by a suitable choice of weights and threshold.
Exercise. Find the weights and threshold for an MCP neuron that has the same output as the AND function. Are there other MCP neurons which have the same output as the AND function? |
We now know that every two input MCP neuron is essentially a logic function. And we've also seen that we can find MCP neurons that have the same output as certain given logic functions. So you might wonder if two input MCP neurons and logic functions are really essentially the same. In other words, for every logic function can we find an MCP neuron that has the same output ? Before we try to answer this question, let's find out just how many logic functions there are.
We know a logic function has to assign 1 or 0 to each of the four ordered pairs in I^2. So there are two possible outputs for each of the four inputs. This means there are sixteen possible logic functions. We've already seen the OR and AND functions. Here's the table of another logic function called the XOR function. The XOR function has output 1 only if either x1 = 1 or x2 = 1, but not both.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We now have tables for the OR, AND, and XOR function. If you look back to Table 3, you'll find a fourth logic function. So we have tables for one fourth of the possible logic functions.
Exercise. Find tables for all sixteen possible logic functions. |
Now that we have tables for the sixteen logic functions, we can try to find two input MCP neurons that have the same output. Of course, there may be more than one choice of weights and threshold that will produce a particular logic function. Because we're allowed to use decimals for the weights and thresholds, there are technically an infinite number of possible two input MCP neurons. But there are only sixteen logic functions. So there are many two input MCP neurons that have the same table. We've found two input MCP neurons for the OR and AND functions. What about the XOR function?
Exercise. Try to find a two input MCP neuron that has the same output as the XOR function. |
We will return to the problem of the XOR function in a later section.