logo
Все готово(Шпоры)

1.1 Понятие о логических функциях

Отличительной особенностью логических функций является то, что они принимают значения в конечных множествах. Иначе говоря, область значений логической функции всегда представляет собой конечную совокупность чисел, символов, понятий, свойств и, вообще, любых объектов.

Если область значений функции содержит k различных элементов, то она называется k-значной функцией. Перечень символов, соответствующих области значений функции, называется алфавитом, а сами символы - буквами этого алфавита: N={a1,a2,...ak}.

Логические функции могут зависеть от одной, двух и, вообще, любого числа переменных (аргументов) - х12..хm. В отличие от самой функции, аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств. В теоретико-множественном смысле логическая функция n переменных

y= f(x1,x2,..xn) (1.1)

представляет собой отображение множества наборов (n- мерных векторов) вида (x1,x2,..xn), являющихся областью ее определения, на множество ее значений N={a1,a2,..ak}, при условии однозначности этого отображения:

f: (x1,x2,..xn)N (1.2)

Логическую функцию можно также рассматривать как операцию, заданную законом композиции X1*X2*..*XnN, где X1,X2,..Xn - множества, на которых определены аргументы.

-----------------------------------------------------------------------------

Бинарное отношение ставит в соответствие паре объектов (a,b) третий объект с. При этом a,b операнды, с - результат операции или композиция объектов a и b. Если a принадлежит А, b принадлежит B, а с принадлежит С, то А*В C - закон композиции.

-----------------------------------------------------------------------------

Логическая функция называется однородной, если она принимает значения из того же множества, что и все ее аргументы, т.е. X1=X2=..=Xn.

Однородная логическая функция рассматривается как закон композиции NnN и определяет некоторую n-местную операцию на конечном множестве N.

Областью определения однородной функции y=f(x1, x2,..xn) служит множество наборов (x1, x2,..xn), называемых словами, где каждый из аргументов xi замещается буквами k-ичного алфавита {0,1,2,..k-1}. Очевидно, число различных слов длины n в k-ичном алфавите равно kn. Т.к. каждому такому слову имеется возможность сопоставить одно из k значений множества N, то общее количество однородных логических функций от n переменных выражается числом k^k^n.