Основные положения дискретной математики

Таб.3б

Таб.3в

Аналогично можно определить операцию соединения не только по условию «равенства», но и по другим условиям сравнения: <,>. Определим например операцию соединения по условию > соединение по условию > отношения 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.

 Скачать реферат