Чтение онлайн

на главную

Жанры

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

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

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

системе счисления с основанием k, т. е. x1kn -1 + x2kn –2 + … + xn– 1k1 + xnk0 = q. Числа q = 0, 1, ..., kn1 служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение строгого порядка). Аналогично номерами функций можно считать kn– разрядные числа в той же системе счисления.

Различные слова длины 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 -

fi1, х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 переменных служит множество слов длины n. Они представляют собой всевозможные наборы из n двоичных цифр и их общее количество равно 2n.

Число всевозможных булевых функций 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. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.

Поделиться:
Популярные книги

Бастард Императора

Орлов Андрей Юрьевич
1. Бастард Императора
Фантастика:
фэнтези
аниме
5.00
рейтинг книги
Бастард Императора

На границе империй. Том 10. Часть 1

INDIGO
Вселенная EVE Online
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 10. Часть 1

Имя нам Легион. Том 7

Дорничев Дмитрий
7. Меж двух миров
Фантастика:
боевая фантастика
рпг
аниме
5.00
рейтинг книги
Имя нам Легион. Том 7

Измена. Вторая жена мужа

Караева Алсу
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Измена. Вторая жена мужа

Буря империи

Сай Ярослав
6. Медорфенов
Фантастика:
аниме
фэнтези
фантастика: прочее
эпическая фантастика
5.00
рейтинг книги
Буря империи

Пенсия для морского дьявола

Чиркунов Игорь
1. Первый в касте бездны
Фантастика:
попаданцы
5.29
рейтинг книги
Пенсия для морского дьявола

На изломе чувств

Юнина Наталья
Любовные романы:
современные любовные романы
6.83
рейтинг книги
На изломе чувств

Тринадцатый II

NikL
2. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Тринадцатый II

Сирота

Шмаков Алексей Семенович
1. Светлая Тьма
Фантастика:
юмористическое фэнтези
городское фэнтези
аниме
5.00
рейтинг книги
Сирота

Законы Рода. Том 9

Flow Ascold
9. Граф Берестьев
Фантастика:
городское фэнтези
попаданцы
аниме
дорама
фэнтези
фантастика: прочее
5.00
рейтинг книги
Законы Рода. Том 9

Красноармеец

Поселягин Владимир Геннадьевич
1. Красноармеец
Фантастика:
боевая фантастика
попаданцы
4.60
рейтинг книги
Красноармеец

Огненный князь 4

Машуков Тимур
4. Багряный восход
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Огненный князь 4

Начальник милиции. Книга 5

Дамиров Рафаэль
5. Начальник милиции
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Начальник милиции. Книга 5

Инкарнатор

Прокофьев Роман Юрьевич
1. Стеллар
Фантастика:
боевая фантастика
рпг
7.30
рейтинг книги
Инкарнатор