Сводка определений - 2 (1158088)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Математическая логикасводка определений и основных фактов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 (т.е. для любого логического следствия данногомножества формул такая импликация общезначима).Множество всех логических следствий – это и есть множество всех логических законов.Замечание.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)