Элементы алгебры логики

Лекция 2. Основные операции реляционной алгебры

Существует два механизма поиска и отбора:

1) контекстный поиск (по заданному фрагменту текста);

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

В обоих случаях система создаёт выборку, в которую включаются записи БД, удовлетворяющие следующим условиям:

1) для контекстного поиска – заданный фрагмент текста входит в указанное пользователем данное;

2) для запроса – логическое выражение для данной записи принимает значение «Истина».

Контекстный поиск требует просмотра всех записей БД и в данном случае нас не интересует. Обратимся к аппарату алгебры логики.

Это наука – один из 21 веке английским математиком Дж. Булем. В основе алгебры логики лежит исчисление высказываний (т.е. законченных по смыслу предложений), каж­дое из которых может быть либо истинным (ТRUЕ), либо ложным (РАLSЕ). Например, высказывание "Воробей — пти­ца" является истинным, а высказывание "5 > 12" — ложным. Из таких элементарных высказываний с помощью "логичес­ких связок" АND (И), ОR (ИЛИ) и др. складываются слож­ные высказывания, каждое из которых тоже может быть ис­тинным или ложным. Например, сложные высказывания

"Воробей—птица" АND (5 < 12)

"Воробей — птица" ОR (5 > 12) истинны, а высказывание

"Воробей — хищник" АМО (5 < 12) ложно.

В компьютерной технологии элементарное высказывание называется условным выражением, а составное высказывание — логическим выражением.

Условное выражение — это высказывание о значениях опе­рандов, и это высказывание может быть истинным или лож­ным. Например, если переменная а в момент высказывания имеет значение 6, то высказывание 2 < а является истинным, а высказывание а > 15 — ложным. Результатом условного выражения является логическое (булево) данное, которое мо­жет принимать только два значения — "Истина" или "Ложь" (в других формулировках — ТRUЕ или РАLSЕ, "Да" или "Нет", 1 или 0). Операндами условного выражения могут быть числовые или текстовые константы (строки символов), пере­менные числового или текстового типа, функции, соединен­ные между собой знаками операций отношения'.

= равно; <> не равно; > больше; < меньше; <= меньше или равно;

>= больше или равно.

Условное выражение является частным случаем логического выражения.

Логическое выражение — это составное высказывание о значениях нескольких условных выражений. Операндами ло­гического выражения могут быть условные выражения, сое­диненные между собой знаками логических операций АN^ или - ОК ("И" или "Или"). Логическое выражение (так же, как и условное) может принимать только булево значение ("Исти­на" или "Ложь"). Например, рассмотрим выражения:

(а > 5) АND (а < 2)

(и > 5) ОR (а < 2)

Первое высказывание является истинным, если одновремен­но а>5 и а<1 (например, при d = 6 и a = 1),а второе выска­зывание будет истинным, если истинно хотя бы одно из сос­тавляющих его высказываний (например, при а =б и любом значении а).

В математике логические операции АND и ОR имеют на­звания:

АND — конъюнкция (И); ОR — дизъюнкция (ИЛИ).

Кроме широко распространенных операций АND и ОК, существуют следующие логические операции: ХОR — дизъюнкция("исключающее ИЛИ"); ЕQV — эквивалентность; IМР — импликация.

Пусть А — первое условное выражение в логической опе­рации, а В — второе. Тогда сводную таблицу значений логи­ческого выражения А ^ В (так называемую таблицу истинно­сти), где ^ — обобщенный знак логической операции, можно записать следующим образом (Т— "Истина", F— "Ложь");

А	В	АND	OR	XOR	ЕQV	IМР
Т	T	Т	T	F	T	T
Т	F	F	T	T	F	F
F	T	F	T	T	F	T
F	F	F	F	F	T	T

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

Существует унарная логическая операция NOT (отрицание, НЕ), выполняемая над одним выражением. Например, выра­жение NОТ (а > А) истинно, если выражение в > Ь — ложно, т.е. если а меньше или равно Ь.

В логических операциях (как и в арифметических) исполь­зуется определенный приоритет: старшая операция — отри­цание, следующая — конъюнкция, потом дизъюнкция. Приоритет операций тоже можно изменить с помощью круглых скобок (прежде всего выполняются операции в самых внут­ренних скобках). Например, в логическом выражении

(а > Ь) ОR (Ь > с) АND NОТ ((а > 0) ОR (с > а)) устанавливается следующий порядок операций:

4 3 2 1

(а > Ь) ОR (Ь > с) АND NОТ ((а > 0) ОR (с > а))

Алгебра логики (ее называют также булевой алгеброй) широко используется и в математике, и в информационной технологии: в языках программирования, в языках запросов информационных систем, в электронных таблицах, даже в языке командных файлов МS-D0S. Для определенности мы привели лишь один из вариантов начертания знаков отноше­ния и логических операций (используемый в МS Ассеss).