Введение в математическую логику и теорию алгоритмов презентация

Содержание

Истинность. Обозначения M = – структура, M ⊨ Φ(a1,. . . , ak) означает, что Φ истинна в M, если вместо свободных переменных xi подставлены элементы ai.

Слайд 1*
Введение в математическую логику и теорию алгоритмов

Алексей Львович Семенов
Лекция 5



Слайд 2 Истинность. Обозначения
M = – структура,
M

⊨ Φ(a1,. . . , ak) означает, что Φ истинна в M, если вместо свободных переменных xi подставлены элементы ai.
Векторные обозначения: a - набор (цепочка) элементов a1,. . . , ak, D* = {Λ} ⋃ D ⋃ D2…
Фиксируем сигнатуру Σ. Все имена отношений из этой сигнатуры. D и Зн могут меняться
Φ – утверждение, т. е. замкнутая (без свободных переменных) формула,
M ⊨ Φ означает, что формула Φ истинна в M.

Слайд 3Модель теории. Семантические свойства.
Теория – множество утверждений
Структура M – модель

теории Г, если M ⊨ Φ для любой Φ ∊ Г.
Замкнутая формула Φ семантически следует из теории Г, если формула Φ истинна в любой модели теории Г.
Обозначение: Г ⊨ Φ.
Теория, у которой есть модель, называется совместной (или семантически непротиворечивой).
Теория, у которой нет моделей, называется несовместной (или семантически противоречивой).
Теория Г семантически полна, если для любого утверждения Φ в той же сигнатуре Г ⊨ Φ или Г ⊨ ¬Φ.
Будем опускать слово «семантически».

Слайд 4Примеры теорий
∃u1,...,un ∀v (v=u1 ∨ . . . ∨ v=un)


Структуры, содержащие не более n элементов.
Задача. Бывают ли теории, у которых нет бесконечных моделей, но для каждого натурального n есть модель, содержащая n элементов?


Слайд 5Линейный порядок
∀u (¬R(u, u)) – антирефлексивность
∀u,v (R(u,v) ∨ R(v,u)

∨ u = v) – трихотомия ∀u,v,w ((R(u,v) ∧ R(v,w)) → R(u,w)) – транзитивность,
Будем писать < вместо R
Следствие из аксиом:
∀u,v ¬(uМодели – структуры, в которых отношение R задает линейный порядок.

Слайд 6Линейный порядок без наибольшего элемента
∀u (¬(u < u))
∀u,v (u

< v ∨ v < u ∨ u = v) ∀u,v,w ((u < v ∧ v < w) → u < w))
∀u ∃v (u < v)
Примеры моделей: Q<, R<, N<, Z<.
Задача. Доказать, что все модели бесконечны.

Слайд 7Теория ΓQ. Плотный линейный порядок без первого и последнего элемента.
∀u

(¬(u < u)) ∀u,v (u < v ∨ v < u ∨ u = v)
∀u,v,w ((u < v ∧ v < w) → u < w)
∀u,v (u < v → (∃w (u < w < v))) – плотность
∀u ∃v (v < u) – неограниченность снизу
∀u ∃v (u < v) – неограниченность сверху
Задачи Какие бывают модели?
Можно ли что-то добавить, чтобы отделить Q< от R< (т.е., чтобы первая структура была моделью, а вторая – нет)?

Слайд 8Теория ΓN : Дискретный линейный порядок с наименьшим элементом.
∀u (¬(u

< u))
∀u,v (u < v ∨ v < u ∨ u = v)
∀u,v,w ((u < v ∧ v < w) → u < w)
∀u ∃v (u < v)
∀u (0 < u ∨ u = 0)
∀u (∃v (u < v ∧ (∀w (u < w → (v=w ∨ v∀u(u ≠ 0 → (∃v(vЗадачи:
Что эта теория «означает» (смысл)?
Какие у нее бывают модели (денотат)?

Слайд 9Изоморфизм
«Одинаковость» структур
Изоморфизм множеств – равномощность
Структуры M1 = ⟨D1, Σ,

Зн1⟩ и M2 = ⟨D2, Σ, Зн2⟩ Взаимно однозначное отображение ψ: D1 на D2. Для любых a ∈ D1*, P ∈ Σ Зн1(P)(a) ⇔ Зн2(P)(ψ(a)).
Задачи:
Изоморфны ли структура положительных и всех рациональных чисел с порядком?
Изоморфны ли две любые счетные модели ΓQ?
Бывают ли модели теории ΓQ, равномощные R, но не изоморфные R

Слайд 10Теории и структуры
M – структура
ThM – теория структуры =

множество утверждений, истинных в структуре M.
Теория класса структур = множество утверждений, истинных в каждой структуре класса
Пусть
m – класс структур,
ϕ – теория.
Определим отображения:
Th (m) – теория класса структур m,
Mod (ϕ) – класс всех моделей теории ϕ.

Th, Mod – соответствие Галуа (анти-монотонное).
Тогда m ⊆ Mod (ϕ) ⇔ Th (m) ⊇ ϕ.

Слайд 11Эквивалентность
Структуры M1 и M2 (элементарно) эквивалентны, если ThM1 = ThM2.
Задача.

Почему изоморфные структуры эквивалентны?
Индукцией по построению (не обязательно замкнутой) формулы Φ:
M1 ⊨ Φ(a) ⇔ M2 ⊨ Φ(ψ(a))
Задача. Бывают ли эквивалентные неизоморфные структуры?

Слайд 12Подструктура. Элементарная подструктура и элементарное расширение
M = ⟨D,Σ,Зн⟩, D1 ⊆ D.


Подструктура M1 = ⟨D1,Σ,Зн1⟩, отображение Зн1 является ограничением Зн на D1.
M1 – элементарная подструктура M : M ⊨ Φ(a) ⇔ M1 ⊨ Φ(a) для любых формул Φ и любых наборов a ∈ D1*. M – элементарное расширение M1. Очевидно M эквивалентна M1.
Бывают ли такие структуры M и M1, что (1) M1 – подструктура M, и (2) M1 эквивалентна M, но (3) M1 не является элементарной подструктурой M?

Слайд 13Критерий Тарского – Воота
Пусть M1 = ⟨D1,Σ,Зн1⟩ – подструктура структуры

M = ⟨D,Σ,Зн⟩, D1 ⊆ D. Следующие два условия эквивалентны:
(1) M1 – элементарная подструктура структуры M
(2) для любой формулы Φ(x,y) и любого набора a ∈ D1* если M ⊨ Φ(a,b) для некоторого b ∈ D, то M ⊨ Φ(a,b′) для некоторого b′ ∈ D1.
Доказательство (1) → (2) - тривиально. Именно:
M ⊨ Φ(a,b) для некоторого b ∈ D ⇒
M ⊨ ∃u Φ(a,u) ⇒
M1 ⊨ ∃u Φ(a,u)) ⇒
M1 ⊨ Φ(a,b′) для некоторого b′ ∈ D1 ⇒
M ⊨ Φ(a,b′).

Слайд 14Критерий Тарского – Воота
(2) → (1). Индукция по построению
M1 ⊨

Φ(a) ⇔ M ⊨ Φ(a), a ∈ D1* Рассмотрим случай, когда Φ = ∃u Ψ(x,u)
⇒. M1 ⊨ ∃u Ψ(a,u) ⇒ M1 ⊨ Ψ(a,b′) для некоторого b′ ∈ M1 ⇒ M ⊨ Ψ(a,b′) ⇒ M ⊨ ∃u Ψ(a,u)
⇐. M ⊨ ∃u Ψ(a,u). M ⊨ Ψ(a,b) для некоторого b ∈ M ⇒ M ⊨ Ψ(a,b′) для некоторого b′ ∈ M1 ⇒ M1 ⊨ Ψ(a,b′) ⇒ M1 ⊨ ∃u Ψ(a,u)
Задача. Провести полное доказательство критерия Тарского – Воота.

Слайд 15Теорема Лёвенгейма – Сколема об элементарной подмодели.
Т. Любая бесконечная структура

с конечной или счетной сигнатурой содержит счетную элементарную подструктуру.
Д. Строим цепь M0 ⊆ M1 ⊆ ... счётных подструктур M.
M0 произвольно. (Для Mi = ⟨D,Σ,Зн⟩ пишем Mi вместо D.)
На i -ом шаге берем все формулы Φ(x,y), все a ∈ Mi * . Если M ⊨ Φ(a,b), для какого-то b ∈ M, помещаем в Mi+1 это b.
M′ = ∪Mi – счетное множество.
Задача.
Как определяется D′ для M′ ?
Доказать что M′ – элементарная подструктура.
Еще один метод – «Объединение цепи».

Слайд 16
Туральф Альберт Скулем (Thoralf Albert Skolem), 1887—1963
Леопольд Лёвенгейм Leopold Löwenheim

26.06.1878 – 5.05.1957

Слайд 17Теорема компактности
Т. (Гедель, Анатолий Иванович Мальцев)
Если любое конечное подмножество теории совместно,

то теория совместна.
Как доказать теорему компактности?
Следствие. Если утверждение является следствием теории, то это утверждение является следствием некоторого конечного подмножества данной теории.
Задача. Вывести следствие из теоремы компактности.

А.И. Мальцев (14.11.1909—07.07.1967)


Слайд 18Полные теории
Γ – Γ ⊨ Φ или Γ ⊨ ¬Φ для

любого утверждения Φ.
Задача. Почему любую совместную теорию можно расширить до полной? Задача. ThM – полна.
Задача. Теория полна тогда и только тогда, когда две любые модели теории эквивалентны.
Задача.
Являются ли теории ΓQ, ΓN полными?
Существуют ли у них неизоморфные счетные модели?


Слайд 19Теорема Лёвенгейма – Сколема об элементарном расширении.
Теорема. Для любой бесконечной

структуры с конечной
или счётной сигнатурой существует элементарное
расширение сколь угодно большой мощности.
Доказательство. Расширяем структуру.
M = , сигнатура ΣM содержит имена для всех
элементов из D, сопоставление Зн естественно
продолжено до Зн'. ThM(M) – теория соответствующей
структуры, M элементарно вложима в модели этой теории.
Новые имена предметов {c} – произвольной мощности,
Г = ThM(M) ⋃ {c ≠ d}.
Г совместна (компактность).
Мощность модели Г не меньше мощности множества
новых имен.

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика