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

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

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

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

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


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

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


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


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


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




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


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


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


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


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




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


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


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


[math]D_x=D_y=D_1,\quad D_z=D_2,\quad D_u=D_3.[/math]

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


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


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


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


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


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

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

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




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


[math](\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).[/math]

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


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


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


[math](\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)[/math]

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


[math](\exists u_1)(\exists u_2)\bigl(u_1\ne u_2\land \psi(x,u_1)\land \psi(x,u_2)\bigr)[/math]

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


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


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


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


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


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

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


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


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

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