Игошин Математическая логика и теория алгоритмов (1019110), страница 103
Текст из файла (страница 103)
В-третьих, Кольмеррор, создавший язык ПРОЛОГ, первоначально предназначал его для обработки естественного языка. Он разработал на ПРОЛОГЕ систему грамматического разбора естественного языка нисходящим методом. Этот формализм был доработан учеными, которые продемонстрировали его успешное применение к системам, которые обрабатывают запросы, сформулированные на естественном языке.
' С. Григор»ев, М.М»розов. Да»айте иоиробуем ПРОЛОГ // Информатика и образование. Г987. 14« 4. 413 В-четвертых, все основные концепции, используемые в формализмах представления знаний для задач искусственного интеллекта, включая семантические сети, фреймы, правила продукций и объектно-ориентированное программирование, можно выразить при помощи логики и реализовать средствами логического программирования. В-пятых, при представлении знаний одной из главных задач является выбор такой формы представления, которая может быть использована в экспертных системах. При помощи ПРОЛОГА были построены экспертные системы для ряда сфер, включая решение уравнений, медицину, законодательство, юриспруденцию, архитектуру, автоматизацию заводского производства, проектирование электронных схем, синтез микропрограмм, анализ финансового положения и помощь в принятии решений.
Простейшие примеры экспертных систем были рассмотрены в предыдущем пункте. и 41. Математическая логика и информатика Информатика — находящаяся в становлении наука, изучающая законы и методы накопления, передачи и обработки информации с помощью ЭВМ (компьютера). В англоязычных странах эта наука получила название «сотрцтег зс1епсе» («вычислительная наука»).
Понятие информатики охватывает области, связанные с разработкой, созданием, использованием и материально- техническим обслуживанием систем обработки информации, включая машины, оборудование, математическое обеспечение, организационные аспекты. Таким образом, информатику определяют три неразрывно связанные между собой части: алгоритмические, программные и технические средства. Современная информатика уходит своими корнями в математику и кибернетику, электронику и системотехнику, логику и лингвистику. Основные научные направления информатики образуют следующие научные дисциплины: теоретические основы вычислительной техники, статистическая теория информации, теория вычислительного эксперимента, алгоритмизация, программирование, искусственный интеллект.
Прикладная информатика обслуживает науку, технику, производство и другие виды человеческой деятельности путем создания и передачи в общество информационной технологии. О логических аспектах некоторых из перечисленных дисциплин информатики мы уже говорили в предыдущих параграфах настоящей главы. В настоящем параграфе будет указано на логический аспект теории баз данных. Общее понятие о базе данных.
Обработка больших массивов информации — наиболее массовая область применения компьютеров. Одним из способов хранения и обработки информации яв- 414 ляются так называемые базы данных. Под данными понимается информация, находящаяся в памяти компьютера или подготовленная для ввода в компьютер. База данных — это организованная совокупность (система) данных, предназначенная для длительного хранения (обычно во внешней памяти компьютера) и постоянного применения. База данных должна быть способна выдавать ответы на запросы.
При этом можно запрашивать то, что непосредственно хранится в базе, но можно запрашивать и производную информацию, т.е. информацию, как-то выражаемую через базисную. База данных является не случайным собранием сведений, но является постоянной основой для некоторого вида конкретной деятельности человека — пользователя базы данных. Базы данных подразделяются на иерархические, сетевые, реляционные.
В реляционных базах информация хранится в виде отношений между данными, а в сетевых и иерархических учитывается некоторая геометрия связей данных. База данных снабжается совокупностью языковых и программных средств, предназначенных для создания, обслуживания (ведения) и использования базы данных многими пользователями — так называемая система управления базами данных. Понятие базы знаний представляет собой обобщение понятия базы данных.
База знаний — организованная совокупность знаний, представленная в форме, допускающей автоматизированное использование этих знаний с помощью компьютера. При этом база знаний содержит не только конкретные факты из той или иной области, но и описание правил и общих закономерностей. Например, при решении задач из тригонометрии базой данных могут служить таблицы значений тригонометрических функций, а в базу знаний будут дополнительно включены различные тригонометрические тождества, выражающие свойства тригонометрических функций и взаимосвязи между ними. С теорией и практикой баз данных и баз знаний связаны различные области математики — математическая логика, алгебра, геометрия.
В следующем пункте рассматривается пример реляционной базы данных, на котором поясняется применение математической логики для описания запросов в базах данных. Реляционная база данных и логика запросов в ией. Реляционная база данных с математической точки зрения представляет собой конечный набор конечных отношений различной арности между заранее определенными множествами элементарных данных. Другими словами, реляционная база данных (точнее, каждое ее состояние) — это конечная модель в смысле математической логики. Над отношениями модели можно осуществлять различные алгебраические операции.
Тем самым теория реляционных баз данных становится областью приложений математической логики 415 и современной алгебры и опирается на точный математический формализм. Пример 41.1. Рассмотрим простой пример реляционной базы данных, содержащей информацию о студенческой группе за один семестр. Будем исходить из трех множеств данных: Р, — множество студентов в данной группе, Р2 — список изучаемых за семестр предметов, Р, — спортивные секции, в которых занимаются студенты. Далее введем множество переменных Х= (х, у, г, и); при этом считаем, что х, у в Рн г в Рв и в Рз. Таким образом, каждой переменной отвечает множество данных, которые эта переменная пробегает: Р„= Р„= Рн Р, = Рм Р„= Рз. Наконец рассмотрим еще определенный список Ф отношений между студентами и учебными предметами, между студентами и спортивными секциями, между студентами и студентами: а) прежде всего в этот список включим отношения ~рм <р, „<р4, <р~ между множеством Р„студентов и множеством Р, учебных предметов.
При этом, например, (х, г) в д~, если студент х по предмету г в данном семестре имеет «тройку». Аналогичен смысл остальных отношений. Каждое из этих отношений можно мыслить как двухместный предикат в;(х, л), заданный на множествах Р„, Р„а соответствующее бинарное отношение, являющееся подмножеством декартова произведения Р„х Р„будет множеством истинности этого предиката; б) символом у(х, и) обозначим отношение (или предикат) между множеством студентов Р, и множеством спортивных секций Р„, означающее, что студент х занимается в секции и; в) введем еше три отношения, на этот раз на множестве всех студентов, связанных с «моральным климатом» в студенческой группе: 1;(х, у) означает, что студент х относится к студенту у доброжелательно; 1~(х, у) — х безразличен к у; Я~(х, у) — х относится к у недоброжелательно.
Соответствующие бинарные отношения являются подмножествами декартова произведения Р„х .0 . Указанный набор Ф определяет базисную информацию — информацию о состоянии дел на каждый данный момент. Эта информация хранится в виде подмножеств соответствующих декартовых произведений. Например: 4!6 х„у в Р, = (Иванов, Петров, Смирнов); г е Р2 = (алгебра, геометрия, математический анализ, английский язык); и в Р, = (бокс, шахматы, туризм).
Обработка информации, хранящейся в базе данных, предполагает определенные действия с базисными подмножествами. Для осуществления этих действий необходимо всю базисную информацию сделать однородной, т.е. «уравнять» в одном и том же большом декартовом произведении. Для этого рассмотрим множество Р = Р, х Р, х Р, х Р„. Проектирование этого множества Р на рассматривавшиеся ранее множества Р„х Р, Р» х Р, и Р» х Р„позволяет рассматривать в качестве базисных отношений некоторые подмножества в Р. Например, если предикат уз(х, г) имеет своим множеством истинности бинарное отношение А ~ Р» х Р„то это же отношение можно рассматривать одновременно как подмножество А' в Р по правилу: упорядоченная четверка (Н„, пу, И„Ы„) из Р принадлежит А', если (и'„, ду) е А.
Теперь все исходные базисные бинарные отношения, заданные на разнообразных множествах, рассматриваются как четырехместные отношения, заданные на одних и тех же множествах Р„Р, ЄЄ, т.е. как подмножества одного и того же множества Р. Перейдем теперь к запросам в нашей базе данных. Допустим, что нас интересует список студентов, которые отлично учатся по всем предметам, занимаются спортом, ко всем доброжелательны и не имеют врагов. Все эти качества могут быть описаны следующей формулой «идеального» студента: ( «з)(ф5 (х 2)) л (Э л)(~у(х и)) л ( «у)(т1(хр у)) л (Э у)(~3(у х)). Это есть формула логики предикатов, в которой предметные переменные, кроме одной переменной — х, связаны.
Таким образом, формула задает одноместный предикат, зависящий от переменной х, пробегающей множество Р, всех студентов данной группы. Множество истинности этого предиката есть подмножество множества Р, и представляет собой множество «идеальных» студентов группы. В данном случае оно состоит из единственного студента Петрова. м и~«««« 417 Таким образом, формула логики предикатов определяет некоторый запрос в базе данных, ответ на который выдается в зависимости от состояния базы данных в данный момент времени. Приведем другие примеры запросов.
Формула (Лз1)(Ззз)(з~ ~ зз н ф~(х, з,) н фз(х, зз)) запрашивает список студентов, имеющих хотя бы две «двойки». Формула — (Ли)(~у(х, и)) дает список студентов, не занимающихся спортом, а формула (Ли1)(Лиз)(и~ Ф иг н 1у(х, и,) л у(х, из)) дает список студентов, занимающихся по меньшей мере двумя видами спорта. Наконец формула — (Лх)(д,(х, г)) дает список предметов, по которым нет неудовлетворительных оценок. Обсудим более подробно понятие запроса в базе данных. Отметим, во-первых, что один и тот же запрос может быть представлен разными формулами. Например, в формуле «идеального» студента вместо (Лу)(гз(у, х)) можно писать ('уу)( яу, х)), что равносильно (Чу)(Я(у, х) ~~ /з(у, х)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
