- •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
В.Н. Дурова М.И. Зайцева В.Н. Макаров
ТЕОРИЯ МНОЖЕСТВ.
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Учебное пособие
Воронеж 2006
Воронежский государственный технический
университет
В.Н. Дурова М.И. Зайцева В.Н. Макаров
ТЕОРИЯ МНОЖЕСТВ.
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Утверждено Редакционно-издательским советом
университета в качестве учебного пособия
Воронеж 2006
Введение
Пособие написано в соответствии с образовательным стандартом специальностей 160201 «Самолето-и вертолетостроение,130501 «Проектирование, сооружение и эксплуатация газонефтепроводов и газонефтехранилищ», 220501 «Управление качеством». Понятия и методы теории множеств и математической логики в связи с компьютеризацией образования должны занимать существенное место в математической подготовке инженера. Большинство вопросов указанных разделов предназначено для самостоятельного изучения студентами. С целью облегчения самостоятельной работы студентов изложение материала сопровождается большим количеством подробно решенных примеров. Приводятся примеры для самостоятельного решения.
1. Элементы теории множеств
1.1 Множества. Основные понятия
Различают аксиоматическую теорию множеств и элементарную теорию множеств. В дальнейшем рассматривается элементарная теория множеств.
Понятие множества и элемента множества принадлежат к числу неопределяемых явно понятий математики, таких, как, например, число, точка и прямая.
Под множеством понимают набор, совокупность каких-либо объектов, обладающих общим характеристическим свойством.
Объекты, из которых составлено множество, называются его элементами.
Понятие множества часто употребляется в повседневной жизни и для него имеется много общеизвестных синонимов (класс, совокупность, толпа, стая), некоторые, из которых имеют специфический оттенок.
Множества обозначаются заглавными буквами латинского алфавита, его элементы – малыми буквами.
Примеры.
1. Множество натуральных чисел (N): 1, 2, 3, …
2. Множество простых чисел (P): 2, 3, 5, 7, 11, …
3. Множество целых чисел (Z): … -2, -1, 0, 1, 2, …
4. Множество действительных чисел (R).
5. Множество комплексных чисел (С).
6. Множество матриц размера m x n;
7. Множество векторов в и т. д.
Принадлежность элемента x множеству М обозначается xМ. В противном случае xМ.
Как правило, считается, что все элементы множества различны. Множество с повторяющимися элементами называется мультимножеством. Мультимножества играют важную роль в комбинаторике. В данном разделе будем рассматривать только множества с различными элементами.
, как объекты, могут быть элементами других множеств. Множество, элементами которого являются множества, обычно называются классом или семейством.
Например, множество групп студентов состоит из элементов (групп), которые, в свою очередь, состоят из студентов.
С емейства множеств обычно обозначаются заглавными «рукописными» буквами латинского алфавита.
Множество, не содержащее ни одного элемента, называется пустым и обозначается .
Множество, состоящее из конечного числа элементов, называется конечным, в.противном случае Рис.1
– беcконечным.
Например, множества N, R – бесконечные множества.
Число элементов в конечном множестве М называется его мощностью и обозначается М= n, если множество М содержит n элементов.
Мощность пустого множества равна 0: = 0.
Для произвольных множеств А и В определяются два типа отношений – отношение включения и отношения равенства.
Множество А называется подмножеством множества В, если каждый элемент из А является элементом В.
Обозначаются (А включено в В). В частности, А и В могут совпадать, поэтому называется также отношением не строгого включения.
Очевидные свойства операции включения:
.
Если и , то говорят, что А есть собственное подмножество В и обозначают . Отношение между множествами в этом случае называется отношением строгого включения. В этом случае
и .
Обычно элементы всех множеств берутся из некоторого одного, достаточно широкого множества U (, Е) (своего для каждого случая), которое называется универсальным (основным) множеством (или универсумом).
Пустое множество, по определению, является подмножеством всякого множества.
Пустое множество и само множество U называются несобственными подмножествами. Все остальные подмножества множества U называются собственными.
Два определения равенства множеств:
1. Множества А и В равны (А=В), если их элементы совпадают.
2. Множества А и В равны, если и .
Очевидно, что для любых множеств А, В и С справедливы соотношения:
Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью и обозначается P(А) или .
Пример. Пусть А={1,2,3}.
Тогда P(А)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.