Основные положения дискретной математики (стр. 4 из 11)
Восемь левых смежных классов:
bc
000 +000=000 000+111=111
001+000=001 001+111=110
010+000=010 010+111=101
011+000=011 011+111=100
100+000=100 100+111=011
101+000=101 101+111=010
110+000=110 110+111=001
111+000=111 111+111=000
| I | II |
| 000 | 111 |
| 001 | 110 |
| 010 | 101 |
| 011 | 100 |
Столбцы данной таблицы есть разбиение множества С. Известно, что разбиение определяет некоторое отношение эквивалентности, тогда процесс декодирования можно производить следующим образом: допустим, что получено сообщение Сi =011. Таким образом теория групп может рассматриваться математической основой теории кодирования.
ЛИНЕЙНАЯ АЛГЕБРА
Вектор
(0, 0, ,0) со всеми координатами равными нулю, называется нулевым. Это единственный n-мерный вектор, для которого выполняются условия:Если r/ 
, то r/+
= r/Если r/ , то r/-
= r/Если r/ , то r/- r/=
Если r/ , то 0* r/=
Если а 
, то а*
= РЕЛЯЦИОННАЯ АЛГЕБРА
Реляционная алгебра широко используется при создании реляционных БД. Носитель реляционной алгебры представляет собой множество отношений, где кроме операций конъюнкции, дизъюнкции, разности и декартового произведения используются операции выбора, проекции и соединения.
Операция выбора представляет собой процедуру построения «горизонтального» подмножества, т. е. подмножества кортежей (строк), обладающими заданными свойствами.
Пример: с помощью операции выбора построим отношение 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/Ai1, Ai2,…Ain) n-арного отношения
называется множество кортежей (аi1, ai2,…,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(x1x2x3x4) = g(x1,x2) означает, что при любых значениях x1 и x2f=g незавасимо от значения x3. Удаляют фиктивные переменные поскольку они не влияют на значение функции и являются с этой точки зрения лишними.
Рассмотрим примеры логических функций:
1) Одна переменная Х имеет 4 логических функции, которые приведены в таблице 1.
Таб.1.
| Х | F0 | F1 | F2 | F3 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Функции F0 и F3 – константы 0 и 1 соответственно;