Combinational logic
- Not to be confused with Combinatory logic.
Combinational logic is a computational model that has less computational power than a Finite-state automaton. Boolean circuits are combinational logic models. This computational model only preserves the current value of an operation and does not retain its history (in definition). It does not even have memory, in contrast to a Finite-state automaton which can use its states as memory.
Definition
Boolean algebra is an example of a combinational logic model. (In short, boolean algebra is can be represented as: boolean addition, +; boolean multiplication, •; boolean negation, ¬). They do not take any other values except for true and false.)
A combinational logic model contains only pure functions (i.e. functions that only use their parameters without mentioning non-parameter values or mutable parameter values; their return value is the same for the same arguments; max(x,y), which returns the maximum value between x and y, is an example of this. This is analogous to mathematical functions. Examples of them can be seen in the subsection.). A combinational logic model should at least contain pure functions of the present input only, and in definition, combinational logic does not require historical values to be preserved.
Examples
Pure functions
These are pure C functions:
ceil(x): returns the ceiling of a number
min(x,y): returns the smaller number between x and y
tan(x): returns the tangent of a number
Impure functions
These functions try to obtain values from a non-parameter:
int reta() {
return a;
}
void dec() {
static int x = 3;
x=x-1;
}
void incx() {
x=x+1;
}
void hello() {
printf("Hello\n");
/* This tries to obtain the value of the string "Hello",
* which is obviously not a parameter of the hello function.
*/
}
void input() {
int a;
scanf("%d",&a);
/* This tries to obtain a string from the console,
* which is not a parameter of the function.
}
These functions try to access the value of a modifyable parameter:
void incp(int *p) {
++*p;
}
void ret(int *q) {
return *q;
}
Computational power
Combinational logic has a small but not insignificant computational power; many of the circuits used in computers (e.g. adders, subtractors, multiplexers) are implemented in boolean algebra, a model of combinational logic. A mathematical expression is a combinational logic model; however, a reverse-polish notation expression might have more computational power than combinational logic, as it might use the stack as part of the storage.