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

Размещено на http://www.allbest.ru/

Лекция Математический аппарат, используемый в задачах искусственного интеллекта

Введение

При создании СИИ используются главным образом три раздела математики: ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ, ПРЕДИКАТЫ и НЕЧЕТКИЕ МНОЖЕСТВА. С помощью исчисления высказываний и теории предикатов обычные предложения на русском языке можно записать в компактной математической форме. Теория нечетких множеств позволяет решать задачи, когда мы не можем провести точное решение.

1. Логика высказываний

В предыдущей главе показано, что рассуждения агента (поиск решений задачи) сводится к определению правил перехода в соответствии с выбранной стратегией. Каждый шаг состоит в проверке агентом истинности левой части правила (факта нахождения среды в состоянии b_i и допустимости действия с_j) и, в случае ее истинности, признании факта перехода из состояния b_i в состояние b_k в результате действия с_j. Естественно, нам хотелось бы иметь математический аппарат, на основе которого можно осуществлять постановку и поиск решения задачи формально, используя наилучшую стратегию поиска. Логика высказываний -- это первый шаг к созданию такого аппарата.

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

Исчисление высказываний (другие названия - алгебра логики, двоичная алгебра, алгебра Буля) рассматривает операции над переменными, которые могут принимать только два значения: 0 и 1.Алгебра логики позволяет формализовать (записывать в виде формул) логические рассуждения. В этих рассуждениях оперируют понятиями ИСТИНА и ЛОЖЬ. Понятие истина при этом обозначается 1, ложь -0.

Функции алгебры логики - двоичные функции удобно формировать и исследовать с помощью специальных таблиц - таблиц истинности, в которых перечисляются все возможные значения одного или нескольких переменных.

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

Первая и последняя функции являются константами, вторая - повторяет x, а вот третья, значения которой противоположны значениям х, широко

Таблица 2.1

используется в алгебре логики и называется ОТРИЦАНИЕМ х, или ИНВЕРСИЕЙ, или просто функцией НЕ х. Других, кроме перечисленных функций одной переменной в алгебре логики не существует.

Функций двух переменных имеется 16, некоторые, наиболее часто используемые, приведены в таблице истинности 2.2.

Первая из этих функций называется ЛОГИЧЕСКИМ СЛОЖЕНИЕМ или ДИЗЪЮНКЦИЕЙ или просто функцией ИЛИ. Часто её обозначают знаком +;

Вторая функция - ЛОГИЧЕСКОЕ УМНОЖЕНИЕ или КОНЪЮНКЦИЯ или функция И. Её часто обозначают знаком умножения - точкой;

Третья, четвертая и пятая функции называются, соответственно ИМПЛИКАЦИЕЙ, СЛОЖЕНИЕМ ПО МОДУЛЮ 2 и ЭКВИВАЛЕНТНОСТЬЮ.

Таблица 2.2

Импликация обращается в нуль, только если значение второго элемента меньше значения первого.

Функция эквивалентности равна 1 при совпадении значений обоих аргументов, а функция сложения по модулю 2 при их несовпадении.

Существуют логические функции трех, четырех и т.д. аргументов. Например,

Y=(x₁x₂) ((( x₂x₁)₃)~₃)

Первое выражение можно прочесть так: если x₁ или x₂ или x₃ истинно (равно 1), то и y истинно (равно1).

Интерпретация второго выражения: если истинны x₁ и x_2, или истинно x₃, то y истинно.

Третье выражение можно прочесть так: Y истинно, если при одновременном несовпадении x ₃ ( отрицание x₃) c логическим произведением: x₁ не совпадает с x₂ на не x_3.

1.1 Синтаксис логики высказываний

Синтаксис логики высказываний прост и имеет прямые синтаксические и семантические аналоги в естественных языках, что чрезвычайно облегчает нам понимание логики высказываний. Символами языка логики высказываний, составляющими ее алфавит, являются логические константы ИСТИНА и ЛОЖЬ, сокращенно обозначаемые буквами И и Л, логические переменные х, у, z, обозначаемые строчными буквами латинского алфавита, логические связки (И), (ИЛИ), (НЕ), ЭКВИВАЛЕНТНО, => (ВЛЕЧЕТ) и круглые скобки. Значениями логических переменных являются логические константы. Предложения языка логики высказываний, называемые также формулами или высказываниями, составляют в соответствии со следующими правилами:

логические константы являются простыми предложениями;

логические переменные также простые предложения;

сложные предложения формируются из простых с помощью связок (И), (ИЛИ), (НЕ), (ЭКВИВАЛЕНТНО), => (ВЛЕЧЕТ);

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

из предложений с помощью связок и скобок можно образовать новые предложения языка логики высказываний;

связки имеют следующий порядок старшинства т.е. связка самая старшая, а связка самая младшая.

Формулы логики высказываний, составленные по этим правилам, называют правильно построенными формулами или сокращенно формулами.

1.2 Семантика логики высказываний

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

Пример1: Студент, который не ходит на занятия и не занимается дома, не сдаст экзамен.

Обозначим через x₁ событие: ходить на занятия; через x₂ событие - заниматься дома, сдать экзамен - x₃ и y- сдать экзамен. Тогда формальная запись на языке алгебры логике будет иметь вид:

.

Пример2. Если истинно утверждение, что Иван и Мария являются родителями и Юры и Анны, то Юра и Анна являются братом и сестрой.

Обозначим: x₁ - Иван, x₂ -Мария, x₃ -Юра, x₄ - Анна, y₁ - родители Юры, y ₂ -родители Анны, y- Юра и Анна- брат и сестра.

То же самое можно описать словами:

Иначе говоря, интерпретация определяет семантику формул (предложений, высказываний) путем сопоставления переменных в формулах со свойствами объектов среды, а отношений между этими свойствами -- с формулами. Это позволяет по значению формул после подстановки вместо переменных конкретных значений свойств судить о наличии или отсутствии у среды тех или иных совокупных свойств или отношений. Если дана какая-либо формула, то подстановка в формулу констант вместо ее переменных называется конкретизацией. Таким образом конкретизация является результатом интерпретации.

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

Истинностные значения любой формулы, т.е. ее семантику, всегда можно задать таблицей, состоящей из двух частей: в левой части таблицы перечислены все наборы значений аргументов, а в правой соответствующие наборам значения формулы. Задание таких таблиц для связок облегчается тем, что значениями аргументов и формул являются только две величины -- И или Л. Такие таблицы в логике высказываний называют таблицами истинности.

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

С помощью алгебры логики можно записывать любое правило и предложение для СИИ..

1.3 Общезначимые формулы и их роль

Формулы, истинные на всех наборах значений своих аргументов, называют общезначимыми формулами. Если какая-либо формула является общезначимой, то этот факт обычно записывается с использованием знака общезначимости = который ставится перед формулой: |=. Проверку формулы на общезначимость можно осуществить с помощью таблицы истинности: если формула истинна во всех строках таблицы истинности, то эта формула общезначима. Рассмотрим, например, формулу . Из табл. ясно, что формула является общезначимой, т.к. значения переменных в последнем столбце всегда истинно.

Ранее было заявлено, что истинность высказывания _{1 2} всегда означает, что истинность ₁ влечет истинность ₂ (здесь ₁ и ₂ являются формулами логики высказываний). Потому, установив факт общезначимости формулы _{1 2} и истинности ₁ , всегда можно сделать заключение об истинности ₂. Таким образом, общезначимость формул вида _{1 2}, называемых импликативными формулами, является важным свойством для получения заключения об истинности ₂ , называемого заключением, при истинности ₁, называемого посылкой. Для простоты импликативные формулы _{1 2} будем называть так же, как и связку , импликацией. В логике высказываний известно много общезначимых формул, называемых обычно законами логики высказываний. Наиболее известными являются следующие законы:

коммутативные

x ₁ x ₂ = x ₂ x ₁, x ₁ x ₂ =x ₂ x ₁ ;

дистрибутивные

x ₁ (x ₂ x ₃) = (x ₁ x ₂) (x₁ x₃),

x₁ (x ₂ x₃) = (x₁ x ₂) (x ₁ x ₃);

ассоциативные

x₁ (x₂ x ₃) = (x₁ x ₂) x₃,

x₁ (x₂ x ₃) = (x₁ x ₂) x ₃;

законы Де Моргана:

=,=,

закон двойного отрицания:

.

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

, . , ,

Сложные формулы, как правило, можно упростить. Для этого можно использовать следующие эквивалентности:

- правила поглощения,

- правило склеивания,

. - Правило вычеркивания.

Их доказательства осуществляются путем построения соответствующих таблиц истинности.

Рассмотрим пример упрощения логической функции. Пусть

Последовательное применение приведенных выше правил дает:

= =

=()=()=1.

Кроме общезначимых, существуют формулы выполнимые и невыполнимые. Формула называется выполнимой, если существуют наборы значений ее аргументов, на которых она принимает истинное значение, и наборы значений, на которых она принимает ложное значение.

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

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

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

2. Нечеткие множества

Записывая и решая задачу на языке исчисления высказываний или предикатов, мы получаем ответ в виде «да» или «нет»,(истина или ложь, 0 или 1). Однако во многих задачах мы не уверены в исходных данных, мы знаем их приближенно и поэтому удовлетворимся приближенным ответом.

Для математического решения таких задач используется нечеткая логика, предложенная американским математиком Л. Заде в начале 60-х годов.

Обычная логика, в которой есть два логических значения ИСТИНА и ЛОЖЬ, связана с таким же четким разделением объектов на два множества. Например, логическое условие

ПРИЗЫВНИК = ((ПОЛ = МУЖСКОЙ) (ВОЗРАСТ>ПРИЗЫВНОЙ))

подразумевает разделение людей по признаку пола МУЖСКОЙ/ЖЕНСКИЙ и по возрасту ВОЗРАСТ>ПРИЗЫВНОЙ/ ВОЗРАСТ<ПРИЗЫВНОЙ. Логическая операция конъюнкции описывает ПРИЗЫВНИКА как пересечение множеств:

Рис. 2.1 Операция пересечения множеств

Вместе с тем во многих случаях приходится иметь дело с не столь определенными понятиями. Например, выражение МОЛОДОЙ ЧЕЛОВЕК не указывает точно ни на какой возраст. Правда, можно отметить, что возраст 10 лет под понятие МОЛОДОГО ЧЕЛОВЕКА. по-видимому, не подпадает, точно так же, как и возраст 50 лет. Однако точно указать диапазон возраста МОЛОДОГО ЧЕЛОВЕКА в виде условия

МОЛОДОЙ ЧЕЛОВЕК= ((ВОЗРАСТ>МИНИМАЛЬНЫЙ) И (ВОЗРАСТ<МАКСИМАЛЬНЫЙ)) невозможно - множество возрастов, подпадающих под понятие МОЛОДОГО ЧЕЛОВЕКА, является нечетким.

Если считать, что принадлежность объекта множеству описывается функцией принадлежности, принимающей значения от 0 до 1, то разница между обычными (четкими) и нечеткими множествами состоит в следующем. Для четкого множества функция принадлежности принимает значения только 0 и 1.

Например, функция принадлежности к призывному возрасту P(y) имеет вид (рис.2.2). В случае же нечеткого множества функция принадлежности принимает и промежуточные значения. Например, функция принадлежности к множеству МОЛОДОЙ ЧЕЛОВЕК может иметь вид( рис.2.3)

Рис. 2.2 Функция принадлежности четкого множества

Рис. 2.3 Функция принадлежности нечеткого множества

и в таком случае описывается формулами:

при y < 15 P(y) = 0;

при 15 < y < 20 P(y) = (y - 15)/5;

при 20 < y < 25 P(y) = 1;

при 25 < y < 30 P(y) = (30 - y)/5;

при y > 30 P(y) = 0.

Иными словами, при возрасте менее 15 и старше 30 лет человек молодым заведомо не является, а в промежутке от 20 до 25 лет - заведомо является. В промежутке от 15 до 20 лет статус МОЛОДОГО ЧЕЛОВЕКА плавно возрастает, принимая значения от 0 до 1, а в промежутке от 25 до 30 лет - убывает от 1 до 0.

Для того, чтобы описать нечеткое множество МОЛОДОЙ ЧЕЛОВЕК, следует указать все его элементы с указанием степени принадлежности элемента множеству. Это делается с помощью записи

МЧ=0.2/16+0.4/17+0.6/18+0.8/19+1/20+1/21+1/22+1/23+1/24+1/25+0.8/26+0.6/27+0.4/28+0.2/29

В тех случаях, когда это не может привести к путанице, можно использовать обычное обозначение коэффициентов, принятое в алгебре. Например, если множество Z состоит из элементов a, b, c, d, e с функцией принадлежности

Z = 0.1/a+0.5/b+0.9/c+0.7/d+0.5/e

это может быть также записано во форме

Z = 0.1a+0.5b+0.9c+0.7d+0.5e

2.1 Операции с нечеткими множествами

К нечетким множествам, как и к четким, применимы операции объединения, пересечения и дополнения. Если считать, что в универсальном множестве U выделены два нечетких множества A и B с функциями принадлежности f и g, то их объединение имеет функцию принадлежности h

переменная множество функция нечеткий

h(u) = max (f(u), g(u))

Например, если

U = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

A = 0.8/0+0.7/1+0.6/2+0.4/3+0.2/4+0.1/5+0.1/6+0.1/7

B = 0.1/3+0.3/5+0.5/7+0.7/8+0.9/9

то A B имеет вид

A B = 0.8/0+0.7/1+0.6/2+0.4/3+0.2/4+0.3/5+0.1/6+0.5/7+0.7/8+0.9/9

Аналогично, функция принадлежности для пересечения нечетких множеств A и B имеет вид min (f(u), g(u)). В том же примере

A B = 0.1/3+0.1/5+0.1/7

Дополнение множества имеет функцию принадлежности, вычисляемую как дополнение до 1 функции принадлежности исходного множества. Так, дополнение множества A имеет функцию принадлежности

A = 0.2/0+0.3/1+0.4/2+0.6/3+0.8/4+0.9/5+0.9/6+0.9/7+1/8+1/9

(Легко заметить, что если множества являются четкими, т.е. функция принадлежности принимает только значения 0 и 1, то построенные указанным образом функции принадлежности описывают обычные операции объединения, пересечения и дополнения множеств.)

НЕЧЕТКАЯ ЛОГИКА

В отличие от обычной логики, где существуют только два значения истинности утверждения ИСТИНА и ЛОЖЬ, в нечеткой логике "значение истинности" утверждения может принимать и промежуточные значения. Считается, что ИСТИНА имеет значение 1, ЛОЖЬ - 0, и истинность любого утверждения u, обозначаемая (u), находится в промежутке между этими значениями.

В нечеткой логике существуют те же логические операции конъюнкции, дизъюнкции и отрицания, однако они определяются иначе, чем в обычной логике. Если истинность логических операций конъюнкции, дизъюнкции и отрицания в обычной логике задается таблицами истинности, то в нечеткой логике она задается формулами. Если истинность утверждения u равна (u), а v - (v), то истинность конъюнкции, дизъюнкции и отрицания выражается формулами

(u v) = min ((u), (v)), (u v) = max ((u), (v))

(u) = 1 - (u)

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

(u v) = (v u), (u v) = (v u)

((u v) w) = (u (v w)), ((u v) w) = (u (v w))

((u)) = (u), ((u v)) = (u v)

((u v)) = (u v), ((u v) w) = ((u w) (v w))

((u v) w) = ((u w) (v w)), (0 u) = (u)

(1 u) = 1, (0 u) = 0, (1 u) = (u)

(Однако аналогия не является полной - например, аналоги формул u u = 0 и u u = 1 в нечеткой логике неверны.)

Используемые в логическом выводе формулы импликации вида A B также могут быть нечеткими, т.е. их уровень истинности может быть меньше 1. В этом случае уровень истинности заключения вычисляется как произведение уровня истинности посылки на уровень истинности импликации. Например, если (A) = 0.9, а (A B) = 0.8, то (B) = 0.72.

Размещено на Allbest.ru