Let X = {x1,x2,...,xi, ...} be variables taking on the values 0 and 1. We call such variables binary variables.
The functions depending on binary variables and taking on the values 0 and 1 are called Boolean functions.
One of the Boole's key contributions was the development of the truth table, which captures logical representation of our functions in a tabular form.
In the truth table all possible input combinations of the variables are enumerated, and a corresponding output value of 0 or 1 is assigned for each input combination, cf. the example below.
| x1 x2 | f(x1,x2) | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
Therefore, if the function depends on n variables, its truth table consists of 2n rows.
Since for each combination of input variables of the function f(x1,...,xn), there are two values that can be assigned to f, then the number of all Boolean function depending on n variables equals the number of binary strings of length 2n and, thus, is equal to 22n.
We denote by 0 and 1 the Boolean function taking on the value 0 (resp. 1) regardless of the values of the input variables. These functions are called constants.
The following Boolean functions f(x1) = x1 and g(x1) = 1 - x1 called identity and negation respectively:
| x1 | x1 | not x1 | |
|---|---|---|---|
|
0 1 | 0 1 |
1 0 |
Some Boolean functions on two variables have standard denotations, as shown in the following table:
| x1 x2 | x1&x2 | x1+x2 | x1#x2 | x1~x2 | x1->x2 | x1/x2 | x1|x2 | ||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
Using these 2-ary functions one can construct formulas. For any formula there exist a corresponding boolean function. Two formulas f(x1,...,xn) and g(x1,...,xn) of the same number of variables are called equivalent (notation f(x1,...,xn) = g(x1,...,xn)) if their corresponding functions are equal.
Check if the following formulas are equivalent: