|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[25] «быть потомком» на множестве людей является частичным порядком, если мы считаем человека своим потомком. Частично упорядоченное множество, даже конечное, может не иметь наибольшего элемента - такого элемента ж, что yRx для любого элемента у. Следует различать понятия наибольшего и максимального элементов: элемент ж называется максимальным (maximal), если не существует большего элемента, т.е. если из xRy следует ж = у. Например, среди нескольких картонных коробок может не быть наибольшей (в которую помещается любая другая), но заведомо есть одна или несколько максимальных (которые не влезают ни в одну другую). Частичный порядок называется линейным (total order, linear order), если для любых элементов а и Ь выполнено либо aRb, либо bRa (или оба - тогда они равны по свойству антисимметричности). Например, отношение «»на множестве натуральных чисел является линейным порядком, а отношение «быть потомком» на множестве людей - нет (можно найти двух человек, не являющихся потомками друг друга). Упражнения 5.2-1 Доказать, что отношение «С» на множестве всех подмножеств множества Z является отношением частичного, но не линейного порядка. 5.2-2 Показать, что для любого положительного га отношение а = b (mod га) является отношением эквивалентности на множестве Z. (Говорят, что а = b (mod га), если существует целое q, для которого a - b = qn.) Сколько классов эквивалентности есть у этого отношения? 5.2-3 Приведите пример отношения, которое а.рефлексивно и симметрично, но не транзитивно; б.рефлексивно и транзитивно, но не симметрично; в.симметрично и транзитивно, но не рефлексивно. 5.2-4 Пусть S - конечное множество, R - отношение эквивалентности на S. Докажите, что если R антисимметрично, что все классы эквивалентности содержат по одному элементу. 5.2-5 Профессор думает, что всякое симметричное и транзитивное отношение рефлексивно, и предлагает такое доказательство: из aRb следует bRa по симметричности, откуда следует aRa по транзитивности. Правильно ли это доказательство? 5.3. Функции Пусть даны два множества А и В. Функцией (function), отображающей А в В, называется бинарное отношение / С А x В, обладающее таким свойством: для каждого а £ А существует ровно одно b £ В, для которого (а, Ъ) £ /. Множество А называется областью определения (domain) функции; для множества В в русском языке нет общепринятого названия, а по-английски оно называется codomain. Можно сказать, что функция / сопоставляет с каждым элементом множества А некоторый элемент множества В. Одному элементу множества А может соответствовать только один элемент множества В, хотя один и тот же элемент В может соответствовать нескольким различным элементам А. Например, бинарное отношение f = {(a,b) : а £ N п b = a mod 2} можно рассматривать как функцию /: N -> {0,1}, поскольку для каждого натурального числа а существует единственное b £ {0,1}, равное a mod 2. Можно записать /(0) = 0, /(1) = 1, /(2) = 0 и так далее. С другой стороны, отношение д = {(а, Ъ) : а, b £ N и а + b четно} не является функцией, поскольку (например) пары (1,3) и (1,5), принадлежащие этому отношению, имеют равные первые члены, но разные вторые. Если пара (а, Ъ) принадлежит отношению /, являющемуся функцией, то говорят, что b является значением (value) функции для аргумента (argument) а, и пишут b = f(a). Чтобы задать функцию, надо указать её значение для каждого аргумента, принадлежащего её области определения. Например, можно задать функцию /: N -т- N формулой /(га) = 2га, которая означает, что / = {(га, 2га) : га £ N}. Две функции f,g: А -> В считаются равными (equal), если /(а) = д(а) для всех а £ А. (Обратите внимание, что с формальной точки зрения мы считаем функции /: А -> В\ и д: А -> В2 различными при В\ ф В2, даже если f(a) = д(а) при всех а!) Конечной последовательностью (finite sequence) длины га называют функцию /, область определения которой есть множество {0,1, 2,..., га- 1}. Конечную последовательность часто записывают как список её значений, т. е. как (/(0), /(1), • • •, f(n- 1)). Бесконечной последовательностью (infinite sequence) называется функция, областью определения которой является множество N натуральных чисел. Например, последовательность Фибоначчи, заданная уравнением (2.13), может быть записана как (0,1,1, 2, 3, 5, 8,13, 21,...). Если область определения функции является декартовым произведением нескольких множества, мы обычно опускаем дополнительные скобки вокруг аргументов. Например, если /: А\ x А2 x ... x Ап -т- В, мы пишем f(cii, а2, , ап) вместо более формального f((ai, а2, , ап))- Каждое из аг- также называется аргументом (argument) функции /, хотя формально её аргументов следовало бы считать га-ку (ai, а2,..., ап). Если Ь = /(а) для некоторой функции /: А -> В и некоторых а £ A, b £ В, то элемент Ь называют образом (image) элемента а. Для произвольного подмножества А1 множества А его образ f(A) определяют формулой f(A) = {Ь £ В : Ь = /(а)для некоторого а £ А}. Множество значений (range) функции / определяется как образ области её определения, т.е. как f(A). Например, множество значений функции /: N -т- N, определённой формулой f(n) = 2га, есть множество всех чётных натуральных чисел, которое можно записать как /(N) = {то : то = 2га для некоторого га £ N}. Функция /: А -т- В называется сюръекцией (surjection), или наложением, если её образ совпадает с множеством В, т.е. всякий элемент Ь £ В является образом некоторого элемента а £ А. Например, функция /: N -> N, заданная формулой /(га) = [п/2\, является сюръекцией. Функция /(га) = 2га не будет сюръекцией, если считать, что /: N -> N, но будет таковой, если считать её отображающей множество натуральных чисел в множество чётных натуральных чисел. Функцию f:A-B, являющуюся сюръекцией, называют также отображением А на В (onto В). Функция /: А -> В называется инъекцией (injection), или вложением, если различным аргументам соответствуют различные значения, т.е. если /(а) ф f(a) при а ф а. Например, функция /(га) = 2га является инъекцией множества N в множество N, поскольку любое число га является образом самое большее одного элемента (га/2, если га четно; нечётные числа не являются образами никаких элементов). Функция /(га) = [п/2\ не является инъекцией, так как (например) /(2) = /(3) = 1. В английской литературе для инъекций употребляется также термин «one-to-one function*. Функция /: А -> В называется биекцией (bijection), если она одновременно является инъекцией и сюръекцией. Например, функция /(га) = ( - 1)п[~га/2], рассматриваемая как функция, отображающая |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||