Множества, отображения, логика



страница2/6
Дата26.11.2012
Размер0.77 Mb.
ТипДокументы
1   2   3   4   5   6
§ 3. Отображения
3.1. Говорят, что задано соответствие

f : X  Y

множества Х на множество Y , если задано подмножество GXY, причем элементу соответствует элемент (обозначение: xGy), если и только если (x, y)G. Таким образом, соответствие f есть триада

f = [XYG],

в которой Xмножество отправления (область определения), Yмножество прибытия, Gграфик соответствия f. Образом элемента x X в соответствии f : X  Y называется множество . Полным прообразом элемента yY в соответствии f : X  Y называется множество .

Пример. Соответствие f удобно понимать с помощью графа, который представляет собой триаду

Граф = [начала  концы  ребра],

при этом ребра обозначаются стрелками, начала — элементы множества Х, концы — элементы множества Y. Вершина и ребро называются инцидентными, если вершина является началом или концом стрелки. Каждое ребро инцидентно ровно двум (возможно, совпадающим) вершинам, одна из которых — начало стрелки, другая — конец.

П
усть Х ={, , }, Y ={1, 2, 3, 4} — множества, и пусть G = {(, 1), (, 2), (, 2), (, 4), (, 3)}  XY — подмножество. Тогда определено соответствие f : X  Y, которое в виде графа изображено на рис. 5.■

3.2. Отображением множества X на множество Y называется соответствие f : X  Y, такое, что образ любого состоит ровно из одного элемента.

Упражнение. Какие из указанных на рис. 6 соответствий являются отображениями?

Два отображения f : X  Y, g : X  Y считаются равносильными, если для всех хХ. Для равносильных отображений f, g используется запись: f = g.

3.3.
Отображение f : X  R называется функцией на множестве X.

3.4. Если XR — числовое множество, то функция f : X  R называется числовой функцией.

3.5. Отображение f : X  Y называется сюръекцией (отображением на), если для любого элемента у Y справедливо неравенство ||1.

Упражнение. Какие из указанных на рис. 6 соответствий являются сюръективными отображениями?

3
.6.
Отображение f : X  Y называется инъекцией (отображением в), если для любого элемента уY справедливо неравенство ||1. Инъективное отображение два различных элемента отображает на два различных элемента.

Упражнение. Какие из указанных на рис. 6 соответствий являются инъективными отображениями?

3.7. Отображение называется биекцией (взаимно однозначным соответствием), если оно одновременно является инъекцией и сюръекцией.

Упражнение. Какие из указанных на рис. 6 соответствий являются биективными отображениями?

Два множества называются равносильными, если между этими множествами существует биекция.

3.8. Биекция множества на себя называется преобразованием (автоморфизмом) данного множества.

3.9. Пример. Тождественным преобразованием множества называется преобразование f : X  Х, такое, что для всех хХ. Тождественное преобразование обозначается idX; оно является биекцией.■

3.10. Соответствие : X  X называется отношением на множестве X.

3.11. Отношение  на множестве Х называется

рефлексивным, если хх,

симметричным, если из ху следует ух,

транзитивным, если из ху и уz следует хz для любых х, у, z  X.

Упражнение 1. Докажите, что отношение параллельности || на множестве всех прямых евклидовой плоскости является рефлексивным, симметричным и транзитивным.

Упражнение 2. Докажите, что отношение включения  на множестве P (Х) рефлексивное, не симметричное, транзитивное.

Упражнение 3. Докажите, что отношение  на множестве R действительных чисел рефлексивное, не симметричное, транзитивное.

Упражнение 4. Докажите, что отношение > на множестве R действительных чисел не рефлексивное, не симметричное, транзитивное.

3.12. Отношение ~ на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично, транзитивно. Если два элемента х, уХ находятся в отношении эквивалентности, то говорят, что они эквивалентны между собой: х ~ у. Все элементы, эквивалентные данному элементу хP (Х), образуют подмножество P (Х) — класс элемента х. Легко доказать, что классы двух элементов либо совпадают, либо не пересекаются. Это позволяет рассматривать классы эквивалентности как элементы множества, которое называется фактор-множеством5 и обозначается .

3.13. Пример. Отношение равносильности в классе K всех множеств является отношением эквивалентности. Любому классу эквивалентности приписывается так называемое кардинальное число, называемое мощностью любого из множеств этого класса. Например, мощность пустого множества равна 0, мощность непустого конечного множества равна числу n его элементов, мощность множества N равна а, мощность множества R равна с. При этом выполняются неравенства 0 < n < a < c. Множество мощности а называется счетным, а мощности сконтинуумом. Более ста лет не решена континуум-проблема: существует ли множество мощности b, такой, что a < b < c?■

3.14. Пример. Будем говорить, что два числа сравнимы по модулю , если их разность mn делится на без остатка (обозначение , читается «m сравнимо с n по модулю p»). Например, 2005  1 mod 12, 3  1 mod 2, 2  0 mod 2. Для любого kZ справедливы сравнения: 2k  0 mod 2, 2k + 1  1 mod 2. Очевидно, отношение сравнения является отношением эквивалентности, поэтому по нему можно факторизовать Z. Фактор-множество



состоит из p классов, которые называются классами вычетов по модулю p.■

3.15. Упражнение. Докажите, что в множестве



можно ввести операции сложения и умножения; докажите, что .

Задание 2. Даны множества А = {n Z| pnq}, В = {n Z| rns} (данные брать в табл. 1). Найти множество отправления и множество прибытия соответствия : В  А, график которого состоит из элементов (x, y)  BA, таких, что х < y2. Построить граф соответствия .

§ 4. Простейшие понятия математической логики
Чем занимается математическая логика? Логика как искус­ство рассуждений зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал Джордж Буль и тем самым заложил основы ма­тематической (символической) логики.6

4.1. Высказывание — это повествовательное предложение, о котором можно точно сказать, истинно оно или ложно. Например, предложение «Множество всех ненулевых чисел не является пустым» является высказыванием, так как это предложение — повествовательное и о нем точно можно сказать, что оно истинно. Другой пример, предложение «Железо — диэлектрик» является высказыванием, причем ложным. Вопросительные и восклицательные предложения не являются высказываниями. Предложение «На Марсе есть жизнь» также не является высказыванием, так как мы не знаем точно, имеется ли жизнь на Марсе.

Строго говоря, понятие «высказывание» является в математической логике неопределяемым, а первое предложение настоящего пункта — всего лишь пояснение на бытовом языке. Но даже из этого пояснения следует, что если L — множество всех высказываний, то определено отображение

: L  Z2,

такое, что для любого АL определим (А) = 1, если А — истинное высказывание, или (А) = 0, если А — ложное высказывание.

4.2. Отрицание. Из высказывания А = «Сегодня — четверг» можно построить новое высказывание (читается: «не А»), с помощью универсального приема: = «Неверно, что А» = «Неверно, что сегодня — четверг». Высказывание называется отрицанием высказывания А. Логическая операция получения из А называется отрицанием. Другими словами, отрицание — это автоморфизм множества L всех высказываний, при этом если А — истина, то Ā — ложь, а если А — ложь, то Ā — истина. Сказанное отражает следующая таблица истинности, которая фактически является определением операции отрицания высказываний.


А

Ā

1

0

0

1


4.3. Следующие четыре операции называются и обозначаются конъюнкция , дизъюнкция , импликация , эквиваленция ; они определяются с помощью таблиц истинности:


А

В

АВ

АВ

АВ

АВ

1

1

1

1

1

1

1

0

0

1

0

0

0

1

0

1

1

0

0

0

0

0

1

1


Каждая из этих операций является двуместной (бинарной), т.е. каждая из них отображает L  L на L. Это немедленно приводит нас к булевым функциям.

4.4. Булевы функции. Объекты с двумя возможными состояниями характеризуются булевыми переменными, которые способны при­нимать лишь два различных значения 0 и 1. Отношения между булевыми переменными представляются бу­левыми функциями вида

f:  Z2,

которые подобно числовым функциям могут зависеть от одной, двух и, вообще, п переменных (аргументов). Запись Y = f (X1, X2, ..., Xп) означает, что Y — функция аргументов X1, X2, ..., Xn. Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества Z2, т. е. характеризу­ются одним из двух возможных состояний.

Функции небольшого числа переменных можно задавать с по­мощью таблиц истинности. Для этого нужно только указать значения функ­ции для каждой комбинации значений ее аргументов.
1   2   3   4   5   6

Похожие:

Множества, отображения, логика iconФакультет
Отображения множеств. Счетные и несчетные множества. Функции множества. Мера множества. Измеримые множества и функции. Интеграл Лебега....
Множества, отображения, логика iconУчебно-методическое пособие Саранск 2012 Отображения. Функции Сведения из теории
Пусть даны некоторые множества и. Бинарное соответствие из в называется отображением множества в множество, если
Множества, отображения, логика iconМатематический анализ
Множества. Декартово произведение двух множеств. Отображения функции, обратная функция. Эквивалентность множеств. Счетность множества...
Множества, отображения, логика iconПрограмма курса дифференциальная топология и риманова геометрия
Топология, топологическое пространство. Гомеоморфизм, сравнение топологий. Открытые и замкнутые множества. Внутренность, замыкание...
Множества, отображения, логика iconГруппы: мк-301, мт-301
Понятия множества и отображения, способы задания множеств. Алгебра множеств и подмножеств. Теорема об отображении множества самого...
Множества, отображения, логика icon1 Содержание дисциплины
Множества, подмножества. Булевы операции над множествами и их свойства. Законы Д’Моргана. Отношения, функциональные отношения, отображения....
Множества, отображения, логика iconМножества и операции со множествами. Понятие множества и мультимножества
Цель таких описаний отразить важнейшие (атрибутные) свойства множества, а именно: разли­чимость всех частей множества, неупорядоченность...
Множества, отображения, логика iconПрограмма государственного экзамена Направление подготовки 230400 «Прикладная математика»
Отображения. Инъективные, сюръективные и биективные отображения. Теорема о произведении (композиции) отображений. Критерий существования...
Множества, отображения, логика icon1-й и 2-й семестры Множества и отображения
Множество и его элементы. Примеры множеств. Отношение включения и его свойства. Операции над множествами: пересечение, объединение,...
Множества, отображения, логика iconРоберт столл множества. Логика. Аксиоматические теории

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org