|
|
Главная » 2010 » Декабрь » 14 » Алгебра логики
|
Рассмотрим первую задачу — отбор строк. Здесь нам на по-мощь вновь приходит фундаментальная наука. Английский ма-тематик Дж. Буль (отец известной писательницы Э.Войнич, ав-тора романа «Овод») еще в XIX веке, изучая законы логики, соз¬дал систему исчисления, называемую алгеброй логики. Несмотря на загадочные знаки, которые появляются в логических выраже¬ниях, основные принципы этой науки вполне доступны всем, кто знает хотя бы элементы обычной алгебры (а точнее, тем, кто знаком с понятиями переменной и значения переменной и умеет считать до двух).,
Основные элементы алгебры логики мы изложим в сопостав-лении с хорошо знакомыми вам понятиями обычной алгебры. Как всегда, речь идет только о принципах: в полном объеме бу-лева алгебра — серьезная наука, для работы в которой умения считать до двух недостаточно.
Напишем простое алгебраическое равенство (взятое наугад):
с = а+2Ь-5.
В правой части равенства записано выражение, которое в ин-форматике называют арифметическим (хотя уместно назвать его и алгебраическим). Арифметическое выражение состоит из операндов, соединенных между собой знаками арифметических операций (сложение, вычитание, умножение, деление). В нашем примере операнды — это две константы 2 и 5, а также перемен¬ные а и Ъ. Подставив конкретные значения а и Ь, мы можем вы¬числить значение арифметического выражения и присвоить его переменной с, записанной в левой части равенства. Например, при а = 2иЬ = 6с=9. В терминах информатики знак «=» — это знак присваивания. Если область определения а и Ъ — все действительные числа, то и с может принимать любое действи¬тельное значение. В частном случае арифметическое выражение может содержать один операнд. Например, в формуле а = Ъ справа находится арифметическое выражение, представленное переменной Ъ.
А теперь напишем равенство: с = а > Ь.
На первый взгляд это бессмыслица. Однако перед нами в правой части не арифметическое, а логическое выражение. И в левой части равенства находится не алгебраическая, а логическая (или булева) переменная. Ее область определения — только два числа: 1 («Истина» или «да») и 0 («Ложь» или «нет»). Логическое выражение отвечает на вопрос — да или нет (например, а > Ы). Результатом логического выражения а > b может' быть либо («да»), либо 0 («нет»), и его можно присвоить логической пере-менной с. Например, если а = 5 и b = 2, то выражение 5 > 2 яв-ляется истинным, и его значение равно 1; если а = 5, a b = 5 или 8, то выражение а > b является ложным, и его значение равно 0.
Примечание. Строго говоря, значениями булевой переменной являются TRUE («Истина») или FALSE («Ложь»). Конкретные же значения, которыми пользуется машина, могут быть разны¬ми, в зависимости от соглашений системы (например, — 1 и 0, или «не нуль» и 0). Пользователя это обычно не интересует. Для определенности мы считаем эти значения единицей и нулем.
Вернемся к примеру с Чейзом. Пусть в ИС переменная (данное), описывающая автора, имеет имя АВТОР, — тогда мы можем написать:
с = АВТ0Р="Чейз".
В этом равенстве знак «=» имеет два значения: слева это знак присваивания, а справа — знак отношения, о котором говорится далее. Кавычками в ИС обычно отмечается конкретное значение текстового данного (это символьный литерал). Просматривая в своей базе данных очередную карточку, машина вычисляет зна-чение логического выражения АВТОР="Чейз". Оно равно 1 (значение фамилии автора в карточке совпадает со значением Чейз, выражение истинно) или 0 (не совпадает). Все карточки, для которых с = 0, машина пропустит.
Зачем мы записываем слева переменную с? Что с ней делать, если и так ясно, что справа либо 1, либо 0? Очень часто пере-менная с действительно не нужна, и машина может принять ре-шение сразу после вычисления значения логического выраже¬ния, не запоминая его. Однако мы хотим подчеркнуть, что с — это полноценная логическая переменная, и при необходимости с ней можно производить дальнейшие логические операции.
Если нам надо найти книги Чейза, изданные в издательстве Луч, мы можем написать более сложное логическое выражение:
АВТ0Р="Чейз" AND ИЗДАТ="Луч".
Комбинация AND предписывает нам так прочитать это выра-жение: автор — Чейз и издательство — Луч. Это выражение ис-тинно (его значение равно 1), если одновременно (т. е. одной карточке) истинны оба составляющих его выражения (т. е. автор — Чейз и издательство — Луч). Это выражение ложно во всех
других трех случаях (например, если автор — Чейз, но издатель¬ство — не Луч).
Теперь мы знаем достаточно, чтобы сформулировать строгие определения.
Операндами логического выражения являются условные выра¬жения вида а > Ь, АВТОР="Чейз". В частном случае логическое выражение может состоять из одного операнда, то есть совпадать по смыслу с условным выражением. Например, условное выра¬жение а > Ь — частный случай логического выражения. Вспом¬ните, что и арифметическое выражение в частном случае может содержать один операнд — константу или переменную.
Значением условного выражения может быть либо 1 («Истина»), либо 0 («Ложь»).
Элементы условного выражения соединяются знаками отно-шения:
= (равно);
> (больше);
< (меньше);
<> (не равно);
>= (больше или равно);
<= (меньше или равно).
Например, выражение аОЬ истинно, если а не равно Ь, а вы-ражение а>— b истинно, если а больше или равно Ъ.
Операнды логического выражения (т. е. условные выражения) соединяются знаками логических операций:
AND — Конъюнкция (И); OR — Дизъюнкция (ИЛИ).
Например, выражение (a>b) AND (c<>d) считается истинным (т. е. равно 1), если истинными являются значения обоих услов¬ных выражений (т. е. а больше b и с не равно d). В остальных случаях оно ложно (значение равно 0). Заметим, что круглые скобки в логических выражениях употребляются так же, как и в арифметических т- для определения приоритета операций. В по¬следнем примере они необязательны (это все равно, что напи¬сать (а)+(Ь)) и использованы нами для наглядности, чтобы более четко выделить два логических операнда.
Если вместо AND («И») вы запишете OR («ИЛИ»): (a>b) OR (c<>d), значение этого выражения равно 1, если истинно хотя
бы одно из двух выражений (в том числе, и оба), т. е. а больше b или с не равно d.
Кроме широко распространенных операций AND и OR, су-ществуют следующие логические операции:
XOR — Дизъюнкция II («исключающее ИЛИ»); EQV — Эквивалентность; IMP — Импликация.
Пусть А — первое условное выражение в логической опера-ции, а В — второе. Тогда сводную таблицу значений логического выражения ААВ, где л — обобщенный знак логической операции (таблицу истинности), можно записать следующим образом (Т — «Истина», F — «Ложь»):
Указанные логические операции являются бинарными, т. е. выполняются над парой условных выражений.
Существует унарная логическая операция NOT (отрицание, НЕ), выполняемая над одним операндом. Например, выражение NOT(a>b) истинно, если выражение а > b — ложно, т. е. если а меньше или равно Ь.
Вы уже знаете (п.12.9.1), что в арифметических операциях принят определенный приоритет операций: старшей операцией считается возведение в степень, далее следуют умножение и де¬ление, затем сложение и вычитание. Приоритет можно изменить с помощью круглых скобок.
В логических операциях также используется определенный приоритет: старшая операция — отрицание, следующая — конъ¬юнкция, потом дизъюнкция. Приоритет операций также можно изменить с помощью круглых скобок (прежде всего выполняют¬ся операции в самых внутренних скобках). Например, в логиче¬ском выражении
(а > b) OR (b > с) AND NOT ((a > 0) OR (с > а)) устанавливается следующий порядок операций
В п. 14.17 приведен пример запроса к информационной сис-теме, результаты которого изменяются в зависимости от измене¬ния приоритета логических операций.
К изложенным сведениям следует добавить несколько приме¬чаний.
«Знаки» условных и логических выражений часто состоят из нескольких символов, поэтому их иногда называют операто-рами. Однако мы будем использовать термин «знак», чтобы из-бежать сочетаний типа «оператор логической операции»-
В информационных системах имя атрибута (данного) игра¬ет ту же роль, что и обозначение обычной алгебраической пере-менной. Например, сравните:
а = 5 о АВТОР = "Чейз".
3. Алгебра логики широко используется и в математике, и в
информационной технологии: в языках программирования, в
языках запросов ИС, в электронных таблицах, даже в языке ко¬
мандных файлов MS-DOS. Для определенности мы привели
лишь один из вариантов начертания знаков отношения и логи¬
ческих операций, используемый в MS Access. В отличие от зна¬
ков арифметических операций (+, —, *, /) здесь нет стандарта, и
в разных случаях (в математике, в языках программирования, в
языках запросов) эти знаки могут записываться по-разному. На¬
пример, вместо «=» часто пишут «==», вместо «О» сочетание
«!=», вместо AND — «&» , или «&&», или «and» и т. д. Для по¬
нимания принципов это не имеет значения.
Итак, вычислив значение логического выражения, машина может присвоить его булевой переменной (вот почему мы писа¬ли с = а > Ь) и использовать в дальнейших логических операци¬ях. Логические выражения (как и арифметические) могут быть сколь угодно сложными, однако на практике вы, как правило, будете иметь дело с более простой логикой, например:
RUB=02 AND DLIT<=80.
Это может означать: выбрать из видеотеки фильмы с кодом рубрики 02 (например, — вестерны) и длительностью не более 80 минут.
Аппарат алгебры логики лежит в основе всех механизмов от¬бора в информационных системах. Реализация этого аппарата может меняться от системы к системе, однако если вы поняли принципы, вам не составит труда освоить конкретный механизм. Например, в широко распространенных" базах данных типа dBASE используется понятие «фильтр», причем фильтр — это просто логическое выражение типа RUB=02 AND DLIT<=80. Информация как бы фильтруется: в выборку включаются только те записи таблицы, для которых значение фильтра равно 1 (т. е. выражение истинно). Примерно такой же фильтр вы можете применить в MS Access и выдать на экран только избранные строки таблицы (см. п. 15.2.2).
В мощных современных системах используется промышлен¬ный язык структурированных запросов SQL (Structured Query Language), который среди прочих предложений имеет англоя¬зычный оператор выборки SELECT (Выбрать). В этом операторе по определенным правилам (как всегда, условным) вы формули¬руете: что выбрать, откуда и при каком фильтре. В переводе на русский язык это может звучать примерно так: выбрать карточки из (from) базы данных "Библиотека", где (where) АВТОР равен "Чейз". В MS Access, которую мы изучаем в главе 14, использу¬ются и фильтр (примерно так же, как в dBASE), и SQL. |
|
Просмотров: 271 |
Добавил: sergei4
| Рейтинг: 0.0/0 |
| Всего комментариев: 1 | |
0   1
Nash (10.01.2012 21:53)
Keep on wirtnig and chugging away!
|
|
|
|
|
|
