Сводка определений - 2 (Старые варианты экзамена)

Математическая логикасводка определений и основных фактовV1.0 final (с) 2006Математическая логика, сводка определений. (с) 2006 GrGr (grgr@later.ru)Небольшое предисловиеЭтот файл составлен по конспекту лекций В.А. Захарова, сделанного небезызвестной ВалейГлазковой, при этом часть определений была слегка переформулирована в более читаемуюформу.

Предполагается, что всех материалов, представленных здесь, хватит для успешнойподготовки к теоретической части экзамена по матлогике на 3 потоке 4 курса ВМиК МГУ.Для практики требуется все-таки порешать задачи и пописать на Прологе ☺. В ближайшеевремя я планирую сделать задачник, а, если дойдут руки, то и полный конспект захаровскихлекций. Если Вы обнаружите опечатки или неточности, немедленно сообщайте мне поадресу grgr@later.ru (большое спасибо Андрею Чернышеву a.k.a. Dr.

Andrew за уженайденные глюки).Важно: данный документ не является истиной в последней инстанции, хотя на званиетаковой и претендует ☺, поэтому в нем могут содержаться неточности и даже ошибки!Будьте внимательны!2Математическая логика, сводка определений. (с) 2006 GrGr (grgr@later.ru)1. Классическая логика предикатов первого порядкаОпределение. Предикат – форма, при помощи которой задаются отношения междуобъектами и субъектамиСлово «предикат» происходит от латинского «предсказывать».Предикаты нулевого порядка – без использования кванторов.Предикаты первого порядка – кванторы используются только по отношению к предметамПредикаты высшего порядка – кванторы используются по отношению к функциям.Определение.

Алфавит (сигнатура) КЛП – это набор счетных множеств:1. предметных переменных, которое обозначается как Var = {x1 , x2 ,..., xn ,...} ;2. предметных констант, которые соответствуют именам предметов и обозначаются какConst = {c1 , c2 ,..., cn ,...} ;3.4.функциональных символов Func = { f1k1 , f 2k2 ,..., f mkm ,...} , где ki – местностьфункционального символа, причем ki ≥ 1 (в противном случае функциональный символявляется константой);предикатных символов, которые используются для обозначения отношений междупредметами и обозначаются Pred = {P1l1 , P2l2 ,..., Prlr ,...} , где li – местность предикатногосимвола (если li = 0 , то данный предикатный символ обозначает утверждение, независящее от каких-либо предметов).Служебные символы – это:- логические связки: &, ∨, →, ¬;- кванторы: ∀ (всеобщности) и ∃ (существования);- знаки препинания: ( ) ,Слова в алфавите – это цепочки символов.Определение.

Термом называется всякое слово, которое может быть построено последующим правилам:1) любая переменная является термом;2) любая константа является термом;3) если f – k-местный функциональный символ, а t1 , t2 ,..., tk - термы, то f (t1 , t2 ,..., tk ) такжебудет являться термом;4) других термов нет.Множество всех термов обозначается как Term.Запись t ( x1 , x2 ,..., xn ) используется для обозначения терма, в котором содержатся толькопеременные из множества { x1 , x2 ,..., xn }.Если t – терм, то выражением Vart будем обозначать множество всех переменных, которыесодержатся в терме t.Если Vart является пустым множеством, то терм t называется остовным термом.Определение. Формулой называется слово в языке КЛП, которое может быть построено последующим правилам:3Математическая логика, сводка определений. (с) 2006 GrGr (grgr@later.ru)1) если P – m-местный предикат, а t1 , t2 ,..., tm - термы, то запись вида P (t1 , t2 ,..., tm ) будетявляться формулой (атомарной формулой);2) если ψ и ϕ - формулы, то формулой также будет являться любое выражение вида¬ ϕ , ¬ ψ , ϕ ∨ ψ , ϕ &ψ , ϕ → ψ ;3) если ϕ - формула, а х – предметная переменная, то формулой также будет являться любоевыражение вида ∀xϕ , ∃xϕ ;4) никаких других формул нет.В формулах наибольший приоритет имеют кванторы и отрицание, затем конъюнкция,дизъюнкция и импликация.Множество всех формул обозначается как Form.Определение.

Областью действия кванторов называется формула ϕ из выражения ∀xϕили ∃xϕ . При этом вхождение переменной х в этих выражениях называется связанным.Если вхождение переменной не связанное, то оно называется свободным.Определение. Связанной (свободной) переменной называется переменная х, если она имеетсвязанное (свободное) вхождение в некоторую формулу.Запись Varϕ обозначает множество всех свободных переменных, входящих в формулу ϕ.Определение.

Если множество Varϕ пусто, то формула ϕ называется замкнутой формулой(предложением).Смысловое содержание языка логики предикатов определяется его семантикой. При этомописание выражений естественного языка является гораздо более сложной задачей, нежелиописание некоторых математических утверждений.Определение. Интерпретация – математическая конструкция, которая позволяет описыватьвсе многообразие воображаемых миров.

Интерпретацией будем называть алгебраическуюсистему I =< D, Const, Func, Pred > , которая состоит из следующих компонент:- DI ≠ ∅ - область интерпретации (предметное множество, универсум), котороепредставляется всеми возможными предметами воображаемого мира;- Const - отображение c ∈ Const → c ∈ DI (предмет в мире I, носящий имя константы с)- Func - отображение Func : f ( n ) ∈ Func → ( f ( n ) : DI → DI ) ;- Pred - отображение Pred : P ( m ) ∈ Pred → ( P ( m ) : DI → {T , F }) .Таким образом, все элементы нашего языка приобретают четкий математический смысл.На основании понятия интерпретации можно оценивать все формулы логики предикатов.Определение.

Пусть I – интерпретация, ϕ - формула от n переменных, d1, d2, …, dn – наборпредметов. Тогда отношением выполнимости называется следующее отношение:I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] , которое обозначает «формула ϕ в интерпретации Iвыполняется на значениях d1, d2, …, dn ее свободных переменных» и определяетсяследующим образом:1. Значение терма на данной интерпретации:4Математическая логика, сводка определений. (с) 2006 GrGr (grgr@later.ru)Если t – терм, d1, d2, …, dm – предметы, то t ( x1 , x2 ,..., xm )[d1 , d 2 ,..., d m ] - это предмет из областиинтерпретации, который является значением терма:- если t = xi, то t ( x1 , x2 ,..., xm )[d1 , d 2 ,..., d m ] будет равен di;- если t – это константа с, то t ( x1 , x2 ,..., xm )[d1 , d 2 ,..., d m ] = c ;- если t = f ( k ) (t1 , t2 ,..., tk ) , тоt ( x1 , x2 ,..., xm )[ d1 , d 2 ,..., d m ] = f ( k ) (t1 ( x1 , x2 ,..., xm )[ d1 , d 2 ,..., d m ],..., tk ( x1 , x2 ,..., xm )[ d1 , d 2 ,..., d m ]) .2.

Отношение выполнимости формулЕсли ϕ - атомарная формула вида P ( k ) (t1 , t2 ,..., tk ) , то выполнимость этой формулыэквивалентна истинности интерпретации предиката Р.Если ϕ - формула вида ¬ ψ ,ψ 1 ∨ ψ 2 ,ψ 1 &ψ 2 ,ψ 1 → ψ 2 , то ее выполнимость эквивалентна⎧ I |= ψ 1 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]1) в случае ψ 1 &ψ 2 : I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ⇔ ⎨⎩ I |= ψ 2 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]⎡ I |= ψ 1 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]2) в случае ψ 1 ∨ ψ 2 : I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ⇔ ⎢⎣ I |= ψ 2 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]⎡ I |≠ ψ 1 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]3) в случаеψ 1 → ψ 2 : I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ⇔ ⎢⎣ I |= ψ 2 ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ]4) в случае ¬ ψ : I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ⇔ I |≠ ψ ( x1 , x2 ,..., xn )[ d1 , d 2 ,..., d n ] .Если ϕ - формула вида ∀x0ψ ( x0 , x1 ,..., xn ) , ∃x0ψ ( x0 , x1 ,..., xn ) , то ее выполнимостьэквивалентна1) в случае ∀x0ψ ( x0 , x1 ,..., xn ) :I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ⇔ ∀d 0 ∈ DI I |= ψ ( x0 , x1 ,..., xn )[ d 0 , d1 , d 2 ,..., d n ] ,2) в случае ∃x0ψ ( x0 , x1 ,..., xn ) :I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] ⇔ ∃d 0 ∈ DI I |= ψ ( x0 , x1 ,..., xn )[d 0 , d1 , d 2 ,..., d n ] .Определение.

Формула ϕ называется выполнимой в интерпретации I, если для некоторогонабора предметов d1, d2, …, dn I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] .Определение. Формула ϕ называется истинной в интерпретации I, если для любого наборапредметов d1, d2, …, dn I |= ϕ ( x1 , x2 ,..., xn )[d1 , d 2 ,..., d n ] .Определение. Формула ϕ называется невыполнимой (или противоречивой) в интерпретацииI, если она не является выполнимой (т.е.

если эта формула соответствует тождественноложному утверждению).Определение. Формула ϕ называется общезначимой, если она является истинной в любойинтерпретации. Общезначимость формулы обозначается |=ϕ.Выполнимые, но не общезначимые формулы наиболее интересны для рассмотрения, тогдакак общезначимые формулы обычно мало информативны.Определение. Пусть Γ ⊆ Form - множество замкнутых формул. Тогда интерпретация Iназывается моделью для множества Г, если любая формула из Г выполнима в даннойинтерпретации.5Математическая логика, сводка определений.

(с) 2006 GrGr (grgr@later.ru)Определение. Пусть ϕ0 – замкнутая формула, а Γ ⊆ Form - множество замкнутых формул.Тогда ϕ0 называется логическим следствием Г (обозначается Γ |= ϕ0 ), если каждая модельдля Г является моделью для ϕ0.Сведем задачу нахождения логического следствия к проблеме общезначимости.Теорема (о логическом следствии). Если ϕ0 , ϕ1 ,..., ϕ n - замкнутые формулы, то {ϕ1 ,..., ϕn }|= ϕ0эквивалентно |= (ϕ1 &...& ϕn ) → ϕ0 (т.е. для любого логического следствия данногомножества формул такая импликация общезначима).Множество всех логических следствий – это и есть множество всех логических законов.Замечание.