Вопрос 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.

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

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

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

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

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

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=(├ ¬x ≈ x)(тождественно ложная формула)

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

Теорема о существовании модели. Для любого непротиворечивого мн-ва формул г сигнатуры 

существует некоторая модель W╞ Г.

Тождественно истинные формулы:

Вопрос 10. Основные эквивалентности .

эквивалентно в , если док-ма секв. |- и |- в .

.

, если для док-в секв. |- и |- использются правила 1)-12)

Предл.

В справедливы все эквивалентности ИВ:

1. 

2. 

3. 

4. 

Предл.

а)

б)

в) \

г) > перем. х не входит свободн. в

д) |

е) /

ж) \

з) / >у не входит в свободн. и никакое вхождение х не находится под квантором или .

Теорема о замене.

Если ф-ла получается из сигнатуры заменой некоторого вхождения подформулы ф-лы на ф-мулу и , то , под квантором или .

Пренексные и клазуальные нормальные формы.

Ф-ла называется безкванторной если не содержит кванторов. Бескванторная ф-ла находится в ДНФ (КНФ), если получается из ф-лы ИВ, находящейся в ДНФ (КНФ), заменой проп. перем. на фтомарные ф-лы сигн. .

Ф-ла находится в пренексной (клазуальной) нормальной форме, если имеет след. вид:

, где ; - бескванторная ф-ла находящаяся в ДНФ (КНФ).

(ПНФ, КлНФ - пренексные и клазуальные нормальные формы).

Теорема

Для любой ф-лы сигн. существует эквиалентная ф-ла сигн. , находящаяся в ПНФ (К₁НФ).

Алгоритм приведения к НФ.

1. удаление :

2. использование з-на де Моргана, з-ны двойного отрицания и св-ва а), б) пред. предл.,

3. исп-е св-ва в)-з),

4. бескванторное ядро

Пример.

Привести ф-лу Х к ПНФ.

- ПНФ, КлНФ.