- •Дидактический план
- •Литература Основная
- •Дополнительная
- •Перечень умений
- •Тематический обзор* введение. Предмет дискретной математики
- •1. Способы задания множества
- •1.1. Множество. Подмножество. Универсальное множество
- •1.2. Операции над множествами: пересечение, объединение, разность, дополнение
- •1.4. Декартово произведение множеств
- •1.3. Порождающая процедура
- •2. Функциональные соответствия
- •2.1. Соответствие между множествами
- •2.2. Взаимно однозначное соответствие
- •2.3. Числовые и точечные промежутки
- •2.4. Суперпозиция функций
- •2.5. Схемы из функциональных элементов
- •3. Алгебраические операции
- •3.1. Операции на множестве
- •3.2. Ассоциативные и коммутативные операции
- •3.3. Двоичная система счисления
- •3.4. Проценты
- •4. Бинарные отношения
- •4.1. Отношения на множествах
- •4.2. Рефлексивные, симметричные, транзитивные отношения
- •4.3. Отношения эквивалентности
- •4.4. Отношения порядка
- •Приложения
- •Примеры решения задач
- •О мощности множеств действительных чисел
- •Двоичный 5-мерный куб
- •Задания для самостоятельной работы
- •1. Составьте логическую схему базы знаний по теме юниты:
- •2. Решить задачи 1–10.
- •Тренинг умений Пример выполнения упражнения тренинга на умение № 1 Задание
- •Решение
- •Пример выполнения упражнения тренинга на умение № 2 Задание
- •Пример выполнения упражнения тренинга на умение № 3 Задание
- •Пример выполнения упражнения тренинга на умение № 4 Задание
- •Пример выполнения упражнения тренинга на умение № 5 Задание
- •Решение
- •Пример выполнения упражнения тренинга на умение № 6 Задание
- •Решение
- •Глоссарий
- •Дискретная математика юнита 1
2.4. Суперпозиция функций
1. Функция n переменных (n-местная функция) – это соответствие типа
A1 A2 . . . An → B (другая форма записи: f(a1, a2, . . . , an) = b,
где ai A, b B). Сложение, вычитание, умножение, деление, возведение в степень являются двуместными функциями: W = x + y, W = x - y, W = x • y, W = x / y, W = xy. Двуместными функциями являются также max(x, y) и min(x, y):
Пример. max (3, -2) = 3; min (3, -2) = -2; max (3, 3) = 3.
Функции обычно задаются вычислительными процедурами, позволяющими по значению аргументов определить значение функции. Форма этих процедур может быть различной: формулы, графики, таблицы.
В понятии формулы важным элементом является операция подстановки, или суперпозиции, позволяющая из одних функций получать другие.
Если в функцию f(X) подставить вместо аргумента Х функцию g(X), получается суперпозиция (или сложная функция) f(g(X)). В этой суперпозиции f(X) – внешняя функция, g(X) – внутренняя. Допускается также переименование переменных.
Пример. Cуперпозицией внешней функции f(x) = sin x и функции g(x) = x2 является функция f(g(x)) = sin (g(x)) = sin(x2); если же внешняя функция g(x), а внутренняя f(x), то суперпозицией g(f(x)) будет (f(x)2 = (sin x)2 = sin2x.
Функции в суперпозиции могут быть не только одноместными.
Суперпозиция функций – функция, полученная из n-местной функции f(x1, x2,..., xn) и системы n функций g1, g2,..., gn некоторой подстановкой функций g1, g2,..., gn во внешнюю функцию f вместо переменных и переименованиями переменных.
Примеры.
1. Cуперпозициями
внешней функции f(X,Y)
= X
/ Y
и
функций g1(X)
=
и
g2(X)
=
aX
являются: функция
,
или функция
,
или функция
,
или функция
.
Более
сложные суперпозиции этих функций:
,
.
2. Примером суперпозиции одноместной функции Y = X, нульместных функций Y = const и двуместных функций Z = X + Y и Z = X ∙ Y является многочлен
.
3. Суперпозициями двуместных функций min(X, Y) и max(X, Y) являются функции трех переменных min(X, max(Y, Z)), min(X, min(Y, Z)), max(X, min(Y, Z)), max(X, max(X, Y)).
4. Класс элементарных функций есть множество всех суперпозиций основных элементарных функций (к ним относятся одноместные: степенные – хα, показательные – ах, логарифмические – logа x, тригонометрические и обратные тригонометрические, а также константы) и двуместных функций, представляющих арифметические операции: x + y, x - y, x • y, x / y.
Класс элементарных функций можно рассматривать как результат порождающей процедуры, в которой используются, исходя из основных элементарных функций, четыре арифметических действия и операция подстановки.
Замечание. Среди основных элементарных функций нет двуместной функции Z = XY. Ее можно выразить суперпозицией других функций: логарифмической S = lg X, показательной T = 10X и умножения – в силу тождества XY = 10Y•lgХ.
Как видно из примеров, в суперпозиции функций могут измениться как сами переменные, так и их число. Заметим также, что, выполняя подстановки, мы преобразовываем формулы, выражающие функции. Формула – это выражение, описывающее суперпозицию и содержащее функциональные знаки, символы независимых переменных (аргументов) и констант (параметров). Формула с использованием скобок определяет порядок действий при вычислении значения функции. Специальные договоренности, позволяющие упростить вид формулы, освобождают ее от некоторых скобок: так в арифметике принято, что умножение и деление связывают сильнее, чем сложение и вычитание, и одночленные сомножители не заключаются в скобки.
2. Рассмотрим еще один пример функционального соответствия. Пусть U – универсальное множество; M – некоторое его подмножество, B = {0, 1} – множество из двух чисел 0 и 1.
Характеристической
функцией множества M
U
– называется отображение
χM:
U →
B, ставящее в
соответствие элементам множества M
единицу, а элементам
дополнения
– ноль.
Примеры. 1. В множестве целых чисел Z для подмножества А квадратов целых чисел (A = {x: x = k2}) имеем: χА(4) = χА(25) = = 1, χА(5) = χА(12) = 0; для подмножества В четных чисел (В = {x: x = 2k}) имеем: χВ(4) = χВ(12) = 1, χВ(5) = χВ(25) = 0.
2. В множестве натуральных чисел U = [0, 7] для множества М = {1, 3, 6} график функции χМ - на рис. 2.7
Рис. 2.7
Легко проверяются следующие свойства характеристической функции множеств, получаемых из множеств M, N операциями пересечения, объединения, разности и дополнения:
= 1 - χM;
χM
∩
N =
χM
•
χ
N ;
χM
N
= χM
+ χ
N
- χM
•
χ
N ;
χM
\
N =
χM
- χM
•
χ
N .
Булеаном В(U) называется множество всех подмножеств множества U.
Если U - конечное множество, U = n, и его элементы занумерованы числами 1, 2,..., n, то каждому подмножеству M U соответствует n-мерный вектор из нулей и единиц с компонентами χM(en), где χM – характеристическая функция множества М. Совокупность всех таких характеристических векторов можно рассматривать как множество точек n-мерного арифметического пространства с координатами 0 или 1. Вместе они образуют n-мерный единичный куб.
Если U – конечное множество и число его элементов U равно n, то число элементов булеана В(U) равно числу 2n характеристических векторов. Подробнее об этом – в разделе «Элементы комбинаторики» Юниты 2.
