8120

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

Лекция

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

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

Русский

2013-02-04

73.5 KB

75 чел.

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

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

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

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


 

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

73912. Економічна думка в Україні в пореформений період 19 століття. М. Бунге, Д. Піхно, С. Вітте, І. Сокальський 22 KB
  Бунге Д. Бунге професор згодом ректор Київського університету у 80ті рр. Бунге вказував на велике значення для розвитку політичної економії правильного визначення її предмета і вважав що складність такого визначення пояснюється позицією ліберальної економічної школи та соціалістів. Бунге критикував соціалістів за те що вони засуджували існуючий порядок і вбачали свій ідеал у новій організації праці у вигаданих формах суспільного устрою3.
73913. Створення К. Марксом і Ф. Енгельсом пролетарської політекономії : початок формування економічного вчення марксизму. Структура та основні проблеми “Капіталу” Пізні наукові праці 42 KB
  Структура та основні проблеми Капіталу Пізні наукові праці . Теоретичні проблеми Капіталу К. Кілька рукописних варіантів Капіталу 1857 1865 Критика політичної економії До критики політичної економії другий та третій попередні варіанти Капіталу у вигляді нарисів та закінчених теоретичних викладок давно були готові до друку однак Маркс намагався надати цьому твору характеру вичерпної логічно закінченої теорії. Однак вихід у світ одночасно всіх томів Капіталу не пощастило забезпечити: праця тривала надалі а...
73914. Маржинальна революція: австрійська школа “граничної корисності” (К. Менгер, Ф. Візер, О. Бьом-Баверек). Принципи економікс А. Маршалла 36.5 KB
  Маржинальна революція : австрійська школа граничної корисност К. Її теоретичними принципами були субєктивний ідеалізм та теорія граничної корисності. Центральне місце в концепціях австрійської школи посідає так звана теорія граничної корисності.Візер розвивав ідеї Менгера у працях Походження й основні закони господарської цінності 1884 Природна цінність 1889 Закон влади 1926 використовуючи принцип граничної корисності для оцінки вартості витрат виробництва.
73915. Релігія та демократія: конгруенція і конфлікт 35 KB
  За Андерсоном демократія може варіюватися проте в своїй основі вона повинна мати такі складові як рівність влада народу участь всіх конкуренція згода і в випадках ліберальної демократії захист прав меншинств та окремих індивідів. Якщо не пояснювати йдеться про політичну економічну соціальну рівність чи рівність можливостей то дана характеристика не може бути надійним покажчиком демократії. Щодо інших індикаторів демократії то вони також на мою думку є досить суперечливими проте за браком місця не будемо їх розглядати. Скажемо...
73916. Економічна глобалізація 54.5 KB
  Ініціали інституціоналізацію про формування системи глобального регулювання яка буде наділеною відповідним обсягом повноважень та легітимністю. Другий шлях – глобальне співробітництво за якого розв‘язання глобальних проблем буде виконуватися не шляхом нав‘язування окремими акторами підходів а шляхом конструктивного і втілюваного в життя діалогу всіх зацікавлених сил. Далі буде логічно виведено розмірковування і про інші проекти. Але зрозуміло що таким чином будуть зачіплятися інтереси якоїсь із національних держав світу адже така...
73917. Феномен глобалізації та процеси глобальних політичних змін: основні концепції та методологічні підходи 44 KB
  Блінова частина якої до якої і пишеться коментар має назву Феномен глобалізації та процеси глобальних політичних змін: основні концепції та методологічні підходи. Фактично прочитавши більшість джерел до семінару №2 у мене склалися деякі погляди на розглядувані речі звісно пов‘язані із процесом глобалізації чи то антиглобалізації які вмістити до якогось конкретного джерела виявилося дуже складним. З одного боку наявність численної кількості визначень може йти на користь вивченню глобалізації адже ця численність є прямим фактом...
73918. Кінець світу, який ми знаємо 98 KB
  Вотерса Кінець світу який ми знаємо. Від цього залежить і мислення людей яке радше ґрунтуватиметься на припущенні гетерогенності світу сильної несхожості усіх його частин а не на припущенні про одну світову сім‘ю. Останнє матиме вплив і на дії людей в усіх кінцях світу які ряснітимуть розмаїтістю. Країни обиралися за таким критеріями: Британія – як дуже впливовий член ЄС і як одна з передових країн світу; Україна – порівняння світової ситуації із справа в нашому суспільстві; США – одна з провідних і найвпливовіших країн світу; Індія –...
73920. Підприємець – не обов’язково лідер 196.5 KB
  Вже минуло більш як два з половиною століття з тих часів, як економісти та соціологи почали систематично розглядати діяльність підприємців, але й досі не існує єдиного загальноприйнятого визначення підприємця. Тож чи дивно, що науковці не накреслили і загальноприйнятого образу підприємця.