Елизаров А.М. Математические методы в библиотечной работе

Подождите немного. Документ загружается.

Например, для высказывательной формы А(х)=

,,Лермонтов написал поэму х" множество М

состоит

из {,,Демон", „Мцыри", „Маскарад", ...}, но в него не-

входит „Герой нашего времени".

Мы видим, что введенное выше понятие позволяет

каждой высказывательной форме поставить в соответст-

вие некоторое множество, а именно ее множество

истинности. Оказывается, и наоборот, по любому мно-

жеству можно описать высказывательную форму, для

которой оно будет служить множеством истинности

Для этого достаточно рассмотреть форму вида „х —

элемент заданного множества". Ясно, что форма ис-

тинна только при тех значениях х, которые принадлежат

исходному множеству.

Над высказывательньши формами мы производим

самые разнообразные логические операции, образовы-

вая новые формы. Как связаны между собой множест-

ва истинности сложной формы и множества истинности,

простых форм? Ответ на этот вопрос проливает свет

на указанную аналогию между алгеброй множеств и

алгеброй высказываний. Пусть выеказывательные

формы А(х), В(х) на множестве X имеют в качестве

множеств истинности М

и М

соответственно.

Форма , ) истинна для тех значений x, при ко-

торых А (х) ложна и наоборот. Поэтому множество

истинности для

состоит из элементов, которые

не принадлежат к множеству истинности формы А(х).

Это можно записать кратко в виде М

Форма А (х)ΛВ(х) истинна для тех х, для

которых истинны и А (x), и В (х). Поэтому в множество

ис-тинности для А(х)/\В(х) нужно включить те

элемен-ты, которые принадлежат и множеству

истинности для А(х), и множеству истинности для В(х),

т. е. М

АΛВ

=М

. Аналогичные рассуждения

приводят нас к формуле М

А\/В

=М

. Установленное

соот-ветствие между высказывательньши формами и

множествами, логическими операциями и операциями

над множествами показывает полную

эквивалентность двух теорий: алгебры логики и

алгебры множеств. В одной из них речь идет о

множествах, в другой — о высказываниях, но с

математической точки зрения они идентичны и

представляют собой интерпретацию

ЕДИНОЙ теории (ее называют булевой алгеброй) на

языке теории множеств и на языке исчисления выска-

зываний. Поэтому можно получать результаты, ка-

сающиеся одних объектов (например, множеств), а

затем формулировать их как утверждения о других

объектах (например, высказываниях).

Например, все логические операции можно изобра-

жать на диаграммах Эйлера — Венна, причем выска-

зывания будут изображаться кругами на плоскости, а

операциям над ними будут соответствовать те или

иные части этих кругов. Другим применением указан-

ного соответствия может служить

Теорема. Высказывательные формы равносиль-

ны тогда и только тогда, когда их множества

истинности совпадают.

Доказательство. Предположим, что А(х)

В(х). В этом случае для соответствующих значе-

ний а высказывания А (а) и В (а) либо одновременно

истинны, либо ложны. Но отсюда следует, что а од-

новременно либо включается в множества М

и М

либо не включается. Значит, М

=М

Докажем обратное. Пусгь а М

= М

. Тогда

высказывания А (а) и В (а) истинны. Если же а М

=М

, то А (а) и В (а) ложны. Поэтому А(х) и В(х)

при любых значениях х принимают ОДНИ И те же

значения истинности, т. е. А(х) В(х) .

Что соответствует случаю включения одного мно-

жества ИСТИННОСТИ в другое? Рассмотрим эту ситуа-дию

детальнее. Пусть М

. Это означает, что любой

элемент а множества М

содержится в М

. На языке

логики это можно переформулировать так: для всех

значений а М

из того, что истинно высказывание А

(а), следует» что истинно высказывание В (а). В

подобных случаях говорят, что высказыва-тельная

форма В(х) логически следует из А(х), и обозначают А

(x) В (х). Если А (х) В (х) и В (х)

А(х), то выполнены сразу два включения

и М

, которые означают равенство М

. Но, как показано в теореме, тогда А(х) В(х).

Таким образом, если А В и В А, то А В.

Понятие логического следования играет важную

роль при построении строгой теории доказательств

(теории логического вывода).

4*. Понятие о логическом выводе. В одну из за-

дач логики входит построение принципов рассужде-

ний, т.е. теории вывода. На практике это сводится к

отысканию правил для решения механическим путем

вопроса о том, можно ли некоторую цепь рассужде-

ний, основываясь на ее форме, считать правильной.

Любая цепь рассуждений состоит из простых шагов,

каждый из которых заключается в проверке того, что

одни высказывания являются непосредственными ло-

гическими следствиями других. При этом часть на-

чальных высказываний, называемых посылками, счи-

тают истинными (на основании опыта, эксперимента

или убеждения) и стремятся на основе нескольких

принципов рассуждений получить последнее высказы-

вание в цепи, называемое заключением. Если исполь-

зованные нами принципы были правильными, то мм

вправе рассматривать полученное заключение как

истинное высказывание.

Например, мы знаем, что если истинно А(х) , то,

независимо от истинности или ложности В(х),

дизъюнкция А(х) V В(х) будет истинной. В этом случае

мы говорим, что А(х) V В(х) логически следует из

А(х). Приведем общее определение, охватывающее

частный случай логического следования высказыватель-

ных форм.

Определение. Логическое выражение У следует

из логического выражения X, если У истинно для

всех значений сходящих переменных, при которых

истинно X (обозначают, как и для форм, X У.

Х—вто посылка, а У — заключение).

Познакомимся с некоторыми простейшими прин-

ципами логического вывода, наиболее часто употреб-

ляемыми в рассуждениях. Прежде всего необходимо

выяснить, когда цепь рассуждений, состоящая из

высказываний А

, А

, ..., А

дает в качестве логи-

ческого следствия высказывание В, иными словами,

когда А

ΛА

Λ...ΛА

В. Основой для ответа слу-

жит следующая

Теорема. Высказывание В есть логическое

следствие высказываний A

, A

,..., А

(т. е. А

/\А

/\....

...ΛA

В) тогда и только тогда, когда импликация

ΛA

Λ ... ΛA

→B истинна при всех значениях пе-

ременных.

Доказательство. Пусть А

ΛА

Λ...ΛA

Это означает, что В истинно всегда, когда истинно

АΛА

Λ...ΛA

. Но тогда импликация А

ΛА

Λ...ΛА

→

→В истинна..

Предположим, что А

/\А

/\ ... ΛA

→B истинна для

всех значений переменных. По определению опера-

ции→тот случай, когда А

/\А

Λ...ΛА

ложно, а В —

истинно, невозможен. Значит, всегда, когда А

ΛА

Λ...

...ΛА

истинно, В также истинно, т. е. А

ΛА

Λ...

...ΛА

→В .

Приведем примеры применения

доказанной теоремы.

Пример 1. Покажем спра-

ведливость правила отделения

(латинское: modus ponens) для

теории вывода: АΛ(А

→В) В.

Для этого составляем таблицу

истинности высказывания АΛ

Λ(А→В)→В (табл. 13) и видим,

что она состоит из одних зна-

чений ,,и". Из доказанной теоремы

следует справедливость правила

отделения.

Пример 2. В логике есть еще целый ряд правил

логического вывода, которые можно доказать анало-

гичным образом. Мы приведем лишь несколько при-

меров:и→А А;(А→В)Λ Ā ; (А→В)Λ(В→С)

→С; АΛВΛ(АΛВ→С) С.

§ 6. Применение логических понятий

в информатике

Ниже мы познакомимся с теоретико-множественной

моделью информационно-поисковой системы (ИПС),

основные моменты работы которой заключаются в

представлении информации и информационном поиске.

Вопросы организации, функционирования и классифи-

кации, ИПС подробно изложены в ([22,] гл. 4, п. 6).

Представление информации в ИПС охватывает процесс

индексирования документов, оформления запросов и

способы хранения информации. Сейчас мы более де-

Таблица 13

АΛ(А→В)→В

тально изучим каждый из этих процессов, основы-

ваясь на аппарате математической логики.

1. Индексирование документов. Процесс индекси-

рования заключается в том, чтобы отобразить содер-

жание документа при помощи некоторого множества

индексационных элементов. В развитых ИПС процесс

индексирования служит приписыванию каждому до-

кументу множества дескрипторов (ключевых слов),

отражающих его содержание и составляющих поиско-

вый образ документа. Отбор дескрипторов, описываю-

щих документ, необходимо осуществлять на основе

нескольких установленных критериев, позволяющих

выбирать конкретные или общие дескрипторы, большое

их число или малое и т. д. Кроме того, должна быть

устранена (по возможности) семантическая многознач-

ность, связанная с выбором различных дескрипторов,

описывающих сходные элементы, и одинаковых дес-

крипторов, обозначающих одинаковые элементы. На-

пример, при описании одного документа можно ис-

пользовать дескриптор „автор книги", а при описании

другого — дескриптор „писатель". Ясно, что при поиске

один документ может быть не обнаружен. Для

устранения подобных ситуаций необходимо либо

составить словарь разрешенных дескрипторов, либо

использовать некоторый тезаурус.

Сейчас мы рассмотрим примеры индексирования

документов, основанныа на использовании одномест-

ных и двухместных высказывательных форм и их

множеств истинности.

Пример. Пусть создается ИПС, в которой должны

храниться библиографические данные о произведениях

русских писателей. При этом в систему вводятся

следующие документы (по маре переиздания):

документ 1. Булгаков, „Бег", 1978;

документ 2. Ильф и Петров, „Золотой теленок", 1978;

документ 3. Булгаков, „Мастер и Маргарита"

1979; документ 4. Блок, „Двенадцать", 1980.

Осуществим отбор дескрипторов для мини-ИПС по

следующим принципам; в качестве ключевых слов

выберем фамилии авторов, названия произведений и

годы последнего издания книг. Проанализировав мас-

сив документов Д1 — Д4, приходим к множеству дес-

крипторов, приведенному в таблице 14, где справа

приведены сокращенные обозначения, составленные

из четырех букв или цифр (см. также ниже пример 3).

5 Т-743 65

Таблица14 Введем классификацию

дескрипторов по классами

авторов; произведений; го-

дов издания. Тогда для ха-

рактеристики принадлеж-

ности дескриптора к тому

или иному классу необхо-

димо определить одномест-

ные высказывательные фор-

мы, описывающие свойства

соответствующих классов:

А (х) = "х автор книги",

К (x) = "х есть книга",

Г(х) = "х год издания книги".

Нетрудно убедиться, что

множества истинности

указанных форм задают разбиение множества дес-

крипторов из таблицы на классы: М

= {БЛГК; БЛКЬ;

ИЛФЬ; ПТРВ}, M

={МCМГ; БЕГЬ; ДВНЦ; ЗЛТК},

={0078; 0079; 0080}.

Перейдем к заданию отношений между дескрипто-

рами. Предположим, что мы хотим описать книги,

написанные одним и тем же автором, порядок изда-

ния книг и т. д. Эти отношения описываются, например,

следующими двухместными высказывательными фор-

мами:

(х, у) = „ х написал книгу у",

( x, y) = " книга х вышла в году у",

(x, у) = „книга х издана раньше книги у".

Тогда множество истинности для R

состоит из

пар {‹БЛГК; МСМГ›, ‹ИЛФЬ; ЗЛТК›, ‹ПТРВ; ЗЛТК›,

‹БЛКЪ; ДВНЦ›, ‹БЛГК; БЕГЬ›}; множество истинности

для R

состоит из пар {(МСМГ; 0079), (БЕГЬ; 0078),

(ЗЛТК; 0078), (ДВНЦ; 0080)}.

2. Хранение информации. Обратимся ко второму

аспекту процесса представления информации в ИПС —

способам хранения информации, приспособленным для

ведения поиска. Введем важное для дальнейшего по-

нятие.

Определение. Файлом (англ. — file) называется

множество данных (элементов), упорядоченное по

определенному признаку.

Дескриптор Символ

Булгаков БЛГК

Бег

БЕГЬ

1978

0078

Иль

ИЛФ

Петров

ПТРВ

Золотой теленок

злтк

1978

0078

Масте

и Ма

га

ита МСМГ

1979

0079

Блок

БЛКЬ

Двенадцать

двнц

1980

0080

Например, список авторов по алфавиту представ-

ляет собой „авторский файл"; названия книг, записан-

ные в порядке выхода в свет, — „титульный файл";

годы издания и переиздания книг—„издательский

файл" и т.д. Составление подобных файлов позволяет

"быстро получить ответы на простейшие запросы, ка-

сающиеся тех или иных библиографических данных

документа. Однако для ответов на сложные запросы

уже необходима самая разнообразная информация,

поэтому поиск приходится осуществлять сразу на

нескольких файлах, что требует длительного времени.

Сейчас большое распространение получила идея соз-

дания базы данных; вместо нескольких файлов, каж-

дый из которых предназначен для определенной ин-

формации, создают единый файл, содержащий всю

информацию. При атом достигается значительная

экономия из-за устранения многочисленного дубли-

рования информации на отдельных файлах. Для ус-

пешной работы с базой данных, очевидно, необходимо

обеспечить доступ к различным частям основного

файла — подфайлам — для отбора требуемой кон-

кретной информации. Это достигается путем создания

в основном файле справочника, указывающего на

расположение подфайлов.

Процесс информационного поиска связан со сле-

дующими операциями над файлами: нахождением эле-

мента файла с требуемым свойством, включением

нового элемента в файл, исключением ненужного

элемента из файла. Рассмотрим несколько примеров

построения файлов.

Последовательные файлы. В таких файлах

элементы располагаются один за другим произволь-

ным образом. Порядок определяется лишь физическим

расположением элементов, не определены ни подфай-

лы, ни разбиения на части. Нет в таком файле и

справочника. Поэтому для нахождения всех элементов

с требуемыми свойствами (или для исключения не-

нужных элементов) необходимо просмотреть весь

файл. Таким образом, для отыскания любого элемента

файла нужно перебрать примерно половину всех за-

писей. Включение нового элемента в последователь-

ный файл не составляет труда — eгo простo вводят в

конец файла.

Пример 1. Осуществим представление в после-

довательном файле всей информации о мини-ИПС из

примера п. 1. Для этого выберем в качестве элементов

файла дескрипторы, описывающие документы, и их

связи друг с другом. Например, дескриптор „Булга-

ков" войдет в файл элементом-А БЛГК, который ука-

зывает на то, что Булгаков — автор книги. Полностью

файл мини-ИПС представлен на рис. 29.

Рис. 29. Последовательный файл

Отметим, что в библиотечных системах последова-

тельные файлы мало применимы из-за неприемлемо

большого времени их просмотра.

Списковые файлы являются обобщением по-

следовательных файлов и уже учитывают связи между

различными элементами. В таких файлах физический

порядок следования элементов не связан с логическим

порядком информационных элементов. Они распола-

гаются в порядке добавления, но каждый элемент

содержит, помимо самого дескриптора, еще два ука-

зателя, которые в совокупности образуют справочник

спискового файла. Первый из указателей ссылается

на элемент, логически предшествующий данному, а

второй — на логически следующий зa данным.

Процедура включения и исключения элементов

остается такой же простой, как и в последовательном

файле — элемент вводят в конец. Однако при этом

требуется изменить указатели логически предшест-

вующего элемента и элемента, следующего за добав-

ленным к файлу. При поиске элемента с требуемым

свойством уже не нужно просматривать весь файл,

а необходимо начать с логически первого элемента

файла и, следуя далее по ссылкам указателей, сравни-

вать код требуемого элемента с кодом каждого про-

сматриваемого указателя. Таким образом, поиск осу-

ществляется, по сути дела, по справочнику, который

обладает намного меньшими объемами, чем исход-

ный файл.

Пример 2. Построим списковый файл для мини-

ИПС, отражающий в своей структуре, кроме дескрип-

торов, еще и описание высказывательной формы

(отношения) R

(x, y) - „книга х издана раньше книги

у". Элементы в основном файле упорядочены по

фамилиям первых авторов, но для библиографического

Рис. 30. Списковый файл

поиска необходимо получать ответы на запросы в

порядке времени выхода книги в свет. Один из спо-

собов организации файла, позволяющий учесть подоб-

ные пожелания, приведен на рис. 30, где указатели

отмечают связи между элементами.

Древовидные файлы являются наиболее рас-

пространенными частными видами списковых файлов

(элементы располагаются в произвольном порядке и

имеют указатели на своих логических соседей). Одна-

ко структура файла выбирается так, чтобы он опи-

сывал дерево (или лес) связей между элементами

(ср. п. 3 § 2). При этом поиск начинается с корня

дерева и осуществляется только по требуемой цепи,

а не по всему дереву. Способ реализации такого за-

дания информации детально рассмотрен в примере.

Пример 3. Осуществим построение авторского

файла для мини-ИПС. Первоначально представим

каждый из дескрипторов "Булгаков", „Блок", „Ильф",

„Петров" в сокращенном (закодированном) виде. Для

этого используем четырехбуквенные комбинации,

составленные по следующим правилам: оставляется

первая буква фамилии; берутся следующие за ней

три согласные буквы. Если фамилия автора короткая

или содержит менее трех слагаемых, то вместо не-

достающих букв записывают „Ь". Если же фамилия

слишком длинная, она сокращается за счет того, что

правый конец не учитывается. Двойные буквы об-

рабатываются как одиночные. После этой обработки

множество дескрипторов вносится в авторский файл,

представляющий лес, где каждое дерево соответствует

одной из букв алфавита. Все элементы файла будут

представлять букву, для которой приведены два ука-

зателя: один для следующей буквы, второй — для

альтернативной буквы, входящей в другую фамилию.

Например, занесем в древовидный файл закодирован-

ные дескрипторы БЛКЬ и БЛГК. Тогда файл будет

выглядеть следующим образом.

Буква Б — указатель на Л,

буква Л —указатель на К—указатель на Г,

буква К —указатель на Ь,

буква Ь —указатель конца,

буква Г — указатель на К,

буква К — указатель конца (см. также рис. 31).

Если в файл необходимо ввести новую фамилию,

например, „Булыгин", закодированную как БЛГН, то