mathlogic-s1-v1-0-0-p1

http://ccfit.nsu.ru/ tarancov/

Конспект лекций по математической логике

(I семестр)

Под ред. Таранцова А., Хмелёвой У.

Лектор: Пальчунов Дмитрий Евгеньевич.

По материалам лекций 2003 г.

c 2003–2004. Копирование, распространение и модификация только с письменного согласия авторов; не требуется разрешения для создания печатной копии электронного варианта документа в некоммерческих целях.

Версия 1.0.0

Содержание

§1. Множества и операции над ними . . . . . . . . . . . . . . . . . . 3

§2. Логика высказываний . . . . . . . . . . . . . . . . . . . . . . . 4

§ 3. Логика предикатов . . . . . . . . . . . . . . . . . . . . . . . . . 7

§4. Машина Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . 10

§5. Частично-рекурсивные функции . . . . . . . . . . . . . . . . . . . 12

§6. Отношения и функции. Специальные бинарные отношения. . . . . . . . 15

§7. Максимальный, минимальный, наименьший, наибольший элемент. Точная верхняя и нижняя грань. . . . . . . . . . . . . . . . . . . . . . . . . 17

§8. Мощность множества . . . . . . . . . . . . . . . . . . . . . . . 20

§9. Счётные множества . . . . . . . . . . . . . . . . . . . . . . . . 21

§10.Континуум . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Авторы выражают благодарность (в алфавитном порядке) Бочарникову Андрею, Калгину Константину, Чуркину Александру, Юдиной Марии за помощь в создании этого документа.

Версия 1.0.0

17)(A −. B) −. C = A −. (B −. C)

18)A −. A =

! A −. A = (A \ A) (A \ A) = = . "

19)A −. = A

20)A ∩ B = A −. B = A B

21)= U

22)U = .

! (Упр.) "

§2. Логика высказываний

Опр. A, B, C — пропозициональные переменные (от англ. preposition).

A, B, C {И, Л}.

Опр. & — конъюнкция (и).

Опр. — дизъюнкция (или).

Опр. → — импликация (если . . . , то).

Опр. ¬ — отрицание (не).

Опр. 2.1. Формулы логики высказываний:

1)Пропозициональная переменная является формулой.

2)Если ϕ, ψ — формулы, то (ϕ & ψ), (ϕ ψ), (ϕ → ψ), ¬ϕ — формулы.

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

Опр. 2.2. Подформула — часть формулы, которая сама является формулой.

Опр. 2.3. Формула называется тождественно истинной, если она принимает значение истина при любых значениях пропозициональных переменных.

Опр. Формула называется тождественно ложной, если она принимает значение ложь при любых значениях пропозициональных переменных.

Опр. Формула называется выполнимой, если она не является тождественно ложной.

Опр. Формула называется опровержимой, если она не является тождественно истинной.

Зам. 2.4.

а) Если формула тождественно истинна, то она выполнима. б) Если формула тождественно ложна, то она опровержима.

в) Формула ϕ тождественно истинна тогда и только тогда, когда формула ¬ϕ тождественно ложна.

г) Формула ϕ выполнима тогда и только тогда, когда формула ¬ϕ опровержима.

! Элементарно. "

Версия 1.0.0

Предл. 2.5. Следующие формулы являются тождественно истинными:

1)A → (B → A)

2)(A → B) → ((A → (B → C)) → (A → C)))

3)((A & B) → A)

4)((A & B) → B)

5)((A → B) → ((A → C) → (A → (B & C))))

6)(A → (A B))

7)(B → (A B))

8)((A → C) → (B → C) → ((A B) → C))

9)((A → ¬B) → (B → ¬A))

10)(¬¬A → A)

11)((A → B) (B → A))

12)((A → B) (A → ¬B))

13)(A ¬A)

14)¬(A & ¬A)

15)(A → ¬¬A)

! Доказываются по таблице истинности "

Опр. 2.6. Двуместное отношение (тильда) называется отношением эквивалентности, если для любых a, b, c выполняются свойства:

1)a a (рефлексивность);

2)a b → b a (симметричность);

3)(a b) & (b c) → a c (транзитивность).

Опр. 2.8. Формулы ϕ, ψ называются эквивалентными (ϕ ψ), если они принимают одни и те же значения истинности при одних и тех же значениях переменных.

Зам. 2.9. — отношение эквивалентности.

! (Упр.) "

Предл. 2.10. Имеют место следующие эквивалентности:

1)A B B A (коммутативность)

2)A & B B & A (коммутативность)

3)A (B C) (A B) C (ассоциативность)

4)A & (B & C) (A & B) & C (ассоциативность)

5)A (B & C) (A B) & (A C) (дистрибутивность)

6)A & (B C) (A & B) (A & C) (дистрибутивность)

7)A A A (идемпотентность)

8)A & A A (идемпотентность)

9)¬¬A A

10)(A → B) (¬A B)

11)¬(A B) ¬A & ¬B (закон де Моргана)

12)¬(A & B) ¬A ¬B (закон де Моргана)

13)(A → ¬B) (B → ¬A)

14)(A → ¬B) ¬(A & B)

15)(A (A & B)) A

http://ccfit.nsu.ru/ tarancov/

16)(A & (A B)) A

17)(A (B & ¬B & C)) A

18)(A & (B ¬B C)) A

! (Упр.) "

Опр. 2.11. Термы теории множеств:

1)Пропозициональные переменные, пустое мн-во , универсум U — термы.

2)Если t1, t2 — термы, то (t1 t2), (t1 ∩ t2), t1 — термы.

3)Других термов нет.

Опр. 2.12. T — множество термов.

Запись t(A, B, C, . . .) T означает, что здесь перечислены все переменные, входящие в терм.

Определим отображение f: T → F (где F — множество формул логики высказываний):

1)f(t1 t2) = f(t1) f(t2)

2)f(t1 ∩ t2) = f(t1) & f(t2)

3)f(t) = ¬f(t)

4)f(A) = A

5)f( ) = (A & ¬A)

6)f(U) = (A ¬A)

Предл. 2.13. Пусть t1 T , t2 T . Тогда t1 = t2 f(t1) f(t2). ! Индукцией по построению термов. "

Опр. 2.14. Пусть ψ — формула, тогда $ψ%ϕξ — результат подстановки ξ

вместо всех вхождений ϕ в формулу ψ.

!Индукцией по построению ψ. "

Сл. 2.17. ϕ ψ (ϕ ψ & ψ не содержит символа «→»)

!ψ = $ϕ%A¬→A BB . "

Опр. 2.18. Формула называется формулой с тесными отрицаниями, если

(1) не содержит символа импликации («→»); (2) отрицание стоит только перед пропозициональными переменными.

Опр. Элементарная конъюнкция — конъюнкция пропозициональных переменных и их отрицаний.

Опр. Элементарная дизъюнкция — дизъюнкция пропозициональных переменных и их отрицаний.

Опр. Конъюнктивная нормальная форма (КНФ) — конъюнкция элемен-

тарных дизъюнкций.

Опр. Дизъюнктивная нормальная форма (ДНФ) — дизъюнкция элемен-

тарных конъюнкций.

Версия 1.0.0

где A — основное множество (универсум); P1, . . . , Pn — предикаты (отношения); f1, . . . , fm — функции (операции); C1, . . . , Ck — константы; σ —

сигнатура.

Опр. Сигнатура σ = P1, . . . , Pn; f1, . . . , fm, C1, . . . , Ck .

Опр. Универсум (основное множество) модели: |N| = A.

!" #

Опр. 3.2. Декартово произведение A × B = (a, b) " a A, b .B

Опр. P An — n-местное отношение.

Опр. f: An → A — n-местная (n-арная) операция (функция) на множестве A.

Каждой функции можно сопоставить предикат:

!" #

=(a1, . . . , an+1) " ai A, f(a1, . . . , an) = an+1 .

Каждая n-местная функция однозначно задаётся своим графиком, который является (n + 1)-местным предикатом.

Опр. Алгебра — алгебраическая система, сигнатура которой содержит только символы операций и константы.

Опр. Модель — система типа R; ≤ (т. е. состоящая из символов отношений).

Опр. 3.3. Терм сигнатуры σ:

1)Предметная переменная x A — терм. Константа c σ — терм.

2)Если t1, . . . , tn — термы, fn σ, то f(t1, . . . , tn) — терм.

3)Других термов нет.

Опр. 3.4. Формулы сигнатуры σ:

1)Если t1, t2 — термы, то t1 = t2 — формула.

2)Если t1, . . . , tn — термы, P n σ, то P(t1, . . . , tn) — формула.

3)Если ϕ, ψ — формулы, то (ϕ ψ), (ϕ & ψ), (ϕ → ψ), ¬ϕ, x ϕ, x ϕ — формулы.

4)Других формул нет.

Опр. 3.5. Подслово — некоторая последовательность подряд идущих символов в слове.

Опр. Подформула — подслово, которое является формулой.

Если x ψ или x ψ — подформулы ϕ, то говорят, что ψ является областью действия квантора x или x.

Опр. Вхождением переменной в формулу называется вхождение этой переменной в какой-то из термов данной формулы. (В формуле x (x = y) есть только одно вхождение переменной x: запись x вхождением не является.)

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

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

Версия 1.0.0

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

Опр. Множество всех свободных переменных формулы:

! " #

FV (ϕ) = x " x — свободная переменная ϕ .

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

Опр. K(σ) = Kσ — класс алгебраических систем сигнатуры σ.

Опр. T (σ) — множество термов сигнатуры σ.

Опр. F(σ) — множество формул сигнатуры σ.

Опр. S(σ) — множество предложений сигнатуры σ.

Зам. 3.6. Если σ1 σ2, то T (σ1) T (σ2), F(σ1) F(σ2), S(σ1)S(σ2), σ1 ≠ σ2 K(σ1) ∩ K(σ2) = .

Опр. 3.7. Значение терма на модели. Пусть зафиксирована σ, A K(σ).

Пусть t T (σ). Пусть γ: X → |A| — означивание переменных, где X —

такое, что FV (t) X. Тогда tA[γ] — значение терма t на модели A при означивании переменных γ. (Например, если t = x X, то tA[γ] = γ(x).)

Опр. 3.8. Истинность формулы на модели. Пусть зафиксирована σ, AK(σ). Пусть ϕ F(σ), FV (ϕ) X, γ: X → |A|. Тогда A |= ϕ[γ], если ϕ истинна на модели A при означивании переменных γ. (Например, если

ϕ = (t1 = t2), t1, t2 T (σ), то A |= ϕ[γ] tA1 [γ] = tA2 [γ].)

Опр. 3.9. Формула называется тождественно истинной, если она истинна на любой модели при любых значениях свободных переменных.

Опр. Формула называется тождественно ложной, если она ложна на любой модели при любых значениях свободных переменных.

Опр. Формула называется выполнимой, если она не является тождественно ложной.

Опр. Формула называется опровержимой, если она не является тождественно истинной.

Зам. 3.10. ϕ — тождественно истинна ¬ϕ — тождественно ложна.

Опр. 3.11. Формулы называются семантически эквивалентными (обознача-

ется ϕ ψ), если A K(σ(ϕ) σ(ψ)), γ: FV (ϕ) FV (ψ) → |A|: A |= ϕ[γ] A |= ψ[γ].

Зам. 3.12. — отношение эквивалентности.

!(Упр.) "

Предл. 3.13. Имеют место следующие эквивалентности:

а) ¬ x ϕ x ¬ϕ

б) ¬ x ϕ x ¬ϕ

в) x (ϕ & ψ) (( x ϕ) & ( x ψ))

!Пусть X = FV (ϕ & ψ), σ = σ(ϕ & ψ), A K(σ), γ: X → |A|.

A |= x (ϕ & ψ) [γ] b |A| A |= (ϕ & ψ) [γbx]b |A| A |= x ϕ[γ] & x ψ[γ]

A |= (( x ϕ) & ( x ψ)). "

http://ccfit.nsu.ru/ tarancov/

г) x (ϕ ψ) (( x ϕ) ( x ψ))

x / FV (ξ):

д) x (ϕ & ξ) (( x ϕ) & ξ) е) x (ϕ & ξ) (( x ϕ) & ξ) ж) x (ϕ ξ) (( x ϕ) ξ) з) x (ϕ ξ) (( x ϕ) ξ)

x, y / FV (ϕ(z)): и) x ϕ(x) y ϕ(y) к) x ϕ(x) y ϕ(y)

Зам. 3.14. Существуют формулы ϕ, ψ, такие что:

а) x (ϕ ψ) ̸(( x ϕ) ( x ψ)) б) x (ϕ & ψ) ̸(( x ϕ) & ( x ψ))

! ϕ = (x > 3), ψ = (x ≤ 3), N = N; ≤, > . "

"

Зам. 3.15. ϕ(x, y) " x y ϕ(x, y) ̸y x ϕ(x, y).

! ϕ(x, y) = (x ≤ y), A = N; ≤. "

Опр. 3.16. Формула ϕ находится в предварённой (пренексной) нормальной форме (ПНФ), если она имеет вид

ϕ = Q1x1 . . . Qnxn ψ(x1 . . . xn, y1 . . . yn),

где Qi { , } («кванторная приставка», пренекс), ψ — безкванторная.

Теорема 3.17. Для любой формулы ϕ существует эквивалентная ей формула ψ, которая находится в ПНФ.

!Алгоритм приведения формулы к ПНФ:

1)Избавиться от импликации.

2)Внести отрицание под кванторы.

3)Переименовать переменные, чтобы, во-первых, разные кванторы действовали по разным переменных, во-вторых, чтобы каждая переменная имела либо свободное, либо связанное вхождение.

4)Выносим кванторы наружу.

"

§ 4. Машина Тьюринга

Машина Тьюринга — это общая модель вычислительной машины.A = {0, 1} — внешний алфавит.

Версия 1.0.0