- •Раздел 1. Элементы математической логики, теории множеств. Основные понятия алгебраических структур: группы, кольца, поля. Глава 1. Элементы математической логики и теории множеств. Содержание
- •Введение
- •§1. Высказывания, операции над высказываниями п.1. Высказывания.
- •П.2. Отрицание высказывания.
- •П.3. Дизъюнкция высказываний.
- •П.4. Конъюнкция высказываний.
- •П.5. Импликация высказываний.
- •П.6. Равносильность (эквивалентность) высказываний.
- •П.2. Законы логики.
- •§2. Формулы алгебры высказываний. Законы логики п.1. Определение формул алгебры высказываний.
- •§3. Предикаты. Кванторы общности и существования п.1. Определение предиката.
- •П.2. Логические операции алгебры предикатов.
- •П.3.Равносильность предикатов.
- •П.4. Квантор общности.
- •П.5. Квантор существования.
- •П.6.Построение отрицания высказываний, содержащих кванторы. Законы Де Моргана.
- •§4. Взаимно обратные теоремы. Необходимые и достаточные условия. Взаимно противоположные теоремы. Доказательство от противного п.1.Стандартная форма записи теоремы.
- •П.2. Обратные теоремы. Необходимые и достаточные условия.
- •П.3. Противоположные теоремы.
- •П.4. Теорема, противоположная обратной (доказательство от противного).
- •§5. Элементы теорий множеств (интуитивная теория множеств). П.1. Множества.
- •П.2. Подмножества.
- •П3. Пустое множество.
- •П.4. Операции над множествами.
- •П.5. Свойства операций над множествами.
- •П.6. Универсальные множества. Дополнение и его свойства.
- •§6. Прямое произведение двух множеств. Бинарные отношения. Отношения эквивалентности и фактор множества. Функции. Отношение порядка. П.1. Прямое произведение множеств.
- •П.2. Бинарные отношения.
- •Виды бинарных отношений.
- •Изображение бинарных отношений графами.
- •Запишем это бинарное отношение как множество пар:
- •П.3. Отношение эквивалентности и фактор множества.
- •П.4. Отношение порядка.
- •Упорядоченные множества.
- •П.5. Функции (отображения).
- •Сужение функции.
- •Виды функций.
- •Композиция функции (сложная функция). Суперпозиция функции.
- •Тождественная (единичная) функция.
- •Обратные функции.
- •Обратные тригонометрические функции.
- •Задачи.
Запишем это бинарное отношение как множество пар:
lllllllllll
П.3. Отношение эквивалентности и фактор множества.
Определение. Бинарное отношение на множестве называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пример. Отношение равно на множестве - это отношение эквивалентности.
Определение. Пусть - отношение эквивалентности на множестве , . Классом эквивалентности, порожденным элементом , называется множество всех элементов из множества , находящихся в отношении с элементом .
Класс эквивалентности,
порожденный элементом
,
обозначается:
(
по
).
Определение. Совокупность всех классов эквивалентности отношение на множестве называется фактор множества множества по отношению эквивалентности .
Обозначается:
Определение.
Разбиением множества
называется такое семейство его непустых
подмножеств, что каждый элемент множества
входит в точности в один из членов
семейства. Другими словами, разбиением
множества
называется совокупность его подмножеств
,
которые обладают следующими свойствами:
,
т.е. разбиение множества
есть свойство его непустых подмножеств,
объединение которых совпадает с
множеством
,
пересечение любых двух из них не пусто.
Пример. Пусть
дано множество
.
Будут ли следующие семейства множеств
разбиением.
1)
;
;
- являются разбиением
2)
;
- являются разбиением
3)
;
- не являются разбиением
Задача. (НИРС)
Пусть
имеет
элементов. Сколько существует разбиений
множества
.
Теорема 1. Пусть - отношение эквивалентности на непустом множестве , тогда фактор множества является разбиением множества .
Доказательство.
Для того, чтобы доказать, что
является разбиением, нужно проверить,
что выполняются три условия:
Проверим, что все классы не пусты. Для этого рассмотрим класс эквивалентности, порожденным элементом . , элемент находится в отношении с элементом , т.е. , т.к. - отношение эквивалентности, то оно рефлексивно.
Возьмём два разных класса эквивалентности
.
Докажем, что пересечение этих классов
пусто:
.
Доказательство от противного: предположим, что
Докажем, что классы
эквивалентности равны, т.е.
.
Пусть
Обратное включение доказывается аналогично.
- противоречие с
условием.
Полученное противоречие доказывает нужное утверждение.
Каждый класс эквивалентности – подмножество множества .
.
Докажем обратное включение:
.
Итак, фактор множества - это разбиение множества .
Теорема доказана.
Теорема 2.
Пусть система множеств
- разбиение множества
.
Определим на множестве
отношение
.
Элемент
находится в отношении
с элементом
тогда и только тогда, когда
принадлежат одному из множеств
:
.
Тогда
- отношение эквивалентности на множестве
и фактор множества
.
Доказательство очевидно, следует из определений.
Из теорем 1 и 2 следует, что задать отношение эквивалентности на множестве это тоже самое, что задать разбиение множества .
П.4. Отношение порядка.
Определение. Бинарное отношение на множестве называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно.
Пример. 1. Отношение на множестве - это отношение частичного порядка (см пример п.2 Бинарные отношения).
2. Отношение включения на множестве семейства множеств - это отношение частичного порядка (см. п. Подмножества).
Определение. Бинарное отношение на множестве называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.
Например, отношение < на - отношение строгого порядка.
Определение.
Отношение частичного порядка
на множестве
называется отношением линейного
порядка, если
или
,
т.е. любые два элемента сравнимы по
отношению
.
Определение.
Отношение строгого порядка
на множестве
- линейное, если
или
или
.
Пример.
1. Отношение
на множестве
-
это отношение строгого линейного
порядка.
2. Отношение на множестве - это отношение частичного линейного порядка на .
3. Можно ли определить вид отношения включения на семействе множеств?
Есть множества, которые не сравнимы по отношению включения, например, множество чётных чисел и множество нечётных чисел, поэтому мы не можем утверждать, что любые два множества сравнимы по отношению включения, а значит, мы не можем определить вид отношения включения.
