Математический аппарат инженера
Шрифт:
Очевидно, число всевозможных слов длины n в k– ичном алфавите равно kn. Так как каждому такому слову имеется возможность предписать одно из k значений множества N, то общее количество однородных функций от n переменных выражается числом k(kn).
Если буквами алфавита служат числа от 0 до k - 1, то каждое слово (х1, х2, ..., xn) символически представляется упорядоченной последовательностью n таких чисел и рассматривается как запись n– разрядного числа в позиционной
Различные слова длины n в данном алфавите образуются как n– перестановки с повторениями (2. 10. 1). Так, в трехзначном алфавите {0, 1, 2} словами длины 4 будут все четырехразрядные числа с основанием k = 3, т. е. 0000, 0001, 0002, 0010, 0011, ..., 2221, 2222, которые соответствуют десятичным числам от 0 до 80 = 2 · З3+ 2 · З2+ 2 · З1 + 2 · 30. Поставив каждому такому четырехразрядному числу в соответствие одну из букв алфавита {0, 1, 2}, получим некоторую функцию четырех переменных
– 505 -
fi(х1, х2, x3, x4), причем количество таких функций выражается огромным числом 381.
Пусть алфавит состоит из трех букв русского алфавита {о, п, т}. Множество пятибуквенных слов в этом алфавите состоит из 35 = 243 элементов. Наряду с такими имеющими прямой смысл словами, как «топот» и «потоп», оно также включает все другие 5-перестановки, например: «ооппт», «поппп», «тттоп» и др.
Примерами однородных логических функций двух переменных могут служить операции сложения и умножения одноразрядных m– значных чисел по модулю т (2. 8. 7), внутренние операции поля Галуа (2. 8. 9) с четырехзначным алфавитом {0, 1, А, В} и т. п.
3. Табличное задание функций. Как и бинарный закон композиции (2. 7. 2), однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы которой соответствуют буквам алфавита. Таким способом представлялись функции одной и двух переменных в (1. 5. 2),(1. 5. 8) и (1. 5. 10). Для представления функций трех и большего числа переменных потребовались бы трехмерные и, вообще, n– мерные таблицы. Этого можно избежать, если столбцы матрицы поставить в соответствие не буквам алфавита, а словам, т. е. образовать kn столбцов. Для каждой функции отводится строка, клетки которой заполняются буквами из данного алфавита. Матрица всех функций n переменных в k– значном алфавите содержит kkn строк и называется общей таблицей соответствия. Например, для k = 3 и n = 2 такая матрица имеет вид:
Номера столбцов определяются расположенными над ними n– разрядными числами с основанием k, каждое из которых читается сверху вниз. Номера функций отождествляются с kn– разрядными числами, которые соответствуют строкам матрицы в той же системе счисления.
4. Двузначные однородные функции. Наиболее простым и в то же время важнейшим классом однородных функций являются двузначные (булевы) функции, частично рассмотренные в (1.5. 2) и последующих пунктах.
– 506 -
Областью
Число всевозможных булевых функций n переменных v = 2nбыстро возрастает с увеличением n (при n = 3 оно равно 256, а при n = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при n = 2).
Булевы функции одной переменной. Общая таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций):
x
|
0
1
|
y
– --
|
– --
– --
|
– --
y0
|
0
0
|
0
y1
|
0
1
|
x
y2
|
1
0
|
x
y3
|
1
1
|
1
Две функции у0 = 0 и у3 = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y1 = х повторяет значения переменной х и потому просто совпадает с ней.
Единственной нетривиальной функцией является у2 = x , называемая отрицанием или инверсией ( x читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.
– !!!!!!!!!!!!!!!!!!!!!
–
– Продолжение следует...
–
– Содержание продолжения -
...
2. Алгебра логики
3. Контактные схемы
4. Логические схемы
5. Минимизация булевых функций
6. Конечные автоматы
1. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.