- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
1.10.4. Композиция и суперпозиция функций. Способы задания функций
Пусть даны две функции : АВ и g: ВС. Функция
h: AC называется композицией функций и g (обозначается og), если имеет место равенство , где хА.
Часто говорят, что функция h получена подстановкой
в g.
Для многоместных функций , возможны различные варианты подстановки в g, дающие функции различных типов. Например, при m=3 и n=4 функция имеет шесть аргументов и тип .
Функция, полученная из некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией . Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы, а также скобки называется формулой.
Существует несколько способов задания функции.
1. Самый прямой способ – задать функцию с помощью списка значений, которые она принимает на элементах области А.
Пример1. Например, одна из функций : АВ с областью , областью значений и образом задаётся предписанием:
Другая функция g: АВ с образом задаётся предписанием
Заметим, что к образам этих функций можно применить булевы операции
и .
Таким образом, чтобы задать функцию, надо определить области А и В, и значения, которые она сопоставляет каждому элементу области А.
2. Графиком;
3. Таблицей;
4. Формулой, описывающей функцию как суперпозицию других (исходных) функций;
5. Рекурсивной вычислительной процедурой.
Пример2. Функция f(x)=1∙2∙3∙ (x-1)x=x! описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами:
1) (0)=1; 2) (х+1)=f(x)·(x+1).
Характеристические функции.
Всякому отношению R из А в В (RAB) можно сопоставить функцию R:AB0…1, полагая 1.10.5.
1.10.5. Представление функций в эвм
Пусть : АВ, множество А конечно и не очень велико, |A|=n. Наиболее общим представлением такой функции является массив array[A] of B, где А – тип данных, значения которых представляют элементы множества А, а В – тип данных, значения которых представляют элементы множества В. Если среда программирования допускает массивы только с натуральными индексами, то элементы множества А нумеруются (то есть и функция представляется с помощью массива array[1,2,…,n] of B
Функция нескольких аргументов представляется многомерным массивом.
Представление функции с помощью массива является эффективным по времени, поскольку реализация массива в большинстве случаев обеспечивает получение значения за постоянное время, не зависящее от размера массива и значения индекса.
Если множество А велико или бесконечно, то использование массивов для представления функций является неэффективным с точки зрения экономии памяти. В таком случае для представления функций используется особый вид процедур, возвращающих единственное значение для заданного аргумента. Обычно такие процедуры также называются «функциями». В некоторых языках программирования определения функции вводится ключевым словом function.
Многомерные функции представляются с помощью нескольких формальных параметров в определении функции.
Пример 1. Таблица выигрышей лотереи устанавливает соответствие G между парами чисел (серия и номер выигравшего билета) и множеством выигрышей М: Является ли данное соответствие функцией, и если да, то какой?
Соответствие , задаваемое таблицей выигрышей является функциональным, так как для каждой указанной пары из (серия, № билета) определён конкретный (единственный) выигрыш из М.
Таким образом, данное соответствие есть двухместная функция . Функция такого типа не всюду определена, значит не является отображением.
Более того, как правило, число выигравших билетов (мощность области определения ) больше перечня наименований выигрышей (мощность области значений ), поэтому данная функция не обладает единственностью прообраза: одному выигрышу может соответствовать несколько билетов. В силу сказанного не является ни инъекцией, ни тем более биекцией.
Пример 2. является ли функция (х)=2х, имеющая тип NN отображением, и если – да, то каким? Имеет ли функция обратную функцию -1, и если – да, то является ли -1 отображением?
Функция (х)=2х, : NN всюду определена на N, однако не сюръективна, так как область значения функции равна (область значений содержит только чётные числа из N). Поэтому является отображением N в N или преобразованием множества N.
Между областью определения и областью значений имеет место взаимно однозначное соответствие: любому элементу nN соответствует один и только один элемент 2n из и наоборот. Поэтому функция (х)=2х, : NN, имеет обратную функцию-1. Однако обратная функция не всюду определена: её областью определения является множество чётных чисел . Поэтому обратная функция -1, в отличие от исходной функции , не является отображением.
Пример 3. Задать несколько возможных типов для функции (х) =.2n Для каждого типа определить:
а). свойства функции ;
б). является ли отображением и, если – да, то каким?
1. Пусть тип функции : NN. Тогда (х) =2n всюду определена, так как , но не сюръективна, так как ( – множество натуральных чисел, являющихся степенями двойки). Следовательно, функция является отображением N в N.
2. : N . Тогда функция всюду определена и сюръективна, следовательно, является отображением N на .
3. : NR. Функция всюду определена, но не сюръективна,
т. е. есть отображение N в R.
4. : R+N . Функция частично определена и сюръективна, поскольку область значений (х) =2n при заданном типе функции представляет множество натуральных чисел, т. е. , значит, не для всех хR+ функция определена,
т. е. . Следовательно, : R+N не является отображением.
5. : RR. Функция всюду определена, но не сюръективна ( не имеет отрицательных значений). Следовательно, – отображение R в R.
6. : R R+. Функция всюду определена и сюръективна, т. е. является отображением R на R+.
Кроме названных свойств во всех случаях есть функциональное соответствие, а для случаев 2) и 6) – взаимно однозначное (биекция).
Пример 4. Чему равна композиция функций (х)=2х и g(x)=1+x?
Пусть функции f(х) и g(x) имеют тип RR. Тогда их композиции возможны в произвольном порядке. Композиция og =h1 представляет собой подстановку в g, т. е. h1 =og =g(f(x))=1+f(x)=1+2x.
Композиция gо = h2есть функция, полученная подстановкой g в , т. е. h2= gо=f(g(x))=2g(x)=2(1+x)=2+2x.
Пример 5. Чему равна композиция функций и ? Каковы области определения композиций и функций?
Пусть функции и имеют тип RR, т. е. отображают одно и тоже множество на себя. Тогда композиция возможна в произвольном порядке и дает функции: h1 =og =g(f(x))= и
h2= gо=f(g(x))=
Области определения исходных функций и их композиций: , , .
Пример 6. Функции и g имеет тип , . Какой тип имеют функции h1 и h2 , являющиеся композициями и g:
а) h1 =og =
б) h1 =og = ?
Функция h1 содержит шесть аргументов и её тип .
Функция h2 содержит восемь аргументов и её тип или .
Пример 7. Пусть функция . Определить функции образованные переименованием:
а) в , б) и в .
1. Переименование в приводит функцию к функции, , которая равна функции двух аргументов:
2. Переименование и в приводит к одноместной функции .
Пример 8. Дано множество A={a, b, c, d} и два преобразования этого множества (т. е. функции типа АА, являющиеся отображением А в А):
=(13, 23, 31, 42); β=(12, 21, 31, 43).
Обычно преобразования конечных множеств записываются так: ;
Чему равна композиция преобразований?
Композиция преобразований – это новое преобразование:
Упражнения стр. 90. Задачник: стр. 18 №23-25.