Оглавление
Глава 1. Множества и математическая логика………………...5
§1.1. Множества и операции над ними………………………5
Вопросы и упражнения для самостоятельной работы………9
§1.2. Отображения и соответствия………………………….10
Вопросы и упражнения для самостоятельной работы…….13
§1.3. Бинарные отношения и их свойства………………….14
Вопросы и упражнения для самостоятельной работы…….20
§1.4. Логика высказываний………………………………….21
Вопросы и упражнения для самостоятельной работы…….25
§1.5. Логика предикатов……………………………………..26
Вопросы и упражнения для самостоятельной работы…….30
Глава 2. Метод математической индукции…………………..33
Вопросы и упражнения для самостоятельной работы…….38
Глава 3. Элементы комбинаторики…………………………...41
§3.1. Выборки………………………………………………...41
Вопросы и упражнения для самостоятельной работы…….49
§3.2. Биномиальные коэффициенты………………………..51
Вопросы и упражнения для самостоятельной работы…….57
Глава 4. Рекуррентные последовательности и производящие функции…………………………………………………………….60
§4.1. Линейные рекуррентные соотношения………………60
Вопросы и упражнения для самостоятельной работы…….67
§4.2. Производящие функции……………………………….69
Вопросы и упражнения для самостоятельной работы……..81
§4.3. Числа Фибоначчи………………………………………83
Вопросы и упражнения для самостоятельной работы…….86
Ответы…………………………………………………………..88
Литература………………………………………………………92
1. Множества и математическая логика
§1.1. Множества и операции над ними
Множество —
это совокупность каких-либо объектов,
называемых егоэлементами, обладающих
некоторым общим для ниххарактеристическим
свойством. Множество
являетсяподмножеством множества
(пишут:
),
если всякий элемент множества
является элементом множества
.
Множество, не содержащее ни одного
элемента, называют пустым и обозначают
символом. Удобно
считать, что все рассматриваемые
множества являются подмножествами
некоторогоуниверсальногомножества
.
Операции над множествами
1. Пересечение
множеств
и
(пишут:
)
— это множество, состоящее из всех тех
элементов, которые принадлежат обоим
множествам
и
.
Если
,
то говорят, что множества
и
не пересекаются.
2. Объединение
множеств
и
(пишут:
)
— это множество, состоящее из всех тех
элементов, которые принадлежат хотя бы
одному из множеств
и
.
3. Разность
множеств
и
(пишут:
)
— это множество, состоящее из всех тех
элементов, которые принадлежат множеству
,
но не принадлежат множеству
.
4. Симметрическая
разность множеств
и
(пишут:
)
— это множество, состоящее из всех тех
элементов, которые принадлежат одному
из множеств
и
,
но не принадлежат другому.
5. Дополнение
множества
состоит из всех тех элементов множества
,
которые не принадлежат множеству
.
Если
— универсальное множество, определенное
контекстом, вместо
пишут
.
6. Прямое (декартово)
произведение множеств
и
(пишут:
)
— это множество всех упорядоченных пар
,
где
и
.
Примеры
1. Пусть
универсальное множество
— множество всех сотрудников некоторой
фирмы;
— множество всех сотрудников данной
организации старше 35 лет;
— множество сотрудников, имеющих стаж
работы более 10 лет;
— множество менеджеров фирмы. Каковы
характеристические свойства элементов
следующих множеств:
а)
;
б)
;
в)
;
г)
;
д)
.
Решение.а)
— множество сотрудников организации,
стаж работы которых не превышает 10 лет.
б)
— множество менеджеров фирмы не старше
35 лет, имеющих стаж работы более 10 лет.
в)
— множество всех сотрудников фирмы
старше 35 лет, а также сотрудников, не
являющихся менеджерами, стаж работы
которых более 10 лет.
г)
— множество сотрудников организации
со стажем работы более 10 лет, не работающих
менеджерами.
д)
— множество менеджеров со стажем работы
не более 10 лет.
2. Пусть
,
,
,
.
Найти: а)
;
б)
;
в)
;
г)
;
д)
.
Решение.а)
.
б)
.
в)
.
г)
.
д)
.
3. Доказать справедливость соотношения
.
Решение.Множества
и
равны, если
и
.
1. Покажем сначала,
что
,
т.е. любой элемент
из множества, заданного левой частью
соотношения, принадлежит и множеству,
заданному правой частью соотношения.
Пусть
.
Тогда
принадлежит одновременно
и
,
т.е.
принадлежит одному из множеств
или
и множеству
.
Следовательно,
принадлежит либо
и
,
либо
и
.
Это означает, что
принадлежит либо пересечению
,
либо пересечению
.
Значит,
принадлежит объединению
.
Это рассуждение можно записать с помощью формул:
Пусть
.
Тогда
и
(
или
)
и (
)
(
и
)
или (
и
)
или
.
Таким образом,
.
2. Покажем теперь,
что
,
т.е. любой элемент
из множества, заданного правой частью
соотношения, принадлежит и множеству,
заданному левой частью соотношения.
Пусть
.
Тогда
или
(
и
)
или (
и
)
(
или
)
и (
)
и
.
Следовательно,
.
Таким образом,
,
что и требовалось доказать.
4. Пусть
,
.
Найти
,
,
,
.
Решение. Имеем:
;
;
;
