Функции алгебры логики
Определение. Функцией алгебры логики ( логической функцией или булевой функцией ) называется функция, аргументы которой и ее значения могут принимать значения из двухэлементного множества ( обычно из Е2 = { 0,1 } ).
Любая логическая функция n переменных может быть задана таблицей,
в левой части которой перечислены 2
наборов значений переменных; в правой
части- значения функции на этих наборах. Наборы переменных располагаются в
лекси-кографическом порядке, который совпадает с порядком возрастания наборов,
рас-сматриваемых как двоичные числа.
Число различных функций n переменных, обозначается
Р2(n). Оно равно Р2(n)=
– числу различных двоичных векторов длины 2. Рассмотрим табличное за-дание функции
одной переменной ( n=1 ). В этом случае различных наборов
пере-менной - 2, 0 и 1. Число различных функций равно Р2(1) =
22 = 4, а различные векторы длины 2 имеют вид (0,0), (0,1), (1,0),
(1,1).
Все эти функции представлены в табл. 1.1.
Таблица 1.1
|
х |
f0 |
f1 |
f2 |
f3 |
|
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
Эти функции называются и обозначаются следующим образом:
f0(x) = 0 - константа ноль, f1(x) = x – тождественная функция,
f2(x) = 
–отрицание
x (читается “ не х“),
f3(x) = 1 – константа
единица.
Рассмотрим функции двух переменных ( n=2 ). В этом случае разных наборов переменных будет 22 = 4, а разных функций Р2(2) = 24 = 16. Вcе эти функции представлены в табл.1.2 в порядке, соответствующем возрастанию чисел от 0 до 15, записанных в двоичной системе счисления. Номера функций соответствуют этим числам.
Таблица 1.2
|
х1 |
X2 |
f0 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
F15 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Некоторые из этих функций имеют специальные названия и обозначения:
следующая