Boolean Algebra

Logical functions

There can be total of 2 raise to the power 2n functions possible for n binary variables. So for n=2 i.e. two variables we have total of 16 functions and we have already talked about few of those like AND, OR, NOT. So there are 13 more functions to be defined.

F0=0

F1=xy

F2=xy’

F3=x

F4=x’y

F5=y

F6=x’y+xy’

F7=x+y

F8=(x+y)’

F9=xy+x’y’

F10=y’

F11=x+y’

F12=x’

F13=x’+y

F14=(xy)’

F15=0

Out of these 16 functions, 2 are constants F0 &F15

And 4 functions are repeated twice: F2 &F4, F10 &F12, F11 &F13, and F3 &F5

Now we are left with 10 functions and 2 out of these 10 are not commutative and associative hence not practical to use. So in the end we are left with 8 logic functions which are actually the 8 standard gates which are defined further separately:

AND, OR, NOT, BUFFER, XOR, X-NOR, NOR, NAND

All the gates can be extended to multi input gate but there is a limit on the extension of number of inputs which is known as fan-in discussed later. All the 8 gates are commutative and associative.

Leave a Reply

Your email address will not be published.