- •1.Совершенные нормальные формы.Правила приведения к сднф и скнф. Минимизация логических функций.
- •§8. Нормальные формы функций.
- •8.2 Нормальные формы.
- •8.3 Совершенные нормальные формы.
- •8.4 Правила приведения произвольной формулы алгебры логики к совершенной нормальной форме.
- •8.6 Способ составления снф для произвольной формулы алгебры логики по таблице истинности.
- •§ 1. Понятие формулы исчисления высказываний.
- •§ 2. Определение доказуемой (выводимой) формулы.
- •Правила вывода.
- •Определение выводимой (доказуемой ) формулы.
- •Правило сложной (одновременной) подстановки (спп).
- •Правило сложного заключения.
- •Правило силлогизма.
- •Правило контр позиции.
- •Правило снятия двойного отрицания.
- •§4.Понятие выводимости формул из совокупности формул.
- •§5. Понятие вывода.
- •§6. Правила выводимости.
- •H,w├a из совокупности формул : “Если а выводима из н, то она вы- водима из ”.
- •5. Теорема дедукции: h, c├ a .
- •§9.Проблемы аксиоматического исчисления высказываний.
- •2. Проблема непротиворечивости исчисления высказываний.
- •3.Проблема полноты исчисление высказываний.
- •4.Проблема независимости аксиом исчисления высказываний.
- •§1. Недостаточность логики высказываний. Понятие предиката.
- •§2. Логические операции над предикатами.
- •§3. Кванторные операции.
- •Квантор всеобщности.
- •Квантор существования.
- •Отрицание предложений с кванторами.
- •§4.Понятие формулы логики предикатов.
- •§5. Значение формулы логики предикатов.
- •§6. Равносильные формулы логики предикатов.
- •§7. Нормальные формы формул логики предикатов.
- •§8. Общезначимость и выполнимость формул. Проблема разрешимости.
- •§9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.
- •9.1 Запись математических предложений и определений в виде формул логики предикатов.
- •9.2. Построение противоположный утверждений.
- •9.3 Прямая, обратная и противоположная теоремы.
- •9.4 Необходимые и достаточные условия.
- •9.5. Доказательство теорем методом от противного.
- •Утверждения о свойствах объектов и отношениях между ними
- •Язык логики предикатов
- •Синтаксис: формулы логики предикатов
- •Семантика: системы и значения формул на их состояниях
- •Реляционные базы данных
- •Реляционная алгебра
- •Теоретико-множественные операции
- •Специальные реляционные операторы
- •Запросы
- •Ограничения целостности
- •Основные определения
- •Тьюрингово программирование
- •Стандартная заключительная конфигурация
- •Односторонние машины Тьюринга
- •Последовательная и параллельная композиции машин Тьюринга
- •Ветвление (условный оператор)
- •Повторение (цикл)
Специальные реляционные операторы
К специальным реляционным операторам относятся:
Выбор
Проекция
Соединение
Деление
Оператор выбора, примененный к отношению R(A1, ..., An), возвращает новое отношение P с тем же набором атрибутов, кортежи которого составляют подмножество кортежей отношения R, удовлетворяющих некоторому условию C. Это записывается как . Условие Cпредставляет из себя булевскую формулу, которая построена из элементарных условий, включающих имена атрибутов R и константы. Примерами элементарных условий являются равенства вида Ai = Aj, Ai=aи неравенства вида Ai <= Aj, Ai <= a, Ai >= a. Тогда отношение Pзадается формулой , где формулаC' получена из условия C заменой имен атрибутов Ai на имена соответствующих переменных xi.
Например, оператору выбора , выбирающему сотрудников с окладом свыше 6000, соответствует формула , задающая отношение :
Номер |
ФИО |
Отдел |
Должность |
Оклад |
1 |
Иванов А.А. |
торговый |
менеджер |
7000 |
5 |
Горев С.В. |
плановый |
зав.отделом |
10000 |
Оператор проекции, примененный к отношению R(A1, ..., An), возвращает все кортежи этого отношения, из которых удалены значения атрибутов, не перечисленных в списке параметров этой операции. Отношение P, являющееся проекцией R на подмножество атрибутов , записывается как . Пусть - это атрибуты отношения, не попавшие в X. Тогда проекция задается формулой .
Например, оператору проекции , составляющему список окладов сотрудников, соответствует формула , задающая двуместное отношение :
ФИО |
Оклад |
Иванов А.А. |
7000 |
Сидоров Н.П. |
5000 |
Сидорова М.И. |
6000 |
Ольгина Н.А. |
5500 |
Горев С.В. |
10000 |
Оператор соединения применяется к двум отношениям и позволяет соединять попарно их кортежи, удовлетворяющие определенным условиям. В реляционной алгебре он представлен в нескольких формах. Пусть Rи S - это отношения со схемами R(A1, ..., An, B1, ..., Bm) и S(B1, ..., Bm, C1, ..., Ck) с общимиатрибутами B1, ..., Bm. Тогда естественное соединение отношений R и S содержит кортежи, которые составлены из кортежей отношения R, продолженных кортежами отношения S. При этом соединяются лишь пары кортежей и , имеющих одинаковые значения всех общих атрибутов B1, ..., Bm. Так как значения общих атрибутов совпадают они входят в схему P по одному разу, т.е. P имеет схему P(A1, ..., An, B1, ..., Bm, C1, ..., Ck). Нетрудно понять, что естественному соединению соответствует формула .
Пусть в дополнение к отношениям Сотрудники и Комнаты в базу данных входит отношение Оборудование:
Оборудование |
||
Этаж |
НомерКомнаты |
Название |
2 |
17 |
компьютер |
2 |
17 |
принтер |
3 |
7 |
ксерокс |
3 |
25 |
принтер |
Тогда отношение определяет доступность тех или иных аппаратов сотрудникам в их комнатах. Оно имеет схему Доступ (НомерСотрудника, Этаж, НомерКомнаты, Название) и представлено в следующей таблице:
Доступ |
|||
НомерСотрудника |
Этаж |
НомерКомнаты |
Название |
3 |
2 |
17 |
компьютер |
3 |
2 |
17 |
принтер |
1 |
2 |
17 |
компьютер |
1 |
2 |
17 |
принтер |
5 |
3 |
7 |
ксерокс |
Здесь соединение производится по двум общим атрибута м Этаж и НомерКомнаты. При этом в соединение не попали сведения о сотрудниках с номерами 2 и 7, в комнатах которых нет оборудования, и о принтере в комнате 25, так как в ней нет сотрудников. Соответствующая формула имеет вид: .
Другой вариант оператора соединения - тета-соединение отношений R и S содержит кортежи, которые составлены из кортежей отношения R, продолженных кортежами отношения S, удовлетворяющими условию C. Синтаксис этого условия такой же, как и у оператора выбора. Так как в C могут входить не только равенства атрибутов, то атрибуты R и S с одинаковыми именами входят в схему P1 дважды (обычно, как и в случае декартова произведения, перед ними помещается через точку имя отношения ). Оператор тета-соединения выражается через операторы выбора и декартового произведения: . Ему соответствует формула , в которой C' - это формула C, где вместо имен атрибутов подставлены имена соответствующих переменных.
Операторы реляционной алгебры можно соединять в сложные выражения, позволяющие выражать необходимые пользователям запросы. Например, чтобы получить список фамилий сотрудников с доступным каждому из них оборудованием, можно использовать выражение
Результат его вычисления представлен в следующей таблице:
ФИО |
Название |
Иванов А.А. |
компьютер |
Иванов А.А. |
принтер |
Сидорова М.И |
компьютер |
Сидорова М.И |
принтер |
Горев С.В. |
ксерокс |
Ее строки соответствуют парам значений переменных f,c, на которых истинна формула .