Формальные логические модели

В основе моделей такого типа лежит понятие формальной системы.

Постановка и решение любой задачи связаны с определенной предметной областью. Так, решая задачу анализа рынка мы вовлекаем в предметную область такие объекты, как конкретные регионы, конкретные товары, конкретные даты и общие понятия "регион", "товар", "дата" и т.д.

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

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

Языки предназначенные для описания предметных областей называются языками представления знаний. Универсальным языком представления знаний является естественный язык. Однако использование естественного языка в системах машинного представления знаний наталкивается на ряд препятствий, главным из которых является отсутствие формальности естественного языка.

Логические выражения, построенные на языке представления знаний, могут быть истинными или ложными. Некоторые из этих выражений, являющиеся всегда истинными, объявляются аксиомами (или постулатами). Они составляют ту базовую систему посылок, исходя из которой и пользуясь определенными правилами вывода, можно получить заключения в виде новых выражений, также являющихся истинными.

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

Всякая формальная теория F = (A, V, W, R), определяющая некоторую аксиоматическую систему, характеризуется:

· наличием алфавита (словаря) – A;

· множеством синтаксических правил – V;

· множеством аксиом, лежащих в основе теории, – W;

· множеством правил вывода – R.

Классическими примерами аксиоматических систем являются исчисление высказываний и исчисление предикатов.

Исчисления высказываний

Логика высказываний – самый простой раздел математической логики, лежащий в основе всех остальных ее разделов. Основными объектами рассмотрения являются высказывания. Под высказыванием понимают повествовательное предложение, о котором можно сказать одно из двух: истинно оно или ложно. Пусть есть множество высказываний, фраз, принимающих значение «истина» или «ложь». Примером могут быть фразы «сегодня холодно». «Идёт дождь», «Коля Петров учится в БГЭУ», «Студент поехал в Китай» и др. Такие высказывания называют их элементарными высказываниями и обозначают прописными буквами латинского алфавита. В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от значений «истинно» и «ложно». Не рассматривается и трёхзначная логика, со значениями, скажем «Да», «Нет», «Не знаю». Ответ отличный от «Да» должен быть «Нет». Древние философы называли этот принцип законом исключения третьего.Высказывание – это утверждение, которое может быть только истинно или ложно. Его принято обозначать символами T (от True), или F (от False), или соответственно, 1 (для истинного значения) или 0 (для значения ложь). Значение высказывания зависит от предметной области. Например, высказывание «температура 30 градусов – жара» будет истинным в Беларуси и ложным на экваторе. Поэтому весьма важно конкретизировать область на которой определено употребляемое высказывание.Из элементарных высказываний строятся более сложные высказывания с помощью логических связок «НЕ», «И», «ИЛИ», «ТО ЖЕ,ЧТО»(«ЭКВИВАЛЕНЦИЯ»),«ИЗ… СЛЕДУЕТ…»(«… ВЛЕЧЁТ…», «…ПОТОМУ, ЧТО…»). Связки логики высказываний представляют функции истинности или функции алгебры логики. В таб.9.1 представлены логические связки и их обозначения. Таблица 9.1. Логические связки

Название	Обозначение	Как читается	Другие обозначения
Отрицание	¬	НЕ	⎯s, not, не
Конъюнкция	∧	И	&,., and, и
Дизъюнкция	∨	ИЛИ	⎢, or, или
Импликация	→	ВЛЕЧЕТ	⇒, ⊃
Эквивалентность	⇔	ЭКВИВАЛЕНТНО	↔, ≈

Отрицанием высказывания p называется высказывание ¬p, которое истинно только тогда, когда p ложно. Пример. Высказывание «Неправда, что идёт снег» является отрицанием высказывания «идёт снег». Конъюнкцией высказываний p и q называется высказывание, которое истинно только тогда, когда p и q истинны., т.е. p = 1 и q = 1. Пример. Чтобы успешно сдать экзамен, нужно иметь высокую отметку за семестр и правильно ответить на вопросы. Для успешной сдачи экзамена нужно выполнить оба условия. Если обозначить как p – «высокая отметка за семестр» и q – «правильно ответить на вопросы», то условием сдачи будет конъюнкция высказываний p ∧ q. Дизъюнкцией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны, т. е. p= 0 и q =0. Пример. («7 больше 3» ∨ «4 равно 2») =1; («7 меньше 3» ∨ «4 равно 2») =0 Импликацией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда p истинно, q ложно, т.е. p = 1 и q = 0 (из p следует q). Импликацию можно пояснить примером с успешной сдачей экзамена:

p ∧ q → r, где r – «успешно сдать экзамен».

Эквиваленцией высказываний p и q называется высказывание, которое истинно только и только тогда, когда значения высказываний p и q совпадают (p эквивалентно q). Таким образом, значения истинности для связок представлены в табл.2.2. Таблица 9.2. Истинность связок

p	q	¬ p	p ∧ q	p ∨ q	p → q	p ⇔ q
0	0	1	0	0	1	1
0	1	1	0	0	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

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

Пример

Найти значение высказывания:

((¬p1∧ p2) → p3) ⇔ (¬p2 ∨ p3),

при p1 = 1, p2 = 0, p3 = 1

1.шаг ((¬p1∧ p2) равно 0

2. шаг (¬p2 ∨ p3) равно 1

3. шаг((¬p1∧ p2) → p3) равно 1

4. шаг ((¬p1∧ p2) → p3) ⇔ (¬p2 ∨ p3) равно 1

Вывод: Значение высказывания равно 1

Следует отметить, что на основании таблицы истинности 9.2 можно построить целый ряд тождеств, упрощающих процедуру вывода.

Исчисление предикатов Логика высказываний позволяет формализовать лишь малую часть множества рассуждений. Высказывания, описывающие некоторые свойства объектов, или отношения между объектами выходят за рамки логики высказываний.Например, мы не сможем судить о логической правильности такого простого рассуждения: «Каждое натуральное число является корнем некоторого квадратного уравнения. Число 5 –натуральное. Следовательно, 5 является корнем некоторого квадратного уравнения». Это неверное логическое заключение.Логика предикатов начинается с анализа строения высказываний, которые выражают тот факт, что объекты обладают некоторыми свойствами, или находятся между собой в некоторых отношениях. Понятие «свойства» и понятие «отношения» рассматриваются как частный случай общего понятия «предиката». Объекты, о которых говорится в высказывании, называются термами или предметными константами. Предметные константы, подобно константам в математике, определяют значения, которые могут быть приписаны в высказываниях предметным переменным. При этом каждой переменной соответствует свое множество предметных констант. Например, если речь идет о студенческой группе, то переменной ФАМИЛИЯ соответствует множество констант – конкретных фамилий студентов группы, переменой ОЦЕНКА – множество констант {3,4,5,6,7,8,9,10}, переменной ВУЗ – множество названий ВУЗов. Над переменными и константами определяются функции так же, как и в математике, т.е. как однозначное отображение декартово произведения X1×X2× …Xm ⇒Y, где Xi и Y – имена предметных переменных. Пример Функции F: X1×X2⇒Y, где X1 – вес товара, X2– его цена, а Y–стоимость, которая определяется как Y=X1⋅X2. Предикатом называется функция, аргументы которой принимают значения из некоторого множества, а сама функция – значение 0 («ложь») или 1 («истина»). Пример предиката: ФАМИЛИЯ = «Петров». Здесь ФАМИЛИЯ – переменная, «Петров» – константа. Предикаты, в которых описывается некоторое свойство объекта, называется предикат-свойство. Если предикат определяет отношение между несколькими объектами, то такой предикат называется предикат-отношение. В зависимости от того, между скольким числом объектов устанавливаются отношения, различают двуместные, трёхместные и n-местные отношенияПредикат называется n-местным (n= 1,2 …), если соответствующая функция есть функция от n-аргументов. Высказывание – не что иное, как предикат без аргумента, или предикат с нулевым числом мест.Так как предикаты принимают значения из {T, F}, то они являются высказываниями, и их можно объединять логическими связками, получая более сложные предикатные функции Если R(x) и E(x)– два одноместных предиката, определённых на некотором множестве M, то логические связки: Отрицание. P3(x) ≡ ¬R(x) – это предикат, который истинен для тех и только для тех объектов из M, для которых предикат R(x) ложен. Его область истинности является дополнением области истинности предиката R(x). Конъюнкция. P1(x) ≡ R(x) & E(x) – это предикат, который истинен для тех и только для тех объектов из M, для которых оба предиката истинны. Таким образом, область истинности предиката P1(x) равна пересечению областей истинности предикатов R(x) и E(x). Дизъюнкция. P2(x) ≡ R(x) ∨ E(x) – это предикат, который ложен для тех и только для тех объектов из M, для которых оба предиката ложны. Таким образом, область истинности предиката P2(x) равна объединению областей истинности предикатов R(x) и E(x). Пример Пусть x = a, y = b, z = c, где a,b,c∈M, P(a, b, c) ≡ R(a, b) & Q(b, c). Предикат P(a, b, c) =1, когда R(a, b) = 1 и Q(b, c)=1. Пример (ФАМИЛИЯ = «Петров»)& (ВУЗ = «БГЭУ»)&(1<КУРС>4). Это сложное высказывание будет «истина» для студента УГТУ 2-го или 3-го курсас фамилией Петров. Для всех остальных студентов значения предиката будет«ложь». Введение переменных и функций позволяет более подробно описывать предметную область, чем при описании через элементарные высказывания смысл которых нам был неважен. Но если там решение можно было найти перебором истинностных значений элементарных высказываний, то перебор по всевозможным значениям предметных переменных становится часто невозможным, поэтому требуются другие методы поиска решений. Предикатам могут быть приписаны кванторы. Естественный язык содержит огромное число кванторов.Выражения: «каждому», «для всех» и т.п. служат примером квантификации, которая состоит из квантора. Именно кванторы делают теорию предикатов гибкой и богатой. Кванторы: общности ∀ (читается как «для всех»); существования ∃ (читается как «существует»). Квантор общности обобщает операцию конъюнкции, квантор существования обобщает операцию дизъюнкции Пример ∀(x) P(x), x∈M. Если множество M состоит из конечного числа объектов M = {a1, a2, a3,…an}, то значение истинности предиката с квантором общности ∀(x) P(x) записывается в виде конъюнкции. P(a1) & P(a2) & P(a3) &…& P(an). Пример ∃(x) P(x), x∈M. Если множество M = {a1, a2, a3,…an}, то значение истинности предиката с квантором существования ∃(x) P(x) совпадает со значением дизъюнкции. P(a1) ∨ P(a2) ∨ P(a3) ∨…∨ P(an). С помощью кванторов создается предикатная модель базы знаний и делаются логические выводы.

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

К тому же, очень высокие требования к предметной области – полнота и непротиворечивость «базового аксиоматического набора» – обусловили то, что в промышленных экспертных системах формальные логические модели практически не используются.

Дата добавления: 2014-01-07