Вопрос 11. Элементарные теории. Сис-ма аксиом теории ….

Элементарные теории. Т-мн-во предл.сигн. ∑ 1 для кот. из Т├φ ,

Следует φ Т. Т-элементарная сигн. Теоремы Σ z c Т , z ├ Т

Z – система аксиом для теории Т. Примеры:

1) Σ={.} z={Vx Vy Vz((xy)z≈x(yz))} z├ Т – теория всех полугрупп

2) Σ={≤} Z- рефл. транз. z├Т Г^Г –теория плотного линейного прядка

3) =<A,Σ>, |A|< ω |Σ|<ω – Все взаимо-я записываются одной

аксиомой φ. φ├ Т –теория алг.системы ,

Т=Тh ()={φ|φ- предл. |φ} Непрот. Теория Т наз. полной если для люб. предл. φ сигн. Σ, φ Т или ¬φТ,,Th()-полная теория.Vx Vy (xy≈yx) Tо ¬Vx Vy (xy≈yx) ↑ неполная теория

Полная теория Т=Th() Теорией Т наз.λ- категоричной(где λ-нек. кардинал), если все модели ╞Th имеющие мощность λ изоморфны

≈, если сущ. φ :A↔B, для кот. 1)P Σ : ╞ P(a1……an)<=> ╞P(φ(a1)… φ(an)) 2) f Σ: ╞f (a1……an)≈a<=>╞f (φ(a1)……φ(an))≈φ(a). Теорема: Т λ- категорична (≥ω),

иТ_∞=Т U { x1,… xn (^ ¬xi≈xj)| n ω} непрот.=> T∞-полная теорема Т_∞={φ| T_∞├ φ} φ-прел. Тnun, Σ={≤}-рефл. антисим. транзит. сравнимость, полность  x y z ≤

 ¬ xVy (x≤ y)

 ¬ Vy (y≤ x) Следствие: (Тmn)’_∞-полная теория

Док: (Tmn)’∞ , ω –категорична (=> полнота)

╞(Tmn)’_∞ ╞ (Tmn)’_{∞ |}a_{2 |}a_{0 |} a’_{1 |} a_{1 |} a’_{2 ≤}

A={a_n , | nω}

A={a_n , | nω}

b’₂ b₀ b₁ b’₁ b₂

φ:A↔B a; ≤ a_j <=> φ(a_i)≤ φ(a_j) , φ(a₀)=b_{0 ,} φ(a₁)=b’_{1 ,} φ(a’₁)=b₁

φ(a₂)=b’_{2 ,} φ(a’₂)=b_{2 .} φ: .

Вопрос 12. Сис-ма аксиом арифметики Пеано…..

Системы Дедекинда – Пеано.

Множество натуральных чисел можно определить двояко:

1. Исходя из Ø последовательно выражать натуральные числа, как множества, состоящие из предыдущих натуральных чисел;

2. Задавать алгебраическую систему N = <N,0, ´>, удовлетворяющую системе аксиом Дедекинда – Пеано.

Теорема Дедекинда – Пеано: Любые две системы Дедекинда – Пиано изоморфны.

По индукции в системе N однозначно определимы двухместные операции сложения и умножения. <N,0,´,+,·>

#13. Подстановка сигнатуры σ. Композиция подстановок. Унификатор и наиболее общий унификатор. Алгоритм унификации. Теорема об алгоритме унификации.

1. Метод резолюции в исчислении предикатов

Подстановка сигнатуры ∑ называется множество вида {t₁/x₁, ...,t_n/x_n} при этомx_i ≠x_j, x_i ≠t_i. ∑ - - пустая подстановка.

Пример.

{ F₁(z)/x,y/z} - подстановка сигнатуры ∑ = {F₁₁⁽¹⁾ }.

{ C₁/x,F₂⁽⁹⁾/y,F₁ (F₂ (C₁))/z} – подстановка сигнатуры ∑ = {C₁⁽⁰⁾,F₂⁽¹⁾,F₁⁽¹⁾,C₁⁽⁰⁾}.

Пусть Ө = {t₁/x₁, ...,t_n/x_n} подстановка сигнатуры ∑.WӨ - множество получаемое изWс помощью одновременной подстановки вместоx₁, ...,x_n термовt₁, ...,t_n.

Пример.

Ө = { C₁/x,F(C₂)/y,y/z}

t = F₁ (x, y, z), тогда t Ө = F₁(C₁, F(C₂), y)

Q = F (x, C₁, z)

Q Ө = F₁ (C₁) ≈ F₁(C₁, C₁, y)

Ө = {t₁/x₁, t_n/x_n}

λ = { g₁/y₁, ... , g_n/y_n}

Ө λ = { t₁, λ/x₁,..., t_nλ/x_n, g₁/g_n,..., g_n/y_n}

Если y_i принадлежит {x₁...x_n}, тоg_i/y_i - вычёркиваем

Если t_iλ=x_i, тоt_i λ/x_i – вычёркиваем

Пример.

Ө = { F₁(y)/x,z/y}; λ = {C₁/x,C₂/y,y/z}

Ө λ= {F₁(y)λ/x,zλ/y,C₁/x,C₂/x,y/z} = {F₁(C₂)/x,y/y,y/z} = {F₁(C₂)/x,y/z}

Өz= Ө любая Ө

Ө ( λ μ ) = (Ө λ ) μ для любых μ,λ, Ө

Определение: пусть Ф = {φ_{1, ....},φ_n} – множество формул сигнатуры ∑; Ө - подстановка сигнатуры ∑. Ө называетсяунификатором множества Ф, если φ₁Ө = … = φ_nӨ.

Пример.

Ф = {P(C₁,y),P(x₁) =C₂} можно заменять только переменные

Ө = {C₁/x,F(C₂)/y} – унификатор множества Ф

Определение: множество формул называется унифицируемым, если для него есть унификатор.

Определение:унификаторσ для множества {φ_{1, ....},φ_n} называется наиболее общим унификатором (НОУ), если для любого другого унификатора Ө существует λ такая что Ө =σλ.

Определение:пустьW= {φ_{1, ....},φ_n} – непустое множество атомарных формул. Множествомрассогласований множестваWназывается множество термовt₁, ...,t_n, гдеt_iвходит в φ_i и начинается с символа стоящего на первой слева позиции в φ_i; на которой не для всех формулφ_{1, ....},φ_nнаходится одинаковый символ.

Пример.

W= {P(x),F(y,z),P(x,c),P(x|= (y,F₁(z)))}

Найдём множество рассогласований Д_l= {F(y,z),C|= (y,F₁(z))}

2. Алгоритм унификации

Определяет, унифицируемость множества атомарных формул, или нет, и если унифицируемо, то находим наиболее общий унификатор.

Дано W–множество атомарных формул.

1. k = 0, w₀ = w, σ₀ = ∑.

2. Если | w_k| = 1 следовательно, множествоWунифицируемо в качестве НОК = σ_k. Иначе находим Д_k – множества рассогласований множестваW_k.

3. Если Д_k содержит переменнуюx_k и термt_kне содержащийx_k, то переходим к 4. иначе – остановка,Wне унифицируемо.

4. σ_k+1=σ_k{t_k/x_k},W_k+1=W_kσ_k+1,k→k+ 1 переходим к шагу 2.

Теорема: еслиWунифицируемо, то алгоритм унификации закончит работу на втором шаге и последняя подстановка σkявляется НОУ.

Пример.

W= {P(z,x,F₂(F₁(y))),P(z,F₂(z),F₂(n))}

1. W₀ =W,σ₀= ∑.

2. | W₀| ≠ 1, тогда Д_k= {c,z}

3. 4. σ₁ =σ₀, {c/z} = {c/z}

W₁ = {P (e, x, F₂(F₁(y))), P(e, F₂(e), F₂(n)}

Следовательно 2 | W₁ | ≠ 1, тогда Дk= {x,F₂(e)}.