Презентация 15 (1131939)

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

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

Математическая логикаи логическое программированиеЛектор:Подымов Владислав Васильевичe-mail:valdus@yandex.ru2016, весенний семестрВступлениеВ Лекции 14 была описана теория множеств Цермело-Френкеля(ZF), содержащаяI аксиому, определяющую равенство множеств(аксиома объёмности)I аксиомы существования большого числа “хороших”множествI аксиому, устраняющую парадоксы теории множеств(аксиома регулярности)ВступлениеВ Лекции 14 была описана теория множеств Цермело-Френкеля(ZF), содержащаяI аксиому, определяющую равенство множеств(аксиома объёмности)I аксиомы существования большого числа “хороших”множествI аксиому, устраняющую парадоксы теории множеств(аксиома регулярности)Достаточно ли только этих аксиом, чтобы полноценнорассуждать о свойствах множеств?Определимые символыВ лекции 14 был введён ряд сокращений, использовавшихся вописании аксиом ZFОпределимые символыВ лекции 14 был введён ряд сокращений, использовавшихся вописании аксиом ZF, например,∅∈XОпределимые символыВ лекции 14 был введён ряд сокращений, использовавшихся вописании аксиом ZF, например,∅ ∈ X,y = x ∪ {x}Определимые символыВ лекции 14 был введён ряд сокращений, использовавшихся вописании аксиом ZF, например,∅ ∈ X,y = x ∪ {x},x ⊆ y,...Определимые символыВ лекции 14 был введён ряд сокращений, использовавшихся вописании аксиом ZF, например,∅ ∈ X,y = x ∪ {x},x ⊆ y,...Эти сокращения позволяли содержательно рассуждать опредметах и отношениях предполагаемой модели теориимножеств, и при этом не расширяли сигнатуру алфавитаОпределимые символыВ лекции 14 был введён ряд сокращений, использовавшихся вописании аксиом ZF, например,∅ ∈ X,y = x ∪ {x},x ⊆ y,...Эти сокращения позволяли содержательно рассуждать опредметах и отношениях предполагаемой модели теориимножеств, и при этом не расширяли сигнатуру алфавитаОпишем общий способ работы с предметами и отношениями, невходящими в сигнатуру теории множествОпределимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределение символаI R — это формула вида ϕ(exn )Определимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределение символаI R — это формула вида ϕ(exn )Iтакое определение придаёт символу R значение отношенияϕОпределимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределение символаI R — это формула вида ϕ(exn )IIтакое определение придаёт символу R значение отношенияϕf — это формула вида ϕ(y, exn )Определимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределение символаI R — это формула вида ϕ(exn )IIтакое определение придаёт символу R значение отношенияϕf — это формула вида ϕ(y, exn )Iтакое определение придаёт символу f следующее значение:y = f(exn ) ≡ ϕ(y, exn )Определимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределение символаI R — это формула вида ϕ(exn )IIf — это формула вида ϕ(y, exn )IIтакое определение придаёт символу R значение отношенияϕтакое определение придаёт символу f следующее значение:y = f(exn ) ≡ ϕ(y, exn )c — это формула вида ϕ(y)Определимые символыРассмотрим предикатный символ R(n) , функциональный символf (n) и константу c, не входящие в сигнатуру рассматриваемогоалфавитаОпределение символаI R — это формула вида ϕ(exn )IIf — это формула вида ϕ(y, exn )IIтакое определение придаёт символу R значение отношенияϕтакое определение придаёт символу f следующее значение:y = f(exn ) ≡ ϕ(y, exn )c — это формула вида ϕ(y)Функциональный или предикатный символ s — определённый,если ему сопоставлено определение DsОпределимые символыПримеры определенийОпределимые символыПримеры определенийD6=(2) :¬x1 = x2Определимые символыПримеры определенийD6=(2) :D⊆(2) :¬x1 = x2∀z (z ∈ x1 → z ∈ x2 )Определимые символыПримеры определенийD6=(2) :D⊆(2) :D∅ :¬x1 = x2∀z (z ∈ x1 → z ∈ x2 )∀z ¬z ∈ x1Определимые символыПримеры определенийD6=(2) :D⊆(2) :D∅ :D{·,·}(2) :¬x1 = x2∀z (z ∈ x1 → z ∈ x2 )∀z ¬z ∈ x1∀z (z = x1 ∨ z = x2 )Определимые символыПримеры определенийD6=(2) :¬x1 = x2D⊆(2) :∀z (z ∈ x1 → z ∈ x2 )D∅ :∀z ¬z ∈ x1D{·,·}(2) : ∀z (z = x1 ∨ z = x2 )D∩(2) :∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 ))Определимые символыПримеры определенийD6=(2) :¬x1 = x2D⊆(2) :∀z (z ∈ x1 → z ∈ x2 )D∅ :∀z ¬z ∈ x1D{·,·}(2) : ∀z (z = x1 ∨ z = x2 )D∩(2) :∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 ))D∪(2) :∀z (z ∈ y ≡ (z ∈ x1 ∨ z ∈ x2 ))Определимые символыПримеры определенийD6=(2) :¬x1 = x2D⊆(2) :∀z (z ∈ x1 → z ∈ x2 )D∅ :∀z ¬z ∈ x1D{·,·}(2) : ∀z (z = x1 ∨ z = x2 )D∩(2) :∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 ))D∪(2) :∀z (z ∈ y ≡ (z ∈ x1 ∨ z ∈ x2 ))D0 =D∅Определимые символыПримеры определенийD6=(2) :¬x1 = x2D⊆(2) :∀z (z ∈ x1 → z ∈ x2 )D∅ :∀z ¬z ∈ x1D{·,·}(2) : ∀z (z = x1 ∨ z = x2 )D∩(2) :∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 ))D∪(2) :∀z (z ∈ y ≡ (z ∈ x1 ∨ z ∈ x2 ))D0 =D∅DS(1) :∀z (z ∈ y ≡ (z ∈ x1 ∨ z = x1 ))Определимые символыПримеры определенийD6=(2) :¬x1 = x2D⊆(2) :∀z (z ∈ x1 → z ∈ x2 )D∅ :∀z ¬z ∈ x1D{·,·}(2) : ∀z (z = x1 ∨ z = x2 )D∩(2) :∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 ))D∪(2) :∀z (z ∈ y ≡ (z ∈ x1 ∨ z ∈ x2 ))D0 =D∅DS(1) :∀z (z ∈ y ≡ (z ∈ x1 ∨ z = x1 ))А как использовать определения при исследовании формулы,содержащей определённые символы?Определимые символыФормулу в сигнатуре, отличной от σ = ∅, ∅, ∈(2) , будемотождествлять с формулой в сигнатуре σ, в которойОпределимые символыФормулу в сигнатуре, отличной от σ = ∅, ∅, ∈(2) , будемотождествлять с формулой в сигнатуре σ, в которойI каждый атом P(t1 , .

. . , tn ) заменён на DP {x1 /t1 , . . . , xn /tn }(P — определённый предикатный символ, отличный от ∈)(каждая переменная xi считается свободной для ti в DP )Определимые символыФормулу в сигнатуре, отличной от σ = ∅, ∅, ∈(2) , будемотождествлять с формулой в сигнатуре σ, в которойI каждый атом P(t1 , . . . , tn ) заменён на DP {x1 /t1 , . .

. , xn /tn }I каждый атом A JcK заменён на ∀y (Dc → A Jc/yK)(P — определённый предикатный символ, отличный от ∈)(каждая переменная xi считается свободной для ti в DP )(c — определённая константа)(y — “свежая” переменная)Определимые символыФормулу в сигнатуре, отличной от σ = ∅, ∅, ∈(2) , будемотождествлять с формулой в сигнатуре σ, в которойI каждый атом P(t1 , .

. . , tn ) заменён на DP {x1 /t1 , . . . , xn /tn }I каждый атом A JcK заменён на ∀y (Dc → A Jc/yK)I каждый атом A Jf(t1 , . . . , tn )K заменён на∀y (Df {x1 /t1 , . . . , xn /tn } → A Jf(t1 , . . . , tn )/yK)(P — определённый предикатный символ, отличный от ∈)(каждая переменная xi считается свободной для ti в DP )(c — определённая константа)(y — “свежая” переменная)(f — определённый функциональный символ)Определимые символыПримерx⊆y∩zОпределимые символыПримерx⊆y∩z;∀u (D∩ {y/u, x1 /y, x2 /z} → x ⊆ u)Определимые символыПримерx⊆y∩z;∀u (D∩ {y/u, x1 /y, x2 /z} → x ⊆ u)=∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → x ⊆ u)Определимые символыПримерx⊆y∩z;∀u (D∩ {y/u, x1 /y, x2 /z} → x ⊆ u)=∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → x ⊆ u);∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → D⊆ {x1 /x, x2 /u})Определимые символыПримерx⊆y∩z;∀u (D∩ {y/u, x1 /y, x2 /z} → x ⊆ u)=∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → x ⊆ u);∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → D⊆ {x1 /x, x2 /u})=∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → ∀z (z ∈ x → z ∈ u))Определимые символыПримерx⊆y∩z;∀u (D∩ {y/u, x1 /y, x2 /z} → x ⊆ u)=∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → x ⊆ u);∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → D⊆ {x1 /x, x2 /u})=∀u (∀w (w ∈ u ≡ (w ∈ y & w ∈ z)) → ∀z (z ∈ x → z ∈ u))В формулах можно использовать любые символы, если им даныопределенияОпределимые символыПримерОпределение натурального числа nОпределимые символыПримерОпределение натурального числа nПредположим, натуральное число (n − 1) определеноОпределимые символыПримерОпределение натурального числа nПредположим, натуральное число (n − 1) определено ТогдаDn : ∀z (z ∈ y ≡ (z = (n − 1) ∨ z ∈ (n − 1)))Определимые символыПримерОпределение натурального числа nПредположим, натуральное число (n − 1) определено ТогдаDn : ∀z (z ∈ y ≡ (z = (n − 1) ∨ z ∈ (n − 1)));∀z (z ∈ y ≡ ∀u (Dn−1 (u) → z = u ∨ z ∈ u))Определимые символыПримерОпределение натурального числа nПредположим, натуральное число (n − 1) определено ТогдаDn : ∀z (z ∈ y ≡ (z = (n − 1) ∨ z ∈ (n − 1)));∀z (z ∈ y ≡ ∀u (Dn−1 (u) → z = u ∨ z ∈ u))В определениях символов можно использовать определённыеранее символыИнтерлюдия: некоторые свойства множествИнтерлюдия: некоторые свойства множествПопробуем доказать такое несложное утверждение:УтверждениеВо всяком бесконечном множестве можно выделитьсчётное подмножествоИнтерлюдия: некоторые свойства множествПопробуем доказать такое несложное утверждение:УтверждениеВо всяком бесконечном множестве можно выделитьсчётное подмножествоДоказательство.В любом бесконечном множестве X содержится хотя бы одинэлемент e1Интерлюдия: некоторые свойства множествПопробуем доказать такое несложное утверждение:УтверждениеВо всяком бесконечном множестве можно выделитьсчётное подмножествоДоказательство.В любом бесконечном множестве X содержится хотя бы одинэлемент e1Множество X \ {e1 } бесконечно, а значит, содержит хотя быодин элемент e2Интерлюдия: некоторые свойства множествПопробуем доказать такое несложное утверждение:УтверждениеВо всяком бесконечном множестве можно выделитьсчётное подмножествоДоказательство.В любом бесконечном множестве X содержится хотя бы одинэлемент e1Множество X \ {e1 } бесконечно, а значит, содержит хотя быодин элемент e2Множество X \ {e1 , e2 } бесконечно, а значит, содержит хотя быодин элемент e3Интерлюдия: некоторые свойства множествПопробуем доказать такое несложное утверждение:УтверждениеВо всяком бесконечном множестве можно выделитьсчётное подмножествоДоказательство.В любом бесконечном множестве X содержится хотя бы одинэлемент e1Множество X \ {e1 } бесконечно, а значит, содержит хотя быодин элемент e2Множество X \ {e1 , e2 } бесконечно, а значит, содержит хотя быодин элемент e3Бесконечно продолжая процесс выбора элементов ei , получимтребуемое счётное подмножество {e1 , e2 , .

. .}HИнтерлюдия: некоторые свойства множествА теперь другое утверждение:УтверждениеДля любого натурального числа N декартовопроизведение N непустых множеств непустоИнтерлюдия: некоторые свойства множествА теперь другое утверждение:УтверждениеДля любого натурального числа N декартовопроизведение N непустых множеств непустоДоказательство.Рассмотрим произвольные непустые множества X1 , . . . , XNX1...X1 × · · · × XNXNИнтерлюдия: некоторые свойства множествА теперь другое утверждение:УтверждениеДля любого натурального числа N декартовопроизведение N непустых множеств непустоДоказательство.Рассмотрим произвольные непустые множества X1 , . . .

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

Тип файла PDF

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

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

Список файлов лекций