Функция f(x1, х2,..., xn), принимающая логическое значение (1 или 0 ) изависящая от логических переменных, называется логической функцией. Логическую функцию можно представить в виде отображения f: En ® E,где множество En = E ´ E ´ … ´ Eестьдекартово произведениевсех упорядоченных наборов (x1, х2,..., xn)таких, что
xi ÎE, i = 1,2,…, n.
Таким образом, область определения логической функции – совокупность всевозможных n-мерных наборов из нулей и единиц, а для её задания достаточно указать, какие значения функции соответствуют каждому из наборов (табл. 2.3).
Наборы в таблице будем располагать в порядке возрастания их номера N. Такой порядок расположения наборов называется стандартным или естественным.
При таком порядке каждому набору α = (α1, …, αn), где αi есть 0 или 1, ставится в соответствие целое число
N = α12n-1+ … + αn-121+ αn.
Наборам (0, 0,...,0, 0), (0, 0,..., 0, 1),..., (1, 1,..., 1, 1)соответствуют числа N = 0, 1,..., 2n-1. Количество входных наборов для функции n переменных равно k = 2n.
Таблица 2.3. Задание логической функции
|
|
N | х1 | х2 | … | хn-1 | хn | f(x1, x2,..., xn-1, хn) |
… | f(0, 0,..., 0, 0) | |||||
… | f(0, 0,..., 0, l) | |||||
… | … | … | … | … | … | ……………… |
2n-2 | … | f(l, 1, …, 1, 0) | ||||
2n-1 | … | f(l, 1, …, 1, 1) |
Все множество наборов переменных по значениям функции на них можно разбить на 2 подмножества:
[1] – единичное множество наборов, на которых f = 1;
[0] – нулевое множество наборов, на которых f = 0.
Теперь определим количество различных функций n переменных. Каждая функция задается набором своих k значений, которому также можно поставить в соответствие k-разрядное двоичное число.
Располагая функции в таблице в порядке возрастания соответствующих им чисел, мы получим все возможные различные функции. Количество таких функций будет равно .
Далее рассмотрим логические функции одной и двух переменных, которые определяют также и операции, используемые при записи логических формул. Их можно считать «элементарными» функциями (табл. 2.4, 2.5).
Таблица 2.4. Функции g(x)
х | g1(x) | g2(x) | g3(x) | g4(x) |
0 0 | 1 1 |
Таблица 2.5. Функции двух переменных f(х1, х2)
х1 х2 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 | f16 |
0 0 | ||||||||||||||||
0 1 | ||||||||||||||||
1 0 | ||||||||||||||||
1 1 |