Лекции 2-11. Математическая логика (до колка) (Лекции 2014), страница 2
Описание файла
Файл "Лекции 2-11. Математическая логика (до колка)" внутри архива находится в папке "Лекции 2014". PDF-файл из архива "Лекции 2014", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. , tk [d1 , d2 , . . . , dn ]).СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛОтношение выполнимости формулЗначение формул в интерпретации определяется при помощиотношения выполнимости |=.Пусть заданы интерпретация I = hDI , Const, Func, Predi,формула ϕ(x1 , x2 , . . . , xn ) и набор d1 , d2 , . . .
, dn элементов(предметов) из области интерпретации DI .Отношение выполнимости I |= ϕ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]формулы ϕ в интерпретации I на наборе d1 , d2 , . . . , dnопределяется рекурсивно.IЕсли ϕ(x1 , x2 , . . . , xn ) = P(t1 , . . . , tm ), тоI |= ϕ(x1 , x2 , . . .
, xn )[d1 , d2 , . . . , dn ]⇐⇒P̄(t1 [d1 , d2 , . . . , dn ], . . . , tm [d1 , d2 , . . . , dn ]) = true;СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛОтношение выполнимости формулIЕсли ϕ(x1 , x2 , . . . , xn ) = ψ1 &ψ2 , тоII |= ϕ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]⇐⇒I |= ψ1 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]I |= ψ2 (x1 , x2 , . . . , xn )[d1 , d2 , .
. . , dn ]Если ϕ(x1 , x2 , . . . , xn ) = ψ1 ∨ ψ2 , тоI |= ϕ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]⇐⇒I |= ψ1 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]илиI |= ψ2 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛОтношение выполнимости формулIЕсли ϕ(x1 , x2 , . . . , xn ) = ψ1 → ψ2 , тоI |= ϕ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]⇐⇒I 6|= ψ1 (x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]илиI |= ψ2 (x1 , x2 , . . .
, xn )[d1 , d2 , . . . , dn ]IЕсли ϕ(x1 , x2 , . . . , xn ) = ¬ψ, тоI |= ϕ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]⇐⇒I 6|= ψ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛОтношение выполнимости формулIЕсли ϕ(x1 , x2 , . . . , xn ) = ∀x0 ψ(x0 , x1 , x2 , . . .
, xn ), тоI |= ϕ(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ]⇐⇒для любого элемента d0 , d0 ∈ DI , имеет местоI |= ψ(x0 , x1 , x2 , . . . , xn )[d0 , d1 , d2 , . . . , dn ]IЕсли ϕ(x1 , x2 , . . . , xn ) = ∃x0 ψ(x0 , x1 , x2 , . . . , xn ), тоI |= ϕ(x1 , x2 , . .
. , xn )[d1 , d2 , . . . , dn ]⇐⇒для некоторого элемента d0 , d0 ∈ DI , имеет местоI |= ψ(x0 , x1 , x2 , . . . , xn )[d0 , d1 , d2 , . . . , dn ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛИнтерпретацияI = hDI , Const, Func, PrediОбласть интерпретацииОценка константDI = {d1 , d2 , d3 };c1 = d1 , c2 = d3 ;Оценка функциональных и предикатныхf(x)P(x)R(x, y )yxfxPd1xd1 d2d1 trued1 trued2 d3d2 falsed2 trued3 d1d3 trued3 falseсимволовd2truefalsetrued3falsetruetrueФормулаϕ = ∀x1 (P(x1 ) → ∃x2 (R(x1 , x2 ) & ¬P(f (x2 ))))СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3I |= R(x1 , x2 )[d1 , d1 ]PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3I |= R(x1 , x2 )[d1 , d1 ]I 6|= P(f (x2 ))[d1 ]PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falseI |= R(x1 , x2 )[d1 , d1 ]I 6|= P(f (x2 ))[d1 ] ⇒ I |= ¬P(f (x2 ))[d1 ]d2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falseI |= R(x1 , x2 )[d1 , d1 ]I 6|= P(f (x2 ))[d1 ] ⇒ I |= ¬P(f (x2 ))[d1 ]I |= R(x1 , x2 ) & ¬P(f (x2 ))[d1 , d1 ]d2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falseI |= R(x1 , x2 )[d1 , d1 ]I 6|= P(f (x2 ))[d1 ] ⇒ I |= ¬P(f (x2 ))[d1 ]I |= R(x1 , x2 ) & ¬P(f (x2 ))[d1 , d1 ]I |= ∃x2 (R(x1 , x2 ) & ¬P(f (x2 )))[d1 ]d2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= R(x1 , x2 )[d1 , d1 ]I 6|= P(f (x2 ))[d1 ] ⇒ I |= ¬P(f (x2 ))[d1 ]I |= R(x1 , x2 ) & ¬P(f (x2 ))[d1 , d1 ]I |= ∃x2 (R(x1 , x2 ) & ¬P(f (x2 )))[d1 ]I |= P(x1) → ∃x2(R(x1, x2)&¬P(f (x2)))[d1]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3I 6|= P(x1 )[d2 ]PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI 6|= P(x1 )[d2 ]I |= P(x1) → ∃x2(R(x1, x2)&¬P(f (x2)))[d2]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3I |= P(x1 )[d3 ]PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]R(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueСЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ] ⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]I 6|= ¬P(f (x2 ))[d2 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]I 6|= ¬P(f (x2 ))[d2 ] ⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d2 ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]I 6|= ¬P(f (x2 ))[d2 ]I 6|= ¬P(f (x2 ))[d3 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d2 ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]I 6|= ¬P(f (x2 ))[d2 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d2 ]I 6|= ¬P(f (x2 ))[d3 ] ⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d3 ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]I 6|= ¬P(f (x2 ))[d2 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d2 ]I 6|= ¬P(f (x2 ))[d3 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d3 ]I 6|= ∃x2 (R(x1 , x2 ) & ¬P(f (x2 )))[d3 ]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛf(x)xd1d2d3fd2d3d1P(x)xd1d2d3PtruefalsetrueR(x, y )yd1xd1 trued2 trued3 falsed2truefalsetrued3falsetruetrueI |= P(x1 )[d3 ]I 6|= R(x1 , x2 )[d3 , d1 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d1 ]I 6|= ¬P(f (x2 ))[d2 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d2 ]I 6|= ¬P(f (x2 ))[d3 ]⇒ I 6|= R(x1 , x2 ) & ¬P(f (x2 ))[d3 , d3 ]I 6|= ∃x2 (R(x1 , x2 ) & ¬P(f (x2 )))[d3 ]I 6|= P(x1) → ∃x2(R(x1, x2)&¬P(f (x2)))[d3]СЕМАНТИКА: ВЫПОЛНИМОСТЬ ФОРМУЛИтак, мы имеемI |= (P(x1 ) → ∃x2 (R(x1 , x2 ) & ¬P(f (x2 ))))[d1 ]I |= (P(x1 ) → ∃x2 (R(x1 , x2 ) & ¬P(f (x2 ))))[d2 ]I 6|= (P(x1 ) → ∃x2 (R(x1 , x2 ) & ¬P(f (x2 ))))[d3 ]Значит,I 6|= ∀x1 (P(x1) → ∃x2(R(x1, x2) & ¬P(f (x2))))КОНЕЦ ЛЕКЦИИ 2.Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А.
ЗахаровЛекция 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)}.ЗамечаниеА какая интерпретация является моделью пустого множестваформул Γ = ∅?Правильный ответ: любая интерпретация . Почему ?МОДЕЛИ.
