Cheap and Secure Web Hosting Provider : See Now

All output functions of a truth table

, , No Comments
Problem Detail: 

http://www.cim.mcgill.ca/~langer/273/3-notes.pdf enter image description here

I can name one more: XNOR. But besides these, what other output functions are there?

Asked By : Rafiduzzaman Sonnet
Answered By : Lieuwe Vinkhuijzen

Suppose you try to come up with a new output function, which you call $A\otimes B$, with new, custom behaviour. You will have to come up with four values: $0\otimes 0, 0 \otimes 1, 1 \otimes 0, 1 \otimes 1$. One arbitrary example is: $0\otimes 0 = 0, 0 \otimes 1 = 1, 1 \otimes 0 = 0, 1 \otimes 1 = 0$. Any sequence of zeroes and ones will do (this is the answer to your question). So you can write a string of four zeroes or ones, and that will represent your function. For example, my function is represented with $0100$. How many such strings are there? Well, try enumerating them: $0000,0001,0010,0011,\ldots$ Hence the remark that there are $2^{4}=16$ possible functions.

Not all of these functions are equally useful. The example I gave is equivalent to $A\otimes B = \neg A \wedge B$. In fact, every (binary) output function can be written as a combination of the three functions $\neg, \wedge, \vee$, i.e. NOT, OR and AND.

Consider functions that use three arguments, $A,B,C$. The truth table of such a function has $8$ entries, so there are a total of $2^{8}=256$ functions on three variables. Can you find a formula for the number of functions on $n$ variables? The example functions in your excerpt are all examples of commutative functions, which are functions $\circ$ where $A\circ B = B \circ A$ for every value of $A$ and $B$. Can you think of a noncommutative function?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57982

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback