Математический аппарат инженера

Сигорский Виталий Петрович

Очевидно, число всевозможных слов длины n в k– ичном алфавите равно kⁿ. Так как каждому такому слову имеется возможность предписать одно из k значений множества N, то общее количество однородных функций от n переменных выражается числом k^(kn).

Если буквами алфавита служат числа от 0 до k - 1, то каждое слово (х₁, х₂, ..., x_n) символически представляется упорядоченной последовательностью n таких чисел и рассматривается как запись n– разрядного числа в позиционной

системе счисления с основанием k, т. е. x₁k^{n -1} + x₂k^{n –2} + … + x_{n– 1}k¹ + x_nk⁰ = q. Числа q = 0, 1, ..., kⁿ– 1 служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение строгого порядка). Аналогично номерами функций можно считать kⁿ– разрядные числа в той же системе счисления.

Различные слова длины n в данном алфавите образуются как n– перестановки с повторениями (2. 10. 1). Так, в трехзначном алфавите {0, 1, 2} словами длины 4 будут все четырехразрядные числа с основанием k = 3, т. е. 0000, 0001, 0002, 0010, 0011, ..., 2221, 2222, которые соответствуют десятичным числам от 0 до 80 = 2 · З³+ 2 · З²+ 2 · З¹ + 2 · 3⁰. Поставив каждому такому четырехразрядному числу в соответствие одну из букв алфавита {0, 1, 2}, получим некоторую функцию четырех переменных

– 505 -

f_i(х₁, х₂, x₃, x₄), причем количество таких функций выражается огромным числом 3⁸¹.

Пусть алфавит состоит из трех букв русского алфавита {о, п, т}. Множество пятибуквенных слов в этом алфавите состоит из 3⁵ = 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– мерные таблицы. Этого можно избежать, если столбцы матрицы поставить в соответствие не буквам алфавита, а словам, т. е. образовать kⁿ столбцов. Для каждой функции отводится строка, клетки которой заполняются буквами из данного алфавита. Матрица всех функций n переменных в k– значном алфавите содержит k^kn строк и называется общей таблицей соответствия. Например, для k = 3 и n = 2 такая матрица имеет вид:

Номера столбцов определяются расположенными над ними n– разрядными числами с основанием k, каждое из которых читается сверху вниз. Номера функций отождествляются с kⁿ– разрядными числами, которые соответствуют строкам матрицы в той же системе счисления.

4. Двузначные однородные функции. Наиболее простым и в то же время важнейшим классом однородных функций являются двузначные (булевы) функции, частично рассмотренные в (1.5. 2) и последующих пунктах.

– 506 -

Областью

определения булевых функций от n переменных служит множество слов длины n. Они представляют собой всевозможные наборы из n двоичных цифр и их общее количество равно 2ⁿ.

Число всевозможных булевых функций n переменных v = 2ⁿбыстро возрастает с увеличением n (при n = 3 оно равно 256, а при n = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при n = 2).

Булевы функции одной переменной. Общая таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций):

x

|

0

1

|

y

– --

|

– --

– --

|

– --

y₀

|

0

0

|

0

y₁

|

0

1

|

x

y₂

|

1

0

|

x

y₃

|

1

1

|

1

Две функции у₀ = 0 и у₃ = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y₁ = х повторяет значения переменной х и потому просто совпадает с ней.

Единственной нетривиальной функцией является у₂ = x , называемая отрицанием или инверсией ( x читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

– !!!!!!!!!!!!!!!!!!!!!
–

– Продолжение следует...
–

– Содержание продолжения -

...

2. Алгебра логики

3. Контактные схемы

4. Логические схемы

5. Минимизация булевых функций

6. Конечные автоматы

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