586 слайдов лекций, страница 2
Описание файла
PDF-файл из архива "586 слайдов лекций", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
"Êàê æå íàçûâàåòñÿ ýòà êíèãà?"Ó Ïîðöèè (ãåðîèíè êîìåäèè "Âåíåöèàíñêèé êóïåö") áûëî òðèøêàòóëêè: èç çîëîòà, ñåðåáðà è ñâèíöà.  îäíîé èç øêàòóëîêõðàíèëñÿ ïîðòðåò Ïîðöèè. Ïîêëîííèêó ïðåäëàãàëîñü âûáðàòüøêàòóëêó, è åñëè îí áûë äîñòàòî÷íî óìåí, ÷òîáû âûáðàòüøêàòóëêó ñ ïîðòðåòîì, òî ïîëó÷àë ïðàâî íàçâàòü Ïîðöèþíåâåñòîé. Íà êðûøêàõ øêàòóëîê áûëè íàäïèñè:Íà çîëîòîéÏîðòðåò â ýòîéøêàòóëêåÍà ñåðåáðÿíîéÏîðòðåò íå â ýòîéøêàòóëêåÍà ñâèíöîâîéÏîðòðåò íå â çîëîòîéøêàòóëêåÑâîåìó ïîêëîííèêó Ïîðöèÿ ïîÿñíèëà, ÷òî èç òðåõâûñêàçûâàíèé íà êðûøêàõ øêàòóëîê, ïî êðàéíåé ìåðå äâàëîæíû.Êàêóþ øêàòóëêó ñëåäóåò âûáðàòü ïîêëîííèêó Ïîðöèè?Çàãàäêà Àëüáåðòà Ýéíøòåéíà 5 ðàçíîöâåòíûõ äîìàõ æèâóò ãðàæäàíå 5 ðàçíûõ ñòðàí,êîòîðûå êóðÿò 5 ðàçíûõ ñîðòîâ ñèãàðåò, ïüþò 5 ðàçíûõíàïèòêîâ è ñîäåðæàò 5 ðàçíûõ æèâîòíûõ. Èçâåñòíî, ÷òî1. Ó ïîëÿêà êðàñíûé äîì.
2. Íåìåö êóðèò Rothmans.3. Êóðèëüùèê Marlboro æèâåò ðÿäîì ñ òåì, êòî äåðæèò êîøêó.4. Ôèíí ïüåò ÷àé. 5. Êóðèëüùèê Camel äåðæèò ïîïóãàÿ.6. Çåëåíûé äîì ñòîèò ñëåâà îò áåëîãî.7. Êóðèëüùèê Kent ïüåò ïèâî. 8. Ãðåê æèâåò â ïåðâîì äîìå.9. Âëàäåëåö ëîøàäè æèâåò ðÿäîì ñ òåì, êòî êóðèò Dunhill.10. Õîçÿèí ñðåäíåãî äîìà ïüåò ìîëîêî.11.
Õîçÿèí æåëòîãî äîìà êóðèò Dunhill.12. Õîçÿèí çåëåíîãî äîìà ïüåò êîôå.13. Øâåä äåðæèò ñîáàêó. 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 , . . . , 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 , . . .