Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Математическая логика и информатика

Математическая логика и информатика


Информатика — находящаяся в становлении наука, изучающая законы и методы накопления, передачи и обработки информации с помощью ЭВМ (компьютера). В англоязычных странах эта наука получила название "computer science" ("вычислительная наука"). Понятие информатики охватывает области, связанные с разработкой, созданием, использованием и материально-техническим обслуживанием систем обработки информации, включая машины, оборудование, математическое обеспечение, организационные аспекты. Таким образом, информатику определяют три неразрывно связанные между собой части: алгоритмические, программные и технические средства.


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


О логических аспектах некоторых из перечисленных дисциплин информатики мы уже говорили в предыдущих параграфах настоящей главы. В настоящем параграфе будет указано на логический аспект теории баз данных.




Общее понятие о базе данных


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


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


С теорией и практикой баз данных и баз знаний связаны различные области математики — математическая логика, алгебра, геометрия.


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




Реляционная база данных и логика запросов в ней


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


Пример 41.1. Рассмотрим простой пример реляционной базы данных, содержащей информацию о студенческой группе за один семестр. Будем исходить из трех множеств данных: D_1 — множество студентов в данной группе, D_2 — список изучаемых за семестр предметов, D_3 — спортивные секции, в которых занимаются студенты. Далее введем множество переменных X=\{x,y,z,u\}; при этом считаем, что x,y\in D_1, z\in D_2, u\in D_3. Таким образом, каждой переменной отвечает множество данных, которые эта переменная пробегает:


D_x=D_y=D_1,\quad D_z=D_2,\quad D_u=D_3.

Наконец рассмотрим еще определенный список \Phi отношений между студентами и учебными предметами, между студентами и спортивными секциями, между студентами и студентами:


а) прежде всего в этот список включим отношения \varphi_2, \varphi_3, \varphi_4, \varphi_5 между множеством D_x студентов и множеством D_z учебных предметов. При этом, например, (x,z)\in \varphi_3, если студент x по предмету z в данном семестре имеет "тройку". Аналогичен смысл остальных отношений. Каждое из этих отношений можно мыслить как двухместный предикат \varphi_{i}(x,z), заданный на множествах D_x,\,D_z, a соответствующее бинарное отношение, являющееся подмножеством декартова произведения D_x\times D_z, будет множеством истинности этого предиката;


б) символом \psi(x,u) обозначим отношение (или предикат) между множеством студентов D_x и множеством спортивных секций D_u, означающее, что студент x занимается в секции {u};


в) введем еще три отношения, на этот раз на множестве всех студентов, связанных с "моральным климатом" в студенческой группе: f_1(x,y) означает, что студент x относится к студенту y доброжелательно; f_2(x,y)x безразличен к y; f_3(x,y)x относится к y недоброжелательно. Соответствующие бинарные отношения являются подмножествами декартова произведения D_x\times D_y.


Указанный набор \Phi определяет базисную информацию — информацию о состоянии дел на каждый данный момент. Эта информация хранится в виде подмножеств соответствующих декартовых произведений. Например:


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

x,y\in D_1= {Иванов, Петров, Смирнов};
z\in D_2= {алгебра, геометрия, математический анализ, английский язык};
u\in D_3= {бокс, шахматы, туризм}.

Обработка информации, хранящейся в базе данных, предполагает определенные действия с базисными подмножествами. Для осуществления этих действий необходимо всю базисную информацию сделать однородной, т. е. "уравнять" в одном и том же большом декартовом произведении. Для этого рассмотрим множество D=D_x\times D_y\times D_z\times D_u. Проектирование этого множества D на рассматривавшиеся ранее множества D_x\times D_y,~ D_x\times D_z и D_x\times D_u позволяет рассматривать в качестве базисных отношений некоторые подмножества в D. Например, если предикат \varphi_5(x,z) имеет своим множеством истинности бинарное отношение A \subseteq D_x\times D_z, то это же отношение можно рассматривать одновременно как подмножество A' в D по правилу: упорядоченная четверка (d_x, d_y,d_z,d_u) из D принадлежит A', если (d_x,d_y)\in A. Теперь все исходные базисные бинарные отношения, заданные на разнообразных множествах, рассматриваются как четырехместные отношения, заданные на одних и тех же множествах D_x,D_y,D_z,D_u, т.е. как подмножества одного и того же множества D.




Перейдем теперь к запросам в нашей базе данных. Допустим, что нас интересует список студентов, которые отлично учатся по всем предметам, занимаются спортом, ко всем доброжелательны и не имеют врагов. Все эти качества могут быть описаны следующей формулой "идеального" студента:


(\forall z)\bigl(\varphi_5(x,z)\bigr)\land (\exists u)\bigl(\psi(x,u)\bigr)\land (\forall y)\bigl(f_1(x,y)\bigr)\land (\exists y)\bigl(f_3(y,x)\bigr).

Это есть формула логики предикатов, в которой предметные переменные, кроме одной переменной — x, связаны. Таким образом, формула задает одноместный предикат, зависящий от переменной x, пробегающей множество D_x всех студентов данной группы. Множество истинности этого предиката есть подмножество множества D_y и представляет собой множество "идеальных" студентов группы. В данном случае оно состоит из единственного студента Петрова.


Таким образом, формула логики предикатов определяет некоторый запрос в базе данных, ответ на который выдается в зависимости от состояния базы данных в данный момент времени.


Приведем другие примеры запросов. Формула


(\exists z_1)(\exists z_2)\bigl(z_1\ne z_2\land \varphi_2(x,z_1)\land \varphi_2(x,z_2)\bigr)

запрашивает список студентов, имеющих хотя бы две "двойки". Формула \lnot(\exists u)\bigl(\psi(x,u)\bigr) дает список студентов, не занимающихся спортом, а формула


(\exists u_1)(\exists u_2)\bigl(u_1\ne u_2\land \psi(x,u_1)\land \psi(x,u_2)\bigr)

дает список студентов, занимающихся по меньшей мере двумя видами спорта. Наконец формула \lnot(\exists x)\bigl(\varphi_2(x,z)\bigr) дает список предметов, по которым нет неудовлетворительных оценок.


Обсудим более подробно понятие запроса в базе данных. Отметим, во-первых, что один и тот же запрос может быть представлен разными формулами. Например, в формуле "идеального" студента вместо \lnot(\exists y)\bigl(f_3(y,x)\bigr) можно писать (\forall y)\bigl(\lnot f_3(y,x)\bigr), что равносильно (\forall y)\bigl(f_1(y,x)\lor f_2(y,x)\bigr). Ясно, что от формы записи запроса зависит скорость вычисления ответа, и поэтому далеко не безразлично, какую запись запроса выбрать.


Две формулы называют равносильными, если в любых состояниях и в любых системах данных этим формулам отвечает один и тот же результат вычислений (ответ). Другими словами, равносильные формулы — это формулы, имеющие одинаковое семантическое содержание. Тогда под запросом можно понимать не одну формулу, а весь класс равносильных ей формул. Правда, здесь возникают трудности, связанные с необходимостью уточнить понятие состояния и с необходимостью предвидеть все возможные состояния базы данных. Эти трудности преодолеваются с помощью математической логики. В математической логике имеется еще один (синтаксический) подход к определению той же равносильности формул, не требующий обращения к состояниям (к семантике). Он основан на подходящем формализованном исчислении. В каждом таком исчислении, как мы знаем, имеется понятие формулы, некоторые формулы объявляются аксиомами исчисления и указываются правила вывода. Две формулы F и G объявляются эквивалентными, если формула F\leftrightarrow G (или (F\to G)\land(G\to F), или (\lnot F\lor G)\land (F\lor\lnot G)) выводима из аксиом (т.е. является теоремой исчисления). Доказывается метатеорема адекватности исчисления: две формулы равносильны в семантическом смысле тогда и только тогда, когда они эквивалентны в указанном сейчас синтаксическом смысле.


Имеется и еще одно применение аксиоматического подхода в теории баз данных. В схему базы данных, как правило, включается определенный набор аксиом, которым должны удовлетворять состояния. В общем случае система аксиом базы данных — это некоторый набор формул в языке первой ступени, связанном с данной базой. Аксиомы выделяют определенный набор состояний и вносят определенное содержание в набор \Phi, в общем, бессодержательных символов отношений. В базах данных эти ограничения называют еще ограничениями целостности. В различных конкретных ситуациях они возникают естественным образом.


Например, в рассмотренном выше примере базы данных студенческой группы добавим еще один одноместный предикат \xi(x), означающий, что студент х получает стипендию. Тогда можем ввести аксиому:


(\exists z)\bigl(\varphi_2(x,z)\lor \varphi_3(x,z)\bigr)\to\lnot \xi(x).

Эта аксиома означает, что во всех рассматриваемых состояниях наличие "двойки" или "тройки" хотя бы по одному предмету лишает студента права на стипендию.

Перейти на форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved