Лекции В.А. Захарова, страница 2

Øâåä äåðæèò ñîáàêó. 14. Ãðåê æèâåò îêîëî ãîëóáîãî äîìà.15. Êóðèëüùèê Marlboro æèâåò ðÿäîì ñ òåì, êòî ïüåò âîäó.Êîìó ïðèíàäëåæèò çîëîòàÿ ðûáêà?ÊÎÍÅÖ ËÅÊÖÈÈ 1.Основыматематическойлогики и логическогопрограммированияЛЕКТОР:Владимир Анатольевич Захаровzakh@cs.msu.suhttp://mathcyb.cs.msu.su/courses/logprog.htmlЛекция 2.Классическая логика предикатовпервого порядкаСинтаксис. Термы и формулы.Семантика. Интерпретация.Выполнимость формул.ПРЕДИКАТлатинский термин («предвидеть,предсказывать»), обозначающийчлен предложения — сказуемое.CтудентCубъектслушаетПредикатлектораОбъектВ более общем смысле предикат — этосвойство, атрибут предмета, отношениемежду предметами, событиями,явлениями.АЛФАВИТБазовые символы.Предметные переменныеVar = {x1 , x2 , .

. . , xk , . . . };Предметные константыConst = {c1 , c2 , . . . , cl , . . . };Функциональные символыFunc = {f1Предикатные символыPred = {P1(n1 )(n2 ), f2(m1 )(m2 ), P2(nr ), . . . , fr, . . . };(ms ), . . . , PsТройка hConst, Pred, Funci называется сигнатурой алфавита., . .

. }.АЛФАВИТБазовые символы.Предметные константы— это имена предметов;Функциональные символыобозначают операциинад предметами;Предикатные символыобозначают отношениямежду предметами.Пример.Константы0, 1, π, . . . ;Функциональные символы+, ×,Предикатные символы=, <, . . . .mod , . . . ;АЛФАВИТЛогические связки и кванторы.КонъюнкцияДизъюнкцияОтрицаниеИмпликация(логическое(логическое(логическое(логическоеКвантор всеобщностиКвантор существованияЗнаки препинания.РазделительСкобки,()И)ИЛИ)НЕ)ЕСЛИ-ТО)&∨¬→.(«для каждого»)(«хотя бы один»)∀∃СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫОпределение терма.Терм — этоxcf (n) (t1 , t2 , .

. . , tn ), если x ∈ Var, если c ∈ Const, если f (n) ∈ Funct1 , t2 , . . . , tn — термыx — переменная;c — константа;составной терм.Term — множество термов заданного алфавита.Vart — множество переменных, входящих в состав терма t.t(x1 , x2 , . . . , xn ) — запись обозначающая терм t, у которогоVart ⊆ {x1 , x2 , . . . , xn }.Если Vart = ∅, то терм t называется основным термом.СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫПримеры термов.x2т. к. x2 ∈ Var ;c1т. к.

c1 ∈ Const;f (2) (x2 , c)т. к. f (2) ∈ Func, x2 , c ∈ Term;×(x, +(1, exp(2, y )))т. к. ×, +, exp ∈ Func,1, 2 ∈ Const, x, y ∈ Var ;x × (1 + 2y )инфиксная форма записи термов;f (c1 , g (h(c1 ), c2 ))основной терм.СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫОпределение формулы.Формула — этоатомарная формулаP (m) (t1 , t2 , . . . , tm )составная формула(ϕ&ψ)(ϕ ∨ ψ)(ϕ → ψ)(¬ϕ)(∀xϕ)(∃xϕ), если P (m) ∈ Pred, {t1 , t2 , . .

. , tm } ⊆ Term;, если ϕ, ψ — формулы;, если x ∈ Var , ϕ — формула.Form — множество всех формул заданного алфавита.СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫP (m) (t1 , t2 , . . . , tm )«значения термов t1 , t2 , . . . , tmнаходятся в отношении P (m) »;(ϕ&ψ)«ϕ и ψ»;(ϕ ∨ ψ)«ϕ или ψ»;(ϕ → ψ)«если ϕ, то ψ»;(¬ϕ)«неверно, что ϕ»;(∀xϕ)«для любого значения x верно ϕ»;(∃xϕ)«существует такое значение x,для которого верно ϕ».СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫПримеры формул.P (2) (x1 , f (c, x2 ))т. к. P (2) ∈ Pred,x1 , f (c, x2 ) ∈ Term;R (1) (x1 )т. к.

R (1) ∈ Pred,x1 ∈ Term;(¬R (1) (x1 ))((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 )))(∃x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))))СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))) )СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))) )Область действия квантора ∃СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))) )6переменная, связанная квантором ∃Область действия квантора ∃СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))) )6связанные вхожденияпеременной x26переменная, связанная квантором ∃Область действия квантора ∃СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀ x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))))Область действия квантора ∀СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀ x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))))6переменная, связанная квантором ∀Область действия квантора ∀СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀ x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))))66связанные вхожденияпеременной x1переменная, связанная квантором ∀Область действия квантора ∀СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀ x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))))6свободные вхожденияпеременной x1Область действия квантора ∀СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.(∃ x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))) )66666свободные вхожденияпеременной x1связанные вхожденияпеременной x1связанные вхождения переменной x2СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.Квантор связывает ту переменную, которая следует за ним.Вхождение переменной в области действия квантора,связывающего эту переменную, называется связанным .Вхождение переменной в формулу, не являющееся связанным,называется свободным .Переменная называется свободной , если она имеет свободноевхождение в формулу.Пример .ϕ = (∃ x2 ((∀x1 (¬R (1) (x1 ))) → P (2) (x1 , f (c, x2 ))) )Формула ϕ имеет единственную свободную переменную x1 .СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫСвободные и связанные переменные.Varϕ — множество свободных переменных формулы ϕ.mSVarti ;ϕ = P (m) (t1 , t2 , .

. . , tm ) Varϕ =i=1ϕ = (ψ1 &ψ2 )ϕ = (ψ1 ∨ ψ2 )ϕ = (ψ1 → ψ2 )Varϕ = Varψ1 ∪ Varψ2 ;ϕ = (¬ψ)Varϕ = Varψ ;ϕ = (∀xψ)ϕ = (∃xψ)Varϕ = Varψ \ {x}.СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫϕ(x1 , x2 , . . . , xn ) — запись, обозначающая формулу ϕ, у которойVarϕ ⊆ {x1 , x2 , .

. . , xn }.Если Varϕ = ∅, то формула ϕ называетсязамкнутой формулой , или предложением .CForm — множество всех замкнутых формул.Соглашение о приоритете логических операцийВ порядке убывания приоритета связки и кванторырасполагаются так:¬, ∀, ∃&∨→СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫПример правильного восстановления скобок∀x1 ¬P(x1 ) & ∃x2 R(x1 , x2 ) → ∃x1 (¬P(x1 ) ∨ P(x2 ))(∀x1 (¬P(x1 ))) & (∃x2 R(x1 , x2 )) → (∃x1 ((¬P(x1 )) ∨ P(x2 )))((∀x1 (¬P(x1 ))) & (∃x2 R(x1 , x2 ))) → (∃x1 ((¬P(x1 )) ∨ P(x2 )))(((∀x1 (¬P(x1 ))) & (∃x2 R(x1 , x2 ))) → (∃x1 ((¬P(x1 )) ∨ P(x2 ))))СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫПример формулы, выражающей математическоеопределениеАлфавитКонстанты0 — константа, действительное число ноль;Функциональные символыh(2) (x, y ) — «абсолютная разность чисел x и y »;Предикатные символыR (1) (x) — «x — действительное число»;N (1) (x) — «x — натуральное число»;S (1) (x) — «x — последовательность действительных чисел»;E (3) (x, y , z) — «x — это y -ый член последовательности z»;<(2) (x, y ) — «число x меньше числа y ».СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫПример формулы, выражающей математическоеопределениеФормула limit(x, y )limit(x, y ) — «число x — предел последовательностидействительных чисел y ».limit(x, y ):R(x) & S(y ) & ∀z(R(z) & < (0, z) →∃u(N(u) & ∀v (N(v ) & < (u, v ) →∃w (E (w , v , y ) & < (h(w , x), z)))))СЕМАНТИКА: ИНТЕРПРЕТАЦИИСемантика — это свод правил, наделяющих значением(смыслом) синтаксические конструкции языка.В языке логики предикатов значением термов являютсяфункции, а значением формул — отношения (предикаты).Значения термов и формул определяются на основеалгебраических систем .Алгебраические системы, используемые в таком качестве,называются интерпретациями .СЕМАНТИКА: ИНТЕРПРЕТАЦИИИнтерпретация сигнатуры hConst, Func, Predi — этоалгебраическая система I = hDI , Const, Func, Predi, гдеIIIIDI — непустое множество, которое называется областьюинтерпретации , предметной областью , или универсумом ;Const : Const → DI — оценка констант ,сопоставляющая каждой константе c элемент (предмет) c̄из области интерпретации;Func : Func (n) → (DIn → DI ) — оценкафункциональных символов , сопоставляющая каждомуфункциональному символу f (n) местности n всюдуопределенную n-местную функцию f̄ (n) на областиинтерпретации;Pred : Pred (m) → (DIm → {true, false}) — оценкапредикатных символов , сопоставляющая каждомупредикатному символу P (m) местности m всюдуопределенное m-местное отношение P̄(m) на областиинтерпретации.СЕМАНТИКА: ИНТЕРПРЕТАЦИИПримерСигнатура Const = {c1 , c2 }, Func = {f (1) }, Pred = {P (1) , R (2) }.Интерпретация I = hDI , Const, Func, Predi:Область интерпретацииОценка константDI = {d1 , d2 , d3 };c1 = d1 , c2 = d3 ;Оценка функциональных и предикатных символовf(x)P(x)R(x, y )xfxPd1d2d3d1 d2d1 trued1 true true falsed2 d3d2 falsed2 true false trued3 d1d3 trued3 false true trueСЕМАНТИКА: ИНТЕРПРЕТАЦИИЗначение термаПусть заданы интерпретация I = hDI , Const, Func, Predi, термt(x1 , x2 , .

. . , xn ) и набор d1 , d2 , . . . , dn элементов (предметов) изобласти интерпретации DI .Значение t(x1 , x2 , . . . , xn )[d1 , d2 , . . . , dn ] терма t(x1 , x2 , . . . , xn )на наборе d1 , d2 , . . . , dn определяется рекурсивно.IЕсли t(x1 , x2 , . . . , 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 , . .