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

Математическая логикаи логическое программированиеЛектор:Подымов Владислав Васильевич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 , . . .