2. Классическая логика предикатов первого порядка. Синтаксис. Термы и формулы.Семантика. Интерпретация. Выполнимость формул (В.А. Захаров - Лекции), страница 2
Описание файла
Файл "2. Классическая логика предикатов первого порядка. Синтаксис. Термы и формулы.Семантика. Интерпретация. Выполнимость формул" внутри архива находится в папке "В.А. Захаров - Лекции". PDF-файл из архива "В.А. Захаров - Лекции", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. , xn ) = xi , тоt(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] = di ;IЕсли t(x1 , x2 , . . . , xn ) = c, тоt(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] = c̄;IЕсли t(x1 , x2 , . . . , xn ) = f (t1 , . . . , tk ), тоt(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] =f̄(t1 [d1 , d2 , . . . , dn ], . . . , 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..