Лекции 2-11. Математическая логика (до колка) (1161869), страница 3
Текст из файла (страница 3)
ЛОГИЧЕСКОЕ СЛЕДСТВИЕПример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)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация 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]I |= (P(x) → R(x))[d]ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀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]I |= (P(x) → R(x))[d]I |= P(x)[d]ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀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]I |= (P(x) → R(x))[d]I |= P(x)[d]I |= R(x)[d]Получили противоречие. Значит, контрмодели I не существует.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀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]I |= (P(x) → R(x))[d]I |= P(x)[d]I |= R(x)[d]Получили противоречие. Значит, контрмодели I не существует.Значит, |= ϕ.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∃x (P(x) → ∀x P(x)) .ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∃x (P(x) → ∀x P(x)) .Предположим, что ϕ необщезначима. Тогда существуетинтерпретация I (контрмодель), которая опровергает ϕ.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∃x (P(x) → ∀x P(x)) .Предположим, что ϕ необщезначима. Тогда существуетинтерпретация I (контрмодель), которая опровергает ϕ.I 6|= ∃x (P(x) → ∀x P(x))ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∃x (P(x) → ∀x P(x)) .Предположим, что ϕ необщезначима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
