8120

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

Лекция

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

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

Русский

2013-02-04

73.5 KB

77 чел.

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

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

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

"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.  Компактность.


 

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

78077. Разработка методики проектирования и изготовления малошовной плетеной одежды с триаксиальной структурой, иммитирующей ткань «Шанель» 4.56 MB
  Главная задача швейной промышленности - удовлетворение потребности людей в одежде высокого качества и разнообразного ассортимента. При проектировании одежды должны использоваться последние достижения науки, техники, прикладного искусства, выбраны рациональные композиционные и конструктивные решения.
78078. Разработка АИС «Кинотеатр» в среде C++Builder 6 1.32 MB
  Вследствие огромной популярности и прогрессивности киноиндустрии возникает потребность в качественном обслуживании посетителей кинотеатров. АИС «Кинотеатр» предназначена для упрощения организации работы оператора кинотеатра.
78079. Аналіз рівеня конкурентоспроможності АТ«Металіст» та шляхи щодо її підвищення 423 KB
  Загострення конкурентної боротьби за збут своєї продукції за місце на ринку поміж фірмамивиробниками змушує шукати їх нові засоби впливу на рішення покупців. Передовий закордонний досвід свідчить що якість безперечно є найбільш вагомою складовою конкуренотоспроможності...
78080. БЛОК КЕРУВАННЯ ГАЗОВОГО КОТЛА НА МК 1.32 MB
  У житлових приміщеннях комфорт визначається температурою, вологістю, швидкістю руху повітря, тепловою характеристикою конструкції будинку, температурою внутрішніх поверхонь кімнати і якістю кімнатного повітря, у робочих приміщеннях до цих параметрів додаються шум, вібрації тощо.
78081. Социально-экономические последствия ресурсно-экологических опасностей современного российского хозяйствования 874 KB
  Экономическое развитие человечества связано с ускоряющимся ростом потребления природных ресурсов планеты в результате которого происходит истощение запасов сырья и ухудшение состояния окружающей среды как следствие интенсивного природопользования и его экологического воздействия.
78082. Особенности выявления эффективности функционирования российской экономики в условиях стабильного осуществления рыночных отношений 593 KB
  Проблема измерения эффективности (результативности) экономики до сих пор остается не до конца изученной. В советской экономике существовал единый народный хозяйственный комплекс (единое предприятие), где можно было измерить эффективность.
78083. СОЦИАЛЬНО-ЭКОНОМИЧЕСКИЕ ПОСЛЕДСТВИЯ РЕФОРМИРОВАНИЯ СИСТЕМЫ РОССИЙСКОГО ВЫСШЕГО ОБРАЗОВАНИЯ 372.5 KB
  В связи с этим особую актуальность приобретают вопросы реформирования современной высшей школы России. Реформирование ВПО России должно отвечать требованиям перспективного экономического роста в стране и учитывать особенности трансформационного периода.
78084. Исследование системы организации ипотечного кредитования и определение основных направлений ее совершенствования в практике российских банков 287 KB
  Российский ипотечный рынок остается крайне привлекательным сегментом для российских банков. Почти 70% участников ипотечного рынка видят ипотечное кредитование в качестве одного из приоритетных направлений своего развития.
78085. НЕДЕЙСТВИТЕЛЬНОСТЬ БРАКА 265.5 KB
  За последние годы резко увеличилось число проституток и наркоманов. Их заболеваемость намного превосходит заболеваемость обычного среднестатистического человека. В связи с этим большое число российских граждан приобрели аналогичные заболевания (ранее неизвестные или малораспространённые).