LectLog3 (Старые лекции, в целом тоже самое)

Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 3.Выполнимые и общезначимыеформулы.Модели. Логическое следование.Проблема общезначимости.Семантические таблицы.ВЫПОЛНИМЫЕ И ОБЩЕЗНАЧИМЫЕФОРМУЛЫФормула ϕ(x1 , . . . , xn ) называется выполнимой в интерпретацииI , если существует такой набор элементов d1 , . .

. , dn ∈ DI , длякоторого имеет место I |= ϕ(x1 , . . . , xn )[d1 , . . . , dn ].Формула ϕ(x1 , . . . , xn ) называется истинной в интерпретации I ,если для любого набора элементов d1 , . . . , dn ∈ DI имеет местоI |= ϕ(x1 , . . . , xn )[d1 , . . . , dn ].Формула ϕ(x1 , . . . , xn ) называется выполнимой , если естьинтерпретация I , в которой эта формула выполнима.Формула ϕ(x1 , . . .

, xn ) называется общезначимой (илитождественно истинной ), если эта формула истинна в любойинтерпретации.Формула ϕ(x1 , . . . , xn ) называется противоречивой (илиневыполнимой ), если она не является выполнимой.ВЫПОЛНИМЫЕ И ОБЩЕЗНАЧИМЫЕФОРМУЛЫПримерыP(x1 )&¬P(x2 ),∀xP(x) → ∃xP(x),∃xP(x) → ∀xP(x)— выполнимые формулы.I1 : DI = {d1 , d2 }, P̄(d1 ) = true, P̄(d2 ) = falseI1 |= P(x1 )&¬P(x2 )[d1 , d2 ],I1 |= ∀xP(x) → ∃xP(x).I2 : DI = {d}, P̄(d) = trueI2 |= ∃xP(x) → ∀xP(x)Формулы P(x1 )&¬P(x2 ), ∃xP(x) → ∀xP(x) необщезначимые.I2 6|= P(x1 )&¬P(x2 )[d, d],I1 6|= ∃xP(x) → ∀xP(x).Формула ∀xP(x) → ∃xP(x) является общезначимой.Но почему? И как в этом убедиться?ВЫПОЛНИМЫЕ И ОБЩЕЗНАЧИМЫЕФОРМУЛЫВыполнимые формулы — это логические формы, которыеслужат для представления знаний. Каждая выполнимаяформула несет определенную информацию.Общезначимые формулы — это трюизмы, банальности,тавтологии, не несущие никакой информации.Какую же роль играют общезначимые формулы?МОДЕЛИ.

ЛОГИЧЕСКОЕ СЛЕДСТВИЕПусть Γ — некоторое множество замкнутых формул, Γ ⊆ CForm.Тогда каждая интерпретация I , в которой выполняются всеформулы множества Γ, называется моделью для множества Γ.Модель для множества формул Γ — это интерпретация(реальный или виртуальный мир), устройство которогоадекватно всем предложениям из множества Γ.ПримерI : DI = {d1 , d2 }, P̄(d1 ) = true, P̄(d2 ) = falseI — модель для множества формул Γ = {∃xP(x), ∃x¬P(x)}.ЗамечаниеА какая интерпретация является моделью пустого множестваформул Γ = ∅?Правильный ответ: любая интерпретация . Почему ?МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕПримерC (x) — «x — квадрат»;S(x) — «x — шар»;B(x) — «x — черный предмет»;W (x) — «x — белый предмет»;U(x, y ) — «предмет x лежит под предметом y ».МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКаждый белый куб лежит под каким-то черным шаром.∀x (W (x) & C (x) → ∃y (B(y ) & S(y ) & U(x, y )))~~~Модель I∀x (W (x) & C (x) & ∃y (B(y ) & S(y ) & U(x, y )))Каждый предмет является белым кубоми лежит под каким-то черным шаром.МОДЕЛИ.

ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель IМОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель I∃x (W (x) & C (x) → ∀y (B(y ) & S(y ) → U(x, y )))МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель I∃x (W (x) & C (x) → ∀y (B(y ) & S(y ) → U(x, y )))Какой-то предмет либо не является белым кубом,либо лежит под каждым черным шаром.МОДЕЛИ.

ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель J∃x (W (x) & C (x) → ∀y (B(y ) & S(y ) → U(x, y )))Какой-то предмет либо не является белым кубом,либо лежит под каждым черным шаром.МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕОбщий принцип правильного построения формул.Каждый предмет, наделенный атрибутом A, обладаетсвойством B:∀x (A(x) → B(x))Некоторый предмет, наделенный атрибутом A, обладаетсвойством B:∃x (A(x) & B(x))МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕОпределениеПусть Γ — некоторое множество замкнутых формул, и ϕ —замкнутая формула.

Формула ϕ называется логическимследствием множества предложений (базы знаний) Γ, есликаждая модель для множества формул Γ является модельюдля формулы ϕ, т. е.для любой интерпретации I : I |= Γ =⇒ I |= ϕЛогические следствия — это «производные» знания, которыенеизбежно сопутствуют «базовым» знаниям Γ, находятся впричинно-следственной зависимости от предложений Γ. Однаиз главных задач (и одновременно наиболее характерноепроявление) интеллектуальной деятельности — это извлечениелогических следствий из баз знаний.МОДЕЛИ.

ЛОГИЧЕСКОЕ СЛЕДСТВИЕОбозначенияЗапись Γ |= ϕ обозначает, что ϕ — логическое следствие Γ .А какие формулы являются логическими следствиями пустойбазы знаний Γ = ∅? Правильный ответ: общезначимые .Поэтому для обозначения общезначимости формулы ϕ будемиспользовать запись|= ϕ .МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕТеорема о логическом следствииПусть Γ = {ψ1 , . . . , ψn } ⊆ CForm, ϕ ∈ CForm. ТогдаΓ |= ϕ ⇐⇒ |= ψ1 & . .

. &ψn → ϕ.Доказательство. ⇒ Пусть I — произвольная интерпретация.Если I 6|= ψ1 & . . . &ψn , то I |= ψ1 & . . . &ψn → ϕ.Если I |= ψ1 & . . . &ψn , то I |= ψi , 1 ≤ i ≤ n, т. е. I — модельдля Γ.Поскольку Γ |= ϕ, получаем I |= ϕ. Значит,I |= ψ1 & . . . &ψn → ϕ.Таким образом, для любой интерпретации I имеет местоI |= ψ1 & . . .

&ψn → ϕ.Значит, ψ1 & . . . &ψn → ϕ — общезначимая формула.МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕТеорема о логическом следствииПусть Γ = {ψ1 , . . . , ψn } ⊆ CForm, ϕ ∈ CForm. ТогдаΓ |= ϕ ⇐⇒ |= ψ1 & . . . &ψn → ϕ.Доказательство. ⇐ Пусть I — модель для множествапредложений Γ, т. е. I |= ψi , 1 ≤ i ≤ n.Тогда I |= ψ1 & . . .

&ψn .Так как |= ψ1 & . . . &ψn → ϕ, верно I |= ψ1 & . . . &ψn → ϕ.Значит, I |= ϕ.Так как I — произвольная модель для Γ, приходим кзаключению Γ |= ϕ.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛОбщезначимые формулы — это каналы причинно-следственнойсвязи, по которым передаются знания, представленные в виделогических формул, преобразуясь при этом из одной формы вдругую.Практически важно уметь определять эти каналы инастраивать их на извлечение нужных знаний.IБаза знаний — множество предложений Γ;IЗапрос к базе знаний — предложение ϕ;IПолучение ответа на запрос — проверка логическогоследствия Γ |= ϕ.Если Γ — конечное множество, то проверка логическогоследствия сводится к проверке общезначимости формулыψ1 & . .

. &ψn → ϕПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛТаким образом, возникает проблемаобщезначимости формул:Для заданной формулы ϕпроверить ее общезначимость:|= ϕ?ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛУтверждение.Для любой формулы ϕ(x1 , . . . , xn ) верно, что1. |= ϕ(x1 , . . . , xn )⇐⇒|= ∀x1 . . . ∀xn ϕ(x1 , . .

. , xn );2.ϕ(x1 , . . . , xn ) — выполнимая⇐⇒∃x1 . . . ∃xn ϕ(x1 , . . . , xn ) — выполнимая;3.ϕ(x1 , . . . , xn ) — выполнима в любой интерпретации⇐⇒|= ∃x1 . . . ∃xn ϕ(x1 , . . . , xn ).ДоказательствоСамостоятельно. Это просто.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛКак же решать проблемуобщезначимости|= ϕ ?Может быть проверять всеинтерпретации по очереди ?ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛНет, такой подход заведомо обречен на неудачу. Почему?Потому, что верноУтверждение.Существует такая замкнутая формула ϕ, которая истиннав любой интерпретации I с конечной предметнойобластью DI , но не является общезначимой .∀x¬R(x, x) &∀x∀y ∀z(R(x, y )&R(y , z) → R(x, z)) →∃x∀y ¬R(x, y ).ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛДоказательство.R(x, y ): «субъект y — начальник субъекта x»;1).

∀x¬R(x, x): «никто не командует самим собой»;2). ∀x∀y ∀z (R(x, y )&R(y , z) → R(x, z)): «начальник моегоначальника — мой начальник»;3). ∃x∀y ¬R(x, y ): «кто-то никому не подчиняется».В каждой компании с конечным множеством сотрудников, вкоторой действуют законы 1) и 2), выполняется и закон 3).Значит, наша формула истинна во всех интерпретациях сконечной предметной областью.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛДоказательство.Но наша формула не является общезначимой.R(x, y ): «натуральное число y больше натурального числа x»1).

∀x¬R(x, x);2). ∀x∀y ∀z (R(x, y )&R(y , z) → R(x, z));выполняются на множестве натуральных чисел.3). ∃x∀y ¬R(x, y ) на множестве натуральных чисел невыполняется: неверно, что существует максимальноенатуральное число.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛНе только перебор всех интерпретаций, но даже проверкуистинности формулы в интерпретации с бесконечнойпредметной областью осуществить затруднительно.Значит, необходимо придумать более изощренный способпроверки.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима.

Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.I 6|= ϕПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ.

Изучим эту контрмодель.I 6|= ϕI |= ∀x (P(x) → R(x)) I 6|= ∀x P(x) → ∀x R(x)ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.I 6|= ϕI |= ∀x (P(x) → R(x)) I 6|= ∀x P(x) → ∀x R(x)I |= ∀x P(x)I 6|= ∀x R(x)ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.I 6|= ϕI |= ∀x (P(x) → R(x)) I 6|= ∀x P(x) → ∀x R(x)I |= ∀x P(x)I 6|= ∀x R(x)I 6|= R(x)[d]ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима.