Системы искусственного интеллекта

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПОДГОТОВКИ ИНЖЕНЕРНЫХ КАДРОВ

КАФЕДРА «СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ И ПОИСКОВОГО КОНСТРУИРОВАНИЯ» 
 
 
 
 
 
 
 
 
 
 
 

Семестровая работа 

По курсу: Системы искусственного интеллекта 
 
 
 
 
 

Выполнил:

Студент группы АУЗ-361С

Шифр:608491

Лимаренко Э.А.

«7»          января                2011 г.

Проверил:

Доцент  Декатов Д.Е.

«____»________________2011 г. 
 
 
 
 
 
 
 
 
 
 
 
 
 

Волгоград 2011 г.

 

1. Определение исчисления высказываний, как формальный системы.

     1.1. Синтаксис исчислении высказываний

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

     Синтаксис исчисления высказываний составляют:

1. Словарь (пропозициональный  логический словарь)    бесконечное  счетное множество высказываний, которые обозначаются строчными  буквами, а также сим волы  логических операций - -| (отрицание), конъюнкция (∩), дизъюнкция (v), импликация (--->, Э или ->), эквивалентность (<=>, +=, <->, или ~).    2. Правила построения синтаксически правильных выражений: а) всякое высказывание есть формула; б) всякая комбинация конечного числа высказываний, связанных знаками логических операций, есть формула.

1.2. Семантика исчисления высказываний

Семантическая область исчисления высказываний состоит  из двух элементов -{Т. F}, или (истина, ложь), или (1,0). Интерпретировать формулу - значит приписать ей одно из двух значений истинности. Семантика логических операций определяется по таблицам истинности (табл. 5, 6).

Таблица 5

Таблица истинности дли операции отрицания 

Таблица 6

Таблица истинности для логических операций

     1.3. Классы формул исчисления высказываний

Формула семантически выполнима (выполнима), если се можно  интерпретировать со значением Т. Например, ( р л ц) - выполнима, т.к. принимает значение Т, если р и ч принимают значение Т. 
 

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

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

Формула, содержащая К высказываний, допускает 2'' интерпретаций. Сам простой способ определения  класса формулы - метод полного перебора, основный на проверке истинности формулы на всех 2К интерпретациях. Это можно сделать, используя таблицы истинности. Однако существуют другие, более эффективные методы, позволяющие избежать полного перебора. 

     1.4. Понятие семитическою дерева

Если Р={Р1...Pn} - множество высказываний, то семантическое дерево - это бинарное дерево, удовлетворяющее следующим условиям:

1)каждая дуга  помечена негативной или позитивной литерой из множества P

2) литеры, которыми  помечены две дуги, выходящие из одного узла, должны быть противоположны;

3) никакая ветвь  (путь) на дереве не содержит более одного вхождения каждой литеры;

4) никакая ветвь  не содержит пары противоположных  литер. Например, для множества  литер Р={р, q} семантическое дерево  имеет вид:   
 

     Каждому узлу N семантического дерева соответствует  функция 1,„ которая сопоставляет истинностное значение некоторым элементам  из множества Р и называется частичной  интерпретацией. Частичная интерпретация 1„ сопоставляет значение Т или F высказыванию р, если некоторая дуга из корня N помечена р или (-j р). Частичная  интерпретация не определена для  высказывания р, если р и (т р) не встречается  на пути из корня в N.

     Семантическое дерево полное, если каждый его лист соответствует некоторой всюду  определенной интерпретации. Для того чтобы определить, выполнима ли формула  А, с помощью алгоритма полного  перебора требуется просмотреть  полное семантическое дерево, соответствующее  высказываниям, встречающимся в  формуле А. формула выполнима, если хотя бы для одного листа А получается значение Т. Этот алгоритм не эффективен, т. к. требуется просматривать 2" интерпретаций. 

     1.5. Алгоритм Куайна

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

Пример. Проверить общезначимость формулы (((p∩q)=>r) ∩ (р=>q))=>(p=>r).

1. Упорядочим  множества элементов высказываний: {p. q, г}. Это эквивалентно тому, что  дуги уровня 1 помечены литерой  р, уровня 2 - литерой q, а уровня 3 - литерой r.

2. Рассмотрим  те интерпретации, при которых  р есть Т. При этом исходная  формула сводится к формуле  ((q^r) ∩q) =>г.

3. Далее q интерпретируем  как Т, тогда формула принимает  вид г от общезначимая формула.

4. Далее q интерпретируем  как F, тогда формула принимает вид F=>f - тоже общезначимая формула, поэтому дальше строить поддерево не нужно.

5. Далее, рассмотрим  те интерпретации, при которых  р принимает значение F, тогда исходная формула имеет вид (F=>t) ∩Т) =>Т - общезначимая формула. Следовательно, исходная формула всегда принимает значение Т, т.е. является общезначимой. 
 
 
 
 
 
 
 

Этому примеру  соответствует построение части  семантического дерева, по. занной на рисунке. 

 

1.6. Алгоритм редукции

Алгоритм редукции позволяет доказать общезначимость форму.1 с помощью приведения их к противоречию. Рассмотрим работу алгоритма на примере.

Пример. Проверить  общезначимость формулы 

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

Аналогично для  следующего шага

В результате получаем следующий набор интерпретаций: Проверяем вторую часть формулы (заключение) на лом наборе иитернрета получаем - Противоречие. Таким образом, исходное предположение о Т что существует интерпретация, на которой формула принимает значение F, б ложным, а формула является общезначимой.

5.7. Алгебраический  подход к определению класса  форму, i

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

Для формул исчисления высказываний справедливы следующие  законы пре разования:

1. Законы дистрибутивности 

 

2. Закон исключения третьего

3. Законы де  Моргана 

4. Преобразование  импликации

5. Двойное отрицание

 

1.7.1. Нормальные формы и алгоритм нормализации 

Каждая логическая формула может изучаться алгебраически  путем Приведения ее к нормальной форме. Возможно приведение к двум нормальным формам конъюнктивной нормальной форме (КНФ) и .титъюнкгиннон нормальной форме (ДНФ)

Конъюнктивная нормальная форма - это конъюнкция конечного  числа дизъюнкций, т. е. формула вида дизъюнкты.

Дизъюнктивная нормальная форма - это дизъюнкция конечного  числа КОНЪЮНКЦИЙ, т. е. формула вида , - конъюнкты.

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

А.и ори гм нормализации 
 
 
 

1. Исключение  операций равносильности и импликации:

2. Продвижение  знака НЕ до высказываний (по законам де Моргана) и погашения двойных отрицаний.

3. Применение  законов дистрибутивности, в результате - получение КНФ или ДНФ.

5) Удаление общезначимых  дизъюнктов (дизъюнктов, содержащих  pV !р) и повторяющихся литер, в результате - получение приведенной нормальной формы (КНФ или ДНФ). После приведения к нормальной форме можно решить вопрос общезначимости. Дизъюнкт общезначим тогда и только тогда, когда он содержит пару противоположных литер. КНФ общезначима тогда и только тогда, когда все се дизъюнкты – общезначимы.

Таким образом, проблема общезначимости  КНФ сводится к проверке оощечимости каждого дизъюнкта, более интересна проблема выполнимости.

1.7.2. Алгоритм Куайна для ДНФ

Алгоритм Куайна для ДНФ позволяет провершь выполнимость и общезн месть приведенной дизъюнктивной  нормальной формы.