Логические функции и логические выражения — урок. Информатика (СПО), Программа 144 ч..

Базы данных как модель предметной области

3. Логические функции и логические выражения

Теория

Реляционный подход организации баз данных, предложенный в $70$-х годах $XX$ века Э. Коддом, основывается на математической теории множеств и математической логике. Использование базы данных предполагает манипулирование данными, включающее в себя поиск необходимых данных. Именно здесь применяются реляционная алгебра и реляционное исчисление, предполагающее вычисление предикатов первого порядка.

Предикат — утверждение, высказанное об объекте.

Утверждение может иметь всего два значения: быть истинным или ложным. Принято считать, что истинное высказывание $=1$, а ложное $=0$. Поиск условий, при котором выражение становится истинным, — одна из задач манипулирования данными в БД.
Учитывая, что логические переменные могут принимать только два значения, у нас есть возможность привести полную таблицу значений логической функции в зависимости от логической операции и значений логических переменных, т. е. задать логическую функцию таблично.
Напомним, что основных (базовых) логических операций — три. Это конъюнкция — логическое умножение (обозначается

\land

или значком $*$, или не обозначается совсем), дизъюнкция — логическое сложение (обозначается

\lor

или значком $+$) и инверсия — логическое отрицание (обозначается

\neg

или чертой над логической переменной). Остальные операции выражаются через базовые.
Приведём таблицы истинности базовых операций, другими словами, таблицы значений логических функций в зависимости от значений логических переменных.

$A$	$B$	$A$ $\land$ $B$
$0$	$0$	$0$
$0$	$1$	$0$
$1$	$0$	$0$
$1$	$1$	$1$

$A$	$B$	$A$ $\lor$ $B$
$0$	$0$	$0$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$1$

$A$	$\neg$ $A$
$0$	$1$
$1$	$0$

И для справки: ещё две операции, на которые часто обращают внимание в тестированиях и экзаменах.

Импликация

A \to B

и эквиваленция

A \equiv B

$A$	$B$	$A \to B$
$0$	$0$	$1$
$0$	$1$	$1$
$1$	$0$	$0$
$1$	$1$	$1$

$A$	$B$	$A \equiv B$
$0$	$0$	$1$
$0$	$1$	$0$
$1$	$0$	$0$
$1$	$1$	$1$

Импликация и эквиваленция выражаются через базовые операции.

A \to B

$=$

\neg A \lor B

;

A \equiv B

$=$

A \land B \lor \neg A \land \neg B

Поиск в БД формулируется в виде словесного запроса, оборота речи, которому можно поставить в соответствие логическую операцию.

Рис. $1$. Логические операции

Пример:

Предположим, что перевозки осуществляются двумя компаниями — Pegasus и Quick. При этом Pegasus зарезервировал время отправления поездов в интервале [$5$:$00$;$17$:$00$], Quick — в интервале [$14$:$00$;$23$:$00$]. Необходимо выбрать временной интервал для поездов компании Alternative, такой, чтобы исключить интервалы, в которые одновременно ходят поезда Pegasus и Quick
Составим логическое выражение, заменив Pegasus и Quick на $P$ и $Q$, а Alternative — на $A$. Выражение

x \in P

обозначает, что время отправления поезда зарезервировано компанией Pegasus.

Получим правило:

\neg ((x \in P) \land (x \in Q)) \to (x \in A) = 1

при любом значении переменной $x$.

Преобразуем исходное выражение, заменив

x \in P

на $P$.

Получим:

\neg (P \land Q) \to A = 1

Заменим импликацию по правилу, приведённому выше:

(P \land Q) \lor A = 1

Т. е. временной интервал, в течение которого курсируют поезда компаний Pegasus и Quick, вместе с временным интервалом, когда курсируют поезда компании Alternative, перекрывают весь интервал движения поездов.

(P \land Q)

— интервал [$14$:$00$;$17$:$00$], тогда $A$ — интервалы [$00$:$00$;$14$:$00$] и [$17$:$00$;$24$:$00$].

Источники:

Предыдущая теория

Вернуться в тему

Следующая теория