Примеры бинарных отношений. 7 страница

На графе, представляющем биективное отображение конечных множеств, их любой вершины выходит в точности одна дуга, а в любую вершину, представляющую элемент множества , входит одна и только одна дуга.

Пример. Биективное отображение на , заданное в виде графа, представлено на рис. 5.3.

Рисунок 5.3 - Биективное отображение на , представленное в виде графа

Пример.Дадим характеристику свойств соответствий, представленных на рис. 5.4:

Рисунок 5.4 - Соответствия

а - соответствие всюду определено, не сюръективно, не инъективно, функционально, не является биективным, является отображением, так как оно всюду определено и функционально;

б - соответствие всюду определено, сюръективно, не функционально;

в - соответствие является биективным, а значит - функцией и отображением;

г - частичное соответствие, сюръективно, инъективно, функционально (однозначно), но не является отображением.

Пример.

Различные виды кодирования (кодирование букв азбукой Морзе, представления чисел в различных системах счисления, секретные шифры, входящие и исходящие номера в деловой переписке и т.д.) являются соответствиями между кодируемыми объектами и присваиваемыми им кодами. Эти соответствия, как правило, обладают всеми свойствами взаимно-однозначного соответствия, кроме, возможно, одного - сюръективности. Единственность образа и прообраза в кодировании гарантирует однозначность шифровки и дешифровки. Отсутствие сюръективности означает, что не каждый код имеет смысл. Например, кодирование телефонов шестизначными номерами не сюръективно, поскольку некоторые номера не соответствуют никаким телефонам. Для кодирующей функции, которая каждому объекту из своей области значений ставит в соответствие некоторый код, обратной будет декодирующая функция, которая каждому коду ставит в соответствие закодированный этим кодом объект. Если кодирующая функция не сюръективна, то декодирующая функция не всюду определена.

5.2 Элементы реляционной алгебры

Алгебра отношений находит широкое применение при формализации реальных объектов. Рассмотрим специфику её использования при создании элементов внутримашинного информационного обеспечения - разработке информационной базы данных. Алгебра отношений в данном случае носит название реляционной алгебры (relation - отношение) и применяется для работы с реляционной моделью данных. Реляционная модель данных с математической точки зрения является табличным представлением данных, которое легко формулируется в терминах отношений.

Рассмотрим отношение , заданное на множествах , которое при работе с реляционными базами данных задается на конечных множествах и поэтому является конечным. Основой построения реляционной базы данных (реляционной модели данных) является отношение , представленное в виде двумерной таблицы (с именем ) размером , где - мощность отношения, а - его арность. Каждый столбец данной таблицы соответствует домену (или атрибуту, соответствующему части домена), строка - кортежу значений атрибутов, находящихся в отношении (или записи отношения ).

Пример.Пусть имеется информация о студентах университета, представленная в следующей таблице.

Фамилия	Инициалы	Группа
Алексеев	И.А.	ПО-01
Андреева	О.П.	ПМ-01
Баранов	Н.П.	ПМ-01
Быкова	Н.А.	ПО-01
Волков	В.В	ПМ-01

Эта информация представляет собой некоторое отношение , заданное на трех множествах: множестве фамилий, множестве инициалов и множестве групп. Отношение можно записать списком его элементов, т.е. {(Алексеев, И.А., ПО-01), (Андреева, О.П., ПМ-01), (Баранов, Н.П., ПМ-01), (Быкова, Н.А., ПО-01), (Волков, В.В, ПМ-01)}. Отношению присваивают имя, например, СТУДЕНТ_1.

Рассмотрим терминологию, применяемую при построении реляционной модели данных.

Определение.

Если , то элемент , соответствующий строке таблицы, называется кортежем (записью).

Пример.

Кортежами являются такие элементы отношения , как (Алексеев, И.А., ПО-01), (Андреева, О.П., ПМ-01), (Баранов, Н.П., ПМ-01) и т.п.

Определение.

Множества или области данных , которые входят в произведение , т.е. на которых определено отношение, называются доменами.

Пример.

Доменами отношения , представленными на рис. 5.5, являются: множество фамилий, множество инициалов и множество групп, соответствующие столбцам таблицы.

Рисунок 5.5 - Домены отношения

Определение.

Наименования столбцов таблицы называют атрибутами.

Пример.

Атрибутами отношения СТУДЕНТ_1 являются: фамилия, инициалы, группа.

Представим это отношение на рис. 5.6.

Рисунок 5.6- Отношение СТУДЕНТ_1

Определение. Схемой отношения является список атрибутов.

Пример.

Схемой отношения СТУДЕНТ_1 является список (Фамилия, Инициалы, Группа).

Для изменения содержимого таких таблиц (реляционных таблиц) в базах данных используются простые следующие операции по заполнению таблицы: добавление, удаление кортежей, изменение значения атрибутов.

Основная идея реляционной алгебры заключается в следующем. Поскольку отношения являются множествами, то средства манипулирования отношениями могут базироваться на таких традиционных теоретико-множественных операциях, как объединение, пересечение, разность, декартово произведение, дополненных некоторыми специальными операциями. Следовательно, носитель реляционной алгебры представляет собой множество отношений , сигнатура кроме операций объединения,пересечения, разности, декартова произведения включает специальные операции над отношениями: ограничение отношений(выбор), проекцию отношений, соединение отношений, деление отношений.

В соответствии с потребностями практики вводятся и некоторые другие операции.

Рассмотрим теоретико-множественные операции, применяемые для преобразования отношений в базе данных, используя термины реляционной алгебры.

Определение.Отношения, к которым применяется операция, будем называть отношениями-операндами.

К теоретико-множественным операциям реляционной алгебры относятся:

- объединение отношений;

- пересечение отношений;

- разность отношений;

- прямое (декартово) произведение отношений.

Эти операции имеют смысл для отношений, определенных на одинаковых доменах.

Определение. Объединение отношений ( ). При выполнении операции объединения двух отношений получаем отношение, включающее все кортежи, входящие хотя бы в одно из отношений-операндов.

Пример.Рассмотрим отношения СТУДЕНТ_1 и СТУДЕНТ_2.

СТУДЕНТ_1

Фамилия	Инициалы	Группа
Алексеев	И.А.	КН-01
Андреева	О.П.	ПМ-01
Баранов	Н.П.	ПМ-01
Быкова	Н.А.	КН-01
Волков	В.В	ПМ-01

СТУДЕНТ_2

Фамилия	Инициалы	Группа
Алексеев	И.А.	КН-01
Быкова	Н.А.	КН-01
Дроздов	И.К.	КН-01
Зайцев	О.Н.	ПМ-01
Кузнецова	Е.В	КН-01

Применим операцию объединения к отношениям СТУДЕНТ_1 и СТУДЕНТ_2.

В результате получим следующее отношение (ВСЕ_СТУДЕНТЫ).

ВСЕ_СТУДЕНТЫ=СТУДЕНТ_1 СТУДЕНТ_2

Фамилия	Инициалы	Группа
Алексеев	И.А.	КН-01
Андреева	О.П.	ПМ-01
Баранов	Н.П.	ПМ-01
Быкова	Н.А.	КН-01
Волков	В.В	ПМ-01
Дроздов	И.К.	КН-01
Зайцев	О.Н.	ПМ-01
Кузнецова	Е.В	КН-01

Определение.

Пересечение отношений ( ). При выполнении операции пересечения двух отношений получаем отношение, включающее только те кортежи, которые входят в оба отношения-операнда.

Пример.

Рассмотрим отношения СТУДЕНТ_1 и СТУДЕНТ_2 (из предыдущего примера). Применим операцию пересечения к отношениям СТУДЕНТ_1 и СТУДЕНТ_2.

В результате получим следующее отношение (СТУДЕНТ_1 СТУДЕНТ_2).

СТУДЕНТ_1 СТУДЕНТ_2

Фамилия	Инициалы	Группа
Алексеев	И.А.	КН-01
Быкова	Н.А.	КН-01

Определение.

Разность отношений (\). Отношение, являющееся разностью двух отношений, включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, являющееся вторым операндом.

Пример.

Рассмотрим отношения СТУДЕНТ_1 и СТУДЕНТ_2 (из предыдущего примера). Применим операцию (\) к отношениям СТУДЕНТ_1 и СТУДЕНТ_2.

В результате получим следующее отношение (СТУДЕНТ_1\СТУДЕНТ_2).

СТУДЕНТ_1\СТУДЕНТ_2

Фамилия	Инициалы	Группа
Андреева	О.П.	ПМ-01
Баранов	Н.П.	ПМ-01
Волков	В.В	ПМ-01

Определение.

Прямое (декартово) произведение отношений ( ). При выполнении прямого произведения двух отношений получаем отношение, множество кортежей которого является декартовым произведением множеств кортежей первого и второго операндов.

Пример.

Рассмотрим отношение СТУДЕНТ_1 (из предыдущих примеров) и КУРС.

КУРС

Уч. год	Курс
2009-2010
2010-2011

Выполним прямое произведение отношения СТУДЕНТ_1 и КУРС.

В результате получим следующее отношение (СТУДЕНТ_1 КУРС).

СТУДЕНТ_1 КУРС

Фамилия	Инициалы	Группа	Уч. год	Курс
Алексеев	И.А.	КН-01	2009-2010
Алексеев	И.А.	КН-01	2010-2011
Андреева	О.П.	ПМ-01	2009-2010
Андреева	О.П.	ПМ-01	2010-2011
Баранов	Н.П.	ПМ-01	2009-2010
Баранов	Н.П.	ПМ-01	2010-2011
Быкова	Н.А.	КН-01	2009-2010
Быкова	Н.А.	КН-01	2010-2011
Волков	В.В	ПМ-01	2009-2010
Волков	В.В	ПМ-01	2010-2011

Далее рассмотрим специальные операции реляционной алгебры, применяемые в базах данных. К таким операциям следует отнести:

- ограничение отношений;

- проекция отношений;

- естественное соединение отношений;

- деление отношений.

Определение.

Ограничение отношений ( ). Результатом ограничения отношения по некоторому атрибуту или атрибутам является отношение, состоящее в точности из тех кортежей, которые удовлетворяют условию .

Пример.

Выполним ограничение отношения ВСЕ СТУДЕНТЫ по атрибуту Группа=КН-01. Результат назовем СТУДЕНТ_КН-01. В результате получим отношение (ВСЕ СТУДЕНТЫ)=СТУДЕНТ_КН-01, содержащее только кортежи, в которых значение атрибута Группа равняется КН-01.

СТУДЕНТ_КН-01

Фамилия	Инициалы	Группа
Алексеев	И.А.	КН-01
Быкова	Н.А.	КН-01
Дроздов	И.К.	КН-01
Кузнецова	Е.В	КН-01

Определение.

Проекция отношения ( ). При выполнении проекции отношения на заданный набор его атрибутов отношение-результат получается путем удаления из отношения-операнда атрибутов, не указанных в заданном наборе.

Схематически выполнение операции представлено на рис. 5.7.

Рисунок 5.7 - Схема выполнения операции проекции по

Пример.Выполним проекцию отношения СТУДЕНТ_1_КУРС по атрибутам Группа, Уч. год, Курс.

( СТУДЕНТ_1_КУРС)

Группа	Уч. год	Курс
КН-01	2009-2010
КН-01	2010-2011
ПМ-01	2009-2010
ПМ-01	2010-2011

Определение. Естественное соединение отношений (І><I). При естественном соединении двух отношений образуется результирующее отношение, кортежи которого являются соединением кортежей первого и второго отношений, если значение общих атрибутов совпадает.

Схематически выполнение операции І><I представлено на рис. 5.8.

Рисунок 5.8 - Схема выполнения операции естественного соединения отношений

Пример.Пусть задано отношение НОМЕР

НОМЕР

Фамилия	Инициалы	Зачетка №	Студ. №
Алексеев	И.А.
Андреева	О.П.
Баранов	Н.П.
Быкова	Н.А.
Волков	В.В
Дроздов	И.К.
Зайцев	О.Н.
Кузнецова	Е.В

Выполним естественное соединение отношений СТУДЕНТ_КН-01 и НОМЕР.

СТУДЕНТ_КН-01 І><I НОМЕР

Фамилия	Инициалы	Группа	Зачетка №	Студ. №
Алексеев	И.А.	КН-01
Быкова	Н.А.	КН-01
Дроздов	И.К.	КН-01
Кузнецова	Е.В	КН-01

Определение.

Деление отношений ( ). Операция деления отношений осуществляется следующим образом. Отношение-делитель должно иметь набор атрибутов, включенный в набор атрибутов делимого. Результирующее отношение содержит те атрибуты делимого, которые не присутствуют в делителе. Значения этих атрибутов берутся из тех кортежей делимого, которые включают в себя кортежи делителя.

Схематически выполнение операции представлено на рис. 5.9.

Рисунок 5.9 - Схема выполнения операции деления отношений ( )

Пример.

Выполним проекцию отношения СТУДЕНТ_КН-01 по атрибутам Фамилия, Инициалы, т.е. ФАМИЛИЯ СТУДЕНТ_КН_01= (СТУДЕНТ_КН-01).

ФАМИЛИЯ СТУДЕНТ_КН_01

Фамилия	Инициалы
Алексеев	И.А.
Быкова	Н.А.
Дроздов	И.К.
Кузнецова	Е.В

Затем произведем деление отношения НОМЕР на отношение ФАМИЛИЯ СТУДЕНТ_КН_01.

В результате деления получим таблицу номеров студентов группы КН-01.

НОМЕР ФАМИЛИЯ СТУДЕНТ_КН_01

Зачетка №	Студ. №

Кроме рассмотренных операций реляционной алгебры, в набор операций базы данных обычно включается операция присваивания, позволяющая сохранить результаты вычисления алгебраических выражений, операция переименования атрибутов, дающая возможность корректно сформировать заголовок (схему) результирующего отношения и другие полезные операции.

5.3 Контрольные вопросы и задания

1. Какое функциональное отношение называется всюду определенным?

2. Как выглядит матрица функционального отношения?

3. Какое функциональное отношение называют отображением множества в ?

4. Что такое сюръекция?

5. Что такое инъекция?

6. Что такое биекция?

7. Какое отображение называется взаимно однозначным?

8. Что называется образом элемента?

9. Что такое прообраз элемента?

10. Перечислите основные свойства отображений.

11. Что представляет собой реляционный метод построения баз данных?

12. Что называется кортежем, атрибутом, доменом?

13. Перечислите теоретико-множественные операции, применяемые при работе с реляционными базами данных. Объясните принцип их выполнения.

14. Перечислите специальные реляционные операции. Объясните принцип выполнения каждой из них.

Лекция 6. Двузначная логика. Булевы функции. Основные понятия

6.1 Двузначная логика

В данном разделе курса «Дискретная математика» рассматриваются базовые элементы аппарата двузначной логики (который был разработан Д. Булем в середине ХІХ века) − булевы функции и преобразования над ними.

Данные функции являются наиболее простым и в то же время важнейшим классом функций, которые используются для описания работы ЭВМ, конечных автоматов, вычислительных систем.

Применение булевых функций легко распространяется на объекты самой общей природы, лишь бы только они характеризовались конечным числом состояний.

Двузначная логика (булева алгебра) имеет дело с такими объектами, которые принимают одно из двух возможных значений (высокое или низкое напряжение, наличие или отсутствие заданного признака у объекта, истинное или ложное высказывание и т.п.).

Понятия, методы и средства данного типа логики лежит в основе современных компьютерных технологий.

6.2 Булевы переменные и функции

Рассмотрим основные понятия и определения алгебры логики.

Пусть задано двухэлементное множество и двоичные переменные, принимающие значения из . Элементы часто обозначают 0 и 1, однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных – логическая: «нет» – «да», «истинно» (и) – «ложно» (или), «false» – «true». Будем считать, что , рассматривая 0 и 1 как формальные символы, не имеющие арифметического смысла.

Определение.

Переменные, которые могут принимать значения только из множества , называются булевыми или логическими переменными. Элемент 1 называется единичным элементом, или единицей; элемент 0 называется нулевым элементом, или нулем. Сами значения 0и1 называются булевыми константами.

Пример.

Булевыми переменными, которые способны принимать лишь два различных значения, характеризуются объекты с двумя возможными состояниями (наличие или отсутствие у объекта определенного признака, низкое или высокое напряжение, истинное или ложное высказывание).

Пример.

В языках программирования для работы с такими переменными, как правило, вводится специальный логический тип (например, в языках Pascal и Java - boolean, в - bool). Переменная этого типа принимает два значения «false» и «true».

Отношения между булевыми переменными представляются булевыми функциями, которые подобно числовым функциям могут зависеть от одной, двух и, вообще, переменных (аргументов).

Определение.

Функция вида , аргументы и значения которой принадлежат множеству , называется -местной булевой (переключательной, логической) функцией.