- •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
1.8 Представление множеств в эвм
Задать представление какого либо объекта (в данном случае множества) – значит описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции.
Применительно к множествам, определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций.
Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев.
Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее представление для данного случая является основой для практического программирования.
Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.
1. Реализация операций над подмножествами заданного универсума U.
Пусть универсум U – конечный и число элементов в нём не превосходит разрядность ЭВМ: . Элементы универсума нумерованы: Подмножество А универсума U представляется кодом (машинным словом) С, в котором:
где - это i-й разряд кода С.
Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества В.
В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно.
2. Представление множеств упорядоченными списками
Если универсум очень велик (или бесконечен), а рассматриваемые подмножества не очень велики, то множества обычно представляются списками элементов.
Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Если элементы в списках упорядочить, например, по возрастанию значения информационного поля, то трудоёмкость всех операций составит О(n). Существует весьма общий алгоритм, известный как алгоритм типа слияния для эффективной реализации операций над множествами, представленными в виде упорядоченных списков.
Задачи для самостоятельного решения
Доказать, что {} .
Доказать, что существует лишь одно множество, не имеющее элементов
Доказать, что {{0, 1}, {0, 2}}{0, 1, 2}.
Осуществить операции над множествами:
A={2, 4, 6, 8}, B={3, 6, 9}, если U={1, 2, 3, …, 10}.
Осуществить операции над множествами А, В U, если A={a, b, d}; B={b, d, e, h}, U={a, b, c, d, e, f, g, h}.
Пусть A={1, 2}, B={2, 3}, C={1, 3}. Найти:
а) ; б) ; в) ;
г) ; д) .
Указать, какие из следующих выражений справедливы:
а) 0; б) = {0}; в) |{}| = 0; г) || = 0?
8. Пусть U={a, b, c, d}, X={a, c}, Y={a, b, d}, Z={b, c}.
Найти множества: а) ; б) ;
в); ; г); ; д) ;
е) ; ж) ; з) ;
и) ; к) ; л) .
Найти множества: а) ; б) ; в) ;
г) ; д) ; е) ; ж),
если U={1, 2, 3, 4, 5, 6}; A={1, 2, 3}; B={1, 3, 5, 6};
C={4, 5, 6}.
Даны два произвольных множества А и В такие, что . Что представляет собой и ?
10. Даны два произвольных множества C и D такие, что .Что можно сказать о и ?
11. Дано произвольное множество Х. найти множества:
а) ; б) ; в) .
Пусть [0, 1], [0, 2] – отрезки на числовой прямой. Дать геометрическую интерпретацию множеств: [0, 1][0, 2], [0, 1]², [0, 2]³.
Какие утверждения верны для всех X, Y, Z?
а) Если XY и YZ, то XZ, б) Если XY и YZ, то XZ,
в) Если и , то,
г) Если XY и YZ, то XZ.
Существуют ли такие множества X, Y, Z, что ; ; ?
Доказать, что .
Построить диаграммы Венна для задачи 8.
Пусть A, B, С U. С помощью диаграмм Венна доказать:
а);
б) ;
в) ; г) ;
д) ; е) ;
ж) ; з). .
Доказать следующие тождества:
а);
б) ;
в) ; г) ;
д)
е) ; ж). .
Доказать, что
а) ;
б) ; в) ;
г) ;
д) ;
е) ;
ж) .
Определить операции ; - через операции :
а) ; б) ; в) .
Доказать, что характеристическая функция множеств удовлетворяет следующим условиям:
;
;
;
Найти все подмножества множеств
, {}, {x}, {1, 2}
Доказать, что:
а); ;
б) любое уравнение относительно множества Х, в правой части которого стоит , равносильно уравнению , где А и В – некоторые множества, в записи которых не содержится символ Х
в) система уравнений имеет решение тогда и только тогда, когда. При этом условии решением системы является любое множество Х такое, что .
Описать метод решения системы уравнений с одним неизвестным.
Решить систему уравнений ,
где А, В и С – данные множества, причем .
Пусть X={0, 1, 2, 3}, Y={a, b, c}. Найти XY, YX.
Доказать, что
а) ;
б) ;
в) ; г) .