8120

Логическое следование. Логический вывод. Метод резолюций в логике предикатов первого порядка

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-02-04

73.5 KB

78 чел.

Логическое следование. Логический вывод. Метод резолюций в логике предикатов первого порядка.

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

Рассмотрим классический пример формализации утверждений естественного языка в логике первого порядка. Возьмем рассуждение: "Каждый человек смертен. Конфуций – человек. Следовательно, Конфуций смертен". Обозначим:

"x есть человек" – через ЧЕЛОВЕК(x),

"x смертен" – через СМЕРТЕН(x). 

Тогда утверждение "каждый человек смертен" может быть представлено формулой:

()(ЧЕЛОВЕК(x) → СМЕРТЕН(x)).

А утверждение "Конфуций – человек" – формулой:

ЧЕЛОВЕК(Конфуций),

и "Конфуций смертен" – формулой:

СМЕРТЕН(Конфуций).

Утверждение в целом теперь может быть записано формулой:

()(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) & ЧЕЛОВЕК(Конфуций) → СМЕРТЕН(Конфуций).

Понятие логического следования

Пусть E – множество формул (логики первого порядка), а C – отдельная формула.

Формула C называется логическим следствием из множества формул E, если она истинна при всех интерпретациях, при которых все формулы множества E одновременно истинны.

Формальная запись:

E  C 

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

Принцип дедукции

Множество формул называется невыполнимым, если не существует интерпретации, при которой все формулы этого множества одновременно истинны:

 E  C  – невыполнимо.

Таким образом, принцип дедукции сводит задачу о логическом следовании к задаче о невыполнимости множества формул.

Для доказательства невыполнимости множества формул используется метод резолюции.

Метод резолюции

Если X и Y – дизъюнкты, то формула  называется резольвентой.

Правило резолюции: пусть x, y – произвольные формулы, а A – атом (элементарная формула), тогда:

╞ – правило резолюции.

 , , тогда

Предположим, что , тогда . Таким образом .

Рассмотрим случай, когда x и y – дизъюнкты (дизъюнкция атомов).

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

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

Единственным невыполнимым дизъюнктом является пустой дизъюнкт, то есть дизъюнкт, не содержащий ни одной литеры. Такие дизъюнкты будем обозначать в дальнейшем константой F (от False).

Алгоритм по преобразованию формул в КНФ (на примере логики высказываний)

1).  Исключение связок, импликаций и эквивалентностей:

2).  Сокращение области действия отрицаний так, чтобы они относились к элементарным формулам:

3).  Закон дистрибутивности:

 Утверждение 1: пусть E – множество формул,  – формулы этого множества, а {Y,X}Z  логическое следствие. Тогда добавление формулы Z к множеству E не меняет его выполнимости/невыполнимости.

 Утверждение 2: добавление резольвент к исходному множеству не меняет его выполнимости/невыполнимости.

Для построения резольвенты находим дизъюнкты, содержащие контрарную пару (пара, имеющая противоположные значения) и строим резольвенту.

Пример 1:

 – родительские дизъюнкты,

– их резольвента.

Пример 2: рассмотрим 2 однолитеральных дизъюнкта  и , их резольвента – пустой дизъюнкт F.

Таким образом, алгоритм метода резолюции предполагает последовательное порождение резольвент от различных пар родительских дизъюнктов до тех пор, пока не будет получен пустой дизъюнкт. Это означает, что множество невыполнимо и тем самым логическое следствие доказано.

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

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

Общие достоинства логики первого порядка

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

1.  Полнота.

2.  Непротиворечивость.

3.  Компактность.


 

А также другие работы, которые могут Вас заинтересовать

46152. Технология производства земляных и бетонных работ 964 KB
  Тип грунта супесь с примесью щебня 30. Земляным сооружением называется инженерное сооружение устраиваемое из грунта в грунтовом массиве или возводимое на поверхности земли. При строительстве ведется переработка грунта с целью подготовки основания под здания устройства дорог. К основным процессам переработки грунта можно отнести: разработку перемещение и укладку его.
46153. Основы организации работы по ведению бухгалтерского учета в кредитных организациях 200.79 KB
  Введение В процессе становления рыночной экономики когда банки действуют в условиях жесткой конкуренции и нестабильной экономической ситуации бухгалтерский учет не сводится только к отражению операций банка. Основная роль его состоит в использовании бухгалтерской информации для планирования активных и пассивных операций банка. Бухгалтерский учет в банке дает возможность ответа на вопросы о состоянии и движении имущества банка денежных средств кредитов фондов о расходах и доходах финансовых результатах деятельности банка.
46154. Создание поверхности для защиты от коррозии внутренних и внешних поверхностей труб тепловых и водопроводных систем 5.53 MB
  Сбор нагрузок на колонны. Колонны предназначены для поддержания железобетонного перекрытия.396 Этажи От перекрытия и покрытия Собственный вес колонны Расчетная суммарная нагрузка Длительная Кратковременная NДЛ NКР NПОЛН 4 1 1171 1223 Расчет нагрузки колонны Подсчет расчетной нагрузки на колонну. Расчет колонны первого этажа N=3504кН; ℓ 01=2.
46155. Оценка эффективности предпринимательской деятельности ОАО «Газпром» 208 KB
  Анализ эффективности деятельности предприятия ОАО Газпром 8 2. Для повышения деловой и инвестиционной активности предприятия все более актуальна необходимость более эффективного управления ими на основе комплексной достаточно полной и объективной системы оценок их финансовохозяйственной деятельности в сложной экономической обстановке рыночных изменений в условиях динамичной внешней среды. Анализ финансовохозяйственной деятельности служит базой для принятия управленческих решений переоценить его значение для эффективного функционирования...
46156. СИСТЕМНО-СТРУКТУРНЫЕ ПОДХОДЫ К МОДЕЛИРОВАНИЮ СИСТЕМ УПРАВЛЕНИЯ 159 KB
  Суть системного подхода можно определить так: это методология научного познания и практической деятельности а также объяснительный принцип в основе которых лежит рассмотрение объекта как системы. Иерархичность познания требующая многоуровневого изучения предмета: изучение самого предмета собственный уровень; изучение этого же предмета как элемента более широкой системы вышестоящий уровень; изучение этого предмета в соотношении с составляющими данный предмет элементами нижестоящий уровень. Можно также сказать что системный...
46157. ОСНОВЫ ТРАНСПОРТНО-ЭКСПЕДИЦИОННОГО ОБСЛУЖИВАНИЯ 1.13 MB
  Сироткин ОСНОВЫ ТРАНСПОРТНОЭКСПЕДИЦИОННОГО ОБСЛУЖИВАНИЯ КУРСОВОЕ ПРОЕКТИРОВАНИЕ Учебнометодическое пособие Нижний Новгород 2010 ФЕДЕРАЛЬНОЕ АГЕНАСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО Волжский государственный инженернопедагогический университет А. Сироткин...
46158. Социология. Общий курс. Учебное пособие 2.78 MB
  социология: общий курс. тощенко получило признание во многих вузах россии так как наука социология в нем трактуется как социология жизни.5я73 тощенко жан терентьевич социология общий курс генеральный директор в. социология как наука.
46159. Web-браузер 16.01 KB
  Среди множества разнообразных программ просмотра гипертекстовых документов наибольшее распространение получили Microsoft Internet Explorer далее Explorer и Netscpe Nvigtor далее Netscpe. Ни та ни другая компания ничего не зарабатывает на распространении своих браузеров Explorer╗бесплатная программа а Netscpe условнобесплатная программа. Далее мы будем ориентироваться на браузер Netscpe. Методы работы с браузером Explorer практически не отличаются от методов работы с Netscpe что позволит приверженцам данного программного продукта...
46160. АДМИНИСТРАТИВНОЕ ПРАВО РОССИИ 797 KB
  Формы и методы государственного управления. Формы государственного управления. Методы государственного управления Правовые акты государственного управления Административно-правовое регулирование в сферах и отраслях управления.