Вопрос 7. Алгебраические системы. Формулы сигнатуры S. Подформулы. Свободные и связанные переменные. Предложения. Истинность формулы на элементах алгебраической системы.

Алгебраическая система сигнатуры S - пара ? = áA, Sñ , где каждому предиксному символу p⁽ⁿ⁾ Î S сопоставлено некоторое n – местное отношение на A, а каждому функциональному символу fⁿ Î S - n местная операция на A.

Атомарные формулы сигнатуры S:

1. если t₁, …, t_n Î T( S ), то t₁ » t₂ – атомарная формула сигнатуры S.

2. если t₁, …, t_n Î T( S ), p^{( n )} Î S, то p(t₁, …, t_n) – атомарная формула сигнатуры S.

3. других формул нет.

Формулы сигнатуры S.

1. любая атомарная формула сигнатуры S, является формулой сигнатуры S.

2. если j и y - формулы сигнатуры S, x Î V, то (j Ú y), (j Ù y), (j ® y), ^Øj, " x j , $ x j - формулы сигнатуры S.

3. других формул нет.

j - формула сигнатуры S, SF(j) – множество подформул j.

1. если j - атомарная формула, то SF(j) – SF(j) = {j}

2. если j = (j₁ Ù j₂), j = (j₁ Ú j₂) или j = (j₁ ® j₂), то SF(j₁) È SF(j₂)

3. если j = ^Øj₁, j = " x j₁ или j = $ x j₁, то SF(j) = SF(j₁) È {j₂}

S = {F⁽²⁾, P⁽¹⁾}

Вхождение переменной Х в формулу j называется связанным, если Х входит в терм или предикат, который находится в области действия квантора "X или $X. Вхождение переменной называется свободным, если оно не является связанным. Переменная Х называется связанной (свободной), если некоторое ее вхождение связанное (свободное).

Предложение называется формула, не имеющая свободных переменных.

1. $z " x($y R(x, y) ® ^Øp(x)); z – фиктивная переменная

2. $y " x(R(x, y) ® $x Q(x))

$y " x(R(x, y) ® $z Q(z))

j, FV(j) Í {x₁, x₂, …, x_n}

Формула j(х₁, …, х_n) сигнатуры S называется тождественно истиной или общезначимой (тождественно ложной или противоречивой), если для любой алгебраической системы Á = áA, Sñ и любых a₁, …, a_n Î A выполняется Á╞ j(a₁, …, a_n). (Á╞ j(a₁, …, a_n).)

Формула j(х₁, …, х_n) называется выполнимой (опровержимой), если для нек. Á = áA, Sñ и нек. a₁, …, a_n Î A выполняется Á╞ j(a₁, …, a_n).

Вопрос 8. Общезначимые и выполнимые формулы. Теорема об общезначимости формул сигнатуры Σ, соответствующих общезначимым формулам ИВ. Выполнимое множество формул. Теорема компактности.

Формула φ(х₁,…,х_n) сигнатуры Σ называется тождественной истинной или общезначимой (тождественно ложной или противоречивой), если для любой алгебраической системы М=<А,Σ>, если для любой алг. системы М=<A, Σ> и любых a₁,…,а_n є A выполняется (М|=φ(a₁,…,а_n) (M(|≠φ(a₁,…,а_n)).

Формула φ(х₁,…,х_n) называется выполнимой (опровержимой), если для некоторой M=<A,Σ> и некоторых a₁,…,а_n є А выполняется М|= φ(а₁,…,а_n) (М|≠φ(а₁,…,а_n))

Теорема: φ(A₁,…,A_n) – тождественно истинной формула ИВ, φ₁,…,φ_n – формулы ИП в степени Σ.

Теорема: М,Д – алгебраические системы сигнатуры Σ, φ: М→Д, то для любой формулы φ(х₁,…,х_n) сигнатуры Σ и любых a₁,…,а_n є А М|=φ( a₁,…,а_n) <=> Д|= φ (f(a₁),…,f(а_n))

Г – множество формул сигнатуры Σ.

Х – множество свободных переменных из Г

Г называется выполнимым, если существует Ш=<M, Σ>, x є X |→a_x єM, так что Ш|=Г.

Ш|= φ(a_х1,…,a_хn) для любых φ(х₁,…,х_n) є Г.

При этом Ш называется моделью для множества Г.

Σ={≤}

Г={"x(x≤x), "x"y(x≤y v y≤x), "xyz((x≤y v y≤z) → x ≤2), "xy((x≤y ^ y≤x) → x≈y)}

<N, ≤ > |= Г

<{0}, ≤ > |= Г

Г ’= Г È{$xy (x≈y);

"xy ((x≤y ^ x≈y) → $z (x≤z ^ z≤y ^ x≈z ^ z≈y))

Свойство плотности

<N, ≤ > |≠ Г ‘

<Q, ≤ > |= Г ‘

Г ‘ имеет лишь бесконечные модели

Г называется локально выполнимым, если люб. кон. F₀ ≤ Г выполнимо.

Теорема Мальцева: Любое локально выполнимое множество формулы выполнимо.

Следствие: Если для любого n є N из множества Г имеет модель мощности ≥ k, то Г имеет бесконечную модель.

Вопрос 9.

Зафиксируем некоторую произвольную сигнатуру S и опр-им исчисление предикатов сигнатуры S( ИП^S ). Аксиомами ИП^S явл. следующие секвенции:

1. φ ├ φ, φ-формула ИП^S

2. ├ x ≈ x, x –переменная

3. x ≈ y, (φ)^Z_X├(φ) ^Z_Y, x,y,z-переменные, φ-формула ИП^S , удовлетворяющего условию на запись (φ)^Z_x и (φ) ^Z_Y

Правила вывода ИП^S таковы:

1. ; 2. ; 3. ; 4. ; 5.

6. ; 7. ; 8. ; 9.

10. ;11. ;12. ;

13. , где x не входит в члены Г свободно; 14. ; 15.

16. , где х не входит в и члены Г свободно.

Следующие секвенции доказуемы:

1. ├ $ x1,…,$xn φ

2."x1, … , "xn ψ├ (ψ)x1,…, xn

Теорема о дедукции. Если Г U {φ,ψ} – мн-во формул ИП^S, то из Г,φ-|ψ следует Г-| φ→ψ.

Теорема Гёделя о полноте. Формула φ исчисления ИП^S доказуема тогда и толь тогда, когда φ тождественно истинна.

Исчисление ИП^S непротиворечиво, т.е. не все формулы ИП^S доказуемы в ИП^S.

Док-во:

S=(├ x ≈ x)(тождественно ложная формула)

=> ╞ S => по т. о полноте S недоказуемо => ИП^S непротиворечиво.