Теория:
Реляционный подход организации баз данных, предложенный в \(70\)-х годах \(XX\) века Э. Коддом, основывается на математической теории множеств и математической логике. Использование базы данных предполагает манипулирование данными, включающее в себя поиск необходимых данных. Именно здесь применяются реляционная алгебра и реляционное исчисление, предполагающее вычисление предикатов первого порядка.
Предикат — утверждение, высказанное об объекте.
Утверждение может иметь всего два значения: быть истинным или ложным. Принято считать, что истинное высказывание \(=1\), а ложное \(=0\). Поиск условий, при котором выражение становится истинным, — одна из задач манипулирования данными в БД.
Учитывая, что логические переменные могут принимать только два значения, у нас есть возможность привести полную таблицу значений логической функции в зависимости от логической операции и значений логических переменных, т. е. задать логическую функцию таблично.
Напомним, что основных (базовых) логических операций — три. Это конъюнкция — логическое умножение (обозначается или значком \(*\), или не обозначается совсем), дизъюнкция — логическое сложение (обозначается или значком \(+\)) и инверсия — логическое отрицание (обозначается или чертой над логической переменной). Остальные операции выражаются через базовые.
Приведём таблицы истинности базовых операций, другими словами, таблицы значений логических функций в зависимости от значений логических переменных.
Учитывая, что логические переменные могут принимать только два значения, у нас есть возможность привести полную таблицу значений логической функции в зависимости от логической операции и значений логических переменных, т. е. задать логическую функцию таблично.
Напомним, что основных (базовых) логических операций — три. Это конъюнкция — логическое умножение (обозначается или значком \(*\), или не обозначается совсем), дизъюнкция — логическое сложение (обозначается или значком \(+\)) и инверсия — логическое отрицание (обозначается или чертой над логической переменной). Остальные операции выражаются через базовые.
Приведём таблицы истинности базовых операций, другими словами, таблицы значений логических функций в зависимости от значений логических переменных.
|
|
|
И для справки: ещё две операции, на которые часто обращают внимание в тестированиях и экзаменах.
Импликация и эквиваленция .
|
|
Импликация и эквиваленция выражаются через базовые операции.
\(=\) ;
\(=\) .
Поиск в БД формулируется в виде словесного запроса, оборота речи, которому можно поставить в соответствие логическую операцию.
Рис. \(1\). Логические операции
Пример:
предположим, что перевозки осуществляются двумя компаниями — Pegasus и Quick. При этом Pegasus зарезервировал время отправления поездов в интервале [\(5\):\(00\);\(17\):\(00\)], Quick — в интервале [\(14\):\(00\);\(23\):\(00\)]. Необходимо выбрать временной интервал для поездов компании Alternative, такой, чтобы исключить интервалы, в которые одновременно ходят поезда Pegasus и Quick
Составим логическое выражение, заменив Pegasus и Quick на \(P\) и \(Q\), а Alternative — на \(A\). Выражение обозначает, что время отправления поезда зарезервировано компанией Pegasus.
Составим логическое выражение, заменив Pegasus и Quick на \(P\) и \(Q\), а Alternative — на \(A\). Выражение обозначает, что время отправления поезда зарезервировано компанией Pegasus.
Получим правило: при любом значении переменной \(x\).
Преобразуем исходное выражение, заменив на \(P\).
Получим: .
Заменим импликацию по правилу, приведённому выше: .
Т. е. временной интервал, в течение которого курсируют поезда компаний Pegasus и Quick, вместе с временным интервалом, когда курсируют поезда компании Alternative, перекрывают весь интервал движения поездов.
— интервал [\(14\):\(00\);\(17\):\(00\)], тогда \(A\) — интервалы [\(00\):\(00\);\(14\):\(00\)] и [\(17\):\(00\);\(24\):\(00\)].
— интервал [\(14\):\(00\);\(17\):\(00\)], тогда \(A\) — интервалы [\(00\):\(00\);\(14\):\(00\)] и [\(17\):\(00\);\(24\):\(00\)].
Источники:
Рис. 1. Логические операции. © ЯКласс.