Реферат: Основные положения дискретной математики
Реляционная алгебра широко используется при создании реляционных БД. Носитель реляционной алгебры представляет собой множество отношений, где кроме операций конъюнкции, дизъюнкции, разности и декартового произведения используются операции выбора, проекции и соединения.
Операция выбора представляет собой процедуру построения «горизонтального» подмножества, т. е. подмножества кортежей (строк), обладающими заданными свойствами.
Пример: с помощью операции выбора построим отношение R/ 5 (расписание экзаменов профессора Иванова). Результатом операции выбора являются строки, в которых домен (столбец) D3 представлен значением профессор Иванов: это 1,6,8-я строки.
Таб.1
| R5 | D1 | D2 | D3 | D4 | D5 |
| 1 | K 5-01 | Теория автоматов | Пр. Иванов | 03.01 | Ауд.210 |
| 6 | K 5-02 | Теория автоматов | Пр. Иванов | 09.01 | Ауд.211 |
| 8 | K 5-04 | Матем. статистика | Пр. Иванов | 10.01 | Ауд.210 |
Для определения проекций отношений множество в реляционной алгебре разбивается на два подмножества в случае бинарного отношения и на n подмножеств в случае n-арного отношения:
, 
Проекцией Пр (R2 /A) бинарного отношения R2 , R2 
на А называется множество элементов 
.
Проекцией Пр (R2 /Ai 1 , Ai 2 ,…Ain ) n-арного отношения 
называется множество кортежей (аi1 , ai 2 ,…,aim ), где 
, каждый из которых является частью элемента n-арного отношения Rn . операция проекции определяет построение «вертикального» подмножества отношения, т. е. множество подмножества кортежей, получаемого выбором одних доменов и исключения других доменов.
Пример: проекция Пр (R5 /D2, , D3 ) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора.
Таб. 2
| R2 | D3 | D3 |
| теория автоматов | пр. Иванов | |
| математическая статистика | пр. Петров | |
| физика | пр. Сидоров | |
| алгоритмические языки | пр. Иванов |
одинаковые строки в таблице объединены в одну.
Операция соединения по двум таблицам, имеющим общий домен, позволят построить одну таблицу, каждая строка которой образуется соединением двух строк исходных таблиц. Из заданных таблиц берут строки, содержащие одно и то же значение из общего домена; общему домену сопоставляется один столбец.
Пример: найдем по двум заданным таблицам (таб.3.а, таб.3. б) результат операции соединения по домену D1 (таб.3.в)
Таб. 3.а
| R5 | D1 | D2 | D3 | D4 | D5 |
| K5-01 | теория автоматов | пр. Иванов | 03.01 | ауд. 210 | |
| K5-02 | математ. статистика | пр. Петров | 03.01 | ауд. 211 | |
| K5-03 | физика | пр. Сидоров | 05.01 | ауд. 211 | |
| K5-04 | алгоритмич. языки | пр. Иванов | 05.01 | ауд. 210 |
Таб.3б
| R5 | D1 | D2 | D3 | D4 | D5 |
| K5-01 | физика | пр. Сидоров | 09.01 | ауд. 210 | |
| K5-04 | математ. статистика | пр. Иванов | 10.01 | ауд. 210 | |
| K5-02 | теория автоматов | пр. Иванов | 09.01 | ауд. 211 | |
| K5-03 | алгоритмич. языки | пр. Петров | 10.01 | ауд. 211 |
Таб.3в
| R5 | D1 | D2 | D3 | D4 | D5 | D/ 2 | D/ 3 | D/ 4 | D/ 5 |
| K5-01 | теор.автом. | пр. Ив | 03.01 | а.210 | физика | пр.Сид | 09.01 | а.210 | |
| K5-02 | мат. стат. | пр. Пет | 03.01 | а.211 | т. авт. | пр.Ив | 09.01 | а.211 | |
| K5-03 | физика | пр. Сид | 05.01 | а.211 | алг.яз. | пр.Пет | 10.01 | а.211 | |
| K5-04 | алг. языки | пр. Ив | 05.01 | а.210 | мат. ст. | пр.Ив | 10.01 | а.210 |
Аналогично можно определить операцию соединения не только по условию «равенства», но и по другим условиям сравнения: 
<,>. Определим например операцию соединения по условию > соединение по условию > отношения Rа по атрибуту х и отношения Rb по атрибуту у (атрибуты х, у являются атрибутами одного и тог же домена общего для отношений Rа , Rb ), х>у называется множество всех кортежей 
, таких, что - конкатенация кортежа аi , принадлежащего Rb , где х - часть аi , у – часть bi и х>у.
Запрос в реляционной БД будет выполнен тем быстрее, чем меньше операций над отношениями он содержит Таким образом представляет практический интерес рассматриваемая выше задача упрощения представления множества через введенные операции.
2 МАТЕМАТИЧЕСКАЯ ЛОГИКА. АЛГЕБРА ЛОГИКИ.
В булевой алгебре рассматривается двухэлементное множество В, элементы которого обозначаются как 0 и 1 и рассматривают их как формальные символы, не имеющие арифметического смысла. Наиболее распространенная интерпретация двоичных переменных – логическая: «да» – «нет», «истина» – «ложь».
Алгебра образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики.
Функцией алгебры логики (или логической функцией) от n-переменных, называется n-арная операция на В.
Логическая функция f (x1,… xn ) – это функция принимающая значения 0,1. Множество всех логических функций обозначается Р2 , множество всех логических функций от n-переменных обозначается Р2 (n). Всякая логическая функция может быть задана таблицей, в левой части которой перечислены все наборы переменных, а в правой части – значения функции на этих наборах.
Переменная хi в функции f(x1,… xi , xi , xi +1 ,…,xn ) называется несущественной (или фиктивной), если f(x1,… xi , 0, xi +1 ,…,xn ) = f(x1,… xi ,1,xi +1 ,…,xn ) при любых значениях остальных переменных, т. е. если изменение значения xi в любом наборе значений x1,… xi не меняет значение функции. Говорят, что функция g получена из функции f удалением фиктивной переменной и наоборот, причем эти функции считаются равными.
Пример: f(x1 x2 x3 x4 ) = g(x1 ,x2 ) означает, что при любых значениях x1 и x2 f=g незавасимо от значения x3 . Удаляют фиктивные переменные поскольку они не влияют на значение функции и являются с этой точки зрения лишними.
Рассмотрим примеры логических функций:
1) Одна переменная Х имеет 4 логических функции, которые приведены в таблице 1.
Таб.1.
| Х | F0 | F1 | F2 | F3 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |