Системы искусственного интеллекта. Учебно-практическое пособие [В. Ю. Яньков] (doc) читать постранично, страница - 8

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

Последовательное применение приведенных выше правил дает:
= =
=()=()=1.
Кроме общезначимых, существуют формулы выполнимые и невыполнимые. Формула называется выполнимой, если существуют наборы значений ее аргументов, на которых она принимает истинное значение, и наборы значений, на которых она принимает ложное значение.
Если формула на всех наборах значений ее аргументов принимает ложное значение, то она называется невыполнимой.
Установление истинности следствия по общезначимой импликативной формуле достаточно универсальный способ для вывода заключений, но требует проверки общезначимости последней. Если формула 1  2 не является общезначимой, то подобного заключения делать нельзя.
Проверку общезначимости можно осуществить с помощью таблицы истинности. Однако построение таблиц истинности слишком трудоемко для того, чтобы можно было решать реальные задачи. Вместо этого используют специальные правила вывода, применение которых базируется не на понятии общезначимости формулы, в частности общезначимости импликативной формулы, а на понятии модели формулы.
2.2. Нечеткие множества
Записывая и решая задачу на языке исчисления высказываний или предикатов, мы получаем ответ в виде «да» или «нет»,(истина или ложь, 0 или 1). Однако во многих задачах мы не уверены в исходных данных, мы знаем их приближенно и поэтому удовлетворимся приближенным ответом.
Для математического решения таких задач используется нечеткая логика, предложенная американским математиком Л. Заде в начале 60-х годов.
Обычная логика, в которой есть два логических значения ИСТИНА и ЛОЖЬ, связана с таким же четким разделением объектов на два множества. Например, логическое условие
ПРИЗЫВНИК = ((ПОЛ = МУЖСКОЙ)  (ВОЗРАСТ>ПРИЗЫВНОЙ))
подразумевает разделение людей по признаку пола МУЖСКОЙ/ЖЕНСКИЙ и по возрасту ВОЗРАСТ>ПРИЗЫВНОЙ/ ВОЗРАСТМИНИМАЛЬНЫЙ) И (ВОЗРАСТ< МАКСИМАЛЬНЫЙ)) невозможно – множество возрастов, подпадающих под понятие МОЛОДОГО ЧЕЛОВЕКА, является нечетким.
Если считать, что принадлежность объекта множеству описывается функцией принадлежности, принимающей значения от 0 до 1, то разница между обычными (четкими) и нечеткими множествами состоит в следующем. Для четкого множества функция принадлежности принимает значения только 0 и 1.
Например, функция принадлежности к призывному возрасту P(y) имеет вид (рис.2.2). В случае же нечеткого множества функция принадлежности принимает и промежуточные значения. Например, функция принадлежности к множеству МОЛОДОЙ ЧЕЛОВЕК может иметь вид (рис.2.3).









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






Рис.2.3. Функция принадлежности нечеткого множества
и в таком случае описывается формулами:
при y=0 , вычисляемая для вершины b и характеризующая близость этой вершины к целевой. При использовании критерия близости к цели, начиная с корневой вершины, просматриваются все соседние ей вершины, выбирается та, для которой h(b) минимальна, и все повторяется вновь для выбранной вершины.
И так до тех пор, пока не будет достигнута целевая вершина, для которой h(b)=0, т.е. выбирается та вершина, которая ближе всего находится к цели. Вид критерия близости к цели зависит от среды (является проблемно зависимым). Чтобы получить достаточно полное представление об этом критерии, вернемся к задаче поиска маршрута из Иванова в Москву. Критерием выбора в этом случае будет минимальное расстояние по прямой (кратчайшее расстояние) от вершины (населенного пункта) до Москвы. Естественно, чтобы значение критерия могло быть вычислено, необходимо иметь карту или какой-либо другой источник информации, содержащий сведения о кратчайших расстояниях от населенных пунктов до Москвы. На рис. 4.5 показана последовательность поиска по критерию близости к цели для примера с поиском маршрута из Иванова в Москву, использованного при рассмотрении монотонного поиска в ширину.





























Рис. 4.5. Поиск по критерию близости к цели
На первом шаге вычисляется кратчайшее расстояние от корневой вершины (Иваново) до Москвы (h=230). На втором шаге просматриваются все вершины (города), в которые ведет дорога из Иванова и вычисляется кратчайшее расстояние h от этих городов до Москвы. По этому критерию ближайшим по прямой до цели (Москвы) оказывается Юрьев-Польский (h=140). На третьем шаге просматриваются все вершины, в которые ведет дорога из Юрьева- Польского.
Для них снова вычисляется кратчайшее расстояние h до Москвы, кратчайшим оказывается расстояние от Киржача (h=76). Наконец, на последнем шаге вновь просматриваются все вершины, в которые ведет дорога из Киржача, а также вычисляется кратчайшее