- •Е. М. Светлая основы высшей математики и информатики Элементы теории множеств и математической логики
- •Ключевые понятия
- •1. Основные понятия
- •2. Операции над множествами
- •3. Алгебраические свойства операций над множествами
- •Ключевые понятия
- •1. Высказывания. Логические операции над высказываниями
- •2. Формулы логики высказываний
- •3. Основные эквивалентные преобразования формул (законы логики высказываний)
- •Упражнения
- •Литература
- •Содержание
- •1. Основные понятия 3
- •2. Операции над множествами 5
- •3. Алгебраические свойства операций над множествами 6
- •Светлая Елена Михайловна основы высшей математики и информатики Элементы теории множеств и математической логики
- •220086, Минск, ул. Славинского, 1, корп. 3.
2. Операции над множествами
Далее предполагаем, что все рассматриваемые множества являются подмножествами некоторого универсального множества V.
Объединением (или суммой) множеств А и В называется множество, состоящее из элементов, которые принадлежат хотя бы одному из этих множеств (рис. 2) (результатом операции является заштрихованная область). Обозначают А В (или А + В). Можно записать
А В = х: х А или х В.
Пересечением (или произведением) множеств А и В называется множество, состоящее из элементов, которые одновременно принадлежат множеству А и множеству В (рис. 3). Обозначают: А В (или А В). А В = = х: х А и х В.
Рис. 2. А В Рис. 3. А В
Разностью множеств А и В называется множество всех тех элементов множества А, которые не содержатся во множестве В (рис. 4). Обозначают: А \ В = х: х А и х В.
Дополнением множества А называется множество всех элементов, не принадлежащих А (рис. 5). Обозначают: .
Рис. 4. А \ В Рис. 5. V \ А
Пример. Пусть V – множество всех сотрудников некоторой юридической фирмы; А – множество всех сотрудников данной фирмы старше 40 лет; В – множество сотрудников, имеющих стаж работы более 15 лет. Какой смысл следующих множеств: а) ; б) В?
Решение.
а) – множество сотрудников, стаж работы которых не превышает 15 лет;
б) В – множество сотрудников фирмы не старше 40 лет, имеющих стаж работы более 15 лет.
Пример. Пусть V = 1, 2, 3, 4, 5, 6, А =1, 3, 4, 5, В = 2, 3, С = 1, 5, 6. Найти: а) ; б) ; в) А ; г) В \ А.
Решение.
а) = V \ А = 1, 2, 3, 4, 5, 6 \ 1, 3, 4, 5 = 2, 6; = V \ В = 1, 2, 3, 4, 5, 6 \ 2, 3 = 1, 4, 5, 6.
Тогда = 2, 6 1, 4, 5, 6 = 1, 2, 4, 5, 6.
б) А В = 1, 3, 4, 5 2, 3 = 3.
Следовательно, = V \ (А В) = 1, 2, 3, 4, 5, 6 \ 3 = 1, 2, 4, 5, 6.
в) = V \ В = 1, 2, 3, 4, 5, 6 \ 2, 3 = 1, 4, 5, 6.
А = 1, 3, 4, 5 1, 4, 5, 6 = 1, 4, 5.
г) В \ А = 2, 3 \ 1, 3, 4, 5 = 2.
3. Алгебраические свойства операций над множествами
Введенные выше операции над множествами обладают рядом свойств. Приведем основные из них:
1
–
коммутативность;
А В = В А
2
–
ассоциативность;
А (В С) = (А В) С
3
–
дистрибутивность;
А (В С) = (А В) (А С)
4) А = А;
5) А V = V;
6) А = ;
7) А V = А;
8) А = V;
9) А = ;
10) = V;
11) .
Доказательство этих свойств (формул) состоит в том, что берут произвольный элемент множества левой части и доказывают, что он принадлежит и множеству правой части, и наоборот.
Операции над множествами обладают принципом двойственности, т.е. если справедливо некоторое соотношение между множествами, то справедливо и «двойственное» соотношение, полученное из данного путем взаимной замены всюду знаков и , V и , и .
Примерами двойственных соотношений являются соотношения в группах 1), 2), 3), соотношения 4) и 7), 5) и 6), 8) и 9), 10) и 11).
Лекция 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
План:
1. Высказывания. Логические операции над высказываниями.
2. Формулы логики высказываний.
3. Основные эквивалентные преобразования формул (законы логики высказываний).